Diffie-Hellman密鑰協商算法_租車

access_timePosted on by admin

※Google地圖已可更新顯示潭子電動車充電站設置地點!!

日本、大陸，發現這些先進的國家已經早就讓電動車優先上路，而且先進國家空氣品質相當好，電動車節能減碳可以減少空污

概述

DH算法是非對稱加密算法的鼻祖，為非對稱加密算法奠定了基礎，主要用途是進行密鑰交換，確保共享的密鑰能夠安全穿越不安全的網絡。該算法其背後有對應數學理論做支撐，簡單來講就是構造一個複雜的計算難題，使得對該問題的求解在現實的時間內無法快速有效的求解（computationally infeasible ）。

這個機制的巧妙在於需要安全通信的雙方可以用這個方法確定對稱密鑰。然後可以用這個對稱密鑰進行加密和解密。但是注意，這個密鑰交換協議/算法只能用於密鑰的交換，而不能進行消息的加密和解密。之所以如此，主要還是由於對稱加密和非對稱加密算法的特性決定的。

1. 對稱加密算法和非對稱加密算法

對稱加密算法

雙方使用的同一個密鑰，既可以加密又可以解密，這種加密方法稱為對稱加密，也稱為單密鑰加密。

優點：速度快，對稱性加密通常在消息發送方需要加密大量數據時使用，算法公開、計算量小、加密速度快、加密效率高。

缺點：在數據傳送前，發送方和接收方必須商定好秘鑰，然後 使雙方都能保存好秘鑰。其次如果一方的秘鑰被泄露，那麼加密信息也就不安全了。另外，每對用戶每次使用對稱加密算法時，都需要使用其他人不知道的唯一秘鑰，這會使得收、發雙方所擁有的鑰匙數量巨大，密鑰管理成為雙方的負擔。

在對稱加密算法中常用的算法有：DES、AES等。

AES：密鑰的長度可以為128、192和256位，也就是16個字節、24個字節和32個字節。

DES：密鑰的長度64位，8個字節。

非對稱加密算法

一對密鑰由公鑰和私鑰組成（可以使用很多對密鑰）。私鑰解密公鑰加密數據，公鑰解密私鑰加密數據（私鑰公鑰可以互相加密解密）。私鑰只能由一方保管，不能外泄。公鑰可以交給任何請求方。

優點：安全。

缺點：速度較慢。

在非對稱加密算法中常用的算法有： DH，RSA等。

兩者區別

  • 算法複雜度:對稱密鑰<非對稱密鑰
  • 加解密速度:對稱密鑰>非對稱密鑰
  • 安全性:對稱密鑰<非對稱密鑰

對稱加密算法相比非對稱加密算法來說，加解密的效率要高得多。但是缺陷在於對於秘鑰的管理上，以及在非安全信道中通訊時，密鑰交換的安全性不能保障。所以在實際的網絡環境中，會將兩者混合使用。因此 ，在https中(TLS\SSL)握手階段使用非對稱加密進行對稱密鑰的協商，而後在後續正常的數據傳輸時，都會使用對稱加密算法進行加密傳輸。

數學基礎

本原根：如果使得 \(a^{m}\equiv 1\ \left( mod\ n \right)\) 成立的最小正冪 \(m\) 滿足 $m=\varphi \left( n \right) $ ,則稱 \(a\) 是 \(n\) 的本原根。 其中 \(\varphi \left( n \right)\) 為歐拉函數。

性質：若 \(a\) 為模 \(n\) 的本原根，則 \(a\)，\(a\) 的平方，\(a\) 的3次方，……，\(a\) 的 \(\varphi \left( n \right)\) 次m方 模 \(n\) 的餘數互不相同，而且構成一個模n的簡化剩餘系。

栗子(原根)：設 \(n=7\)，則 \(\varphi \left( 7 \right) =7\times \left( 1-\frac{1}{7} \right) =6\)

※廣告預算用在刀口上，台北網頁設計公司幫您達到更多曝光效益

有別於一般網頁架設公司，除了模組化的架站軟體，我們的營業主軸還包含：資料庫程式開發、網站建置、網頁設計、電子商務專案開發、系統整合、APP設計建置、專業網路行銷。

  • 當 \(n=2\) 時，我們需要找到一個 \(m\), 使得 \(2^m\%7=1\)，且剛好 \(m==\varphi \left( 7 \right)\)，首先我們能找到當 \(m=3\) 時，\(2^3\%7=1\)，但是卻不等於 \(\varphi \left( 7 \right)\)，因此不滿足。
  • 當 \(n=3\)時，類比上面一點，可以發現 \(m=6\) 時，兩點都能滿足。因此 \(3\) 為 \(7\) 的一個原根。

question：找了很多資料對原本根和原根的區別，還是很含糊！有大神的話，希望能教教我，感謝啦！

算法流程及原理

假設Alice需要與Bob協商一個秘鑰（秘鑰本質上就是一個比特序列，從計算的角度看就是一個大數）。

  1. 首先Alice與Bob共享一個素數 \(p\) 以及該素數 \(p\) 的本原根 \(g\) (generator)，且 \(2\le g\le p-1\)。這兩個數可以不經過加密的由一方發送到另一方，至於誰發送給誰並不重要，只要保證雙方都能知道 \(p\) 和 \(g\) 即可。
  1. 而後Alice產生一個私有的隨機數 \(A\)，滿足 \(1\le A\le p-1\)，然後計算 \(g^Amod\ p=Y_a\)，將結果 \(Y_a\) 通過公網發送給Bob; 與此同時，Bob也產生一個私有的隨機數 \(B\)，滿足 \(1\le B\le p-1\)，計算 \(g^Bmod\ p=Y_b\)，再將結果 \(Y_b\) 通過公網發送給Alice。

  1. 此時Alice知道的信息有\(p\),\(g\),\(A\),\(Y_a\),\(Y_b\)，其中数字 \(A\) 是Alice私有的，只有她自己知道，其他的信息都是別人可能知道的；同樣Bob知道的信息有\(p\),\(g\),\(A\),\(Y_a\),\(Y_b\)，其中数字 \(B\) 是Bob私有的，只有自己知道。

    到目前為止，Alice和Bob之間的密鑰協商結束。

    Alice通過計算 \(K_a=\left( Y_b \right) ^A\ mod\ p\) 得到密鑰 \(K_a\)，同樣的，Bob通過計算 \(K_b=\left( Y_a \right) ^B\ mod\ p\) 得到密鑰 \(K_b\)，可以證明，必然滿足 \(K_a=K_b\)。由此，Alice和Bob得到了相同的密鑰，達成了密鑰協商的目的。

    證明：\(K_a=K_b\)

    對於Alice有：

    \(K_a=\left( Y_b \right) ^Amod\ p=\left( g^Bmod\ p \right) ^A\ mod\ p=g^{B\times A}\ mod\ p\)

    對於Bob有：

    \(K_b=\left( Y_a \right) ^Bmod\ p=\left( g^Amod\ p \right) ^B\ mod\ p=g^{A\times B}\ mod\ p\)

    上面的運算過程，可根據取模運算的性質可得【a ^ b % p = ((a % p)^b) % p】，由上可得，Alice和Bob生成的密鑰其實是進行相同的運算過程，因此必然有 \(K_a=K_b\)。

  2. 如果存在一個竊聽者Eve，他能否破解密鑰呢？很顯然Eve能夠竊聽到 \(p\),\(g\),\(Y_a\),\(Y_b\)，所以問題轉變了，Eve能否根據這些信息計算出 \(K_a\) 和 \(K_b\) ？要計算 \(K_a\) 和 \(K_b\) 需要知道A和B。

    以計算A為例，Eve能根據 \(p\),\(g\),\(Y_a\) 通過 \(g^Amod\ p=Y_a\) 計算出 \(A\) 嗎？ 目前所知的最佳算法Pollard’s rho algorithm for logarithms 時間複雜度是 \(O\left( \sqrt{p} \right)\), 但是實際應用中的 \(p\) 為二進制，假設這個 \(p\) 的長度為 \(n\), 這個複雜度實際上是 $O\left( 2^{\frac{n}{2}} \right) $，這個一個指數級的複雜度，是非常高的。因此求解該問題在計算上的困難程度保證了DH算法的安全性。

安全性問題

那DH密鑰協商算法是否就一定安全呢？我們所熟知的，存在一種偽裝者攻擊(中間人攻擊)能夠對這種密鑰協商算法造成威脅。

假設密鑰協商過程中，在Alice和Bob有一個稱為Alan的主動攻擊者，他能夠截獲Alice和Bob的消息並偽造假消息，考慮以下情況。

  1. Alice和Bob已經共享一個素數 \(p\) 以及其該素數 \(p\) 的本原根 \(g\)，當然Alan也監聽到報文得知了這個兩個消息。
  2. 此時Alice計算 \(g^Amod\ p=Y_a\) ，然而將 \(Y_a\) 發送給Bob的過程中被Alan攔截了，Alan自己選定了一個隨機數 \(C\), 計算 \(Y_c=g^C\ mod\ p\), 然後將 \(Y_c\) 發送給Bob。
  1. 同時Bob計算 \(g^Bmod\ p=Y_b\)，同樣在將 \(Y_b\) 發送給Alice的過程中被Alan攔截下來，Alan自己選定了一個隨機數D ，計算 \(g^Dmod\ p=Y_d\) 發送給了Alice
  1. 由於Alice和Bob通訊的消息被替換，Alice計算出來的密鑰實際上為Alice和Alan之間協商的密鑰：\(K_{ad}=g^{D\times A}\ mod\ p\)；Bob計算出來的密鑰實際上是Blob和Alan之間協商的密鑰：\(K_{bc}=g^{C\times B}\ mod\ p\) 。如果之後Alice和Bob用他們各自計算出來的密鑰加密任何信息，Alan截獲之後都能夠解密得到明文，而Alan也能夠偽裝成Alice或者Bob給雙方發消息，而不至於被發現。

代碼為java實現。

參考

https://www.cnblogs.com/qcblog/p/9016704.html

https://www.cnblogs.com/wushaopei/p/11979200.html

https://blog.csdn.net/l18339702017/article/details/81625257

https://www.jiamisoft.com/blog/24603-dcfdcjm.html

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

※超省錢租車方案

商務出差、學生出遊、旅遊渡假、臨時用車!GO 神州租賃有限公司!合法經營、合法連鎖、合法租賃小客車!