Diffie-Hellmanas: genialus saugaus tinklo ryšio algoritmas

Pradėkime nuo greito minties eksperimento.

Jūs turite 3 kompiuterių tinklą, kuriuos naudoja Alice, Bob ir Charlie. Visi 3 dalyviai gali siųsti pranešimus, bet tik taip, kad visi kiti prie tinklo prisijungę klientai galėtų jį perskaityti. Tai yra vienintelė įmanoma dalyvių bendravimo forma.

Jei Alisa siunčia pranešimą per laidus, jį gauna ir Bobas, ir Čarlis. Kitaip tariant, Alisa negali siųsti tiesioginės žinutės Bobui taip pat, kai Čarlis taip pat negauna jos.

Tačiau Alisa nori nusiųsti Bobui konfidencialią žinutę ir nenori, kad Čarlis galėtų ją perskaityti.

Atrodo neįmanoma laikantis šių griežtų taisyklių, tiesa? Gražus dalykas, kad šią problemą 1976 m. Išsprendė Whitfieldas Diffie ir Martinas Hellmanas.

Tai yra supaprastinta realaus pasaulio versija, tačiau susiduriame su ta pačia problema bendraudami per didžiausią kada nors egzistavusį tinklą.

Paprastai jūs nesate tiesiogiai prisijungę prie interneto, tačiau esate mažesnio vietinio tinklo, vadinamo „Ethernet“, dalis.

Šis mažesnis tinklas gali būti laidinis arba belaidis („Wi-Fi“), tačiau pagrindinė koncepcija išlieka. Jei siunčiate signalą per tinklą, šį signalą gali perskaityti visi kiti klientai, prisijungę prie to paties tinklo.

Kai išsiųsite pranešimą į banko serverį su savo kreditinės kortelės informacija, visi kiti vietinio tinklo klientai gaus pranešimą, įskaitant maršrutizatorių. Tada jis persiųs jį tikram banko serveriui. Visi kiti klientai nepaisys pranešimo.

Bet ką daryti, jei tinkle yra kenkėjiškas klientas, kuris neignoruos jūsų konfidencialių pranešimų, bet juos perskaitys? Kaip įmanoma, kad jūs vis dar turite pinigų savo banko sąskaitoje?

Šifravimas

Šiuo metu yra aišku, kad turime naudoti tam tikrą šifruotę, kad įsitikintume, jog pranešimas Alice ir Bobas yra įskaitomas, o Charlie - visiškai nesąžiningas.

Šifravimas atliekamas šifravimo algoritmu, kuris paima raktą (pavyzdžiui, eilutę) ir grąžina užšifruotą vertę, vadinamą šifriniu tekstu. Šifruotas tekstas yra tik visiškai atsitiktinai atrodanti eilutė.

Svarbu, kad užšifruotą vertę (šifrinį tekstą) galima iššifruoti tik naudojant pradinį raktą. Tai vadinama simetrinio rakto algoritmu, nes laiškui iššifruoti reikia to paties rakto, kuriuo jis buvo užšifruotas. Taip pat yra asimetrinių raktų algoritmų, tačiau mums jų dabar nereikia.

Kad būtų lengviau tai suprasti, pateikiamas manekeno šifravimo algoritmas, įdiegtas „JavaScript“:

function encrypt(message, key) { return message.split("").map(character => { const characterAsciiCode = character.charCodeAt(0) return String.fromCharCode(characterAsciiCode+key.length) }).join(""); }

Šioje funkcijoje aš susiejau kiekvieną simbolį į kitą simbolį, atsižvelgdamas į duoto rakto ilgį.

Kiekvienas simbolis turi sveiką skaičių, vadinamą ASCII kodu. Yra žodynas, kuriame yra visi simboliai su kodu, vadinamas ASCII lentele. Taigi mes padidinome šį skaičių pagal rakto ilgį:

Šifruoto teksto iššifravimas yra gana panašus. Tačiau užuot pridėję, mes atimame rakto ilgį iš kiekvieno šifruoto teksto simbolio, taigi mes grąžiname originalų pranešimą.

function decrypt(cipher, key) { return cipher.split("").map(character => { const characterAsciiCode = character.charCodeAt(0) return String.fromCharCode(characterAsciiCode-key.length) }).join(""); }

Galiausiai, čia yra manekeno šifravimas:

const message = "Hi Bob, here is a confidential message!"; const key = "password"; const cipher = encrypt(message, key); console.log("Encrypted message:", cipher); // Encrypted message: Pq(Jwj4(pmzm(q{(i(kwvnqlmv|qit(um{{iom) const decryptedMessage = decrypt(cipher, key); console.log("Decrypted message:", decryptedMessage); // Decrypted message: Hi Bob, here is a confidential message!

Pranešimui pritaikėme tam tikrą šifravimo laipsnį, tačiau šis algoritmas buvo naudingas tik demonstravimo tikslais, norint suprasti, kaip elgiasi simetriškojo rakto šifravimo algoritmai.

Be to, kad blogai tvarkomi kampiniai atvejai ir parametrų tipai, kyla keletas šio diegimo problemų.

Pirmiausia kas 8 simbolių ilgio raktas gali iššifruoti pranešimą, kuris buvo užšifruotas raktu „slaptažodis“. Norime, kad šifravimo algoritmas galėtų iššifruoti pranešimą tik tuo atveju, jei suteikiame jam tą patį raktą, kuriuo buvo šifruotas pranešimas. Durų spyna, kurią galima atidaryti kiekvienu kitu raktu, nėra tokia naudinga.

Antra, logika yra per paprasta - ASCII lentelėje kiekvienas simbolis perkeliamas vienodai, o tai yra per daug nuspėjama. Mums reikia kažko sudėtingesnio, kad būtų sunkiau sužinoti pranešimą be rakto.

Trečia, nėra minimalaus rakto ilgio. Šiuolaikiniai algoritmai veikia su mažiausiai 128 bitų ilgio raktais (~ 16 simbolių). Tai žymiai padidina galimų raktų skaičių ir tuo pačiu šifravimo saugumą.

Galiausiai, užšifruoti arba iššifruoti pranešimą užtrunka per mažai laiko. Tai yra problema, nes norint išbandyti visus įmanomus raktus ir nulaužti užšifruotą pranešimą, nereikia per daug laiko.

Tai yra ranka rankon su rakto ilgiu: algoritmas yra saugus, jei aš, kaip užpuolikas, noriu rasti raktą, tada turiu išbandyti daugybę raktų derinių ir vieno derinio išbandymas užtrunka palyginti ilgai.

Yra daugybė simetriško šifravimo algoritmų, kuriais buvo nagrinėjami visi šie teiginiai, dažnai naudojami kartu norint rasti gerą greičio ir saugumo santykį kiekvienoje situacijoje.

Populiaresni simetrinio rakto algoritmai yra „Twofish“, „Serpent“, AES („Rijndael“), „Blowfish“, CAST5, RC4, TDES ir IDEA.

Jei norite sužinoti daugiau apie kriptografiją, peržiūrėkite šį pokalbį.

Raktų mainai

Panašu, kad sumažinome pradinę probleminę erdvę. Naudodami šifravimą, galime sukurti pranešimą, kuris yra prasmingas šalims, turinčioms teisę skaityti informaciją, tačiau kitiems neįskaitomas.

Kai Alisa nori parašyti konfidencialią žinutę, ji pasiimdavo raktą, juo užšifruodavo savo pranešimą ir per laidus išsiųsdavo šifruotą tekstą. Tiek Bobas, tiek Charlie gaus šifruotą pranešimą, tačiau nė vienas iš jų negalėjo jo interpretuoti be Alice rakto.

Dabar vienintelis klausimas, į kurį reikia atsakyti, yra tai, kaip Alisa ir Bobas gali rasti bendrą raktą tiesiog bendraudami per tinklą ir neleisdami Charlie sužinoti to paties rakto.

Jei Alisa atsiųs raktą tiesiai laidais, Čarlis jį sulaikys ir galės iššifruoti visus Alisos pranešimus. Taigi tai nėra sprendimas. Tai vadinama raktų mainų problema informatikoje.

„Diffie – Hellman“ raktų mainai

Šis šaunus algoritmas suteikia galimybę sukurti bendrą raktą tarp dviejų žmonių tokiu būdu, kad raktas nebūtų matomas stebint ryšį.

Pirmiausia pasakysime, kad yra didžiulis pirminis skaičius, žinomas visiems dalyviams, tai yra vieša informacija. Mes tai vadiname „p“ arba moduliu .

There is also another public number called "g" or base,which is less than p.

Don't worry about how these numbers are generated. For the sake of simplicity let's just say Alice picks a very big prime number (p) and a number which is considerably less than p. She then sends them through the wires without any encryption, so all participants will know these numbers.

Example: To understand this through an example, we'll use small numbers. Let's say p=23 and g=5.

As a second step both Alice (a) and Bob (b) will pick a secret number, which they won't tell anybody, it's just locally living in their computers.

Example:Let's say Alice picked 4 (a=4), and Bob picked 3 (b=3).

As a next step, they will do some math on their secret numbers, they will calculate:

  1. the base (g) in the power of their secret number,
  2. and take the calculated number's modulo to p.
  3. Call the result A (for Alice) and B (for Bob).

Modulo is a simple mathematical statement, and we use it to find the remainder after dividing one number by another. Here is an example: 23 mod 4 = 3, because 23/4 is 5 and 3 remains.

Maybe it's easier to see all of this in code:

// base const g = 5; // modulus const p = 23; // Alice's randomly picked number const a = 4; // Alice's calculated value const A = Math.pow(g, a)%p; // Do the same for Bob const b = 3; const B = Math.pow(g, b)%p; console.log("Alice's calculated value (A):", A); // Alice's calculated value (A): 4 console.log("Bob's calculated value (B):", B); // Bob's calculated value (B): 10

Now both Alice and Bob will send their calculated values (A, B) through the network, so all participants will know them.

As a last step Alice and Bob will take each other's calculated values and do the following:

  1. Alice will take Bob's calculated value (B) in the power of his secret number (a),
  2. and calculate this number's modulo to p and will call the result s (secret).
  3. Bob will do the same but with Alice's calculated value (A), and his secret number (b).

At this point, they successfully generated a common secret (s), even if it's hard to see right now. We will explore this in more detail in a second.

In code:

// Alice calculate the common secret const secretOfAlice = Math.pow(B, a)%p; console.log("Alice's calculated secret:", secretOfAlice); // Alice's calculated secret: 18 // Bob will calculate const secretOfBob = Math.pow(A, b)%p; console.log("Bob's calculated secret:", secretOfBob); // Bob's calculated secret: 18

As you can see both Alice and Bob got the number 18, which they can use as a key to encrypt messages. It seems magic at this point, but it's just some math.

Let's see why they got the same number by splitting up the calculations into elementary pieces:

In the last step, we used a modulo arithmetic identity and its distributive properties to simplify nested modulo statements.

So Alice and Bob have the same key, but let's see what Charlie saw from all of this. We know that p and g are public numbers, available for everyone.

We also know that Alice and Bob sent their calculated values (A, B) through the network, so that can be also caught by Charlie.

Charlie knows almost all parameters of this equation, just a and b remain hidden. To stay with the example, if he knows that A is 4 and p is 23, g to the power of a can be 4, 27, 50, 73, ... and infinite other numbers which result in 4 in the modulo space.

He also knows that only the subset of these numbers are possible options because not all numbers are an exponent of 5 (g), but this is still an infinite number of options to try.

This doesn't seem too secure with small numbers. But at the beginning I said that p is a really large number, often 2000 or 4000 bits long. This makes it almost impossible to guess the value of a or b in the real world.

The common key Alice and Bob both possess only can be generated by knowing a or b, besides the information that traveled through the network.

If you're more visual, here is a great diagram shows this whole process by mixing buckets of paint instead of numbers.

Here p and g shared constants represented by the yellow "Common paint". Secret numbers of Alice and Bob (a, b) is "Secret colours", and "Common secret" is what we called s.

This is a great analogy because it's representing the irreversibility of the modulo operation. As mixed paints can't be unmixed to their original components, the result of a modulo operation can't be reversed.

Summary

Now the original problem can be solved by encrypting messages using a shared key, which was exchanged with the Diffie-Hellman algorithm.

With this Alice and Bob can communicate securely, and Charlie cannot read their messages even if he is part of the same network.

Ačiū, kad skaitėte iki šiol! Tikiuosi, kad gavote vertę iš šio įrašo ir supratote kai kurias šio įdomaus bendravimo srauto dalis.

Jei buvo sunku sekti šio paaiškinimo matematiką, pateikiame puikų vaizdo įrašą, kuris padės suprasti algoritmą be matematikos iš aukštesnio lygio.

Jei jums patiko šis įrašas, galbūt norėsite sekti mane „Twitter“ ir surasti įdomesnių šaltinių apie programavimą ir programinės įrangos kūrimą.