RSA公鑰加密算法是1977年由羅納德·李維斯特（Ron Rivest）、阿迪·薩莫爾（Adi Shamir）和倫納德·阿德曼（Leonard Adleman）一起提出的。1987年7月首次在美國(guó)公布，當(dāng)時(shí)他們?nèi)硕荚诼槭±砉W(xué)院工作實(shí)習(xí)。RSA就是他們?nèi)诵帐祥_頭字母拼在一起組成的。

　　RSA是目前最有影響力和最常用的公鑰加密算法，它能夠抵抗到目前為止已知的絕大多數(shù)密碼攻擊，已被ISO推薦為公鑰數(shù)據(jù)加密標(biāo)準(zhǔn)。

　　今天只有短的RSA鑰匙才可能被強(qiáng)力方式解破。到2008年為止，世界上還沒有任何可靠的攻擊RSA算法的方式。只要其鑰匙的長(zhǎng)度足夠長(zhǎng)，用RSA加密的信息實(shí)際上是不能被解破的。但在分布式計(jì)算和量子計(jì)算機(jī)理論日趨成熟的今天，RSA加密安全性受到了挑戰(zhàn)和質(zhì)疑。

　　RSA算法基于一個(gè)十分簡(jiǎn)單的數(shù)論事實(shí)：將兩個(gè)大質(zhì)數(shù)相乘十分容易，但是想要對(duì)其乘積進(jìn)行因式分解卻極其困難，因此可以將乘積公開作為加密密鑰。

　　RSA公開密鑰密碼體制。所謂的公開密鑰密碼體制就是使用不同的加密密鑰與解密密鑰，是一種“由已知加密密鑰推導(dǎo)出解密密鑰在計(jì)算上是不可行的”密碼體制。

　　在公開密鑰密碼體制中，加密密鑰（即公開密鑰）PK是公開信息，而解密密鑰（即秘密密鑰）SK是需要保密的。加密算法E和解密算法D也都是公開的。雖然解密密鑰SK是由公開密鑰PK決定的，但卻不能根據(jù)PK計(jì)算出SK。

　　正是基于這種理論，1978年出現(xiàn)了著名的RSA算法，它通常是先生成一對(duì)RSA 密鑰，其中之一是保密密鑰，由用戶保存；另一個(gè)為公開密鑰，可對(duì)外公開，甚至可在網(wǎng)絡(luò)服務(wù)器中注冊(cè)。為提高保密強(qiáng)度，RSA密鑰至少為500位長(zhǎng)，一般推薦使用1024位。這就使加密的計(jì)算量很大。為減少計(jì)算量，在傳送信息時(shí)，常采用傳統(tǒng)加密方法與公開密鑰加密方法相結(jié)合的方式，即信息采用改進(jìn)的DES或IDEA對(duì)話密鑰加密，然后使用RSA密鑰加密對(duì)話密鑰和信息摘要。對(duì)方收到信息后，用不同的密鑰解密并可核對(duì)信息摘要。

　　RSA算法是第一個(gè)能同時(shí)用于加密和數(shù)字簽名的算法，也易于理解和操作。RSA是被研究得最廣泛的公鑰算法，從提出到現(xiàn)今的三十多年里，經(jīng)歷了各種攻擊的考驗(yàn)，逐漸為人們接受，截止2017年被普遍認(rèn)為是最優(yōu)秀的公鑰方案之一。

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

　　素?cái)?shù)

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

　　互質(zhì)數(shù)

　　百度百科上的解釋是：公因數(shù)只有1的兩個(gè)數(shù)，叫做互質(zhì)數(shù)。；維基百科上的解釋是：互質(zhì)，又稱互素。若N個(gè)整數(shù)的最大公因子是1，則稱這N個(gè)整數(shù)互質(zhì)。

　　常見的互質(zhì)數(shù)判斷方法主要有以下幾種：

　　兩個(gè)不同的質(zhì)數(shù)一定是互質(zhì)數(shù)。例如，2與7、13與19。

　　一個(gè)質(zhì)數(shù)，另一個(gè)不為它的倍數(shù)，這兩個(gè)數(shù)為互質(zhì)數(shù)。例如，3與10、5與 26。

　　相鄰的兩個(gè)自然數(shù)是互質(zhì)數(shù)。如 15與 16。

　　相鄰的兩個(gè)奇數(shù)是互質(zhì)數(shù)。如 49與 51。

　　較大數(shù)是質(zhì)數(shù)的兩個(gè)數(shù)是互質(zhì)數(shù)。如97與88。

　　小數(shù)是質(zhì)數(shù)，大數(shù)不是小數(shù)的倍數(shù)的兩個(gè)數(shù)是互質(zhì)數(shù)。例如 7和 16。

　　2和任何奇數(shù)是互質(zhì)數(shù)。例如2和87。

　　1不是質(zhì)數(shù)也不是合數(shù)，它和任何一個(gè)自然數(shù)在一起都是互質(zhì)數(shù)。如1和9908。

　　輾轉(zhuǎn)相除法。

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

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

　　模運(yùn)算

　　模運(yùn)算即求余運(yùn)算。“模”是“Mod”的音譯。和模運(yùn)算緊密相關(guān)的一個(gè)概念是“同余”。數(shù)學(xué)上，當(dāng)兩個(gè)整數(shù)除以同一個(gè)正整數(shù)，若得相同余數(shù)，則二整數(shù)同余。

　　兩個(gè)整數(shù)a，b，若它們除以正整數(shù)m所得的余數(shù)相等，則稱a，b對(duì)于模m同余，記作： a ≡ b （mod m）；讀作：a同余于b模m，或者，a與b關(guān)于模m同余。例如：26 ≡ 14 （mod 12）。