RSA取自三個發明者羅納德·李維斯特（Ron Rivest）、阿迪·薩莫爾（Adi Shamir）和倫納德·阿德曼（Leonard Adleman）名字的首字母，1977年提出至今仍被廣泛應用，是一種非對稱加密演算法。

RSA演算法基於的原理，基本上來說，加密和解密資料圍繞著模冪運算，這是取模計算中的一種。取模計算是整數計算中的一種常見形式。x mod n的結果就是x / n的餘數。比如，40 mod 13 = 1，因為40 / 13 = 3，餘數為1。模冪運算就是計算a mod n的過程。

使用RSA演算法對資料進行加密和解密，首先要確定分組的大小。為了實現這一步，必須確保該分組可以儲存的最大數值要小於n的位數。比如，如果p和q都是200位數字的素數，則n的結果將小於400位。因而，所選擇的分組所能儲存的最大值應該要以是接近於400。在實踐中，通常選擇的位數都是比n小的2的整數次冪。比如，如果n是209，要選擇的分組大小就是7位，因為2 = 128比209小，但2 = 256又大於209。

要從緩衝區M中加密第（i）組明文M，使用公鑰(e,n)來獲取M的數值，對其求e次冪，然後再對n取模。這將產生一組密文C。對n的取模操作確保了C將和明文的分組大小保持一致。因而，要加密明文分組有：

C = M mod n

之前提到過，尤拉函式是採用冪模運算來加密資料的基礎，根據尤拉函式及其推導式，能夠將密文解密回原文。

要對緩衝區中C中的第（i）組密文進行解密，使用私鑰(d,n)來獲取C的數值部分，對其求d次冪，然後再對n取模。這將產生一組明文M。因此，要解密密文分組有：

M = C mod n

圖示：採用二進位制平方-乘演算法來計算模冪

一什麼是RSA

RSA是一種密碼體制。RSA加密演算法是一種非對稱加密演算法。在公開金鑰加密和電子商業中RSA被廣泛使用。RSA是目前使用最廣泛的公鑰密碼體制之一。為它是資訊通訊安全的基石，保證了加密資料不會被破解

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

（1）甲方選擇某一種加密規則，對資訊進行加密；

（2）乙方使用同一種規則，對資訊進行解密。

由於加密和解密使用同樣規則（規則就簡稱"金鑰"），這就是"對稱加密"。

這種模式必須解決一個問題：通訊雙方必須同時擁有“金鑰”，也就是說，把資訊加密解決的問題，轉化為金鑰的儲存和傳遞，就成了最頭疼的問題。

1976年，兩位美國計算機學家Whitfield Diffie 和 Martin Hellman，提出了一種全新的思路，解決金鑰的儲存和傳遞問題，這就是著名的"Diffie-Hellman金鑰交換演算法"。這個演算法的原理就是：加密和解密可以使用不同的規則，這要規則間有某種關聯關係，可以推匯出金鑰，就避免了直接傳遞金鑰。這種新的加密模式被稱為"非對稱加密演算法"。

1977年由羅納德·李維斯特（Ron Rivest）、阿迪·薩莫爾（Adi Shamir）和倫納德·阿德曼（Leonard Adleman）一起提出了RSA,"非對稱加密演算法",RSA就是他們三人姓氏開頭字母拼在一起組成的。具有里程碑式的貢獻，開創了密碼學的先河，是的密碼在資訊保安和通訊保密方面做出了巨大的貢獻。

這種演算法非常可靠，金鑰越長，它就越難破解。根據已經披露的文獻，目前被破解的最長RSA金鑰是768個二進位制位。也就是說，長度超過768位的金鑰，還無法破解（至少沒人公開宣佈）。因此可以認為，1024位的RSA金鑰基本安全，2048位的金鑰極其安全。

RSA演算法的安全性基於RSA問題的困難性，也就是基於大整數因子分解的困難性上。但是RSA問題不會比因子分解問題更加困難，也就是說，在沒有解決因子分解問題的情況下可能解決RSA問題，因此RSA演算法並不是完全基於大整數因子分解的困難性上的。

（1）互質

如果兩個正整數，除了1以外，沒有其他公因子，我們就稱這兩個數是互質。

（2）尤拉函式

如果兩個正整數m和n互質，那麼m的φ(n)次方減去1，可以被n整除

（3）費馬小定理

尤拉定理的特殊情況：如果兩個正整數m和n互質，而且n為質數！那麼φ(n)結果就是n-1。

設p，q是兩個素數，n=p*q；

假設整數e滿足1<e<φ（n）,(e, φ（n）)=1;

1、那麼e，φ（n）就滿足了定理（5），所以就存在整數s、d，e*d+s* φ（n）=1；

2、假設存在一個整數a，（a，n）=1；那麼a和q，p也應該互素，即（a，p）=1；（a，q）=1；

既然（a，p）=1；那就滿足了定理（6）；所以a^φ（p）=1 mod p；

等式兩邊同時做φ（q）次冪運算，得到（a^φ（p））^φ（q）=1^φ（q） mod p,

整理得a^(φ（p）*φ（q）)=1 mod p;

套用定理（5），φ（n）=φ（p）*φ（q），所以a^φ（n）=1 mod p;

等式兩邊同時做s次冪運算，得到a^（s*φ（n））=(1^s) modp=1 mod p;

左右在個乘以a，得到a^(1+（s*φ（n））)=a mod p;

這是我們發現1+（s*φ（n））不就是e*d嗎？（套用1、結論）；所以：

a^(e*d)=a mod p;①這是一個重要的結論，同理，q，p在本質上是相同的，所以

a^(e*d)=a mod q;②

算式①和算式②可以利用剩餘定理得出結論a^(e*d)=a mod （p*q）;

剩餘定理是比較複雜的，不過我們可以狹義的理解為這樣的數學題，一個整數，被5除餘1，被7除餘1，那麼這個整數最小是多少呢？答案是36，因為這個整數一定被5*7=35除餘1，所以它是36，71,106……所以最小是36；

那麼a^(e*d)=a mod （p*q）就很好理解了，因為n=p*q;所以a^（e*d）=a mod n;

以密碼通訊中的兩位經典人物 ：Alice和Bob，為例。描述一下非稱加密演算法的流程，假設愛麗絲要與鮑勃進行加密通訊，她該怎麼生成公鑰和私鑰呢？

在此可以看到，非對稱加密是透過兩個金鑰（公鑰-私鑰）來實現對資料的加密和解密的。公鑰用於加密，私鑰用於解密。

現在就來看看RSA演算法是怎麼來對資料進行加密的吧，如下是一幅RSA加密演算法流程及加密過程圖。

　加密過程：

　　A提取訊息m的訊息摘要h（m），並使用自己的私鑰對摘要h（m）進行加密，生成簽名s

　　A將簽名s和訊息m一起，使用B的公鑰進行加密，生成密文c，傳送給B。

　　解密過程：

　　B接收到密文c，使用自己的私鑰解密c得到明文m和數字簽名s

　　B使用A的公鑰解密數字簽名s解密得到H（m）。

　　B使用相同的方法提取訊息m的訊息摘要h（m）

　　B比較兩個訊息摘要。相同則驗證成功;不同則驗證失敗。

　　RSA加密過程簡述

　　A和B進行加密通訊時，B首先要生成一對金鑰。一個是公鑰，給A，B自己持有私鑰。A使用B的公鑰加密要加密傳送的內容，然後B在透過自己的私鑰解密內容。

　　數字簽名的作用是保證資料完整性，機密性和傳送方角色的不可抵賴性

　　假設A要想B傳送訊息，A會先計算出訊息的訊息摘要，然後使用自己的私鑰加密這段摘要加密，最後將加密後的訊息摘要和訊息一起傳送給B，被加密的訊息摘要就是“簽名”。

　　B收到訊息後，也會使用和A相同的方法提取訊息摘要，然後使用A的公鑰解密A傳送的來簽名，並與自己計算出來的訊息摘要進行比較。如果相同則說明訊息是A傳送給B的，同時，A也無法否認自己傳送訊息給B的事實。

　　其中，A用自己的私鑰給訊息摘要加密成為“簽名”；B使用A的公鑰解密簽名檔案的過程，就叫做“驗籤”。

上面就是RSA的原理和全部過程，真正的應用中，不需要理解 如此複雜的 密碼學原理。有很多開源的庫，可以直接使用。

RSA公鑰體制的安全性是基於大數分解（嚴格的說是對兩個大質數的乘積進行分解）這一數學難題的。 儘管RSA是目前使用最為廣泛的公鑰加密演算法，但人們對其安全性的質疑和研究自其誕生之日起就從沒停止過。更令人擔憂的是，RSA中的指數運算保留了輸入的乘積結構。

最近，來自澳洲昆士蘭大學和中國中科大的兩個研究小組獨立的建造出了能夠執行Shor演算法的量子計算機原型。而Shor正是一種能夠高效的進行大數分解運算的計算機！對此，《新科學家》雜誌報道說：出現能夠執行Shor演算法的量子計算機具有極為深遠的意義，這意味著量子計算帶來的最為可怕的威脅即將成為現實——它能夠輕鬆的破解保護我們銀行賬號等的密碼！所以說，道高一尺魔高一丈，破解和反破解是永恆的話題。