密鑰交換演算法

① DH密鑰交換（Diffie–Hellman key exchange）演算法筆記

注意：只是個人理解，可能有不正確的地方
下文中 代表乘方運算，例如2 3=2 2 2=6，參考： http://zh.wikipedia.org/wiki/%E5%86%AA
%代表模運算，例如5%3=2，參考： http://zh.wikipedia.org/wiki/%E6%A8%A1%E9%99%A4
DH密鑰交換演算法的作用是使通信雙方可以在不安全的通道中建立一個相同的密鑰，用於加密通信。
基本原理示例：
1、通信方A和通信方B約定一個初始數g，g是公開的，如g=5
2、A生成一個隨機數a，a是保密的，如a=6
3、A計算g a發送給B，g a=5^6
4、B生成一個隨機數b，b是保密的，如b=15
5、B計算g b發送給A，g b=5^15
6、A接收到g b後，再使用保密的a，計算(g b) a=g (a b)=5^(6 15)
7、B接收到g a後，再使用保密的b，計算(g a) b=g (a b)=5^(6 15)
8、這樣通信方A和B得到一個相同的「密鑰」g (a*b)=5 (6 15)
整個通信過程中g、g a、g b是公開的，但由於g、a、b都是整數，通過g和g a得到a還是比較容易的，b也是如此，所以最終的「密鑰」g (a b)還是可以被計算出來的。所以實際的過程還需要在基本原理上加入新的計算—— 模運算 ：
1、通信方A和通信方B約定一個初始數g，如g=5，一個質數p，如p=23，g和p是公開的
2、A生成一個隨機數a，a是保密的，如a=6
3、A計算g a%p發送給B，g a%p=5^6%23=8
4、B生成一個隨機數b，b是保密的，如b=15
5、B計算g b%p發送給A，g b%p=5^15%23=19
6、A接收到g b%p後，再使用保密的a，計算(g b%p) a%p=19 6%23=2
7、B接收到g a%p後，再使用保密的b，計算(g a%p) b%p=8 15%23=2
8、這樣通信方A和B得到一個相同的密鑰：2
(g b%p) a%p=(g a%p) b%p的證明：
如果a=2：
(g b%p) a%p=(g b%p) 2%p=(g b-n*p) 2%p=(g (2*b)-2*g b n p+(n p) 2)%p=g (2 b)%p
可以看出(g b-n*p) 2展開後除g (2*b)外，其它都是p的倍數，所以整個算式的結果是g (2 b)%p
同理對(g^b-n p) a展開後除g (a b)外，其它都是p的倍數，所以整個算式的結果是g^(a b)%p
同樣可以得出(g a%p) b%p=g^(a b)%p
所以(g b%p) a%p=(g a%p) b%p
整個通信過程中g、p、g a%p、g b%p是公開的，這時通過g、p、g a%p得到a比較難，同樣通過g、p、g b%p得到b比較難，所以最終的密鑰是比較安全的。
以g=5、p=23、g^a%p=8計算a為例，a=log(5, (8+23 n))，這個只能將n的可能值逐個帶入公式試驗才能得到a的值。如果a、p是比較大的數那麼計算更加困難。
如果注意的是，為了防止應用優化演算法計算上述問題， 質數p不是隨便選擇 的，需要符合一定的條件。 隨機數a、b的生成演算法也必需注意 ，應使結果盡可能隨機，不能出現可預測的規律，否則會使破解變的容易。
通過上述計算過程也可以看出DH演算法不僅可以應用在2方通信的情況，如果 多方通信 ，也可以使用該演算法。
DH密鑰交換演算法 無法驗證對方身份 ，所以DH密鑰交換演算法 不能抵禦中間人攻擊 （MITM，Man-in-the-middle attack）。
參考：
wiki： http://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exchange

原文鏈接: https://my.oschina.net/u/1382972/blog/330456

② 通信安全：哈希、加密、證書、簽名、密鑰協商、ECDH、TLS、DTLS

哈希也叫散列，是把任意長度的輸入通過散列演算法變換成固定長度的輸出，該輸出就是散列值，也叫摘要（Digest）。

這種轉換是一種 壓縮映射。 也就是，散列值的空間通常遠小於輸入的空間，不同的輸入可能會散列成相同的輸出，所以不可能從散列值來確定唯一的輸入值，但如果輸出的位數足夠，不同輸入散列成相同輸出的概率非常非常小。

簡單的說， 散列就是一種將任意長度的消息壓縮到某一固定長度的消息摘要的過程 。

散列是不可逆的 ，也就是無法通過輸出還原輸入，此特性常被用於密碼保存。

SHA-512、MD5等都是著名的散列函數，MD5生成的散列碼是128位，甚至MD5就是哈希的同名詞，你可以通過網站：https://passwordsgenerator.net/sha512-hash-generator/ 在線計算哈希。

散列有什麼用？

加密就是把 明文變成密文的過程，解密就是反方向把密文變成明文 。

比如著名的 凱撒密碼 ，就是把每個字對應到另一個，這樣的話，只要有密碼本，就能對照完成加解密。比如最簡單的，對於英文26個字母，每個字母右移3個，abc變成def，這也是一種加密，當然這種加密很簡單，很容易被破譯。

而諸如AES（高級加密標准）、3DES（三重數據加密演算法）則被公認為很難破解，不過山東大學女教授王小雲很厲害，破解了MD5和SHA-1，迫使加密標准升級，最終當上了院士。

對稱加密

對稱加密就是加解密的密鑰是一樣的，優點是快，這也是傳統的加密方式，像AES、3DES都是對稱加密。

非對稱加密

非對稱加密用於加解密的密鑰不一樣，有2個密鑰，公鑰和私鑰，公鑰可以公開，私鑰妥善保管。RSA、ECC（橢圓曲線加密演算法）、DH（密鑰交換演算法）這些都是非對稱加密。

非對稱加密很慢，有多慢？相比對稱加密慢1000倍，因為慢，所以它常用於密鑰協商（Handshake），協商出會話密鑰後，再用對稱密鑰加密通信數據。

1976年，Whitfield Diffie和Martin Hellman首次提出了非對稱加密的概念，該演算法被稱為Diffie-Hellman密鑰交換。然後在1978年，麻省理工學院的Ron Rivest，Adi Shamir和Leonard Adleman發表了RSA 演算法。這些都可以被視為非對稱加密的基礎。

非對稱加密也稱為公鑰基礎結構，又稱PKI。 非對稱加密的提出是密碼學上的一次革命，影響深遠。

非對稱加密演算法用私鑰加密，用公鑰解密，或者用公鑰加密，用私鑰解密。

證書就是為了證明我是我，比如你要訪問中國銀行網站，但中行官網如何證明它是中行官網呢？答案就是數字證書。

CA是數字證書中心，伺服器需要找CA做認證，讓CA給自己頒布數字證書，數字證書內一般包含服務的一些信息、以及伺服器的公鑰，通過CA的私鑰加密後，產生的數字證書，因為CA的權威性，且它的公鑰天下皆知，所以，如果你能用CA的公鑰解開證書，那便可證明該證書一定是CA頒發的，要不然它不會有CA的私鑰，也便沒法產生可用CA公鑰解密的證書。

所以，由此可見，數字證書用到了非對稱加密。

日常生活中也有簽名，每個人的筆跡是不一樣的，你刷卡消費後在賬單簽上大名，服務員校驗過之後保存下來，你哪天賴賬，便可以有簽名為證，因為別人寫的字跟你的筆跡終有差別。

那數字簽名是什麼呢？比如a發一封email，接收方怎麼證明這封信是a寫的？

本質上，數字簽名也是利用了非對稱加密。

前面講了，非對稱加密有公鑰和私鑰，如果發生方用私鑰加密，然後接收方用發送方的公鑰可以解密，那便可以證明是從某發送方發送的，因為別人拿不到你的私鑰，也便無法用你的私鑰加密，你不能抵賴。

數字簽名通常先對內容算哈希，產生內容摘要，再用私鑰加密，得到簽名。

下面舉一個例子來說明這幾個問題：

張三有2把鑰匙，一把公鑰，公告天下，一把私鑰，妥善保管，只有自己知道，很明顯，非對稱加密。

李四給張三寫信，寫完之後，用張三的公鑰加密，通過郵局寄給張三，即使郵遞員拆開信封看，他也看不懂，因為內容是密文，只有張三的密鑰才能解密。

張三收到信後，用私鑰解密，可以正常閱讀。

現在張三要給李四回信，寫完後，用hash函數生成摘要digest。

然後張三，再用私鑰對摘要加密，生成數字簽名signature。

然後把簽名附在信的下面，一起發給李四。

過程是：信明文 -> hash -> digist -> 私鑰加密 -> signature。

李四收到回信後，用張三的公鑰對數字簽名解密，得到摘要，由此證明，信確實是張三發出的，為什麼？因為如果不是張三發的，那寫信的人就沒有張三私鑰，用別的私鑰加密得到的簽名，是無法用張三的公鑰解開的。

李四，再對信的內容做hash，得到摘要，與上一步得到的摘要對比，如果一致，則證明信的內容沒有被修改過，信的內容是完整的。

復雜的情況出現了。

王五，用自己的公鑰替換李四保存的張三的公鑰，也就是王五欺騙了李四，李四誤把王五的公鑰當張三的公鑰，這樣一來，王五就能冒充張三給李四寫信（王五用自己的私鑰加密）。

問題是什麼？問題是李四不能確信自己保存的公鑰真的是張三的公鑰。如果客戶端電腦上存的工商銀行官網的公鑰，實際上是騙子公司的公鑰，那就麻煩大了。

怎麼破？讓張三去認證中心CA（Certificate Authority），為公鑰做認證，怎麼做呢？CA中心用自己的私鑰，對張三的公鑰和其他相關信息一起加密，生成數字證書（Digital Certificate）。

張三拿到數字證書後，以後給李四回信，在簽名的同時，附帶上數字證書。

李四收到信之後，從CA的公鑰解開數字證書，取出張三的公鑰（一定是真的），然後就能放心的愉快的按之前的流程解開簽名了。

數字證書加入後，核心區別就是張三的公鑰不再保存在李四處，而是通過數字證書下發。

為什麼數字證書里的張三的公鑰一定是真的呢？因為CA是權威機構，假設全世界就一家（其實不止，但也不多），它的公鑰天下盡知，就是固定的串，所以能用CA公鑰解開的證書，一定是CA頒布的，因為CA用它的私鑰加密產生的證書。很明顯，非對稱加密能用於證明我是我。

密鑰交換演算法

著名的DH密鑰交換演算法，這個演算法很有意思，也很巧妙，簡而言之，就是通信雙方交換一點信息（不怕被偷看到），然後就在兩端，分布產生出一個相同的密鑰，神奇啊。

有一個很有意思的例子。

Alice和Bob要協商出一個公共的顏色，他們可以交換信息，但交換的信息，可以被偷看到，怎麼辦？既能協商出公共顏色，又不能讓別人知道呢。

密鑰交換演算法的原理跟這個差不多，網上有大量的資料講述這個問題，我覺得理解了上面的例子，再看ECDH便也不難了。

眾所周知http是互聯網協議，但是它不夠安全，所以後面有改進版的https，其實就是多了一個TLS，這個是傳輸層加密，本質上，就是通過handshake，協商出一個會話密鑰，後面的數據傳遞，都用這個密鑰做對稱加解密。

我們經常講安全通道，其實也就是協商出一個會話密鑰，他並不神秘。胡亂放幾張圖片吧。

為了減少這幾個RTT，又想了各種辦法，然後復用連接的話，就可以做到0RTT，1RTT了。

就說這些吧，最後拋幾個名詞，有興趣自行網路學習：DTLS，HMAC，AEAD，重放攻擊，放大攻擊，是不是很高端？

③ 什麼是dh演算法

DH演算法是一種密鑰交換協議。

DH演算法，全稱為Diffie-Hellman密鑰交換演算法，是一種在公開網路上安全地生成共享密鑰的協議。它是非對稱加密演算法的一種應用，由Whitfield Diffie和Martin Hellman在1976年提出。其核心思想是通過構造一個公開的共享密鑰來確保在不安全的通信環境中，雙方能夠安全地建立一個共享的密鑰，進而確保通信的安全性。這種演算法廣泛應用於網路通信中的密鑰交換場景。

DH演算法的工作原理如下：

DH演算法基於離散對數運算的單向性特點來實現密鑰交換。簡單來說，離散對數是一種特殊的數學運算，它使得從一個數推算出其對應的原始數非常困難。在DH演算法中，雙方各自擁有一個私有密鑰和公開密鑰。演算法通過特定的數學運算規則生成共享密鑰，這個共享密鑰由雙方的公鑰和私有密鑰共同決定。這種密鑰交換協議的特點是，即使通信雙方在網路中是匿名的，也能安全地生成一個共享的密鑰。由於這個密鑰是由雙方共同生成的，所以攻擊者很難預測或竊取這個密鑰。通過這種方式，DH演算法保證了通信的安全性。

DH演算法的應用場景：

DH演算法廣泛應用於各種需要安全通信的場景中，如網路上的數據加密傳輸、身份驗證協議等。特別是在虛擬世界的場景中，網路通信的安全性和隱私保護至關重要。DH演算法提供了一種有效的手段來確保通信雙方在不安全的網路環境中安全地建立共享密鑰，從而確保通信的安全性和隱私保護。此外，由於其強大的安全性表現，DH演算法也被廣泛應用於許多加密貨幣和區塊鏈技術中，以確保交易的安全性和匿名性。

④ 簡要介紹DH密鑰交換演算法

姓名：朱睿琦

學號：15180288015

參考：https://ke..com/item/Diffie-Hellman/9827194?fr=aladdin

http://blog.csdn.net/fw0124/article/details/8462373

【嵌牛導讀】：隨著互聯網路的高速發展，計算機運算能力的提升，對信息的保密也有了更近一步的要求——不僅信息要保密，密鑰也要保密。DH(Diffie-Hellman)演算法就提供了使密鑰安全通過不安全網路的方法。

【嵌牛鼻子】：DH演算法，密鑰，網路信息安全

【嵌牛提問】：DH演算法是用來保護什麼在網路中的通信安全？DH密鑰交換的基本原理是什麼？

【嵌牛正文】：(1)、演算法描述

離散對數的概念：

原根 ：如果 a 是素數 p 的一個原根，那麼數值：

a mod p ， a^ 2 mod p ，…， a^( p-1) mod p

是各不相同的整數，且以某種排列方式組成了從 1 到 p-1 的所有整數。

離散對數 ：如果對於一個整數 b 和素數 p 的一個原根 a ，可以找到一個唯一的指數 i ，使得：

b =（ a的i次方） mod p 其中 0 ≦ i ≦ p-1

那麼指數 i 稱為 b 的以 a 為基數的模p的離散對數。

Diffie-Hellman演算法的有效性依賴於計算離散對數的難度，其含義是：當已知大素數 p 和它的一個原根 a 後，對給定的 b ，要計算 i ，被認為是很困難的，而給定 i 計算 b 卻相對容易。

Diffie-Hellman演算法：

假如用戶A和用戶B希望交換一個密鑰。

取素數 p 和整數 a ， a 是 p 的一個原根，公開 a 和p。

A選擇隨機數XA< p ，並計算YA= a^ XA mod p。

B選擇隨機數XB< p ，並計算YB= a^ XB mod p。

每一方都將X保密而將Y公開讓另一方得到。

A計算密鑰的方式是：K=(YB) ^XA mod p

B計算密鑰的方式是：K=(YA) ^XB mod p

證明：

(YB)^ XA mod p = ( a^ XB mod p )^ XA mod p

= ( a^ XB)^ XA mod p = ( a^ XA) ^XB mod p (<-- 密鑰即為 a^(XA*XB) mod p )

=( a^ XA mod p )^ XB mod p = (YA) ^XB mod p

由於XA和XB是保密的，而第三方只有 p 、 a 、YB、YA可以利用，只有通過取離散對數來確定密鑰，但對於大的素數 p ，計算離散對數是十分困難的。

例子：

假如用戶Alice和用戶Bob希望交換一個密鑰。

取一個素數 p =97和97的一個原根 a =5。

Alice和Bob分別選擇秘密密鑰XA=36和XB=58，並計算各自的公開密鑰：

YA= a^ XA mod p =5^36 mod 97=50

YB= a^ XB mod p =5^58 mod 97=44

Alice和Bob交換了公開密鑰之後，計算共享密鑰如下：

Alice：K=(YB) ^XA mod p =44^36 mod 97=75

Bob：K=(YA) ^XB mod p =50^58 mod 97=75

(2)、安全性

當然，為了使這個例子變得安全，必須使用非常大的XA, XB 以及 p ， 否則可以實驗所有的可能取值。(總共有最多97個這樣的值, 就算XA和XB很大也無濟於事)。

如果 p 是一個至少 300 位的質數，並且XA和XB至少有100位長， 那麼即使使用全人類所有的計算資源和當今最好的演算法也不可能從a, p 和a^(XA*XB) mod p 中計算出 XA*XB。

這個問題就是著名的離散對數問題。注意g則不需要很大, 並且在一般的實踐中通常是2或者5。

在最初的描述中，迪菲－赫爾曼密鑰交換本身並沒有提供通訊雙方的身份驗證服務，因此它很容易受到中間人攻擊。

一個中間人在信道的中央進行兩次迪菲－赫爾曼密鑰交換，一次和Alice另一次和Bob，就能夠成功的向Alice假裝自己是Bob，反之亦然。

而攻擊者可以解密（讀取和存儲）任何一個人的信息並重新加密信息，然後傳遞給另一個人。因此通常都需要一個能夠驗證通訊雙方身份的機制來防止這類攻擊。

有很多種安全身份驗證解決方案使用到了迪菲－赫爾曼密鑰交換。例如當Alice和Bob共有一個公鑰基礎設施時，他們可以將他們的返回密鑰進行簽名。