Diffie-Hellman: Algoritma Genius Di Sebalik Komunikasi Rangkaian Selamat

Mari mulakan dengan eksperimen pemikiran pantas.

Anda mempunyai rangkaian 3 komputer, yang digunakan oleh Alice, Bob, dan Charlie. Ketiga-tiga peserta boleh menghantar mesej, tetapi dengan cara semua pelanggan lain yang bersambung ke rangkaian dapat membacanya. Ini adalah satu-satunya bentuk komunikasi antara peserta.

Sekiranya Alice menghantar mesej melalui wayar, Bob dan Charlie akan menerimanya. Dengan kata lain, Alice tidak dapat mengirim pesanan langsung kepada Bob tanpa Charlie menerimanya juga.

Tetapi Alice ingin menghantar mesej sulit kepada Bob dan tidak mahu Charlie dapat membacanya.

Nampaknya mustahil dengan peraturan yang ketat ini, bukan? Perkara yang indah bahawa masalah ini diselesaikan pada tahun 1976 oleh Whitfield Diffie dan Martin Hellman.

Ini adalah versi dunia nyata yang disederhanakan, tetapi kami menghadapi masalah yang sama ketika berkomunikasi melalui rangkaian terbesar yang pernah ada.

Biasanya, anda tidak disambungkan secara langsung ke internet, tetapi anda adalah sebahagian daripada rangkaian tempatan yang lebih kecil, yang dipanggil Ethernet.

Rangkaian yang lebih kecil ini boleh berwayar atau tanpa wayar (Wi-Fi), tetapi konsep asasnya tetap ada. Sekiranya anda menghantar isyarat melalui rangkaian, isyarat ini dapat dibaca oleh semua pelanggan lain yang disambungkan ke rangkaian yang sama.

Setelah anda menghantar mesej ke pelayan bank anda dengan maklumat kad kredit anda, semua pelanggan lain di rangkaian tempatan akan menerima mesej tersebut, termasuk penghala. Ia kemudian akan meneruskannya ke pelayan bank yang sebenarnya. Semua pelanggan lain akan mengabaikan mesej tersebut.

Tetapi bagaimana jika ada pelanggan jahat dalam rangkaian yang tidak akan mengabaikan mesej sulit anda, tetapi membacanya? Bagaimana mungkin anda masih mempunyai wang di akaun bank anda?

Penyulitan

Cukup jelas pada ketika ini bahawa kita perlu menggunakan beberapa jenis penyulitan untuk memastikan bahawa mesej itu dapat dibaca untuk Alice dan Bob, tetapi omong kosong untuk Charlie.

Maklumat enkripsi dilakukan oleh algoritma enkripsi, yang mengambil kunci (misalnya tali) dan memberikan kembali nilai yang dienkripsi, yang disebut ciphertext. Ciphertext hanyalah rentetan yang kelihatan secara rawak.

Penting bahawa nilai yang dienkripsi (ciphertext) dapat didekripsi hanya dengan kunci asal. Ini dipanggil algoritma kekunci simetri kerana anda memerlukan kunci yang sama untuk menyahsulitkan mesej seperti yang dienkripsi. Terdapat juga algoritma kunci asimetri, tetapi kami tidak memerlukannya sekarang.

Untuk lebih mudah memahami ini, berikut adalah algoritma penyulitan dummy yang dilaksanakan dalam JavaScript:

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

Dalam fungsi ini, saya memetakan setiap watak menjadi watak lain berdasarkan panjang kunci yang diberikan.

Setiap watak mempunyai representasi integer, yang disebut kod ASCII. Terdapat kamus yang mengandungi semua watak dengan kodnya, yang disebut jadual ASCII. Oleh itu, kami menambah bilangan bulat ini dengan panjang kekunci:

Mendekripsi ciphertext hampir serupa. Tetapi bukannya penambahan, kami mengurangkan panjang kunci dari setiap watak dalam ciphertext, jadi kami mendapat kembali mesej asalnya.

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

Akhirnya inilah tindakan penyulitan dummy:

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!

Kami menerapkan beberapa tahap enkripsi pada mesej, tetapi algoritma ini hanya berguna untuk tujuan demonstrasi, untuk mengetahui bagaimana algoritma penyulitan kunci simetri berperilaku.

Terdapat beberapa masalah dengan pelaksanaan ini selain menangani kes sudut dan jenis parameter dengan buruk.

Pertama sekali, setiap 8 karakter panjang boleh menyahsulitkan mesej yang disulitkan dengan kunci "kata laluan". Kami mahu algoritma penyulitan hanya dapat mendekripsi mesej jika kami memberikannya kunci yang sama dengan mesej yang disulitkan. Kunci pintu yang boleh dibuka oleh setiap kunci lain tidak begitu berguna.

Kedua, logikanya terlalu sederhana - setiap watak dialihkan jumlah yang sama dalam jadual ASCII, yang terlalu dapat diramalkan. Kita memerlukan sesuatu yang lebih kompleks untuk menjadikannya lebih sukar untuk mengetahui mesej tanpa kunci.

Ketiga, tidak ada panjang kunci minimum. Algoritma moden berfungsi dengan sekurang-kurangnya kunci panjang 128 bit (~ 16 aksara). Ini secara signifikan meningkatkan bilangan kunci yang mungkin, dan dengan ini keselamatan penyulitan.

Terakhir, memerlukan sedikit masa untuk mengenkripsi atau menyahsulitkan mesej. Ini adalah masalah kerana tidak memerlukan banyak masa untuk mencuba semua kunci yang mungkin dan memecahkan mesej yang dienkripsi.

Ini bersesuaian dengan panjang kunci: Algoritma selamat jika saya sebagai penyerang ingin mencari kuncinya, maka saya perlu mencuba sebilangan besar kombinasi kunci dan memerlukan masa yang agak lama untuk mencuba satu kombinasi.

Terdapat pelbagai algoritma enkripsi simetri yang menangani semua tuntutan ini, yang sering digunakan bersama untuk mencari nisbah kelajuan dan keselamatan yang baik untuk setiap keadaan.

Algoritma kekunci simetri yang lebih popular ialah Twofish, Serpent, AES (Rijndael), Blowfish, CAST5, RC4, TDES, dan IDEA.

Sekiranya anda ingin mengetahui lebih lanjut mengenai kriptografi secara umum, periksa ceramah ini.

Pertukaran kunci

Nampaknya kami mengurangkan ruang masalah yang asal. Dengan penyulitan, kita dapat membuat mesej yang bermakna bagi pihak yang layak membaca maklumat, tetapi yang tidak dapat dibaca oleh orang lain.

Semasa Alice ingin menulis mesej sulit, dia akan memilih kunci dan mengenkripsi mesejnya dan menghantar ciphertext melalui wayar. Kedua-dua Bob dan Charlie akan menerima mesej yang dienkripsi, tetapi tidak ada yang dapat menafsirkannya tanpa kunci Alice.

Satu-satunya soalan yang harus dijawab ialah bagaimana Alice dan Bob dapat mencari kunci bersama hanya dengan berkomunikasi melalui rangkaian dan menghalang Charlie daripada mencari kunci yang sama.

Sekiranya Alice menghantar kuncinya terus melalui wayar, Charlie akan memintasnya dan dapat menyahsulit semua mesej Alice. Jadi ini bukan jalan penyelesaian. Ini dipanggil masalah pertukaran utama dalam sains komputer.

Pertukaran kunci Diffie – Hellman

Algoritma yang hebat ini menyediakan cara menghasilkan kunci bersama antara dua orang sedemikian rupa sehingga kunci tidak dapat dilihat dengan memerhatikan komunikasi.

Sebagai langkah pertama, kita akan mengatakan bahawa terdapat bilangan perdana yang besar, yang diketahui oleh semua peserta, ini adalah maklumat umum. Kami memanggilnya "p" atau modulus .

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.