一、RSA?的歷史
1976 年以前，所有的加密方法都是同一種模式：
?。?）甲方選擇某一種加密規(guī)則，對(duì)信息進(jìn)行加密；
?。?）乙方使用同一種規(guī)則，對(duì)信息進(jìn)行解密。
由于加密和解密使用同樣規(guī)則（簡稱"密鑰"），這被稱為"對(duì)稱加密算法"（Symmetric-key algorithm）。
這種加密模式有一個(gè)最大弱點(diǎn)：甲方必須把加密規(guī)則告訴乙方，否則無法解密。保存和傳遞密鑰，就成了最頭疼的問題。
1976 年，兩位美國計(jì)算機(jī)學(xué)家 Whitfield Diffie 和 Martin Hellman，提出了一種嶄新構(gòu)思，可以在不直接傳遞密鑰的情況下，完成解密。這被稱為"Diffie-Hellman密鑰交換算法"。這個(gè)算法啟發(fā)了其他科學(xué)家。人們認(rèn)識(shí)到，加密和解密可以使用不同的規(guī)則，只要這兩種規(guī)則之間存在某種對(duì)應(yīng)關(guān)系即可，這樣就避免了直接傳遞密鑰。
這種新的加密模式被稱為"非對(duì)稱加密算法"。
?。?）乙方生成兩把密鑰（公鑰和私鑰）。公鑰是公開的，任何人都可以獲得，私鑰則是保密的。
?。?）甲方獲取乙方的公鑰，然后用它對(duì)信息加密。
?。?）乙方得到加密后的信息，用私鑰解密。
如果公鑰加密的信息只有私鑰解得開，那么只要私鑰不泄漏，通信就是安全的。
1977 年，三位數(shù)學(xué)家 Rivest、Shamir 和 Adleman 設(shè)計(jì)了一種算法，可以實(shí)現(xiàn)非對(duì)稱加密。這種算法用他們?nèi)齻€(gè)人的名字命名，叫做?RSA 算法。從那時(shí)直到現(xiàn)在，RSA 算法一直是最廣為使用的"非對(duì)稱加密算法"。毫不夸張地說，只要有計(jì)算機(jī)網(wǎng)絡(luò)的地方，就有 RSA 算法。
這種算法非常可靠，密鑰越長，它就越難破解。根據(jù)已經(jīng)披露的文獻(xiàn)，目前被破解的最長 RSA 密鑰是 768 個(gè)二進(jìn)制位。也就是說，長度超過 768 位的密鑰，還無法破解（至少?zèng)]人公開宣布）。因此可以認(rèn)為，1024 位的 RSA 密鑰基本安全，2048 位的密鑰極其安全。
下面解釋 RSA 算法的原理?？梢钥吹剑琑SA 算法并不難，只需要一點(diǎn)數(shù)論知識(shí)就可以理解。
二、RSA?理論基礎(chǔ)
2.1 互質(zhì)關(guān)系
如果兩個(gè)正整數(shù)，除了 1 以外，沒有其他公因子，我們就稱這兩個(gè)數(shù)是互質(zhì)關(guān)系（coprime）。比如，15 和 32 沒有公因子，所以它們是互質(zhì)關(guān)系。這說明，不是質(zhì)數(shù)也可以構(gòu)成互質(zhì)關(guān)系。
關(guān)于互質(zhì)關(guān)系，不難得到以下結(jié)論：
1. 任意兩個(gè)質(zhì)數(shù)構(gòu)成互質(zhì)關(guān)系，比如 13 和 61
2. 一個(gè)數(shù)是質(zhì)數(shù)，另一個(gè)數(shù)只要不是前者的倍數(shù)，兩者就構(gòu)成互質(zhì)關(guān)系，比如 3 和 10
3. 如果兩個(gè)數(shù)之中，較大的那個(gè)數(shù)是質(zhì)數(shù)，則兩者構(gòu)成互質(zhì)關(guān)系，比如 97 和 57
4. 1 和任意一個(gè)自然數(shù)是都是互質(zhì)關(guān)系，比如 1 和 99
5. p 是大于 1 的整數(shù)，則 p 和 p-1 構(gòu)成互質(zhì)關(guān)系，比如 57 和 56
6. p 是大于 1 的奇數(shù)，則 p 和 p-2 構(gòu)成互質(zhì)關(guān)系，比如 17 和 15
2.2 歐拉函數(shù)
請(qǐng)思考以下問題：
任意給定正整數(shù) n，請(qǐng)問在小于等于 n 的正整數(shù)之中，有多少個(gè)與 n 構(gòu)成互質(zhì)關(guān)系？（比如，在 1 到 8 之中，有多少個(gè)數(shù)與 8 構(gòu)成互質(zhì)關(guān)系？）
計(jì)算這個(gè)值的方法就叫做歐拉函數(shù)，以 φ(n) 表示。在 1 到 8 之中，與 8 形成互質(zhì)關(guān)系的是 1、3、5、7，所以 φ(n) = 4。
φ(n) 的計(jì)算方法并不復(fù)雜，但是為了得到最后那個(gè)公式，需要一步步討論。
第一種情況
如果 n=1，則 φ(1) = 1 。因?yàn)?與任何數(shù)（包括自身）都構(gòu)成互質(zhì)關(guān)系。
第二種情況
如果 n 是質(zhì)數(shù)，則 φ(n)=n-1 。因?yàn)橘|(zhì)數(shù)與小于它的每一個(gè)數(shù)，都構(gòu)成互質(zhì)關(guān)系。比如 5 與 1、2、3、4 都構(gòu)成互質(zhì)關(guān)系。
第三種情況
如果 n 是質(zhì)數(shù)的某一個(gè)次方，即 n = p^k (p 為質(zhì)數(shù)，k 為大于等于 1 的整數(shù))，則
比如 φ(8) = φ(2^3) =2^3 - 2^2 = 8 -4 = 4。
這是因?yàn)橹挥挟?dāng)一個(gè)數(shù)不包含質(zhì)數(shù) p，才可能與 n 互質(zhì)。而包含質(zhì)數(shù) p 的數(shù)一共有 p^(k-1) 個(gè)，即1×p、2×p、3×p、...、p^(k-1)×p，把它們?nèi)コ?，剩下的就是與 n 互質(zhì)的數(shù)。
上面的式子還可以寫成下面的形式：
可以看出，上面的第二種情況是 k=1 時(shí)的特例。
第四種情況
如果 n 可以分解成兩個(gè)互質(zhì)的整數(shù)之積，
n = p1 × p2
則
φ(n) = φ(p1p2) = φ(p1)φ(p2)
即積的歐拉函數(shù)等于各個(gè)因子的歐拉函數(shù)之積。比如，φ(56)=φ(8×7)=φ(8)×φ(7)=4×6=24。
這一條的證明要用到"中國剩余定理"，這里就不展開了，只簡單說一下思路：如果 a 與 p1 互質(zhì) (a<p1)，b 與 p2 互質(zhì) (b<p2)，c 與 p1p2 互質(zhì) (c<p1p2)，則 c 與數(shù)對(duì) (a,b) 是一一對(duì)應(yīng)關(guān)系。由于 a 的值有 φ(p1) 種可能，b 的值有 φ(p2) 種可能，則數(shù)對(duì) (a,b) 有 φ(p1)φ(p2) 種可能，而 c 的值有 φ(p1p2) 種可能，所以 φ(p1p2) 就等于 φ(p1)φ(p2)。
第五種情況
因?yàn)槿我庖粋€(gè)大于 1 的正整數(shù)，都可以寫成一系列質(zhì)數(shù)的積。
根據(jù)第 4 條的結(jié)論，得到
再根據(jù)第 3 條的結(jié)論，得到
也就等于
這就是歐拉函數(shù)的通用計(jì)算公式。比如，1323 的歐拉函數(shù)，計(jì)算過程如下：
2.3 歐拉定理
歐拉函數(shù)的用處，在于歐拉定理。"歐拉定理"指的是：
如果兩個(gè)正整數(shù) a 和 n 互質(zhì)，則 n 的歐拉函數(shù) φ(n) 可以讓下面的等式成立：
也就是說，a 的 φ(n) 次方被 n 除的余數(shù)為1。或者說，a 的 φ(n) 次方減去 1，可以被 n 整除。比如，3 和 7 互質(zhì)，而 7 的歐拉函數(shù) φ(7) 等于6，所以 3 的 6 次方（729）減去 1，可以被 7 整除（728/7=104）。
歐拉定理的證明比較復(fù)雜，這里就省略了。我們只要記住它的結(jié)論就行了。
歐拉定理可以大大簡化某些運(yùn)算。比如，7 和 10 互質(zhì)，根據(jù)歐拉定理，
已知 φ(10) 等于 4，所以馬上得到 7 的 4 倍數(shù)次方的個(gè)位數(shù)肯定是 1。
因此，7 的任意次方的個(gè)位數(shù)（例如 7 的 222 次方），心算就可以算出來。
歐拉定理有一個(gè)特殊情況。
假設(shè)正整數(shù) a 與質(zhì)數(shù) p 互質(zhì)，因?yàn)橘|(zhì)數(shù) p 的 φ(p) 等于 p-1，則歐拉定理可以寫成
這就是著名的費(fèi)馬小定理。它是歐拉定理的特例。
歐拉定理是 RSA 算法的核心。理解了這個(gè)定理，就可以理解 RSA。
2.4 模反元素
還剩下最后一個(gè)概念：
如果兩個(gè)正整數(shù) a 和 n 互質(zhì)，那么一定可以找到整數(shù) b，使得 ab-1 被 n 整除，或者說 ab 被 n 除的余數(shù)是 1。
這時(shí)，b 就叫做 a 的"模反元素"。
比如，3 和 11 互質(zhì)，那么 3 的模反元素就是 4，因?yàn)?(3 × 4)-1 可以被 11 整除。顯然，模反元素不止一個(gè)， 4 加減 11 的整數(shù)倍都是 3 的模反元素 {...,-18,-7,4,15,26,...}，即如果 b 是 a 的模反元素，則 b+kn 都是 a 的模反元素。
歐拉定理可以用來證明模反元素必然存在。
可以看到，a 的 φ(n)-1 次方，就是 a 的模反元素。
好了，需要用到的數(shù)學(xué)工具全部介紹完了。RSA 算法涉及的數(shù)學(xué)知識(shí)，就是上面這些，接下來介紹公鑰和私鑰到底是怎么生成的。
三、RSA 密鑰生成
我們通過一個(gè)例子，來理解 RSA 算法。假設(shè)愛麗絲要與鮑勃進(jìn)行加密通信，她該怎么生成公鑰和私鑰呢？
第一步，隨機(jī)選擇兩個(gè)不相等的質(zhì)數(shù)p和q。
愛麗絲選擇了 61 和 53。（實(shí)際應(yīng)用中，這兩個(gè)質(zhì)數(shù)越大，就越難破解。）
第二步，計(jì)算 p 和 q 的乘積 n。
愛麗絲就把 61 和 53 相乘。
n = 61×53 = 3233
n 的長度就是密鑰長度。3233 寫成二進(jìn)制是 110010100001，一共有 12 位，所以這個(gè)密鑰就是 12 位。實(shí)際應(yīng)用中，RSA 密鑰一般是 1024 位，重要場合則為 2048 位。
第三步，計(jì)算 n 的歐拉函數(shù) φ(n)。
根據(jù)公式：
φ(n) = (p-1)(q-1)
愛麗絲算出 φ(3233) 等于 60×52，即 3120。
第四步，隨機(jī)選擇一個(gè)整數(shù) e，條件是 1< e < φ(n)，且 e 與 φ(n) 互質(zhì)。
愛麗絲就在 1 到 3120 之間，隨機(jī)選擇了 17。（實(shí)際應(yīng)用中，常常選擇 65537。）
第五步，計(jì)算 e 對(duì)于 φ(n) 的模反元素 d。
所謂"模反元素"就是指有一個(gè)整數(shù) d，可以使得 ed 被 φ(n) 除的余數(shù)為 1。
ed ≡ 1 (mod φ(n))
這個(gè)式子等價(jià)于
ed - 1 = kφ(n)
于是，找到模反元素 d，實(shí)質(zhì)上就是對(duì)下面這個(gè)二元一次方程求解。
ex + φ(n)y = 1
已知 e=17, φ(n)=3120，
17x + 3120y = 1
這個(gè)方程可以用"擴(kuò)展歐幾里得算法"求解，此處省略具體過程?？傊瑦埯惤z算出一組整數(shù)解為 (x,y)=(2753,-15)，即 d=2753。
至此所有計(jì)算完成。
第六步，將 n 和 e 封裝成公鑰，n 和 d 封裝成私鑰。
在愛麗絲的例子中，n=3233，e=17，d=2753，所以公鑰就是 (3233,17)，私鑰就是（3233, 2753）。
實(shí)際應(yīng)用中，公鑰和私鑰的數(shù)據(jù)都采用?ASN.1?格式表達(dá)（實(shí)例）。
四、RSA 算法的可靠性
回顧上面的密鑰生成步驟，一共出現(xiàn)六個(gè)數(shù)字：
p q n φ(n) e d
這六個(gè)數(shù)字之中，公鑰用到了兩個(gè)（n 和 e），其余四個(gè)數(shù)字都是不公開的。其中最關(guān)鍵的是 d，因?yàn)?n 和 d 組成了私鑰，一旦 d 泄漏，就等于私鑰泄漏。
那么，有無可能在已知 n 和 e 的情況下，推導(dǎo)出 d？
（1）ed≡1 (mod φ(n))。只有知道 e 和 φ(n)，才能算出 d。
（2）φ(n)=(p-1)(q-1)。只有知道 p 和 q，才能算出 φ(n)。
（3）n=pq。只有將 n 因數(shù)分解，才能算出 p 和 q。
結(jié)論：如果 n 可以被因數(shù)分解，d 就可以算出，也就意味著私鑰被破解。
可是，大整數(shù)的因數(shù)分解，是一件非常困難的事情。目前，除了暴力破解，還沒有發(fā)現(xiàn)別的有效方法。維基百科這樣寫道：
"對(duì)極大整數(shù)做因數(shù)分解的難度決定了 RSA 算法的可靠性。換言之，對(duì)一極大整數(shù)做因數(shù)分解愈困難，RSA 算法愈可靠。假如有人找到一種快速因數(shù)分解的算法，那么 RSA 的可靠性就會(huì)極度下降。但找到這樣的算法的可能性是非常小的。今天只有短的 RSA 密鑰才可能被暴力破解。到 2008 年為止，世界上還沒有任何可靠的攻擊 RSA 算法的方式。只要密鑰長度足夠長，用 RSA 加密的信息實(shí)際上是不能被解破的。"
舉例來說，你可以對(duì) 3233 進(jìn)行因數(shù)分解（61×53），但是你沒法對(duì)下面這個(gè)整數(shù)進(jìn)行因數(shù)分解：
12301866845301177551304949 58384962720772853569595334 79219732245215172640050726 36575187452021997864693899 56474942774063845925192557 32630345373154826850791702 61221429134616704292143116 02221240479274737794080665 351419597459856902143413
它等于這樣兩個(gè)質(zhì)數(shù)的乘積：
33478071698956898786044169 84821269081770479498371376 85689124313889828837938780 02287614711652531743087737 814467999489 × 36746043666799590428244633 79962795263227915816434308 76426760322838157396665112 79233373417143396810270092 798736308917
事實(shí)上，這大概是人類已經(jīng)分解的最大整數(shù)（232 個(gè)十進(jìn)制位，768 個(gè)二進(jìn)制位）。比它更大的因數(shù)分解，還沒有被報(bào)道過，因此目前被破解的最長 RSA 密鑰就是 768 位。
五、RSA 加密和解密
有了公鑰和密鑰，就能進(jìn)行加密和解密了。
（1）加密要用公鑰 (n,e)
假設(shè)鮑勃要向愛麗絲發(fā)送加密信息 m，他就要用愛麗絲的公鑰 (n,e) 對(duì) m 進(jìn)行加密。這里需要注意，m 必須是整數(shù)（字符串可以取 ascii 值或 Unicode 值），且 m 必須小于 n。
所謂"加密"，就是算出下式的 c：
me?≡ c (mod n)
愛麗絲的公鑰是 (3233, 17)，鮑勃的 m 假設(shè)是 65，那么可以算出下面的等式：
6517?≡ 2790 (mod 3233)
于是，c 等于2790，鮑勃就把 2790 發(fā)給了愛麗絲。
（2）解密要用私鑰(n,d)
愛麗絲拿到鮑勃發(fā)來的 2790 以后，就用自己的私鑰 (3233, 2753) 進(jìn)行解密?？梢宰C明，下面的等式一定成立：
cd?≡ m (mod n)
也就是說，c 的 d 次方除以 n 的余數(shù)為 m?，F(xiàn)在，c 等于2790，私鑰是 (3233, 2753)，那么，愛麗絲算出
27902753?≡ 65 (mod 3233)
因此，愛麗絲知道了鮑勃加密前的原文就是 65。
至此，"加密--解密"的整個(gè)過程全部完成。
我們可以看到，如果不知道 d，就沒有辦法從 c 求出 m。而前面已經(jīng)說過，要知道 d 就必須分解 n，這是極難做到的，所以 RSA 算法保證了通信安全。
你可能會(huì)問，公鑰 (n,e) 只能加密小于 n 的整數(shù) m，那么如果要加密大于 n 的整數(shù)，該怎么辦？有兩種解決方法：一種是把長信息分割成若干段短消息，每段分別加密；另一種是先選擇一種"對(duì)稱性加密算法"（比如?DES），用這種算法的密鑰加密信息，再用 RSA 公鑰加密 DES 密鑰。
六、私鑰解密的證明
最后，我們來證明，為什么用私鑰解密，一定可以正確地得到 m。也就是證明下面這個(gè)式子：
cd?≡ m (mod n)
因?yàn)?，根?jù)加密規(guī)則
ｍe?≡ c (mod n)
于是，c 可以寫成下面的形式：
c = me?- kn
將 c 代入要我們要證明的那個(gè)解密規(guī)則：
(me?- kn)d?≡ m (mod n)
它等同于求證
med?≡ m (mod n)
由于
ed ≡ 1 (mod φ(n))
所以
ed = hφ(n)+1
將 ed 代入：
mhφ(n)+1?≡ m (mod n)
接下來，分成兩種情況證明上面這個(gè)式子。
（1）m 與 n 互質(zhì)。
根據(jù)歐拉定理，此時(shí)
mφ(n)?≡ 1 (mod n)
得到
(mφ(n))h?× m ≡ m (mod n)
原式得到證明。
（2）m 與 n 不是互質(zhì)關(guān)系。
此時(shí)，由于 n 等于質(zhì)數(shù) p 和 q 的乘積，所以 m 必然等于 kp 或 kq 。
以 m = kp為例，考慮到這時(shí) k 與 q 必然互質(zhì)，則根據(jù)歐拉定理，下面的式子成立：
(kp)q-1?≡ 1 (mod q)
進(jìn)一步得到
[(kp)q-1]h(p-1)?× kp ≡ kp (mod q)
即
(kp)ed?≡ kp (mod q)
將它改寫成下面的等式
(kp)ed?= tq + kp
這時(shí) t 必然能被 p 整除，即 t=t'p
(kp)ed?= t'pq + kp
因?yàn)?m=kp，n=pq，所以
med?≡ m (mod n)
原式得到證明。
