本文作者：一起剝堅果

　　作者： 阮一峰

　　上一次，我介紹了一些數(shù)論知識。

　　有了這些知識，我們就可以看懂RSA算法。這是目前地球上最重要的加密算法。



　　六、密鑰生成的步驟

　　我們通過一個例子，來理解RSA算法。假設愛麗絲要與鮑勃進行加密通信，她該怎么生成公鑰和私鑰呢？



　　第一步，隨機選擇兩個不相等的質數(shù)p和q。

　　愛麗絲選擇了61和53。（實際應用中，這兩個質數(shù)越大，就越難破解。）

　　第二步，計算p和q的乘積n。

　　愛麗絲就把61和53相乘。

　　n = 61×53 = 3233

　　n的長度就是密鑰長度。3233寫成二進制是110010100001，一共有12位，所以這個密鑰就是12位。實際應用中，RSA密鑰一般是1024位，重要場合則為2048位。

　　第三步，計算n的歐拉函數(shù)?(n)。

　　根據(jù)公式：

　　?(n) = (p-1)(q-1)

　　愛麗絲算出?(3233)等于60×52，即3120。

　　第四步，隨機選擇一個整數(shù)e，條件是1< e < ?(n)，且e與?(n) 互質。

　　愛麗絲就在1到3120之間，隨機選擇了17。（實際應用中，常常選擇65537。）

　　第五步，計算e對于?(n)的模反元素d。

　　所謂"模反元素"就是指有一個整數(shù)d，可以使得ed被?(n)除的余數(shù)為1。

　　ed ≡ 1 (mod ?(n))

　　這個式子等價于

　　ed - 1 = k?(n)

　　于是，找到模反元素d，實質上就是對下面這個二元一次方程求解。

　　ex + ?(n)y = 1

　　已知 e=17, ?(n)=3120，

　　17x + 3120y = 1

　　這個方程可以用"擴展歐幾里得算法"求解，此處省略具體過程。總之，愛麗絲算出一組整數(shù)解為 (x,y)=(2753,-15)，即 d=2753。

　　至此所有計算完成。

　　第六步，將n和e封裝成公鑰，n和d封裝成私鑰。

　　在愛麗絲的例子中，n=3233，e=17，d=2753，所以公鑰就是 (3233,17)，私鑰就是（3233, 2753）。

　　實際應用中，公鑰和私鑰的數(shù)據(jù)都采用ASN.1格式表達（實例）。

　　七、RSA算法的可靠性

　　回顧上面的密鑰生成步驟，一共出現(xiàn)六個數(shù)字：

　　?(n)

　　這六個數(shù)字之中，公鑰用到了兩個（n和e），其余四個數(shù)字都是不公開的。其中最關鍵的是d，因為n和d組成了私鑰，一旦d泄漏，就等于私鑰泄漏。

　　那么，有無可能在已知n和e的情況下，推導出d？

　?。?）ed≡1 (mod ?(n))。只有知道e和?(n)，才能算出d。

　?。?）?(n)=(p-1)(q-1)。只有知道p和q，才能算出?(n)。

　?。?）n=pq。只有將n因數(shù)分解，才能算出p和q。

　　結論：如果n可以被因數(shù)分解，d就可以算出，也就意味著私鑰被破解。

　　可是，大整數(shù)的因數(shù)分解，是一件非常困難的事情。目前，除了暴力破解，還沒有發(fā)現(xiàn)別的有效方法。維基百科這樣寫道：

　　"對極大整數(shù)做因數(shù)分解的難度決定了RSA算法的可靠性。換言之，對一極大整數(shù)做因數(shù)分解愈困難，RSA算法愈可靠。

　　假如有人找到一種快速因數(shù)分解的算法，那么RSA的可靠性就會極度下降。但找到這樣的算法的可能性是非常小的。今天只有短的RSA密鑰才可能被暴力破解。到2008年為止，世界上還沒有任何可靠的攻擊RSA算法的方式。

　　只要密鑰長度足夠長，用RSA加密的信息實際上是不能被解破的。"

　　舉例來說，你可以對3233進行因數(shù)分解（61×53），但是你沒法對下面這個整數(shù)進行因數(shù)分解。

　　12301866845301177551304949

　　58384962720772853569595334

　　79219732245215172640050726

　　36575187452021997864693899

　　56474942774063845925192557

　　32630345373154826850791702

　　61221429134616704292143116

　　02221240479274737794080665

　　351419597459856902143413

　　它等于這樣兩個質數(shù)的乘積：

　　33478071698956898786044169

　　84821269081770479498371376

　　85689124313889828837938780

　　02287614711652531743087737

　　814467999489

　　×

　　36746043666799590428244633

　　79962795263227915816434308

　　76426760322838157396665112

　　79233373417143396810270092

　　798736308917

　　事實上，這大概是人類已經(jīng)分解的最大整數(shù)（232個十進制位，768個二進制位）。比它更大的因數(shù)分解，還沒有被報道過，因此目前被破解的最長RSA密鑰就是768位。

　　八、加密和解密

　　有了公鑰和密鑰，就能進行加密和解密了。

　?。?）加密要用公鑰 (n,e)

　　假設鮑勃要向愛麗絲發(fā)送加密信息m，他就要用愛麗絲的公鑰 (n,e) 對m進行加密。這里需要注意，m必須是整數(shù)（字符串可以取ascii值或unicode值），且m必須小于n。

　　所謂"加密"，就是算出下式的c：

　　me ≡ c (mod n)

　　愛麗絲的公鑰是 (3233, 17)，鮑勃的m假設是65，那么可以算出下面的等式：

　　6517 ≡ 2790 (mod 3233)

　　于是，c等于2790，鮑勃就把2790發(fā)給了愛麗絲。

　?。?）解密要用私鑰(n,d)

　　愛麗絲拿到鮑勃發(fā)來的2790以后，就用自己的私鑰(3233, 2753) 進行解密。可以證明，下面的等式一定成立：

　　cd ≡ m (mod n)

　　也就是說，c的d次方除以n的余數(shù)為m?，F(xiàn)在，c等于2790，私鑰是(3233, 2753)，那么，愛麗絲算出

　　27902753 ≡ 65 (mod 3233)

　　因此，愛麗絲知道了鮑勃加密前的原文就是65。

　　至此，"加密--解密"的整個過程全部完成。

　　我們可以看到，如果不知道d，就沒有辦法從c求出m。而前面已經(jīng)說過，要知道d就必須分解n，這是極難做到的，所以RSA算法保證了通信安全。

　　你可能會問，公鑰(n,e) 只能加密小于n的整數(shù)m，那么如果要加密大于n的整數(shù)，該怎么辦？有兩種解決方法：一種是把長信息分割成若干段短消息，每段分別加密；另一種是先選擇一種"對稱性加密算法"（比如DES），用這種算法的密鑰加密信息，再用RSA公鑰加密DES密鑰。

　　九、私鑰解密的證明

　　最后，我們來證明，為什么用私鑰解密，一定可以正確地得到m。也就是證明下面這個式子：

　　因為，根據(jù)加密規(guī)則

　?。韊 ≡ c (mod n)

　　于是，c可以寫成下面的形式：

　　c = me - kn

　　將c代入要我們要證明的那個解密規(guī)則：

　　(me - kn)d ≡ m (mod n)

　　它等同于求證

　　med ≡ m (mod n)

　　由于

　　所以

　　ed = h?(n)+1

　　將ed代入：

　　mh?(n)+1 ≡ m (mod n)

　　接下來，分成兩種情況證明上面這個式子。

　　（1）m與n互質。

　　根據(jù)歐拉定理，此時

　　m?(n) ≡ 1 (mod n)

　　得到

　　(m?(n))h × m ≡ m (mod n)

　　原式得到證明。

　?。?）m與n不是互質關系。

　　此時，由于n等于質數(shù)p和q的乘積，所以m必然等于kp或kq。

　　以 m = kp為例，考慮到這時k與q必然互質，則根據(jù)歐拉定理，下面的式子成立：

　　(kp)q-1 ≡ 1 (mod q)

　　進一步得到

　　[(kp)q-1]h(p-1) × kp ≡ kp (mod q)

　　即

　　(kp)ed ≡ kp (mod q)

　　將它改寫成下面的等式

　　(kp)ed = tq + kp

　　這時t必然能被p整除，即 t=t＇p

　　(kp)ed = t＇pq + kp

　　因為 m=kp，n=pq，所以

　?。ㄍ辏?br/>
　　關于本文

　　本文授權轉載自阮一峰的網(wǎng)絡日志

原文地址：http://iphone.myzaker.com/l.php?l=522d6bac7f52e90c7b000002