李 彬

（湖北第二師范學(xué)院 湖北 武漢 430000）

1 非對(duì)稱加密的概述

1.1 背景

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

1.2 核心原理

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

1.3 與對(duì)稱加密的不同點(diǎn)

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

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

2 非對(duì)稱加密的原理

（1）生成密鑰對(duì)使用的算法一般使用RSA 算法生成密鑰對(duì)，一般基于下面兩個(gè)數(shù)論上的事實(shí)：

i.已有確定一個(gè)整數(shù)是不是質(zhì)數(shù)的快速概率算法。

ii.尚未找到確定一個(gè)非常大的合數(shù)的質(zhì)因數(shù)的快速算法。

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

（2）Miller-Rabin 算法：

引理1（費(fèi)馬定理）設(shè)p 是素?cái)?shù)，a 為整數(shù)，且（a,p）=1，則ap-1 ≡1（modp）。

證明：考慮1,2,3……（p-1）這p-1 個(gè)數(shù)字，給它們同時(shí)乘上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（二次探測(cè)定理）如果p 是一個(gè)素?cái)?shù)，且0[x[p,則方程χ2≡1（modp）的解為χ=1，p-1。

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

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

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

∵p 為質(zhì)數(shù)

∴χ=1 或者χ=p-1

總之，若n 是素?cái)?shù)，則a^m ≡1（modn）,或存在0 ≤r ≤q-1，使a^（2r·m）≡n-1（modn）。

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

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

（3）生成密鑰對(duì)的過程：

1）首先，使用Miller-Rabin 算法生成兩個(gè)大的素?cái)?shù)p，q，且p，q 是保密的。

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

3）選擇一個(gè)隨機(jī)數(shù)e（0 ＜e ＜ψ（n）），使得（e，ψ（n））=1，即e 和ψ 互素。

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

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

3 非對(duì)稱加密的應(yīng)用

若A 用戶想要向B 用戶發(fā)送一個(gè)郵件，那么他需要先用郵件內(nèi)容生成一個(gè)MD5 值，然后再將時(shí)間戳和MD5 值和其他某些標(biāo)記一起用私鑰加密成數(shù)字簽名。

假設(shè)C 用戶將郵件內(nèi)容篡改，那么B 用戶通過對(duì)比郵件內(nèi)容MD5 以及用A 用戶公鑰解密的數(shù)字簽名內(nèi)的MD5 值就能發(fā)現(xiàn)內(nèi)容被篡改過。即滿足i 特性。

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

若將A 文件的數(shù)字簽名放到B 文件上，則可以通過對(duì)比MD5 值來判斷簽名和文件是否是對(duì)應(yīng)的。

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

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