Diffie-Hellman: Den geniale algoritme bag sikker netværkskommunikation

Lad os starte med et hurtigt tankeeksperiment.

Du har et netværk på 3 computere, der bruges af Alice, Bob og Charlie. Alle 3 deltagere kan sende beskeder, men bare på en måde, så alle andre klienter, der har forbindelse til netværket, kan læse det. Dette er den eneste mulige kommunikationsform mellem deltagerne.

Hvis Alice sender en besked gennem ledningerne, får både Bob og Charlie den. Med andre ord kan Alice ikke sende en direkte besked til Bob uden at Charlie også modtager den.

Men Alice vil sende en fortrolig besked til Bob og vil ikke have, at Charlie kan læse den.

Virker umuligt med disse strenge regler, ikke? Det smukke, at dette problem blev løst i 1976 af Whitfield Diffie og Martin Hellman.

Dette er en forenklet version af den virkelige verden, men vi står over for det samme problem, når vi kommunikerer gennem det største netværk, der nogensinde har eksisteret.

Normalt har du ikke direkte forbindelse til internettet, men du er en del af et lokalt mindre netværk, kaldet Ethernet.

Dette mindre netværk kan være kablet eller trådløst (Wi-Fi), men grundkonceptet forbliver. Hvis du sender et signal gennem netværket, kan dette signal læses af alle andre klienter, der er tilsluttet det samme netværk.

Når du først sender en besked til din banks server med dine kreditkortoplysninger, får alle andre klienter i det lokale netværk beskeden, inklusive routeren. Det videresender det derefter til bankens faktiske server. Alle andre klienter ignorerer beskeden.

Men hvad hvis der er en ondsindet klient i netværket, der ikke ignorerer dine fortrolige meddelelser, men læser dem i stedet? Hvordan er det muligt, at du stadig har penge på din bankkonto?

Kryptering

Det er lidt klart på dette tidspunkt, at vi skal bruge en slags kryptering for at sikre, at meddelelsen er læsbar for Alice og Bob, men fuldstændig gibberish for Charlie.

Kryptering af oplysninger udføres af en krypteringsalgoritme, der tager en nøgle (for eksempel en streng) og giver tilbage en krypteret værdi, kaldet ciphertext. Ciphertext er bare en helt tilfældig streng.

Det er vigtigt, at den krypterede værdi (krypteringstekst) kun kan dekrypteres med den originale nøgle. Dette kaldes en symmetrisk nøglealgoritme, fordi du har brug for den samme nøgle til at dekryptere meddelelsen, som den blev krypteret med. Der er også asymmetriske nøglealgoritmer, men vi har ikke brug for dem lige nu.

For at gøre det lettere at forstå dette er her en dummy-krypteringsalgoritme implementeret i JavaScript:

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

I denne funktion kortlagde jeg hvert tegn til et andet tegn baseret på længden af ​​den givne nøgle.

Hvert tegn har et heltal, kaldet ASCII-kode. Der er en ordbog, der indeholder alle tegn med dens kode, kaldet ASCII-tabellen. Så vi steg dette heltal med nøglens længde:

Dekryptering af ciphertext er ret ens. Men i stedet for tilføjelse trækker vi nøglelængden fra hvert tegn i krypteringsteksten, så vi får den originale besked tilbage.

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

Endelig her er dummy-kryptering i aktion:

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!

Vi anvendte en vis grad af kryptering til meddelelsen, men denne algoritme var kun nyttig til demonstrationsformål for at få en fornemmelse af, hvordan symmetriske nøglekrypteringsalgoritmer opfører sig.

Der er et par problemer med denne implementering udover at håndtere hjørnesager og parametertyper dårligt.

Først og fremmest kan hver 8 tegn lange nøgle dekryptere beskeden, der blev krypteret med nøglen "adgangskode". Vi ønsker, at en krypteringsalgoritme kun kan dekryptere en meddelelse, hvis vi giver den den samme nøgle, som meddelelsen blev krypteret med. En dørlås, der kan åbnes med hver anden nøgle, er ikke så nyttig.

For det andet er logikken for enkel - hvert tegn skiftes det samme beløb i ASCII-tabellen, hvilket er for forudsigeligt. Vi har brug for noget mere komplekst for at gøre det sværere at finde ud af meddelelsen uden nøglen.

For det tredje er der ikke en minimal nøgellængde. Moderne algoritmer fungerer med mindst 128 bit lange nøgler (~ 16 tegn). Dette øger antallet af mulige nøgler betydeligt, og dermed krypteringens sikkerhed.

Endelig tager det for lidt tid at kryptere eller dekryptere meddelelsen. Dette er et problem, fordi det ikke tager for meget tid at afprøve alle mulige nøgler og knække den krypterede besked.

Dette er hånd i hånd med nøglelængden: En algoritme er sikker, hvis jeg som angriber vil finde nøglen, så er jeg nødt til at prøve et stort antal tastekombinationer, og det tager relativt lang tid at prøve en enkelt kombination.

Der er en bred vifte af symmetriske krypteringsalgoritmer, der adresserede alle disse påstande, ofte brugt sammen for at finde et godt forhold mellem hastighed og sikkerhed i enhver situation.

De mere populære algoritmer med symmetrisk nøgle er Twofish, Serpent, AES (Rijndael), Blowfish, CAST5, RC4, TDES og IDEA.

Hvis du vil lære mere om kryptografi generelt, så tjek denne samtale.

Nøgleudveksling

Det ser ud til, at vi har reduceret det oprindelige problemrum. Med kryptering kan vi oprette en besked, der er meningsfuld for parter, der er berettigede til at læse oplysningerne, men som er ulæselige for andre.

Når Alice ønsker at skrive en fortrolig besked, vælger hun en nøgle og krypterer sin besked med den og sender krypteringsteksten gennem ledningerne. Både Bob og Charlie ville modtage den krypterede besked, men ingen af ​​dem kunne fortolke den uden Alice's nøgle.

Nu er det eneste spørgsmål, der skal besvares, hvordan Alice og Bob kan finde en fælles nøgle bare ved at kommunikere via netværket og forhindre Charlie i at finde ud af den samme nøgle.

Hvis Alice sender sin nøgle direkte gennem ledningerne, ville Charlie opfange den og være i stand til at dekryptere alle Alice's meddelelser. Så dette er ikke en løsning. Dette kaldes nøgleudvekslingsproblemet inden for datalogi.

Diffie – Hellman nøgleudveksling

Denne seje algoritme giver en måde at generere en delt nøgle mellem to personer på en sådan måde, at nøglen ikke kan ses ved at observere kommunikationen.

Som et første skridt vil vi sige, at der er et enormt primtal, som alle deltagere kender, det er offentlig information. Vi kalder det "p" eller modul .

Der er også et andet offentligt nummer kaldet "g" eller base ,hvilket er mindre end s .

Du skal ikke bekymre dig om, hvordan disse tal genereres. Af enkelheds skyld lad os bare sige, at Alice vælger et meget stort primtal ( p ) og et tal, der er betydeligt mindre end p . Derefter sender hun dem gennem ledningerne uden kryptering, så alle deltagere kender disse numre.

Eksempel: For at forstå dette gennem et eksempel bruger vi små tal. Lad os sige, at p = 23 og g = 5 .

Som et andet trin vælger både Alice ( a ) og Bob ( b ) et hemmeligt nummer, som de ikke fortæller nogen, det bor bare lokalt i deres computere.

Eksempel:Lad os sige, at Alice valgte 4 ( a = 4 ), og Bob valgte 3 ( b = 3 ).

Som et næste trin vil de lave matematik på deres hemmelige tal, de vil beregne:

  1. basen ( g ) i kraft af deres hemmelige nummer,
  2. og tag det beregnede tals modulo til p .
  3. Kald resultatet A (for Alice) og 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.

Tak for læsningen indtil videre! Jeg håber, at du fik noget ud af dette indlæg og forstod nogle dele af dette interessante kommunikationsflow.

Hvis det var svært at følge matematikken i denne forklaring, er her en fantastisk video, der hjælper dig med at forstå algoritmen uden matematik fra et højere niveau.

Hvis du kunne lide dette indlæg, kan du følge mig på Twitter for at finde nogle mere spændende ressourcer om programmering og softwareudvikling.