淺談非對稱加密方式及其應用

李 彬

（湖北第二師范學院 湖北 武漢 430000）

1 非對稱加密的概述

1.1 背景

非對稱加密是美國學者Dime 和Henman 在1976 年提出的一種新的密鑰交換協議，用于解決信息公開傳送和密鑰管理問題。

1.2 核心原理

非對稱加密加、解密信息的過程需使用一組密鑰對，稱為公鑰和私鑰。若使用公鑰加密信息，則只能使用私鑰進行解密，若使用私鑰進行加密，則只能使用公鑰進行解密。要求公鑰公開給其他人，私鑰必須由用戶保存且保密。并且不能輕易通過公鑰推出私鑰[1]。

1.3 與對稱加密的不同點

對稱加密時只有一個密鑰，加密和解密的過程都由同一個密鑰來完成。這樣帶來的問題就是：如果將一段信息用密鑰加密，那么別人解密這個信息也需要這個密鑰。如何將這個密鑰在網絡上完整地，不泄露地傳給對方很難做到。

而非對稱加密使用一對密鑰，可以將公鑰公布給所有人，只需要把私鑰保存好就行。若A 要向B 發送信息，那么A 只需要使用B 已經公開的公鑰信息，B 收到信息后用自己的私鑰就能解開信息。

2 非對稱加密的原理

（1）生成密鑰對使用的算法一般使用RSA 算法生成密鑰對，一般基于下面兩個數論上的事實：

i.已有確定一個整數是不是質數的快速概率算法。

ii.尚未找到確定一個非常大的合數的質因數的快速算法。

目前，雖然還未找到高效的素性檢測方法，但是已經有了一些隨機算法能夠用于素性檢測以及因數分解[2]。以下描述的MillerRabin 算法就是這樣的一種方法：

（2）Miller-Rabin 算法：

引理1（費馬定理）設p 是素數，a 為整數，且（a,p）=1，則ap-1 ≡1（modp）。

證明：考慮1,2,3……（p-1）這p-1 個數字，給它們同時乘上a，得到a,2a,3a……（p-1）a。

∵a ≠b（modp）,（c,p）=1

∴ac ≠bc（modp）

∴1x2x3……（p-1）≡a.2a.3a……（p-1）a（modp）

∴（p-1）!≡（p-1）!ap-1（modp）

∵（（p-1）!,p）=1

∴ap-1 ≡1（modp）

引理2（二次探測定理）如果p 是一個素數，且0[x[p,則方程χ2≡1（modp）的解為χ=1，p-1。

證明：易知χ2≡0（modp）

∴（χ+1）（χ-1）≡0（modp）

∴p|（χ-1）（χ+1）

∵p 為質數

∴χ=1 或者χ=p-1

總之，若n 是素數，則a^m ≡1（modn）,或存在0 ≤r ≤q-1，使a^（2r·m）≡n-1（modn）。

由上面的分析可知，素數一定通過Miller 測試。所以，如果n 不能通過Miller 測試，則n 一定是合數；如果n能通過Miller 測試，則n 很可能是素數。這就是Miller-Rabin 算法。

可以證明Miller-Rabin 算法給出的錯誤結果的概率小于等于1/4。若反復測試k次，則錯誤概率可降低至（1/4）^k。這僅僅只是一個大概的保守估計，在實際操作過程中效果會更加突出，更加高效。

（3）生成密鑰對的過程：

1）首先，使用Miller-Rabin 算法生成兩個大的素數p，q，且p，q 是保密的。

2）計算n=pq 和ψ（n）=（p-1）（q-1）,其中ψ（n）是保密的。

3）選擇一個隨機數e（0 ＜e ＜ψ（n）），使得（e，ψ（n））=1，即e 和ψ 互素。

4）計算得到d，使得dxemodψ（n）=1，即在與n 互素的數中選取與ψ（n）互素的數。

5）其中私鑰是d，公鑰是（e，n）。

3 非對稱加密的應用

若A 用戶想要向B 用戶發送一個郵件，那么他需要先用郵件內容生成一個MD5 值，然后再將時間戳和MD5 值和其他某些標記一起用私鑰加密成數字簽名。

假設C 用戶將郵件內容篡改，那么B 用戶通過對比郵件內容MD5 以及用A 用戶公鑰解密的數字簽名內的MD5 值就能發現內容被篡改過。即滿足i 特性。

若該消息可以通過A 用戶的公鑰解密數字簽名，那么該數字簽名一定是由A 的私鑰加密，若A 的私鑰沒有泄漏，且MD5 值相同，那么就可以證明該消息一定是A 發出的。即滿足ii 和iii 特性。

若將A 文件的數字簽名放到B 文件上，則可以通過對比MD5 值來判斷簽名和文件是否是對應的。

（1）發送郵件的完整過程：若A 用戶想要向B 用戶發送一個郵件，那么他需要先用郵件內容生成一個MD5 值，然后再將時間戳和MD5 值和其他某些標記一起用私鑰加密成數字簽名。然后將郵件內容和數字簽名一起用B 的公鑰加密成密文發送給B。B 收到消息后，先用自己的私鑰解密成郵件內容和數字簽名，再用A 的公鑰解密數字簽名得到MD5。通過對比郵件內容的MD5 和數字簽名的MD5 是否相同可以檢測出郵件內容有沒有被篡改[3]。

（2）發送公開聲明的完整過程：若A 想發送一個公開聲明，那么他需要先用聲明內容生成一個MD5 值，然后再將時間戳和MD5 值和其他某些標記一起用私鑰加密成數字簽名，然后加在聲明的后面發送出去。其他用戶收到這份聲明，可以用A 用戶的公鑰驗證數字簽名的MD5 值和聲明內容的MD5 值是否相等來判斷這份聲明是否是A 發出的。