Diffie-Hellman: Genijalni algoritam iza sigurne mrežne komunikacije

Krenimo s brzim misaonim eksperimentom.

Imate mrežu od 3 računala koja koriste Alice, Bob i Charlie. Sva 3 sudionika mogu slati poruke, ali samo na način da ih mogu čitati svi ostali klijenti koji su se povezali na mrežu. Ovo je jedini mogući oblik komunikacije između sudionika.

Ako Alice pošalje poruku putem žica, dobivaju je i Bob i Charlie. Drugim riječima, Alice ne može poslati izravnu poruku Bobu, a da je Charlie također ne primi.

Ali Alice želi poslati povjerljivu poruku Bobu i ne želi da je Charlie može pročitati.

Čini se nemogućim s ovim strogim pravilima, zar ne? Lijepa stvar koju ovaj problem 1976. godine rješavaju Whitfield Diffie i Martin Hellman.

Ovo je pojednostavljena verzija stvarnog svijeta, ali suočavamo se s istim problemom kada komuniciramo kroz najveću mrežu koja je ikad postojala.

Obično niste izravno povezani s internetom, ali dio ste lokalne manje mreže, nazvane Ethernet.

Ova manja mreža može biti žičana ili bežična (Wi-Fi), ali osnovni koncept ostaje. Ako signal šaljete mrežom, taj signal mogu pročitati svi drugi klijenti povezani na istu mrežu.

Jednom kada na poslužitelj banke pošaljete poruku s podacima o kreditnoj kartici, svi drugi klijenti u lokalnoj mreži dobit će poruku, uključujući usmjerivač. Zatim će ga proslijediti stvarnom poslužitelju banke. Svi ostali klijenti ignorirat će poruku.

Ali što ako u mreži postoji zlonamjerni klijent koji neće ignorirati vaše povjerljive poruke, već će ih umjesto toga pročitati? Kako je moguće da još uvijek imate novac na svom bankovnom računu?

Šifriranje

U ovom je trenutku nekako jasno da moramo koristiti neku vrstu šifriranja kako bismo bili sigurni da je poruka čitljiva za Alice i Bob, ali za Charlieja potpuna nerazumljivost.

Šifriranje podataka vrši se algoritmom šifriranja, koji uzima ključ (na primjer niz) i vraća šifriranu vrijednost, zvanu šifrirani tekst. Šifrotekst je samo posve slučajni niz.

Važno je da se šifrirana vrijednost (šifrirani tekst) može dešifrirati samo originalnim ključem. To se naziva algoritam simetričnog ključa jer vam za dešifriranje poruke treba isti ključ s kojim je šifrirana. Postoje i algoritmi s asimetričnim ključevima, ali oni nam trenutno nisu potrebni.

Da bismo to lakše razumjeli, evo lažnog algoritma za šifriranje implementiranog u JavaScript:

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

U ovoj sam funkciji preslikao svaki znak u drugi znak na temelju duljine zadanog ključa.

Svaki znak ima cjelobrojni prikaz, koji se naziva ASCII kod. Postoji rječnik koji sadrži sve znakove sa svojim kodom, a zove se ASCII tablica. Tako smo povećali ovaj cijeli broj za duljinu ključa:

Dešifriranje šifriranog teksta prilično je slično. Ali umjesto dodavanja, oduzimamo duljinu ključa od svakog znaka u šifrenom tekstu, pa vraćamo izvornu poruku.

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

Konačno, ovdje je lažna enkripcija na djelu:

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!

Primijenili smo određeni stupanj šifriranja na poruku, ali ovaj algoritam bio je koristan samo u demonstracijske svrhe kako bismo stekli osjećaj kako se ponašaju algoritmi šifriranja sa simetričnim ključem.

Postoji nekoliko problema s ovom implementacijom, osim lošeg rukovanja kutnim slučajevima i vrstama parametara.

Prije svega, svaki ključ dug 8 znakova može dešifrirati poruku koja je šifrirana ključem "lozinka". Želimo da algoritam šifriranja može dešifrirati poruku samo ako joj damo isti ključ s kojim je poruka šifrirana. Brava na vratima koju može otvoriti svaki drugi ključ nije toliko korisna.

Drugo, logika je prejednostavna - svaki se znak u ASCII tablici premješta u jednakom iznosu, što je previše predvidljivo. Treba nam nešto složenije kako bismo otežali otkrivanje poruke bez ključa.

Treće, ne postoji minimalna duljina ključa. Suvremeni algoritmi rade s najmanje 128 bitnih dugih tipki (~ 16 znakova). To značajno povećava broj mogućih ključeva, a time i sigurnost šifriranja.

Na kraju, potrebno je premalo vremena za šifriranje ili dešifriranje poruke. To je problem jer ne treba previše vremena za isprobavanje svih mogućih ključeva i probijanje šifrirane poruke.

To je ruku pod ruku s duljinom ključa: Algoritam je siguran ako ja kao napadač želim pronaći ključ, tada moram isprobati velik broj kombinacija tipki i potrebno je relativno dugo vremena da isprobam jednu kombinaciju.

Postoji širok raspon simetričnih algoritama za šifriranje koji su obradili sve ove tvrdnje, a često se koriste zajedno kako bi se pronašao dobar omjer brzine i sigurnosti u svakoj situaciji.

Popularniji algoritmi sa simetričnim ključem su Twofish, Serpent, AES (Rijndael), Blowfish, CAST5, RC4, TDES i IDEA.

Ako želite saznati više o kriptografiji općenito, pogledajte ovaj razgovor.

Razmjena ključeva

Čini se da smo smanjili izvorni problem. Šifriranjem možemo stvoriti poruku koja je značajna za stranke koje ispunjavaju uvjete za čitanje podataka, ali koja je drugima nečitka.

Kad Alice želi napisati povjerljivu poruku, odabrala bi ključ i njime šifrirala svoju poruku i poslala šifrirani tekst žicama. I Bob i Charlie primili bi šifriranu poruku, ali nitko od njih nije je mogao protumačiti bez Aliceina ključa.

Sad je jedino pitanje na koje treba odgovoriti kako Alice i Bob mogu pronaći zajednički ključ samo komunicirajući putem mreže i spriječiti Charlieja da sazna taj isti ključ.

Ako Alice pošalje svoj ključ izravno kroz žice, Charlie će ga presresti i moći dešifrirati sve Aliceine poruke. Dakle, ovo nije rješenje. To se u računalnoj znanosti naziva ključnim problemom razmjene.

Razmjena ključeva Diffie – Hellman

Ovaj cool algoritam pruža način generiranja zajedničkog ključa između dvoje ljudi na takav način da se ključ ne može vidjeti promatranjem komunikacije.

Kao prvi korak, reći ćemo da postoji ogroman prost broj, poznat svim sudionicima, to su javne informacije. Zovemo ga "p" ili modul .

Tu je i još jedan javni broj koji se naziva "g" ili baza ,što je manje od str .

Ne brinite kako se generiraju ti brojevi. Radi jednostavnosti recimo samo da Alice odabere vrlo velik prost broj ( p ) i broj koji je znatno manji od p . Zatim ih šalje putem žica bez ikakve enkripcije, tako da će svi sudionici znati ove brojeve.

Primjer: Da bismo to razumjeli na primjeru, poslužit ćemo se malim brojevima. Recimo p = 23 i g = 5 .

Kao drugi korak i Alice ( a ) i Bob ( b ) će odabrati tajni broj, koji nikome neće reći, već samo lokalno živi u njihovim računalima.

Primjer:Recimo da je Alice odabrala 4 ( a = 4 ), a Bob 3 ( b = 3 ).

Kao sljedeći korak, oni će malo izračunati svoje tajne brojeve, izračunati će:

  1. baza ( g ) u potenciji njihovog tajnog broja,
  2. i uzmi modulo izračunatog broja na str .
  3. Nazovite rezultat A (za Alice) i B (za Boba).

Modulo je jednostavan matematički iskaz i pomoću njega pronalazimo ostatak nakon dijeljenja jednog broja s drugim. Evo primjera: 23 mod 4 = 3 , jer je 23/4 5, a 3 ostaje.

Možda je sve ovo lakše vidjeti u kodu:

// 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

Sada će i Alice i Bob poslati svoje izračunate vrijednosti ( A , B ) putem mreže, tako da će ih svi sudionici znati.

Kao posljednji korak Alice i Bob međusobno će uzeti izračunate vrijednosti i učiniti sljedeće:

  1. Alice će uzeti Bobovu izračunatu vrijednost ( B ) u potenciji njegovog tajnog broja ( a ),
  2. i izračunajte modul ovog broja na p i pozvat će rezultat s (tajno).
  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.

Thanks for reading this far! I hope you got some value from this post and understood some parts of this interesting communication flow.

If it was hard to follow the math of this explanation, here is a great video to help you understand the algorithm without math, from a higher level.

If you liked this post, you may want to follow me on Twitter to find some more exciting resources about programming and software development.