Diffie-Hellman: Ο αλγόριθμος του μεγαλοφυούς πίσω από την ασφαλή επικοινωνία δικτύου

Ας ξεκινήσουμε με ένα γρήγορο πείραμα σκέψης.

Έχετε ένα δίκτυο 3 υπολογιστών, που χρησιμοποιείται από την Άλις, τον Μπομπ και τον Τσάρλι. Και οι 3 συμμετέχοντες μπορούν να στείλουν μηνύματα, αλλά μόνο με τρόπο που όλοι οι άλλοι πελάτες που έχουν συνδεθεί στο δίκτυο μπορούν να το διαβάσουν. Αυτή είναι η μόνη δυνατή φόρμα επικοινωνίας μεταξύ των συμμετεχόντων.

Εάν η Άλις στέλνει ένα μήνυμα μέσω των καλωδίων, τόσο ο Μπομπ όσο και ο Τσάρλι το λαμβάνουν. Με άλλα λόγια, η Άλις δεν μπορεί να στείλει ένα άμεσο μήνυμα στον Μπομπ χωρίς να το λάβει και ο Τσάρλι.

Αλλά η Αλίκη θέλει να στείλει ένα εμπιστευτικό μήνυμα στον Μπομπ και δεν θέλει ο Τσάρλι να μπορεί να το διαβάσει.

Φαίνεται αδύνατο με αυτούς τους αυστηρούς κανόνες, σωστά; Το όμορφο πράγμα που το πρόβλημα λύθηκε το 1976 από τους Whitfield Diffie και Martin Hellman.

Αυτή είναι μια απλοποιημένη έκδοση του πραγματικού κόσμου, αλλά αντιμετωπίζουμε το ίδιο πρόβλημα όταν επικοινωνούμε μέσω του μεγαλύτερου δικτύου που υπήρχε ποτέ.

Συνήθως, δεν είστε άμεσα συνδεδεμένοι στο Διαδίκτυο, αλλά είστε μέρος ενός τοπικού μικρότερου δικτύου, που ονομάζεται Ethernet.

Αυτό το μικρότερο δίκτυο μπορεί να είναι ενσύρματο ή ασύρματο (Wi-Fi), αλλά η βασική ιδέα παραμένει. Εάν στείλετε ένα σήμα μέσω του δικτύου, αυτό το σήμα μπορεί να αναγνωστεί από όλους τους άλλους πελάτες που είναι συνδεδεμένοι στο ίδιο δίκτυο.

Μόλις εκδώσετε ένα μήνυμα στον διακομιστή της τράπεζάς σας με τα στοιχεία της πιστωτικής σας κάρτας, όλοι οι άλλοι πελάτες στο τοπικό δίκτυο θα λάβουν το μήνυμα, συμπεριλαμβανομένου του δρομολογητή. Στη συνέχεια θα το προωθήσει στον πραγματικό διακομιστή της τράπεζας. Όλοι οι άλλοι πελάτες θα αγνοήσουν το μήνυμα.

Τι γίνεται όμως αν υπάρχει κακόβουλος πελάτης στο δίκτυο που δεν θα αγνοήσει τα εμπιστευτικά σας μηνύματα, αλλά θα τα διαβάσει; Πώς είναι δυνατόν να έχετε ακόμα χρήματα στον τραπεζικό σας λογαριασμό;

Κρυπτογράφηση

Είναι κάπως σαφές σε αυτό το σημείο ότι πρέπει να χρησιμοποιήσουμε κάποιο είδος κρυπτογράφησης για να βεβαιωθούμε ότι το μήνυμα είναι αναγνώσιμο για την Αλίκη και τον Μπομπ, αλλά πλήρης ασυναρτησία για τον Τσάρλι.

Οι πληροφορίες κρυπτογράφησης γίνονται από έναν αλγόριθμο κρυπτογράφησης, ο οποίος παίρνει ένα κλειδί (για παράδειγμα μια συμβολοσειρά) και επιστρέφει μια κρυπτογραφημένη τιμή, που ονομάζεται ciphertext. Το ciphertext είναι απλώς μια εντελώς τυχαία συμβολοσειρά.

Είναι σημαντικό η κρυπτογραφημένη τιμή (ciphertext) να μπορεί να αποκρυπτογραφηθεί μόνο με το αρχικό κλειδί. Αυτό ονομάζεται αλγόριθμος συμμετρικού κλειδιού επειδή χρειάζεστε το ίδιο κλειδί για την αποκρυπτογράφηση του μηνύματος με το οποίο κρυπτογραφήθηκε. Υπάρχουν επίσης αλγόριθμοι ασύμμετρου-κλειδιού, αλλά δεν τους χρειαζόμαστε τώρα.

Για να το καταλάβετε ευκολότερα, ακολουθεί ένας εικονικός αλγόριθμος κρυπτογράφησης που εφαρμόζεται σε JavaScript:

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

Σε αυτήν τη λειτουργία, χαρτογράφησα κάθε χαρακτήρα σε έναν άλλο χαρακτήρα με βάση το μήκος του δεδομένου κλειδιού.

Κάθε χαρακτήρας έχει μια ακέραια αναπαράσταση, που ονομάζεται κωδικός ASCII. Υπάρχει ένα λεξικό που περιέχει όλους τους χαρακτήρες με τον κωδικό του, που ονομάζεται πίνακας ASCII. Έτσι, αυξήσαμε αυτόν τον ακέραιο από το μήκος του κλειδιού:

Η αποκρυπτογράφηση του ciphertext είναι παρόμοια. Αλλά αντί για προσθήκη, αφαιρούμε το μήκος του κλειδιού από κάθε χαρακτήρα του κρυπτογραφημένου κειμένου, οπότε λαμβάνουμε πίσω το αρχικό μήνυμα.

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

Τέλος, εδώ είναι η εικονική κρυπτογράφηση σε δράση:

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!

Εφαρμόσαμε κάποιο βαθμό κρυπτογράφησης στο μήνυμα, αλλά αυτός ο αλγόριθμος ήταν χρήσιμος μόνο για σκοπούς επίδειξης, για να κατανοήσουμε πώς συμπεριφέρονται οι αλγόριθμοι κρυπτογράφησης συμμετρικού κλειδιού.

Υπάρχουν μερικά προβλήματα με αυτήν την εφαρμογή, εκτός από τον χειρισμό κακών περιπτώσεων και τύπων παραμέτρων.

Πρώτα απ 'όλα, κάθε πλήκτρο διάρκειας 8 χαρακτήρων μπορεί να αποκρυπτογραφήσει το μήνυμα που κρυπτογραφήθηκε με το κλειδί "κωδικός πρόσβασης". Θέλουμε ένας αλγόριθμος κρυπτογράφησης να μπορεί να αποκρυπτογραφεί ένα μήνυμα μόνο εάν του δώσουμε το ίδιο κλειδί με το οποίο κρυπτογραφήθηκε το μήνυμα. Μια κλειδαριά πόρτας που μπορεί να ανοίξει κάθε άλλο κλειδί δεν είναι τόσο χρήσιμη.

Δεύτερον, η λογική είναι πολύ απλή - κάθε χαρακτήρας μετατοπίζεται το ίδιο ποσό στον πίνακα ASCII, ο οποίος είναι πολύ προβλέψιμος. Χρειαζόμαστε κάτι πιο περίπλοκο για να δυσκολευτούμε να βρούμε το μήνυμα χωρίς το κλειδί.

Τρίτον, δεν υπάρχει ελάχιστο μήκος κλειδιού. Οι σύγχρονοι αλγόριθμοι λειτουργούν με τουλάχιστον πλήκτρα μήκους 128 bit (~ 16 χαρακτήρες). Αυτό αυξάνει σημαντικά τον αριθμό των πιθανών κλειδιών, και με αυτό την ασφάλεια της κρυπτογράφησης.

Τέλος, χρειάζεται πολύ λίγος χρόνος για την κρυπτογράφηση ή την αποκρυπτογράφηση του μηνύματος. Αυτό είναι ένα πρόβλημα επειδή δεν χρειάζεται πολύς χρόνος για να δοκιμάσετε όλα τα πιθανά κλειδιά και να σπάσετε το κρυπτογραφημένο μήνυμα.

Αυτό συμβαδίζει με το μήκος του κλειδιού: Ένας αλγόριθμος είναι ασφαλής εάν εγώ ως εισβολέας θέλω να βρω το κλειδί, τότε πρέπει να δοκιμάσω έναν μεγάλο αριθμό συνδυασμών κλειδιών και χρειάζεται σχετικά μεγάλο χρονικό διάστημα για να δοκιμάσω έναν μόνο συνδυασμό.

Υπάρχει ένα ευρύ φάσμα συμμετρικών αλγορίθμων κρυπτογράφησης που αντιμετώπισαν όλες αυτές τις αξιώσεις, που χρησιμοποιούνται συχνά μαζί για να βρουν μια καλή αναλογία ταχύτητας και ασφάλειας για κάθε περίπτωση.

Οι πιο δημοφιλείς αλγόριθμοι συμμετρικού κλειδιού είναι οι Twofish, Serpent, AES (Rijndael), Blowfish, CAST5, RC4, TDES και IDEA.

Αν θέλετε να μάθετε περισσότερα σχετικά με την κρυπτογραφία γενικά, δείτε αυτήν την ομιλία.

Ανταλλαγή κλειδιών

Φαίνεται ότι μειώσαμε τον αρχικό προβληματικό χώρο. Με την κρυπτογράφηση, μπορούμε να δημιουργήσουμε ένα μήνυμα που έχει νόημα για τα μέρη που είναι κατάλληλα να διαβάσουν τις πληροφορίες, αλλά το οποίο δεν είναι αναγνώσιμο για άλλους.

Όταν η Αλίκη θέλει να γράψει ένα εμπιστευτικό μήνυμα, θα έπαιρνε ένα κλειδί και θα κρυπτογράφησε το μήνυμά της μαζί του και θα έστελνε το κρυπτογράφημα μέσω των καλωδίων. Τόσο ο Μπομπ όσο και ο Τσάρλι θα λάβουν το κρυπτογραφημένο μήνυμα, αλλά κανένας από αυτούς δεν θα μπορούσε να το ερμηνεύσει χωρίς το κλειδί της Αλίκης.

Τώρα η μόνη ερώτηση που πρέπει να απαντηθεί είναι πώς η Άλις και ο Μπομπ μπορούν να βρουν ένα κοινό κλειδί μόνο επικοινωνώντας μέσω του δικτύου και εμποδίζοντας τον Τσάρλι να ανακαλύψει το ίδιο κλειδί.

Εάν η Άλις στέλνει το κλειδί της απευθείας μέσω των καλωδίων, η Τσάρλι θα το παρεμπόδιζε και θα μπορούσε να αποκρυπτογραφήσει όλα τα μηνύματα της Αλίκης Αυτό δεν είναι λοιπόν λύση. Αυτό ονομάζεται βασικό πρόβλημα ανταλλαγής στην επιστήμη των υπολογιστών.

Ανταλλαγή κλειδιών Diffie – Hellman

Αυτός ο δροσερός αλγόριθμος παρέχει έναν τρόπο δημιουργίας ενός κοινόχρηστου κλειδιού μεταξύ δύο ατόμων με τέτοιο τρόπο ώστε το κλειδί να μην είναι ορατό παρατηρώντας την επικοινωνία.

Ως πρώτο βήμα, θα πούμε ότι υπάρχει ένας τεράστιος πρώτος αριθμός, γνωστός σε όλους τους συμμετέχοντες, είναι δημόσιες πληροφορίες. Το ονομάζουμε "p" ή συντελεστή .

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.

Ευχαριστώ που διαβάσατε μέχρι τώρα! Ελπίζω να έχετε κάποια αξία από αυτήν την ανάρτηση και να καταλάβετε ορισμένα μέρη αυτής της ενδιαφέρουσας ροής επικοινωνίας.

Εάν ήταν δύσκολο να ακολουθήσετε τα μαθηματικά αυτής της εξήγησης, εδώ είναι ένα υπέροχο βίντεο που θα σας βοηθήσει να κατανοήσετε τον αλγόριθμο χωρίς μαθηματικά, από υψηλότερο επίπεδο.

Αν σας άρεσε αυτή η ανάρτηση, ίσως θελήσετε να με ακολουθήσετε στο Twitter για να βρείτε πιο συναρπαστικούς πόρους σχετικά με τον προγραμματισμό και την ανάπτυξη λογισμικού.