RSA是第一個(gè)也是使用的最廣發(fā)的公鑰加密算法，在1978年由R.Rivest、AdiShamir和Adleman三人發(fā)明，并以他們的名字命名。RSA算法的安全性基于大數(shù)因子分解的困難性，下面介紹一下它的基本原理：

1、生成公鑰和私鑰

(1) 選取兩個(gè)大素?cái)?shù)：p和q；

(2)計(jì)算n=p*q；

(3)計(jì)算小于n并且與n互質(zhì)的整數(shù)的個(gè)數(shù)，即歐拉函數(shù)o(n) = (p - 1) * (q - 1)；

(4)隨機(jī)選擇加密密鑰e， 使1<e<o(n)， 且與o(n)互質(zhì)；

(5)最后，利用歐幾里得算法計(jì)算解密密鑰，使其滿足ed = 1(mod o(n))；

然后將(e, n)公開，即為公鑰PK，私人保存好d,即為私鑰SK;

2、加密

將明文m分解成等長(zhǎng)數(shù)據(jù)塊m1，m2， ……，mi。加密時(shí)，按如下公式進(jìn)行計(jì)算即可：

ci=（mi）^ e（mod n），密文c則由c1，c2，……ci組成。

3、解密

與加密一樣，按如下公式進(jìn)行計(jì)算：

mi=（ci）^d（mod n），明文m則由m1，m2，……，mi組成。

以上就是RSA算法的公私鑰產(chǎn)生、加密和解密的過程。整個(gè)過程中，最難理解的部分應(yīng)是1.5中的求私鑰d,很多課本提到的都是歐幾里德算法，但并未具體的計(jì)算過程，下面本人就通過一個(gè)實(shí)例向大家介紹歐幾里德算法在RSA中的應(yīng)用。

例：令p=47，q=71，求用RSA算法加密的公鑰和私鑰。
計(jì)算如下：
（1）n=pq=47*71=3337；
（2）?（n）=（p-1）*（q-1）=46*70=3220；
（3）隨機(jī)選取e=79（滿足與3220互質(zhì)的條件）；
（4）則私鑰d應(yīng)該滿足：79*d mod 3220 = 1；
那么這個(gè)式子（4）如何解呢？這里就要用到歐幾里得算法（又稱輾轉(zhuǎn)相除法），解法如下：
（a）式子（4）可以表示成79*d-3220*k=1（其中k為正整數(shù)）；
（b）將3220對(duì)79取模得到的余數(shù)60代替3220，則變?yōu)?9*d-60*k=1；
（c）同理，將79對(duì)60取模得到的余數(shù)19代替79，則變?yōu)?9*d-60*k=1；
（d）同理，將60對(duì)19取模得到的余數(shù)3代替60，則變?yōu)?9*d-3*k=1；
（e）同理，將19對(duì)3取模得到的余數(shù)1代替19，則變?yōu)閐-3*k=1；

當(dāng)d的系數(shù)最后化為1時(shí)，
令k=0，代入（e）式中，得d=1；
將d=1代入（d）式，得k=6；
將k=6代入（c）式，得d=19；
將d=19代入（b）式，得k=25；
將k=25代入（a）式，得d=1019，這個(gè)值即我們要求的私鑰d的最終值。
此時(shí)，我們即可得到公鑰PK=（e，n）={79，3337}，私鑰SK={1019，3337}，后面的加密和解密直接套相應(yīng)公式即可。

現(xiàn)在給個(gè)字符"C"，我們?cè)賮硌堇[如何加解密。

取質(zhì)數(shù)13和7

(1) n = 13*7 = 91

(2)o(n) = 12 * 6 = 72

(3)取72互質(zhì)的數(shù)：5

(4)則私鑰應(yīng)該滿足：5*d mod72=1

即：5 * d ?- 72 * K = 1 ---------------@2

將72 % 5得2替代72，則5*d - 2 * k = 1 ?-------------- @1

將5 % 2得1替代5，則d - 2 * k = 1

令k = 0, 得d = 1

將d = 1 代入@1中，則k = 2

將k = 2代入@2中， 則d = 29

此時(shí)，我們即可得到公鑰PK=（e，n）={5，?91}，私鑰SK={29，?91}

字符“C”對(duì)應(yīng)的ascii碼表值為67

67 * 67 ?mode??91= ?30

30 * 67 mode 91= ?8

?8 * 67 mode 91?= 81

81 * 67 mod 91 = 58

以此方式連續(xù)乘次數(shù)為5次(公鑰)，最后得到加密數(shù)值 58

若要解密這個(gè)數(shù)值58，以上述相同方式連續(xù)乘以自己29次，即可得到解密數(shù)值 67。

參考文章：

http://8btc.com/thread-1240-1-1.html

http://blog.sina.com.cn/s/blog_4fcd1ea30100yh3a.html

總結(jié)

以上是生活随笔為你收集整理的RSA算法演绎的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。