1 RSA 算法概述
1．1 RSA的實(shí)現(xiàn)
RSA 算法，也就是加密解密的過(guò)程比較容易理解：
1.1.1 公鑰密鑰對(duì)的生成
a 生成兩個(gè)大素?cái)?shù) p 和 q.
b 令 n = p * q and f(n) = (p-1) (q-1)
c 選擇 b (1< b < f(n)) 使得 gcd(b, f(n))=1, 即b與f(n)互質(zhì)
d 找到 a = b^(-1) mod f(n),即 a*b=1 (mod f(n))
e 結(jié)果：(n,b)為公鑰對(duì)； (p,q,a) 為密鑰對(duì).
舉例說(shuō)明: Ⅰ. 我們選擇 p=11 q=13, 則有：
n = 11*13=143
f(n)=(p-1)(q-1)=10*12=120;
Ⅱ. 選擇b=37 , (我們有gcd(37,120)=1)
我們可以計(jì)算出 a=13, (有a*b=481=1 mod 120)
Ⅲ. 于是有(143,37)為公鑰對(duì)；(11,13,13)為密鑰對(duì).
1.1.2 加密解密
對(duì)于任意 x,y?Zn（自然數(shù)）,依習(xí)慣, x為原文,y為密文. E( x)為加密, D(y) 為解密.
我們有E(x) = x^b (mod n) D(y) = y^a (mod n)
舉例說(shuō)明： 由上例，我們有原文 x=2
加密：y= x^b mod n=2^37 mod 143 = 12.
解密：x= D(y) = y^a mod n = 12^13 mod 143 =2.
顯然, 實(shí)際應(yīng)用時(shí)是不可能這么簡(jiǎn)單的。從公鑰對(duì) (n,b), 得到 a, p,q或是f(n) 在計(jì)算上應(yīng)該是不可行的。
1.2 RSA 成立的證明
根據(jù)前面的例子，我們可以看到對(duì)于任意的x<n (實(shí)際應(yīng)用中，我們把原文分成許多長(zhǎng)度位u位的小段, 有2^u<=n, 使得x<n) , 通過(guò)加密再解密的過(guò)程都可以得到原文x, 下面給出一般性的證明：
由上，我們有： x= D(y) = D(x^b) = (x^b)^a = x^ab (mod n)
也就是說(shuō)我們需要證明上式成立，即：
x ^ ab mod n = x (1)
a.首先我們有恒等式: X^(p-1) (mod p) =1, 其中p是素?cái)?shù)，X是非零整數(shù)。
譬如有 X=3, p=7, 則有3^6 mod 7 = 729 mod 7 =1
(這個(gè)等式來(lái)自費(fèi)馬定理，不要再試圖讓我給出這個(gè)定理的證明哦！據(jù)說(shuō)這個(gè)定理到現(xiàn)在還沒(méi)有人能夠完全證明.汗!對(duì)數(shù)論感興趣的同學(xué)可以去參考[1]或是去Google搜索fermat theorem)
b. 于是我們有X^(p-1)(q-1) mod p = (X^(p-1))^(q-1) mod p = 1^(q-1) mod p=1
即 X^(p-1)(q-1) mod p=1
c. 同樣對(duì)于任意整數(shù)k, 有X^k(p-1)(q-1) mod p=1
d. 上等式兩端同時(shí)乘X,則有 X^(k(p-1)(q-1)+1) mod p = X
e. 即X^(kf(n)+1) mod p = X
f. 因?yàn)?SPAN lang=EN-US>ab mod f(n)=1， 我們可以寫成 ab = k’f(n)+1
g. 因?yàn)?SPAN lang=EN-US>k和k’可以是任意整數(shù)，所以由e,f可以的到：
X^ab mod p = X
h. 同樣的，我們有 X^ab mod q = X
i. 因?yàn)?SPAN lang=EN-US>p,q都是素?cái)?shù)，我們有 X^ab mod n = X. 即（1）式