第3章數據加密技術3.2.1RSA算法和DH算法編著：

秦燊勞翠金

3.2非對稱加密技術通過前面的學習，我們知道，對稱加密技術要求發送者和接收者事先將對稱密鑰共享，如果雙方事先沒有共享密鑰，一方就要想辦法將所用的對稱密鑰傳送給另一方。萬一密鑰在傳送過程中被攻擊者截獲，攻擊者就可以解密出所有用這個對稱密鑰加密的密文了。但如何安全的將對稱密鑰傳送給對方，一直是個大問題。直到1976年美國科學家WhitfieldDiffie和MartinHellman提出DH算法，才解決了這個難題。DH算法不直接傳遞密鑰，只傳遞用自己的私鑰加密某數后的值，最終雙方都能計算出一把與對方完全一致的新密鑰，雙方再用這把新密鑰來加密和解密數據。受DH算法啟發，麻省理工學院的三位科學家Rivest、Shamir和Adleman于1977年提出了RSA算法，該算法把密鑰分成了兩把，加密和解密使用不同的密鑰，私鑰由擁有者保管，不在網絡間傳輸，公鑰則是公開的。RSA算法是第一個能同時用于加密和數字簽名的算法。常見的非對稱加密算法有：RSA、DH、ECC等。下面，借助工具軟件RSA-TOOL，先介紹RSA算法，再介紹DH算法，說明如何生成和運用非對稱密鑰。一、RSA算法RSA算法是如何工作的呢？下面以張三與李四通信為例。張三擁有一對密鑰，分別是張三的公鑰和張三的私鑰。其中，張三的公鑰是公開的，共享給所有人，如何確保張三的公鑰不被偽造，將在后文中講解；張三的私鑰是保密的，只有張三可以使用。李四若要加密數據給張三，可用張三的公鑰加密。張三收到后，再用自己的私鑰解密，讀取明文。攻擊者沒有張三的私鑰，只有張三的公鑰和截獲到的密文，是無法獲取明文的。RSA密鑰對的生成方法如下：首先，要秘密地選取兩個大素數。為了便于計算和說明，這里選兩個小素數7和17，還要選取一個與（7-1）×（17-1）互素的數（即與96互素的數）作為公鑰，這里選5作為公鑰。接著，打開工具軟件RSA2TOOL，將進制設置為10進制，輸入公鑰5，第一個素數7，第二個素數17，點擊“CalcD”按鈕，即可算出循環周期是119，私鑰是77。我們可以把循環周期合并到公鑰和私鑰中書寫，即把公鑰記為（5，119），把私鑰記為（77，119）。3.2.1RSA算法和DH算法為便于理解，下面用不嚴謹的方法描述一下RSA算法大致是如何工作的。RSA算法要用到歐拉函數與費馬小定理。歐拉函數的特例：假如a是素數，那么a的歐拉函數等于a-1。費馬小定理的特例：假如a是素數、b是一個整數，那么b^(a-1)moda=1。圖3-2-1軟件工具RSA-Tool為便于理解，下面用不嚴謹的方法描述一下RSA算法大致是如何工作的。RSA算法要用到歐拉函數與費馬小定理。歐拉函數的特例：假如a是素數，那么a的歐拉函數等于a-1。費馬小定理的特例：假如a是素數、b是一個整數，那么b^(a-1)moda=1。以選取兩個小素數7和17為例：根據費馬小定理，對于素數7，任意取一個整數b，可得到：b^(7-1)mod7=1，即b^6mod7=1;根據費馬小定理，對于素數17，任意取一個整數b，可得到：b^（17-1）mod17=1，即b^16mod17=1;由此可知：b^(6×16)mod(7×17)=1，即：b^96mod119=1如果存在一個數mod96等于1，比如385mod96=1，385=4×96+1，那么，b^385mod119=b^（4×96+1）mod119=【（b^（4×96））mod119】×【（b^1）mod119】=1×b=b可見，只要找到兩個數，它們的乘積mod96等于1，這兩個數就是公鑰和私鑰。原因如下：比如，我們可以找到兩個與96互素的數：5和77，5×77=385，385mod96=1，由上式b^385mod119=b可知：b^(5×77)mod119=b把5×77拆開來寫，上式也可寫成：【b^5mod119】^77mod119=b其中，【b^5mod119】可以看成對b進行加密，得到的結果就是密文；接著，（密文^77mod119）是對密文進行解密，得到的結果就是解密后的明文b。演算過程中，從7×17求得119很容易。119是公開的，如果能將119分解成7乘以17，再根據公鑰5就可以破解出私鑰是77了。但實際應用中，采用的是兩個上百位的十進制大素數。由這兩個上百位十進制數的乘積得到一個很大的數，RSA算法的安全性就取決于對這個大數分解的難度。將長達1024位或2048位的十進制大數分解成兩個素數相乘，這樣的難度非常大，接近不可能。因此，只要密鑰位數足夠大，RSA算法是安全的。例題：已知RSA公鑰是(5,119)，私鑰是（77，119），請用公鑰(5,119)加密字母A（A的ASCII碼是65，即加密：65），再用私鑰對密文進行解密。明文：65用公鑰加密：用公鑰（5，119）進行加密，（65^5）mod119=46即加密后，得到密文：46用私鑰解密：用私鑰（77，119）進行解密，(46^77)mod119=65，即解密得到明文：65因為公鑰是公開的，即5和119是公開的，若能對119作因數分解，就可以破解出私鑰了，對119進行因數分解很容易，可以分解成7×17。但對1024位、2048位這樣的大數進行因數分解是不可行的，因此，只要密鑰位數夠大，RSA算法是安全的。二、DH算法DH是Diffie-Hellman的首字母縮寫，DH算法是WhitefieldDiffie與MartinHellman在1976年提出了一個的密鑰交換算法。它可以使用不對稱加密算法，為通信雙方生成相同的臨時對稱密鑰，然后雙方利用這個臨時對稱密鑰進一步傳送真正使用的對稱密鑰。一）原理很簡單，簡單的運算過程舉例如下：1.公開兩個數：5和97。2.A、B雙方各自取一個保密的數：A方選取36。B方選取58。3.A計算出5^36mod97給B。B計算出5^58mod97給A。4.A根據((5^58mod97)^36)mod97得到對稱密鑰：((5^58^36)mod97。5.B根據((5^36mod97)^58)mod97得到對稱密鑰：((5^36)^58)mod97。可以看出，A、B雙方得到的對稱密鑰是一至的。二）具體過程如下：1.各自產生密鑰對。2.交換公鑰。3.用對方的公鑰和自己的私鑰運行DH算法得到一個臨時的對稱密鑰M。4.A產生一個對稱密鑰N，用臨時密鑰M加密后發給B。5.B用臨時密鑰M解密得到對稱密鑰N。6.B用這個對稱密鑰N來解密A的數據。比較關鍵的一步，雙方是如何對方的公鑰計算得到臨時的對稱密鑰M的？三）舉例說明。1.各自產生密鑰對。先解釋什么是原根。若存在g∈[2,p-1]，對于所有i∈[1,p-1]，計算(g^i)%p得到的結果都是互不相同的，那么數g就是數p的一個原根。每個素數都有原根。1）雙方協商一個素數和這個素數的一個原根，這個素數和它的原根是公開的。如取素數q=97和97的一個原根a=5。q和a由雙方協商，并且都是公開的。2）A、B雙方各自選擇一個小于q的隨機數作為自己的私有密鑰(即小于97的隨機數）。A選的私鑰XA=36。B選的私鑰XB=58。3）A、B雙方計算各自的公開密鑰：A的公鑰YA=（5^36）mod97=50B的公鑰YB=（5^58）mod97=442.交換公鑰。3.根據DH算法，用對方的公鑰和自己的私鑰進行運算，得到臨時的對稱密鑰M。