Diffie-Hellman: Droša tīkla komunikācijas ģēnija algoritms

Sāksim ar ātru domu eksperimentu.

Jums ir 3 datoru tīkls, kurus izmanto Alise, Bobs un Čārlijs. Visi 3 dalībnieki var nosūtīt ziņojumus, bet tikai tādā veidā, lai visi citi klienti, kuri ir izveidojuši savienojumu ar tīklu, varētu tos izlasīt. Šī ir vienīgā iespējamā saziņas forma starp dalībniekiem.

Ja Alise sūta ziņojumu pa vadiem, to saņem gan Bobs, gan Čārlijs. Citiem vārdiem sakot, Alise nevar nosūtīt tiešu ziņojumu Bobam, ja arī Čārlijs to nesaņem.

Bet Alise vēlas nosūtīt Bobam konfidenciālu ziņojumu un nevēlas, lai Čārlijs varētu to izlasīt.

Šķiet neiespējami ar šiem stingrajiem noteikumiem, vai ne? Skaisti, ka šo problēmu 1976. gadā atrisināja Vitfīlds Difijs un Martins Helmens.

Šī ir vienkāršota reālās pasaules versija, taču mēs saskaramies ar to pašu problēmu, sazinoties pa lielāko tīklu, kāds jebkad pastāvējis.

Parasti jums nav tieša savienojuma ar internetu, bet jūs esat daļa no lokāla mazāka tīkla, ko sauc par Ethernet.

Šis mazākais tīkls var būt vadu vai bezvadu (Wi-Fi), taču pamatkoncepcija paliek. Ja sūtāt signālu caur tīklu, šo signālu var nolasīt visi citi klienti, kas ir savienoti ar to pašu tīklu.

Kad esat izsūtījis ziņojumu uz bankas serveri ar savu kredītkartes informāciju, visi citi vietējā tīkla klienti saņems ziņojumu, ieskaitot maršrutētāju. Pēc tam tā pārsūtīs to uz faktisko bankas serveri. Visi pārējie klienti ignorēs ziņojumu.

Bet ko tad, ja tīklā ir ļaunprātīgs klients, kurš neignorēs jūsu konfidenciālos ziņojumus, bet gan tos nolasīs? Kā iespējams, ka jūsu bankas kontā joprojām ir nauda?

Šifrēšana

Šajā brīdī ir skaidrs, ka mums ir jāizmanto sava veida šifrēšana, lai pārliecinātos, ka ziņa ir lasāma Alisei un Bobam, bet Čārlijam - pilnīga ņurdēšana.

Informācijas šifrēšanu veic šifrēšanas algoritms, kas paņem atslēgu (piemēram, virkni) un atdod šifrētu vērtību, ko sauc par šifrēto tekstu. Šifrētais teksts ir tikai pilnīgi nejauša izskata virkne.

Ir svarīgi, lai šifrēto vērtību (šifrēto tekstu) varētu atšifrēt tikai ar sākotnējo atslēgu. To sauc par simetriskās atslēgas algoritmu, jo ziņojuma atšifrēšanai jums ir nepieciešama tā pati atslēga, ar kuru tā tika šifrēta. Ir arī asimetrisko atslēgu algoritmi, taču mums tie šobrīd nav vajadzīgi.

Lai to būtu vieglāk saprast, šeit ir JavaScript ieviests šifrēšanas algoritms:

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

Šajā funkcijā es katru simbolu kartēju citā rakstzīmē, pamatojoties uz dotās atslēgas garumu.

Katrai rakstzīmei ir vesels skaitlis, ko sauc par ASCII kodu. Ir vārdnīca, kurā ir visas rakstzīmes ar kodu, ko sauc par ASCII tabulu. Tātad mēs palielinājām šo skaitli pēc atslēgas garuma:

Šifrētā teksta atšifrēšana ir diezgan līdzīga. Bet pievienošanas vietā mēs no katra šifrētā teksta atņemam atslēgas garumu, lai mēs atgūtu sākotnējo ziņojumu.

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

Visbeidzot, šeit ir fiktīvā šifrēšana:

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!

Ziņojumam mēs izmantojām zināmu šifrēšanas pakāpi, taču šis algoritms bija noderīgs tikai demonstrēšanas nolūkos, lai iegūtu priekšstatu par to, kā uzvedas simetrisko atslēgu šifrēšanas algoritmi.

Papildus sliktai stūra lietu un parametru veidu apstrādei ir dažas problēmas ar šo ieviešanu.

Pirmkārt, katra 8 rakstzīmju garā atslēga var atšifrēt ziņojumu, kas tika šifrēts ar atslēgu "parole". Mēs vēlamies, lai šifrēšanas algoritms varētu atšifrēt ziņojumu tikai tad, ja mēs tam piešķiram to pašu atslēgu, ar kuru ziņojums tika šifrēts. Durvju slēdzene, kuru var atvērt ar katru otro atslēgu, nav tik noderīga.

Otrkārt, loģika ir pārāk vienkārša - ASCII tabulā katrs raksturs tiek pārvietots vienādā daudzumā, kas ir pārāk paredzams. Mums ir nepieciešams kaut kas sarežģītāks, lai būtu grūtāk uzzināt ziņojumu bez atslēgas.

Treškārt, nav minimāla atslēgas garuma. Mūsdienu algoritmi darbojas ar vismaz 128 bitu gariem taustiņiem (~ 16 rakstzīmes). Tas ievērojami palielina iespējamo atslēgu skaitu un līdz ar to arī šifrēšanas drošību.

Visbeidzot, ziņojuma šifrēšana vai atšifrēšana prasa pārāk maz laika. Šī ir problēma, jo visu iespējamo atslēgu izmēģināšana un šifrētā ziņojuma uzlaušana neprasa pārāk daudz laika.

Tas ir roku rokā ar atslēgas garumu: algoritms ir drošs, ja es kā uzbrucējs vēlos atrast atslēgu, tad man ir jāizmēģina liels skaits taustiņu kombināciju, un vienas kombinācijas izmēģināšana prasa salīdzinoši ilgu laiku.

Ir plašs simetrisku šifrēšanas algoritmu klāsts, kas attiecas uz visiem šiem apgalvojumiem, kurus bieži lieto kopā, lai katrā situācijā atrastu labu ātruma un drošuma attiecību.

Populārākie simetrisko atslēgu algoritmi ir Twofish, Serpent, AES (Rijndael), Blowfish, CAST5, RC4, TDES un IDEA.

Ja vēlaties uzzināt vairāk par kriptogrāfiju kopumā, apskatiet šo sarunu.

Atslēgu apmaiņa

Izskatās, ka mēs samazinājām sākotnējo problēmu telpu. Izmantojot šifrēšanu, mēs varam izveidot ziņojumu, kas ir nozīmīgs pusēm, kurām ir tiesības lasīt informāciju, bet kas nav lasāms citiem.

Kad Alise vēlas rakstīt konfidenciālu ziņojumu, viņa izvēlētos atslēgu un ar to šifrētu savu ziņojumu un pa vadiem nosūtītu šifrēto tekstu. Gan Bobs, gan Čārlijs saņems šifrēto ziņojumu, taču neviens no viņiem to nevarēja interpretēt bez Alises atslēgas.

Tagad vienīgais jautājums, uz kuru jāatbild, ir tas, kā Alise un Bobs var atrast kopīgu atslēgu, tikai sazinoties tīklā, un neļauj Čārlijam uzzināt to pašu atslēgu.

Ja Alise atsūtītu atslēgu tieši pa vadiem, Čārlijs to pārtvertu un spētu atšifrēt visus Alises ziņojumus. Tātad tas nav risinājums. To sauc par atslēgas apmaiņas problēmu datorzinātnēs.

Difijas – Helmanas atslēgu apmaiņa

Šis lieliskais algoritms nodrošina veidu, kā ģenerēt kopīgu atslēgu starp diviem cilvēkiem tādā veidā, ka atslēgu nevar redzēt, novērojot komunikāciju.

Kā pirmo soli mēs teiksim, ka ir milzīgs primārais numurs, kuru zina visi dalībnieki, tā ir publiska informācija. Mēs to saucam par "p" vai moduli .

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.

Paldies, ka lasījāt tik tālu! Es ceru, ka jūs ieguvāt kādu vērtību no šī ieraksta un sapratāt dažas šīs interesantās komunikācijas plūsmas daļas.

Ja bija grūti sekot šī skaidrojuma matemātikai, šeit ir lielisks video, kas palīdzēs jums izprast algoritmu bez matemātikas no augstāka līmeņa.

Ja jums patika šī ziņa, varat sekot man Twitter, lai atrastu vēl aizraujošākus resursus par programmēšanu un programmatūras izstrādi.