RSA加密算法是最常用的非對稱加密算法，由羅納德·李維斯特（Ron Rivest）、阿迪·薩莫爾（Adi Shamir）和倫納德·阿德曼（Leonard Adleman）于1977年一起提出，RSA就是他們三人姓氏開頭字母拼在一起組成的。非對稱加密算法的特點就是加密秘鑰和解密秘鑰不同，秘鑰分為公鑰和私鑰，用私鑰加密的明文，隻能用公鑰解密；用公鑰加密的明文，隻能用私鑰解密。
RSA是第一個比較完善的公開密鑰算法，它既能用于加密，也能用于數字簽名。這個算法經受住了多年深入的密碼分析，雖然密碼分析者既不能證明也不能否定RSA的安全性，但這恰恰說明該算法有一定的可信性，目前它已經成為最流行的公開密鑰算法。RSA的安全基于大數分解的難度。其公鑰和私鑰是一對大素數（100到200位十進制數或更大）的函數。從一個公鑰和密文恢複出明文的難度，等價于分解兩個大素數之積（這是公認的數學難題）。
首先複習一下數學上的幾個基本概念，它們在後面的介紹中要用到：
一、 什麼是“素數”？
素數是這樣的整數，它除了能表示為它自己和1的乘積以外，不能表示為任何其它兩個整數的乘積。例如，15＝3＊5，是以15不是素數；又如，12＝6＊2＝4＊3，是以12也不是素數。另一方面，13除了等于13＊1以外，不能表示為其它任何兩個整數的乘積，是以13是一個素數。素數也稱為“質數”。
二、什麼是“互質數”（或“互素數”）？
國小數學教材對互質數是這樣定義的：“公約數隻有1的兩個數，叫做互質數。”這裡所說的“兩個數”是指自然數。
判别方法主要有以下幾種（不限于此）：
（1）兩個質數一定是互質數。例如，2與7、13與19。
（2）一個質數如果不能整除另一個合數，這兩個數為互質數。例如，3與10、5與 26。
（3）1不是質數也不是合數，它和任何一個自然數在一起都是互質數。如1和9908。
（4）相鄰的兩個自然數是互質數。如 15與 16。
（5）相鄰的兩個奇數是互質數。如 49與 51。
（6）大數是質數的兩個數是互質數。如97與88。
（7）小數是質數，大數不是小數的倍數的兩個數是互質數。如 7和 16。
（8）兩個數都是合數（二數差又較大），小數所有的質因數，都不是大數的約數，這兩個數是互質數。如357與715，357=3×7×17，而3、7和17都不是715的約數，這兩個數為互質數。等等。
三、什麼是模指數運算？
指數運算誰都懂，不必說了，先說說模運算。模運算是整數運算，有一個整數m，以n為模做模運算，即m mod n。怎樣做呢？讓m去被n整除，隻取所得的餘數作為結果，就叫做模運算。例如，10 mod 3=1；26 mod 6=2；28 mod 2 =0等等。
模指數運算就是先做指數運算，取其結果再做模運算。如(5^3) mod 7 = (125 mod 7) = 6。
接下來正式講解RSA加密算法。
四、RSA算法描述
RSA的公鑰、私鑰的組成，以及加密過程、解密過程的公式可見于下表：
| 公鑰KU | n：兩素數p和q的乘積（p和q必須保密）（n為模值） e：與(p-1)*(q-1)互質（e稱為公鑰指數） |
| 私鑰KR | n：兩素數p和q的乘積（p和q必須保密）（n為模值） d：滿足(d*e) mod ((p-1)*(q-1)) = 1（d稱為私鑰指數） |
| 加密過程 | C=M^e mod n （C為密文） |
| 解密過程 | M=C^d mod n （M為明文） |
其中，符号^表示數學上的指數運算；mod表示模運算，即相除取餘數。具體算法步驟如下：
（1）選擇一對不同的、足夠大的素數p，q。
（2）計算n=p*q。
（3）計算f(n)=(p-1)*(q-1)，同時對p, q嚴加保密，不讓任何人知道。
（4）找一個與f(n)互質的數e作為公鑰指數，且1<e<f(n)。
（5）計算私鑰指數d，使得d滿足(d*e) mod f(n) = 1
（6）公鑰KU=(e,n)，私鑰KR=(d,n)。
（7）加密時，先将明文變換成0至n-1的一個整數M。若明文較長，可先分割成适當的組，然後再進行交換。設密文為C，則加密過程為：C=M^e mod n。
（8）解密過程為：M=C^d mod n。
五、執行個體描述
本文不對RSA算法的正确性作嚴格的數學證明，我們通過一個簡單的例子來了解RSA的工作原理。為了便于計算。在以下執行個體中隻選取小數值的素數p,q,以及e，假設使用者A需要将明文“key”通過RSA加密後傳遞給使用者B，過程如下：
（1）設計公私密鑰(e,n)和(d,n)。
令p=3，q=11，得出n=p×q=3×11=33；f(n)=(p-1)(q-1)=2×10=20；取e=3，（3與20互質）則e×d mod f(n) = 1，即3×d mod 20 =1。
d怎樣取值呢？可以用試算的辦法來尋找。試算結果見下表：
通過試算我們找到，當d=7時，e×d mod f(n) = 1等式成立。是以，可令d=7。進而我們可以設計出一對公私密鑰，加密密鑰（公鑰）為：KU =(e,n)=(3,33)，解密密鑰（私鑰）為：KR =(d,n)=(7,33)。
（2）英文數字化。
将明文資訊數字化，并将每塊兩個數字分組。假定明文英文字母編碼表為按字母順序排列數值，即：
則得到分組後的key的明文資訊為：11，05，25。
（3）明文加密
使用者加密密鑰(3,33) 将數字化明文分組資訊加密成密文。由C=M^e mod n得：
M1 = C1^e mod n = 11^3 mod 33 = 11
M2 = C2^e mod n = 5^3 mod 33 = 26
M3 = C3^e mod n = 25^3 mod 33 = 16
是以，得到相應的密文資訊為：11，26，16。
（4）密文解密
使用者B收到密文，若将其解密，隻需要計算M=C^d mod n，即：
C1 = M1^d mod n = 11^7 mod 33 = 11
C2 = M2^d mod n = 26^7 mod 33 = 5
C3 = M3^d mod n = 16^7 mod 33 = 25
使用者B得到明文資訊為：11，05，25。根據上面的編碼表将其轉換為英文，我們又得到了恢複後的原文“key”。
當然，實際運用要比這複雜得多，由于RSA算法的公鑰私鑰的長度（模長度）要到1024位甚至2048位才能保證安全，是以，p、q、e的選取、公鑰私鑰的生成，加密解密模指數運算都有一定的計算程式，需要仰仗計算機高速完成。
六、RSA的安全性
首先，我們來探讨為什麼RSA密碼難于破解？
在RSA密碼應用中，公鑰KU是被公開的，即e和n的數值可以被第三方竊聽者得到。破解RSA密碼的問題就是從已知的e和n的數值（n等于pq），想法求出d的數值，這樣就可以得到私鑰來破解密文。從上文中的公式：(d*e) mod ((p-1)*(q-1)) = 1，我們可以看出，密碼破解的實質問題是：從p*q的數值，去求出(p-1)和(q-1)。換句話說，隻要求出p和q的值，我們就能求出d的值而得到私鑰。
當p和q是一個大素數的時候，從它們的積p*q去分解因子p和q，這是一個公認的數學難題。比如當p*q大到1024位時，迄今為止還沒有人能夠利用任何計算工具去完成分解因子的任務。是以，RSA從提出到現在已近二十年，經曆了各種攻擊的考驗，逐漸為人們接受，普遍認為是目前最優秀的公鑰方案之一。
缺點1：雖然RSA的安全性依賴于大數的因子分解，但并沒有從理論上證明破譯RSA的難度與大數分解難度等價。即RSA的重大缺陷是無法從理論上把握它的保密性能如何。
下表列出了對同一安全級别所對應的密鑰長度。
| 保密級别 | 對稱密鑰長度（bit） | RSA密鑰長度（bit） | ECC密鑰長度（bit） | 保密年限 |
| 80 | 80 | 1024 | 160 | 2010 |
| 112 | 112 | 2048 | 224 | 2030 |
| 128 | 128 | 3072 | 256 | 2040 |
| 192 | 192 | 7680 | 384 | 2080 |
| 256 | 256 | 15360 | 512 | 2120 |
缺點2：從上邊可以看出，同樣安全級别的加密算法，RSA需要更長的密鑰。這就使運算速度較慢，較對稱密碼算法慢幾個數量級。且随着大數分解技術的發展，這個長度還在增加，不利于資料格式的标準化。
缺點3：RSA産生密鑰很麻煩，受到素數産生技術的限制，因而難以做到一次一密。
是以，使用RSA隻能加密少量資料，大量的資料加密還要靠對稱密碼算法。實際應用中一般用來加密對稱算法的密鑰，而密文多用對稱加密算法加密傳輸。
七、RSA1024/2048
RSA算法密鑰長度的選擇是安全性和程式性能平衡的結果，密鑰長度越長，安全性越好，加密解密所需時間越長。實際中常使用1024bit秘鑰和2048bit秘鑰，分别稱為RSA1024和RSA2048。秘鑰包含公鑰和私鑰，即公鑰私鑰長度一樣，都是1024bit或2048bit。RSA幾個特性如下：
1.密鑰長度增長一倍，公鑰操作所需時間增加約4倍，私鑰操作所需時間增加約8倍，公私鑰生成時間約增長16倍。
2. 一次能加密的密文長度與密鑰長度成正比， len_in_byte(raw_data) = len_in_bit(key)/8 -11，如1024bit的密鑰，一次能加密的内容長度為 1024/8 -11 = 117 byte。是以非對稱加密一般都用于加密對稱加密算法的密鑰，而不是直接加密内容。
3. 加密後密文的長度為密鑰的長度，如密鑰長度為1024bit(128Byte)，最後生成的密文固定為 1024bit(128Byte)。
關于RSA密鑰長度、明文長度和密文長度請參考：RSA密鑰長度、明文長度和密文長度。
參考文獻：
[1]https://www.cnblogs.com/jiftle/p/7903762.html
[2]https://blog.csdn.net/liwei16611/article/details/83751851
[3]http://blog.sina.com.cn/s/blog_4fcd1ea301012o4q.html