前言

RSA算法是現(xiàn)今使用最廣泛的公鑰密碼算法，也是號(hào)稱地球上最安全的加密算法。本文主要參考了參考資料中的文章，加上自己的理解，算是總結(jié)了。

歷史

對稱加密算法

1976年以前，所有的加密方法都是同一種模式：

（1）甲方選擇某一種加密規(guī)則，對信息進(jìn)行加密；

（2）乙方使用同一種規(guī)則，對信息進(jìn)行解密。

簡單點(diǎn)說：由于加密和解密使用同樣規(guī)則（簡稱"密鑰"）

這種加密模式有一個(gè)最大缺點(diǎn)：甲方必須把加密規(guī)則告訴乙方，否則無法解密。保存和傳遞密鑰，就都成了最頭疼的問題。

非對稱加密算法

1976年，兩位美國計(jì)算機(jī)學(xué)家Whitfield Diffie 和 Martin Hellman，提出了一種嶄新構(gòu)思，可以在不直接傳遞密鑰的情況下，完成解密。

（1）乙方生成兩把密鑰（公鑰和私鑰）。公鑰是公開的，任何人都可以獲得，私鑰則是保密的。
（2）甲方獲取乙方的公鑰，然后用它對信息加密。
（3）乙方得到加密后的信息，用私鑰解密。

如果公鑰加密的信息只有私鑰解得開，那么只要私鑰不泄漏，通信就是安全的。

RSA加密算法簡史

1977年，三位數(shù)學(xué)家Rivest、Shamir 和 Adleman 設(shè)計(jì)了一種算法，可以實(shí)現(xiàn)非對稱加密。這種算法用他們?nèi)齻€(gè)人的名字命名。從那時(shí)直到現(xiàn)在，RSA算法一直是最廣為使用的 非對稱加密算法。

必備數(shù)學(xué)知識(shí)

RSA加密算法中，只用到質(zhì)數(shù)、互質(zhì)數(shù)、指數(shù)運(yùn)算、模運(yùn)算等幾個(gè)簡單的數(shù)學(xué)知識(shí)。所以，我們也需要了解這幾個(gè)概念。

1. 質(zhì)數(shù)

質(zhì)數(shù)又稱素?cái)?shù)，指在一個(gè)大于1的自然數(shù)中，除了1和此整數(shù)自身外，不能被其他自然數(shù)整除的數(shù)。這個(gè)概念，我們在上初中，甚至小學(xué)的時(shí)候都學(xué)過了，這里就不再過多解釋了。

1. 互質(zhì)數(shù)

百度百科上的解釋是：公因數(shù)只有1的兩個(gè)數(shù)，叫做互質(zhì)數(shù)。；維基百科上的解釋是：互質(zhì)，又稱互素。若N個(gè)整數(shù)的最大公因子是1，則稱這N個(gè)整數(shù)互質(zhì)。
常見的互質(zhì)數(shù)判斷方法主要有以下幾種：

1. 兩個(gè)不同的質(zhì)數(shù)一定是互質(zhì)數(shù)。例如，2與7、13與19。
2. 一個(gè)質(zhì)數(shù)，另一個(gè)不為它的倍數(shù)，這兩個(gè)數(shù)為互質(zhì)數(shù)。例如，3與10、5與 26。
3. 相鄰的兩個(gè)自然數(shù)是互質(zhì)數(shù)。如 15與 16。
4. 相鄰的兩個(gè)奇數(shù)是互質(zhì)數(shù)。如 49與 51。
5. 較大數(shù)是質(zhì)數(shù)的兩個(gè)數(shù)是互質(zhì)數(shù)。如97與88。
6. 小數(shù)是質(zhì)數(shù)，大數(shù)不是小數(shù)的倍數(shù)的兩個(gè)數(shù)是互質(zhì)數(shù)。例如 7和 16。
7. 2和任何奇數(shù)是互質(zhì)數(shù)。例如2和87。
8. 1不是質(zhì)數(shù)也不是合數(shù)，它和任何一個(gè)自然數(shù)在一起都是互質(zhì)數(shù)。如1和9908。
9. 輾轉(zhuǎn)相除法。

3.指數(shù)運(yùn)算

指數(shù)運(yùn)算又稱乘方計(jì)算，計(jì)算結(jié)果稱為冪。n^m指將n自乘m次。把n^m看作乘方的結(jié)果，叫做”n的m次冪”或”n的m次方”。其中，n稱為“底數(shù)”，m稱為“指數(shù)”。

4.模運(yùn)算

模運(yùn)算即求余運(yùn)算?！澳！笔恰癕od”的音譯。和模運(yùn)算緊密相關(guān)的一個(gè)概念是“同余”。數(shù)學(xué)上，當(dāng)兩個(gè)整數(shù)除以同一個(gè)正整數(shù)，若得相同余數(shù)，則二整數(shù)同余。
　　兩個(gè)整數(shù)a，b，若它們除以正整數(shù)m所得的余數(shù)相等，則稱a，b對于模m同余，記作: a ≡ b (mod m)；讀作：a同余于b模m，或者，a與b關(guān)于模m同余。例如：26 ≡ 14 (mod 12)。

5.歐拉函數(shù)

任意給定正整數(shù)n，計(jì)算在小于等于n的正整數(shù)之中，有多少個(gè)與n構(gòu)成互質(zhì)關(guān)系？計(jì)算這個(gè)值的方法就叫做歐拉函數(shù)，以φ(n)表示.

例如，在1到8之中，與8形成互質(zhì)關(guān)系的是1、3、5、7，所以φ(n)=4

在RSA算法中，我們需要知道歐拉函數(shù)對以下定理成立

如果n可以分解成兩個(gè)互質(zhì)的整數(shù)之積，即n=p×q，則有：φ(n)=φ(pq)=φ(p)φ(q);

即積的歐拉函數(shù)等于各個(gè)因子的歐拉函數(shù)之積。比如，φ(56)=φ(8×7)=φ(8)×φ(7)=4×6=24。

算法基礎(chǔ)

公鑰與密鑰的產(chǎn)生

假設(shè)Alice想要通過一個(gè)不可靠的媒體接收Bob的一條私人訊息。她可以用以下的方式來產(chǎn)生一個(gè)公鑰和一個(gè)私鑰：

1. 隨意選擇兩個(gè)大的質(zhì)數(shù)p和q，p不等于q，計(jì)算N=pq。
2. 根據(jù)歐拉函數(shù)，求得r = (p-1)(q-1)
3. 選擇一個(gè)小于 r 的整數(shù)* e*，求得 e 關(guān)于模 r 的模反元素，命名為d。（模反元素存在，當(dāng)且僅當(dāng)e與r互質(zhì)）
4. 將* p 和 q 的記錄銷毀。
   (N,e)是公鑰，(N,d)*是私鑰。Alice將她的公鑰(N,e)傳給Bob，而將她的私鑰(N,d)藏起來。

加密消息

假設(shè)Bob想給Alice送一個(gè)消息m，他知道Alice產(chǎn)生的N和e。他使用起先與Alice約好的格式將m轉(zhuǎn)換為一個(gè)小于N的整數(shù)n，比如他可以將每一個(gè)字轉(zhuǎn)換為這個(gè)字的Unicode碼，然后將這些數(shù)字連在一起組成一個(gè)數(shù)字。假如他的信息非常長的話，他可以將這個(gè)信息分為幾段，然后將每一段轉(zhuǎn)換為n。用下面這個(gè)公式他可以將n加密為c：

n^e ≡ c (mod N)

計(jì)算c并不復(fù)雜。Bob算出c后就可以將它傳遞給Alice。

解密消息

Alice得到Bob的消息c后就可以利用她的密鑰d來解碼。她可以用以下這個(gè)公式來將c轉(zhuǎn)換為n：

c^d ≡ n (mod N)

得到n后，她可以將原來的信息m重新復(fù)原。
解碼的原理是：

c^d ≡ n ^e·d(mod N)

以及ed ≡ 1 (mod p-1)和ed ≡ 1 (mod q-1)。由費(fèi)馬小定理可證明（因?yàn)?em>p和q是質(zhì)數(shù)）

n ^e·d ≡ n (mod p) 　和 　n ^e·d ≡ n (mod q)

這說明（因?yàn)?em>p和q是不同的質(zhì)數(shù)，所以p和q互質(zhì)）

n ^e·d ≡ n (mod pq)

RSA加密算法的缺點(diǎn)

雖然RSA加密算法作為目前最優(yōu)秀的公鑰方案之一，在發(fā)表三十多年的時(shí)間里，經(jīng)歷了各種攻擊的考驗(yàn)，逐漸為人們接受。但是，也不是說RSA沒有任何缺點(diǎn)。由于沒有從理論上證明破譯RSA的難度與大數(shù)分解難度的等價(jià)性。所以，RSA的重大缺陷是無法從理論上把握它的保密性能如何。在實(shí)踐上，加密和解密花費(fèi)時(shí)間長、速度慢，只適合對少量數(shù)據(jù)進(jìn)行加密。

參考資料：
1、http://www.ruanyifeng.com/blog/2013/06/rsa_algorithm_part_one.html
2、http://www.ruanyifeng.com/blog/2013/07/rsa_algorithm_part_two.html
3、http://en.wikipedia.org/wiki/RSA_(cryptosystem)
4、http://blog.sciencenet.cn/home.php?mod=space&uid=287179&do=blog&id=391134
5、https://segmentfault.com/a/1190000004461428
6、http://blog.csdn.net/aitangyong/article/details/53861894