什么是RSA算法

　　RSA公鑰加密算法是1977年由羅納德·李維斯特（Ron Rivest）、阿迪·薩莫爾（Adi Shamir）和倫納德·阿德曼（Leonard Adleman）一起提出的。1987年7月首次在美國公布，當時他們三人都在麻省理工學院工作實習。RSA就是他們三人姓氏開頭字母拼在一起組成的。

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

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

　　RSA算法基于一個十分簡單的數論事實：將兩個大質數相乘十分容易，但是想要對其乘積進行因式分解卻極其困難，因此可以將乘積公開作為加密密鑰。

　　基本含義

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

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

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

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

　　RSA加密算法原理

　　RSA加密算法中，只用到素數、互質數、指數運算、模運算等幾個簡單的數學知識。所以，我們也需要了解這幾個概念即可。

　　素數

　　素數又稱質數，指在一個大于1的自然數中，除了1和此整數自身外，不能被其他自然數整除的數。這個概念，我們在上初中，甚至小學的時候都學過了，這里就不再過多解釋了。

　　互質數

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

　　常見的互質數判斷方法主要有以下幾種：

　　兩個不同的質數一定是互質數。例如，2與7、13與19。

　　一個質數，另一個不為它的倍數，這兩個數為互質數。例如，3與10、5與 26。

　　相鄰的兩個自然數是互質數。如 15與 16。

　　相鄰的兩個奇數是互質數。如 49與 51。

　　較大數是質數的兩個數是互質數。如97與88。

　　小數是質數，大數不是小數的倍數的兩個數是互質數。例如 7和 16。

　　2和任何奇數是互質數。例如2和87。

　　1不是質數也不是合數，它和任何一個自然數在一起都是互質數。如1和9908。

　　輾轉相除法。

　　指數運算

　　指數運算又稱乘方計算，計算結果稱為冪。nm指將n自乘m次。把nm看作乘方的結果，叫做”n的m次冪”或”n的m次方”。其中，n稱為“底數”，m稱為“指數”。

　　模運算

　　模運算即求余運算。“模”是“Mod”的音譯。和模運算緊密相關的一個概念是“同余”。數學上，當兩個整數除以同一個正整數，若得相同余數，則二整數同余。

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