Diffie-Hellman：安全網絡通信背后的天才算法

Let's start with a quick thought experiment.

讓我們從快速思考實驗開始。

You have a network of 3 computers, used by Alice, Bob, and Charlie. All 3 participants can send messages, but just in a way that all other clients who connected to the network can read it. This is the only possible communication form between participants.

您有3臺計算機組成的網絡，供Alice，Bob和Charlie使用。所有3個參與者都可以發送消息，但是其方式是連接到網絡的所有其他客戶端都可以讀取消息。這是參與者之間唯一可能的溝通形式。

If Alice sends a message through the wires, both Bob and Charlie get it. In other words, Alice cannot send a direct message to Bob without Charlie receiving it as well.

如果愛麗絲通過電線發送消息，則鮑勃和查理都會收到消息。換句話說，愛麗絲必須在查理也沒有收到的情況下才能向鮑勃發送直接消息。

But Alice wants to send a confidential message to Bob and doesn't want Charlie to be able to read it.

但是愛麗絲(Alice)希望向鮑勃(Bob)發送機密消息，并且不希望查理(Charlie)能夠閱讀該消息。

Seems impossible with these strict rules, right? The beautiful thing that this problem is solved in 1976 by Whitfield Diffie and Martin Hellman.

這些嚴格的規則似乎不可能，對吧？ 1976年，Whitfield Diffie和Martin Hellman解決了這個問題。

This is a simplified version of the real world, but we face the same problem when communicating through the biggest network that's ever existed.

這是現實世界的簡化版本，但是在通過迄今為止最大的網絡進行通信時，我們也面臨同樣的問題。

Usually, you are not directly connected to the internet, but you are part of a local smaller network, called Ethernet.

通常，您不是直接連接到Internet，而是屬于本地小型網絡(稱為以太網)的一部分。

This smaller network can be wired or wireless (Wi-Fi), but the base concept remains. If you send a signal through the network this signal can be read by all other clients connected to the same network.

這個較小的網絡可以是有線或無線(Wi-Fi)，但基本概念仍然存在。如果通過網絡發送信號，則連接到同一網絡的所有其他客戶端都可以讀取該信號。

Once you emit a message to your bank's server with your credit card information, all other clients in the local network will get the message, including the router. It will then forward it to the actual server of the bank. All other clients will ignore the message.

將帶有信用卡信息的消息發送到銀行的服務器后，本地網絡中的所有其他客戶端(包括路由器)都將收到該消息。然后它將轉發到銀行的實際服務器。所有其他客戶端將忽略該消息。

But what if there is a malicious client in the network who won't ignore your confidential messages, but read them instead? How is it possible you still have money on your bank account?

但是，如果網絡中存在一個惡意客戶端，該客戶端不會忽略您的機密消息，而是會讀取它們，該怎么辦？您如何在銀行帳戶上仍然有錢？

加密 (Encryption)

It's kind of clear at this point that we need to use some kind of encryption to make sure that the message is readable for Alice and Bob, but complete gibberish for Charlie.

在這一點上很明顯，我們需要使用某種加密方式來確保該消息對Alice和Bob可讀，但對于Charlie則是完全亂碼。

Encrypting information is done by an encryption algorithm, which takes a key (for example a string) and gives back an encrypted value, called ciphertext. The ciphertext is just a completely random-looking string.

信息加密是通過一種加密算法完成的，該算法獲取一個密鑰(例如字符串)，并返回一個稱為密??文的加密值。密文只是一個看起來完全隨機的字符串。

It's important that the encrypted value (ciphertext) can be decrypted only with the original key. This is called a symmetric-key algorithm because you need the same key for decrypting the message as it was encrypted with. There are also asymmetric-key algorithms, but we don't need them right now.

重要的是，加密值(密文)只能用原始密鑰解密。這稱為對稱密鑰算法，因為您需要使用與解密消息時相同的密鑰來解密消息。也有非對稱密鑰算法，但是我們現在不需要它們。

To make it easier to understand this, here is a dummy encryption algorithm implemented in JavaScript:

為了更容易理解，這是用JavaScript實現的虛擬加密算法：

In this function, I mapped each character into another character based on the length of the given key.

在此功能中，我根據給定鍵的長度將每個字符映射到另一個字符。

Every character has an integer representation, called ASCII code. There is a dictionary that contains all characters with its code, called the ASCII table. So we incremented this integer by the length of the key:

每個字符都有一個整數表示形式，稱為ASCII碼。有一個包含所有字符及其代碼的字典，稱為ASCII表。因此，我們將該整數增加了密鑰的長度：

Decrypting the ciphertext is pretty similar. But instead of addition, we subtract the key length from every character in the ciphertext, so we get back the original message.

解密密文非常相似。但是，除了加法，我們從密文中的每個字符中減去密鑰長度，因此我們得到了原始消息。

Finally here is the dummy encryption in action:

最后是實際的虛擬加密：

We applied some degree of encryption to the message, but this algorithm was only useful for demonstration purposes, to get a sense of how symmetric-key encryption algorithms behave.

我們對消息應用了一定程度的加密，但是此算法僅用于演示目的，以了解對稱密鑰加密算法的行為。

There are a couple of problems with this implementation besides handling corner cases and parameter types poorly.

除了處理極少情況和參數類型外，此實現還有幾個問題。

First of all every 8 character-long key can decrypt the message which was encrypted with the key "password". We want an encryption algorithm to only be able to decrypt a message if we give it the same key that the message was encrypted with. A door lock that can be opened by every other key isn't that useful.

首先，每8個字符長的密鑰可以解密用密鑰“ password”加密的消息。我們希望加密算法僅在給消息提供與加密消息相同的密鑰時才能夠解密消息。可以用其他任何鑰匙打開的門鎖不是那么有用。

Secondly, the logic is too simple – every character is shifted the same amount in the ASCII table, which is too predictable. We need something more complex to make it harder to find out the message without the key.

其次，邏輯太簡單了–每個字符在ASCII表中的移動量都是相同的，這太可預測了。我們需要更復雜的東西，以使其更難找到沒有密鑰的消息。

Thirdly, there isn't a minimal key length. Modern algorithms work with at least 128 bit long keys (~16 characters). This significantly increases the number of possible keys, and with this the secureness of encryption.

第三，沒有最小的密鑰長度。現代算法使用至少128位長的密鑰(?16個字符)工作。這顯著增加了可能的密鑰數量，并因此增加了加密的安全性。

Lastly, it takes too little time to encrypt or decrypt the message. This is a problem because it doesn't take too much time to try out all possible keys and crack the encrypted message.

最后，花費很少的時間來加密或解密消息。這是一個問題，因為它不需要花費太多時間來嘗試所有可能的密鑰并破解加密的消息。

This is hand in hand with the key length: An algorithm is secure if I as an attacker want to find the key, then I need to try a large number of key combinations and it takes a relatively long time to try a single combination.

這與密鑰長度密切相關：如果作為攻擊者我想找到密鑰，則算法是安全的，那么我需要嘗試大量的密鑰組合，并且嘗試單個組合需要相對較長的時間。

There is a wide range of symmetric encryption algorithms that addressed all of these claims, often used together to find a good ratio of speed and secureness for every situation.

有各種各樣的對稱加密算法可以解決所有這些問題，通常將它們結合使用以找到每種情況下良好的速度和安全性比率。

The more popular symmetric-key algorithms are Twofish, Serpent, AES (Rijndael), Blowfish, CAST5, RC4, TDES, and IDEA.

最受歡迎的對稱密鑰算法是Twofish ， Serpent ， AES ( Rijndael )， Blowfish ， CAST5 ， RC4 ， TDES和IDEA 。

If you want to learn more about cryptography in general check out this talk.

如果您想進一步了解有關密碼學的更多信息，請查看此演講。

密鑰交換 (Key exchange)

It looks like we reduced the original problem space. With encryption, we can create a message which is meaningful for parties who are eligible to read the information, but which is unreadable for others.

看來我們減少了原來的問題空間。通過加密，我們可以創建一條消息，該消息對有資格閱讀該信息的各方有意義，而對于其他人則不可讀。

When Alice wants to write a confidential message, she would pick a key and encrypt her message with it and send the ciphertext through the wires. Both Bob and Charlie would receive the encrypted message, but none of them could interpret it without Alice's key.

當愛麗絲(Alice)要寫機密消息時，她會選擇一個密鑰并用它加密消息，然后通過電線發送密文。 Bob和Charlie都將收到加密的消息，但是沒有Alice的密鑰，他們都無法解釋它。

Now the only question to answer is how Alice and Bob can find a common key just by communicating through the network and prevent Charlie from finding out that same key.

現在唯一要回答的問題是，愛麗絲和鮑勃如何僅通過網絡進行通信就能找到一個公用密鑰，從而阻止查理找到相同的密鑰。

If Alice sends her key directly through the wires Charlie would intercept it and would be able to decrypt all Alice's messages. So this is not a solution. This is called the key exchange problem in computer science.

如果Alice直接通過電線發送她的密鑰，Charlie將會攔截它并能夠解密所有Alice的消息。因此，這不是解決方案。這稱為計算機科學中的密鑰交換問題。

Diffie-Hellman密鑰交換 (Diffie–Hellman key exchange)

This cool algorithm provides a way of generating a shared key between two people in such a way that the key can't be seen by observing the communication.

這種很酷的算法提供了一種在兩個人之間生成共享密鑰的方式，這種方式使得通過觀察通信無法看到密鑰。

As a first step, we'll say that there is a huge prime number, known to all participants, it's public information. We call it "p" or modulus.

首先，我們要說的是一個巨大的質數，所有參與者都知道，這是公共信息。我們稱其為“ p”或模量 。

There is also another public number called "g" or base, which is less than p.

還有另一個稱為“ g”或base的公用號碼，小于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.

不必擔心這些數字是如何生成的。為了簡單起見，我們只說愛麗絲選擇了一個很大的質數( p )，而這個數大大小于p 。然后，她通過電線將其發送，無需任何加密，因此所有參與者都將知道這些號碼。

Example: To understand this through an example, we'll use small numbers. Let's say p=23 and g=5.

示例：為了通過示例理解這一點，我們將使用少量數字。假設p = 23和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.

第二步，愛麗絲( a )和鮑勃( b )都會選擇一個秘密號碼，他們不會告訴任何人，這只是本地居住在他們的計算機中。

Example: Let's say Alice picked 4 (a=4), and Bob picked 3 (b=3).

例：假設愛麗絲(Alice)選擇4( a = 4 )，鮑勃(Bob)選擇3( b = 3 )。

As a next step, they will do some math on their secret numbers, they will calculate:

下一步，他們將對自己的密碼進行一些數學運算，他們將計算：

the base (g) in the power of their secret number,
以他們的秘密編號為準的基數( g )，
and take the calculated number's modulo to p.
并將計算出的數字取模p 。
Call the result A (for Alice) and B (for Bob).
將結果稱為A (對于Alice)和B (對于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.

模數是一個簡單的數學表達式，在將一個數除以另一個后，我們用它來查找余數。這是一個示例： 23 mod 4 = 3 ，因為23/4是5且剩余3個。

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.

現在，愛麗絲和鮑勃都將通過網絡發送他們的計算值( A ， B )，因此所有參與者都將知道它們。

As a last step Alice and Bob will take each other's calculated values and do the following:

作為最后一步，愛麗絲和鮑勃將獲取彼此的計算值并執行以下操作：

Alice will take Bob's calculated value (B) in the power of his secret number (a),
愛麗絲(Alice)將以鮑勃(Bob)的計算值( B )為其秘密數字( a )的冪，
and calculate this number's modulo to p and will call the result s (secret).
并計算該數字對p的模，然后將結果稱為s (秘密)。
Bob will do the same but with Alice's calculated value (A), and his secret number (b).
鮑勃將做同樣的事情，但要使用愛麗絲的計算值( A )和他的秘密號碼( 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.

在這一點上，他們成功地產生了共同的秘密(S)，即使它是很難看到現在。我們將在稍后詳細探討。

In code:

在代碼中：

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.

如您所見，Alice和Bob都獲得了18號，他們可以將其用作加密消息的密鑰。在這一點上看起來很神奇，但這只是一些數學。

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.

因此，愛麗絲(Alice)和鮑勃(Bob)具有相同的密鑰，但讓我們看看查理(Charlie)從這一切中看到了什么。我們知道p和g是公用號碼，每個人都可以使用。

We also know that Alice and Bob sent their calculated values (A, B) through the network, so that can be also caught by Charlie.

我們也知道Alice和Bob通過網絡發送了他們的計算值( A ， B )，因此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.

查理幾乎知道該方程的所有參數，只有a和b保持隱藏。留在例如，如果他知道A是4，p為23，g到的電源可以是4，27，50，73，...以及其導致4中的模數空間中無限其它數量。

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.

他還知道，只有這些數字的子集才是可能的選擇，因為并非所有數字的指數都是5( g )，但這仍然是可以嘗試的無數選擇。

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.

數量較少似乎不太安全。但是一開始我說p是一個很大的數字，通常是2000或4000位長。這使得幾乎不可能猜測現實世界中a或b的值。

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.

除了通過網絡傳播的信息之外，愛麗絲和鮑伯都擁有的公用密鑰只能通過知道a或b來生成。

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.

在這里， p和g共享由黃色“通用涂料”表示的常數。愛麗絲(Alice)和鮑勃(Bob)的秘密數字( a ， b )是“秘密顏色”，而“共同秘密”就是我們所說的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.

這是一個很好的類比，因為它表示模運算的不可逆性。由于混合的涂料不能與原始成分混合，因此取模運算的結果不可逆。