RSA加密演算法

RSA加密演算法是一種 非對稱加密演算法。在公鑰加密標準和電子商業中RSA被廣泛使用。RSA是1977年由（Ron Rivest）、（Adi Shamir）和（Leonard Adleman）一起提出的。當時他們三人都在麻省理工學院工作。RSA就是他們三人姓氏開頭字母拼在一起組成的。

公鑰和私鑰的產生
假設Alice想要通過一個不可靠的媒體接收Bob的一條私人訊息。她可以用下面的方式來產生一個公鑰和一個密鑰：
1.隨意選擇兩個大的質數p和q，p不等於q，計算N=pq。
2.根據 歐拉函數 ,與n互質的整數個數為(p-1)(q-1)
3.選擇一個整數e與(p-1)(q-1)互質,並且e小於(p-1)(q-1)
4.用以下這個公式計算d：d× e ≡ 1 (mod (p-1)(q-1)) 將p和q的記錄銷毀。
5. (N,e)是公鑰，d是私鑰。d是秘密的，而N是公眾都知道的。Alice將她的公鑰傳給Bob，而將她的私鑰藏起來。

加密消息
假設Bob想給Alice送一個消息m，他知道Alice產生的N和e。他使用起先與Alice約好的格式將m轉換為一個小於N的整數n，比如他可以將每一個字轉換為這個字的Unicode碼，然後將這些數字連在一起組成一個數字。假如他的信息非常長的話，他可以將這個信息分為幾段，然後將每一段轉換為n。用下面這個公式他可以將n加密為c：

計算c並不複雜。Bob算出c後就可以將它傳遞給Alice。

解密消息
Alice得到Bob的消息c後就可以利用她的密鑰d來解碼。她可以用下面這個公式來將c轉換為n：

得到n後，她可以將原來的信息m重新複原。
解碼的原理是 ed ≡ 1 (mod p-1)和ed ≡ 1 (mod q-1)。
------------------------------------

以下是網路上的範例

如果你想和別人祕密通訊，那麼你可以先選定兩個非常巨大的質數P1、P2作為私人鑰匙（(private key，解密用的），然後將 P1× P2 的乘積作為加密用的公開鑰匙 (public key)，你可以把公開鑰匙 (public key)公佈在名片上或在網路上。那麼，別人要傳一封密函給你，他必需要先得到你的公開鑰匙 (public key)，按照一個約定的方法將信件加密後送出。你在收到密函後，再用你的私人鑰匙(private key)就可以解出密函原文

張三選p=3，q=11; 此時N=pxq=3x11=33。
張三選出1個與(p-1)x(q-1)=(3-1)(11-1) =2x10=20互質數e=3。
(e,N)=(3,33)即為張三的公開金鑰張三選1個數d=7當作解密金匙,
滿足e．d＝1 mod 20，亦即，7x3＝1 mod 20。

令明文 M=19（e=3, N=33, d=7）
加密:　C=Me mod N=193 mod 33=6859 mod 33=28.
解密:　M=Cd mod N=287 mod 33=19.
例：
(1)RSA加密法的兩個質數若選P=2與Q=7，則N值為何? {公式:N=P×Q}

N=14

(2)e值可為何值(選擇題)?
(a)3 (b)4 (c)5 {公式: e與(P-1)*(Q-1)必須互質}

(3) 將M=4加密後即得密碼文(C值)為何值? {公式:C=Me(mod N)}

C=2

(4) d值可為何值(選擇題)?
(a)5 (b)6 (c)7 {公式:e×d=1(mod (P-1) × (Q-1)) }

(5)用(4)的d值，求(3)的密碼文(C值)所對應的原來資料為何?
{公式:M=Cd(mod N)} M=Cd mod N=25 mod 14=4.
M=4