Diffie-Hellman: A biztonságos hálózati kommunikáció mögött álló zseniális algoritmus

Kezdjük egy gyors gondolatkísérlettel.

3 számítógépes hálózata van, amelyeket Alice, Bob és Charlie használ. Mindhárom résztvevő küldhet üzeneteket, de csak úgy, hogy a hálózathoz csatlakozó összes többi ügyfél el tudja olvasni. Ez az egyetlen lehetséges kommunikációs forma a résztvevők között.

Ha Alice üzenetet küld a vezetéken, Bob és Charlie is megkapja. Más szavakkal, Alice nem küldhet közvetlen üzenetet Bobnak anélkül, hogy Charlie is megkapná.

De Alice bizalmas üzenetet akar küldeni Bobnak, és nem akarja, hogy Charlie el tudja olvasni.

Ezekkel a szigorú szabályokkal lehetetlennek tűnik, igaz? A szép dolog, hogy ezt a problémát 1976-ban oldotta meg Whitfield Diffie és Martin Hellman.

Ez a való világ egyszerűsített változata, de ugyanazzal a problémával szembesülünk, amikor a valaha létező legnagyobb hálózaton keresztül kommunikálunk.

Általában nem közvetlenül csatlakozik az internethez, de egy helyi kisebb hálózat része, az úgynevezett Ethernet.

Ez a kisebb hálózat lehet vezetékes vagy vezeték nélküli (Wi-Fi), de az alapkoncepció megmarad. Ha jelet küld a hálózaton keresztül, akkor ezt a jelet minden más, ugyanahhoz a hálózathoz csatlakozó kliens olvassa.

Amint a bankkiszolgálójának üzenetet küld a hitelkártya adataival, a helyi hálózat összes többi ügyfele megkapja az üzenetet, beleértve az útválasztót is. Ezután továbbítja a bank tényleges szerverének. Az összes többi ügyfél figyelmen kívül hagyja az üzenetet.

De mi van akkor, ha van egy rosszindulatú kliens a hálózatban, aki nem hagyja figyelmen kívül a bizalmas üzeneteit, hanem elolvassa őket? Hogyan lehetséges, hogy még mindig van pénz a bankszámláján?

Titkosítás

Ezen a ponton valahogy világos, hogy valamilyen titkosítást kell használnunk annak biztosítására, hogy az üzenet olvasható legyen Alice és Bob számára, de Charlie számára teljes hamisítás.

Az adatok titkosítását egy titkosítási algoritmus végzi, amely kulcsot (például egy karakterláncot) vesz fel, és visszaad egy titkosított értéket, az úgynevezett titkosítást. A rejtjelezési szöveg csak egy teljesen véletlenszerű megjelenésű karakterlánc.

Fontos, hogy a titkosított értéket (rejtjelszöveget) csak az eredeti kulccsal lehet visszafejteni. Ezt szimmetrikus kulcsú algoritmusnak nevezzük, mert az üzenet visszafejtéséhez ugyanaz a kulcs kell, mint amellyel titkosították. Vannak aszimmetrikus kulcsú algoritmusok is, de ezekre jelenleg nincs szükségünk.

Ennek könnyebb megértése érdekében itt van egy dummy titkosítási algoritmus, amely a JavaScript-ben valósul meg:

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

Ebben a függvényben az egyes karaktereket egy másik karakterré térképeztem fel az adott kulcs hossza alapján.

Minden karakternek van egy egész ábrázolása, az úgynevezett ASCII kód. Van egy szótár, amely az összes karaktert tartalmazza a kódjával, az úgynevezett ASCII táblázat. Tehát növeltük ezt az egész számot a kulcs hosszával:

A titkosított szöveg visszafejtése meglehetősen hasonló. De az összeadás helyett kivonjuk a kulcs hosszát a rejtjeles szöveg minden karakteréből, így visszakapjuk az eredeti üzenetet.

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

Végül itt van a dummy titkosítás működés közben:

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!

Bizonyos fokú titkosítást alkalmaztunk az üzenetre, de ez az algoritmus csak demonstrációs célokra volt hasznos, hogy megértsük, hogyan viselkednek a szimmetrikus kulcsú titkosítási algoritmusok.

A sarok esetek és a paramétertípusok rossz kezelése mellett van néhány probléma ezzel a megvalósítással.

Először minden 8 karakter hosszú kulcs visszafejtheti a "jelszóval" titkosított üzenetet. Azt akarjuk, hogy egy titkosítási algoritmus csak akkor tudja visszafejteni az üzenetet, ha ugyanazt a kulcsot adjuk meg neki, amellyel az üzenetet titkosították. A minden más kulccsal nyitható ajtózár nem olyan hasznos.

Másodszor, a logika túl egyszerű - az ASCII táblában minden karakter ugyanannyit tolódik el, ami túl kiszámítható. Valami összetettebbre van szükségünk, hogy megnehezítsük az üzenet megismerését a kulcs nélkül.

Harmadszor, nincs minimális kulcshossz. A modern algoritmusok legalább 128 bites hosszú kulcsokkal (~ 16 karakter) működnek. Ez jelentősen megnöveli a lehetséges kulcsok számát, és ezzel együtt a titkosítás biztonságát.

Végül túl kevés időbe telik az üzenet titkosítása vagy visszafejtése. Ez azért probléma, mert nem kell túl sok idő az összes lehetséges kulcs kipróbálására és a titkosított üzenet feltörésére.

Ez kéz a kézben van a kulcs hosszával: Egy algoritmus biztonságos, ha támadóként meg akarom találni a kulcsot, akkor nagyszámú kulcskombinációt kell kipróbálnom, és egyetlen kombináció kipróbálása viszonylag sok időt vesz igénybe.

Szimmetrikus titkosítási algoritmusok széles skálája létezik, amelyek mindegyik igényt kielégítik, gyakran együtt használják, hogy minden helyzethez megfelelő sebesség és biztonság arányt találjanak.

A legnépszerűbb szimmetrikus kulcsú algoritmusok a Twofish, a kígyó, az AES (Rijndael), a Blowfish, a CAST5, az RC4, a TDES és az IDEA.

Ha többet szeretne megtudni a rejtjelezésről általában, nézze meg ezt a beszélgetést.

Kulcscsere

Úgy tűnik, hogy csökkentettük az eredeti problémateret. Titkosítással létrehozhatunk egy üzenetet, amely értelmes az információk elolvasására jogosult felek számára, de mások számára olvashatatlan.

Amikor Alice bizalmas üzenetet akar írni, kiválasztott egy kulcsot, ezzel titkosította az üzenetét, és a vezetékeken keresztül elküldte a titkosítást. Bob és Charlie is megkapja a titkosított üzenetet, de egyikük sem tudta Alice kulcs nélkül értelmezni.

Most csak arra a kérdésre kell válaszolni, hogy Alice és Bob miként találhatnak közös kulcsot pusztán a hálózaton keresztüli kommunikáció révén, és megakadályozhatják Charlie-t abban, hogy azonos kulcsot megtudjon.

Ha Alice közvetlenül a vezetéken keresztül küldi a kulcsát, Charlie lehallgatja, és képes lesz visszafejteni Alice összes üzenetét. Tehát ez nem megoldás. Ezt hívják a számítástechnika kulcscsere-problémájának.

Diffie – Hellman kulcscsere

Ez a hűvös algoritmus lehetőséget nyújt két ember közötti megosztott kulcs létrehozására oly módon, hogy a kulcs ne legyen látható a kommunikáció megfigyelésével.

Első lépésként azt mondjuk, hogy van egy hatalmas prímszám, amelyet minden résztvevő ismer, ez nyilvános információ. "P" -nek vagy modulusnak hívjuk .

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.

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.