RSA

RSA密碼演算法扼要描述如下：

RSA可以讓使用者在公開的網路來進行安全私密的加解密演算法(非對稱式，公鑰、私鑰對，用其中一把進行加密的密文，可以成對的另一把解密，還原出明文)。

其加解密演算法是：

取兩個(大)質數p、q，算得其乘積N，

再取一介於 1 ~ (p－1)x(q－1) 之間，且與 (p－1)x(q－1) 互質的數為e。

將 N、e 公告發佈成為公鑰；任何人都可以在網路上查到並取得用以加解密。

然而，構成N的p、q則是秘密，且（p－1）和（q－1）的值，當然也是無從得知的祕密，除非分解出N的大質因數p和q。

RSA的安全因此是基於：大質因數的分解(Wiki:對極大整數做因數分解的難度決定了RSA演算法的可靠性。)。

私鑰的算法：

1.根據歐拉函數，求得 $r=\varphi (N) = \varphi (p)\varphi (q)=(p-1)(q-1)$

2.取一小於 $r$ 的整數 $e$ ，使 $e$ 與 $r$ 互質。並求得 $e$ 關於 $r$ 的模反元素，為 $d$

【範例】

取p=61、q=53 (實務上需取用越大的質數越安全，RSA相對越不易破解)

則N=61 x 53=3233

$varphi (n)$ 為歐拉函數（小於等於 $n$ 且與 $n$ 互質的正整數個數），
歐拉函數的值 $r$ = $varphi (n)$ = 𝜑(pq)=φ(p)φ(q)=(p−1)(q−1)

因此 $r$ =φ(3233)=(61-1)(53-1)=3120

在1~3120之間，取一整數 $e$ ，並與3120互質；假設取 $e$ =17。故，公鑰為(N, e)=(3233, 17)

然後，計算模反元素得d=2753 (模反元素modular multiplicative inverse，詳附註)。故，私鑰為(N, d)=(3233, 2753)

【加解密】

假設明文m=65

【加密】c=m^emod(N)=65¹⁷mod(3233)=2790

【解密】m=c^dmod(N)=2790²⁷⁵³mod(3233)=65

RSA運算中只要P、Q之值夠大，便足抵擋暴力破解法攻擊。

【應用場景】客戶先把委託銀行處理的文件（例如要求匯出一筆款項）數位化之後，得到一個小於p、q的數目m，m稱為明文。

然後將m^e除以N之後的餘數c(即：取模數得c)傳給銀行，c稱為密文。

從m得到c的過程稱為加密，截密者可以截到c，但是無法知道m。

銀行本身則保留一個密鑰d，滿足e^d除以（p－1）（q－1）的餘數是1。

在接到客戶送來的密文r之後，銀行計算r^d，然後再除以N，餘數就是客戶原始的明文m。

整個保密的關鍵在於截密者不知道p和q，如果知道，就可以據以算出（p－1）（q－1），並且透過e來算d。因此p和q必須是一個「至少數百位的大質數」，讓截密者永遠無法將N分解為p、q的乘積。

【附註】from Wiki

模反元素也稱為模倒數，或者模反元素。

一整數a對同餘n之模反元素是指滿足以下公式的整數 b

{displaystyle a^{-1}equiv b{pmod {n}}.}

{displaystyle abequiv 1{pmod {n}}.}

整數 a 對模數 n 之模反元素存在的充分必要條件是 a 和 n 互質。
若模反元素存在，在模數 n 下的除法可以用和對應模反元素的乘法來達成；此概念和實數除法的概念相同。

用歐拉定理

歐拉定理證明當 ${displaystyle a,n}$ 為兩個互質的正整數時，則有 ${displaystyle a^{varphi (n)}equiv 1{pmod {n}}}$ ，其中 ${displaystyle varphi (n)}$ 為歐拉函數（小於等於 ${displaystyle n}$ 且與 ${displaystyle n}$ 互質的正整數個數）。

上述結果可分解為 ${displaystyle a^{varphi (n)}=acdot a^{varphi (n)-1}equiv 1{pmod {n}}}$ ，其中 ${displaystyle a^{varphi (n)-1}}$ 即為 ${displaystyle a}$ 關於模 ${displaystyle n}$ 之模反元素。