RSA公鑰與私鑰運算之演算過程
RSA源起
RSA加密演算法是一種非對稱加密演算法，在現代公開密鑰加密系統中被廣泛使用。RSA是1977年由羅納德·李維斯特（Ron Rivest）、阿迪·薩莫爾（Adi Shamir）和倫納德·阿德曼（Leonard Adleman）一起提出的。當時他們三人都在麻省理工學院工作。RSA就是他們三人姓氏開頭字母拼在一起組成的。對極大整數做因數分解的難度決定了RSA演算法的可靠性。換言之，對一極大整數做因數分解愈困難，RSA演算法愈可靠。以上訊息截錄自WiKi。
RSA同時也是SSL通訊中很重要的一個演算法，沒有了RSA的話，SSL就不可能得以運行。RSA的觀念是每個人都必須有一把公鑰與一把私鑰，公鑰可以放在網路上傳輸（就算被竊取、監聽也無妨）以及被拿去當加密鑰匙，私鑰要自己好好的保存著，如果不見了那一切都完了。這樣的加密、解密方式，被稱為「非對稱加密演算法」。下圖為：Ron Rivest、Adi Shamir、Leonard Adleman三人的照片。
一家專門研究RSA技術的公司RSA Security提出了8個巨大合成數（RSA-640、RSA-704、RSA-768、RSA-896、RSA-1024、RSA-1536、RSA-2048）讓數學家（電腦）作質因數分解，用來驗證RSA在某個時期的安全性，這些合成數為兩個巨量的質數之相乘積，一般的電腦根本無法進行因數分解。在2009年12月12日，編號為RSA-768宣告分解成功，因此這代表下一個威脅RSA-1024的時代來臨。RSA-768因數分解資訊如下：
1230186684530117755130494958384962720772853569595334792197
3224521517264005072636575187452021997864693899564749427740
6384592519255732630345373154826850791702612214291346167042
9214311602221240479274737794080665351419597459856902143413
=
3347807169895689878604416984821269081770479498371376856891
2431388982883793878002287614711652531743087737814467999489
×
3674604366679959042824463379962795263227915816434308764267
6032283815739666511279233373417143396810270092798736308917
歐拉函數
RSA運算的核心起源於歐拉函數，歐拉函數的定義是在數論中，對正整數n，小於或等於n的正整數中與n互質的總個數（互質的定義請參考WiKi 互質）。此函數以其首名研究者歐拉命名，它又稱為φ函數。舉例來說：
φ(8) = 4; 因為1, 3, 5, 7均和8互質。
在歐拉函數中，有一個特別的狀況，就是如果有兩個整數互為質數時，他們相乘後的積如果恰為n值，那麼可以透過過下列的公式快速的算出互質個數。
n = p \* q; //令p與q互質
φ(n) = φ(p\*q) = φ(p)\*φ(q) = (p-1)\*(q-1);
假設我們選定p=11, q=13，並確定p與q互為質數，那麼我們可以套用上面的歐拉函數算出下列的結論。
n = 11 \* 13 = 143;
φ(143) = φ(11\*13) = φ(11)\*φ(13) = (11-1)\*(13-1) = 120;
這裡會出現一個重要的結論，我們可以發現n是120，化成2進制就是「1111000」，那也就是說這一個密鑰的基礎長度就是7 bits，這只是實驗性的參數，真正要運用的話，請使用1024 bits或2048 bits。
另外請挑選出一個「隨機整數」e，並套用到1 < e < φ(n)，並且挑選到的e與φ(n)必須互質。所以我們挑選e=23，23與120為互質沒錯。
模反元素
又稱為同餘式，例如：23 ≡ 2 (mod 3)；這邊純就模反元素應用於RSA演算來討論，也就是：如果有兩個正整數e, n互為「質數」，那麼一定可以找到一個整數d，讓ed被n除的餘數是1，換個方式來說就是ed-1可以被n整除。數學表示式如下：
ed ≡ 1 (mod φ(n))
已經e=23、φ(n)=120，接著我們進行ed ≡ 1 (mod φ(n))的化簡可得到一個二元一次方程式為等價式「eX + φ(n)Y = 1」。二元一次方程式的求解通常需要兩個運算式來代入，但我們可以知道最大公因數的定理：「給予二整數a、b，必存在有整數X、Y使得aX + bY = gcd(a,b)」。因此下面我們將進行擴展式歐幾里得演算法（Extended Euclidean Algorithm）來進行推算。
Extended Euclidean Algorithm Strat
--------------
47X + 30Y = 1 (舉用WiKi - http://goo.gl/WQij6F的例子)
--------------
先利用輾轉相除法運算
--------------
47 = 1 \* 30 + 17
30 = 1 \* 17 + 13
17 = 1 \* 13 + 4
13 = 3 \* 4 + 1
--------------
換算成餘數等式
--------------
47 - 1 \* 30 = 17
30 - 1 \* 17 = 13
17 - 1 \* 13 = 4
13 - 3 \* 4 = 1
--------------
逆運算
--------------
1 \* 13 - 3 \* 4 = 1 (抄上面最後一行)
1 \* 13 - 3 \* (17 - 1 \* 13) = 1 (記住一個觀念，千萬不可以把項式乘開)
1 \* 13 - 3 \* 17 + (3 \* 13) = 1
-3 \* 17 + 4 \* 13 = 1
-3 \* 17 + 4 \* (30 - 1 \* 17) = 1
-3 \* 17 + (4 \* 30) - (4 \* 17) = 1
4 \* 30 - (7 \* 17) = 1
4 \* 30 - 7 \* (47 - 1 \* 30) = 1
4 \* 30 - (7 \* 47) + (7 \* 30) = 1
-7 \* 47 + (11 \* 30) = 1
--------------
結論：X = -7, Y = 11
--------------
--------------
套用在我們假設的7 bits密鑰範例上：
23X + 120Y = 1
--------------
120 = 5 \* 23 + 5
23 = 4 \* 5 + 3
5 = 1 \* 3 + 2
3 = 1 \* 2 + 1
--------------
換算成餘數等式
--------------
120 - 5 \* 23 = 5
23 - 4 \* 5 = 3
5 - 1 \* 3 = 2
3 - 1 \* 2 = 1
--------------
逆運算
--------------
1 \* 3 - 1 \* 2 = 1
1 \* 3 - 1 \* (5 - 1 \* 3) = 1
1 \* 3 - 1 \* 5 + 1 \* 3 = 1
-1 \* 5 + 2 \* 3 = 1
-1 \* 5 + 2 \* (23 - 4 \* 5) = 1
-1 \* 5 + 2 \* 23 - 8 \* 5 = 1
2 \* 23 - 9 \* 5 = 1
2 \* 23 - 9 \* (120 - 5 \* 23) = 1
2 \* 23 - 9 \* 120 + 45 \* 23 = 1
47 \* 23 - 9 \* 120 = 1
--------------
結論：X = 47, Y = -9
--------------
上述例子算出一個整數解為(47, -3)，因此我們得出私鑰就是d=47。
公鑰與私鑰的封裝
在文章中舉的例子，我們可以得到下列參數，這將會是在我們運行RSA時的重要依據。
p = 11 （產生完馬上丟棄）
q = 13 （產生完馬上丟棄）
n = p \* q = 143
φ(n) = 120
e = 23 //encode
d = 27 //decode
公鑰為 (n, e) = (143, 23)
私鑰為 (n, d) = (143, 47)
公鑰與私鑰的驗證
假設A產生出上述的公鑰(143, 23)以及私鑰(143, 47)，透過一般純文字的方式將公鑰送給B，B取得到公鑰後，要將訊息文字"X"透過RSA演算法進行公鑰加密運算「m^e ≡ c (mod n)」。
因為 m^e ≡ c (mod n) //message，而X的ASCII是88（10進制）
88^23 ≡ c (mod 143)
c = 121 //RSA加密後的文字
P.S Windows 7之後的小算盤可以開起工程模式進行計算，千萬不要笨到自己用手去算88的23次方，除非你很無聊，詳見下圖。另外我們也可以在圖中發現與明白，我們用超簡單的兩位數質數產生的運算就有多龐大了，可見RSA演算法消耗的CPU運算是很恐怖的。
A收到由B送過來的資料「121」，取出自己的私鑰(143, 47)，套用RSA的解密公式進行運算「c^d ≡ m (mod n)」。
因為 c^d ≡ m (mod n) //content
121^47 ≡ c (mod 143)
c = 88 //RSA解密後的文字，即為X的ASCII碼88（10進制），故證明之。
寫在最後
除非n=p*q中的這個n，可以利用某種運算被快速的因數分解，例如這個例子中的n是143，否則RSA演算法要被破解的難度非常之高。在寫這篇文章的此刻，全世界並沒有一個有效率的方式可以進行大型質數的因數分解。如果你很有自信的話，請解一下RSA-1024合成數的因數分解吧，別忘了解開是有大獎的喔！一定會上全世界的頭條新聞！！
RSA-1024 =
135066410865995223349603216278805969938881475605667027524485143851526510604859533833940287150571909441798207282164471551373680419703964191743046496589274256239341020864383202110372958725762358509643110564073501508187510676594629205563685529475213500852879416377328533906109750544334999811150056977236890927563