"我想不到要講什麼。"
---

RSA演算法

演算法的準備步驟有五個，更準確來說是四個。
當 Alice 要傳訊息給 Bob 時，

依據我們前天所講的結論是會使用到 Bob 的公鑰加密，所以首先要先設定公鑰。

設定的步驟如下：

1.選擇兩個大質數，分別是 p和 q。
2. n = p×q
3. (p-1)(q-1)
4. 選擇一個 e ∈{1, 2 , ... , }，使得e 跟 互質。
5.d×e ≡1(mod )

舉個例子來說，

1. p = 11, q = 7
2. n = 11×7 = 77
3. 
4. 挑選1到59中跟60互質的數，我挑e = 17
5. 找到 e ( =17 ) 的乘法反元素 d = 53

公私鑰

算完以上的數字之後，

從上面的例子來說，就是私鑰是53，公鑰是(77, 17)
將公鑰公開，私鑰藏好。
要注意只能公開 n 跟 e。
私鑰是絕對不能被別人知道的數字，也就是公開的數字必須不能推導出私鑰（d）。

來看一下要推導出公鑰 d 需要哪些東西。
看到第五步，d 是 e 的乘法反元素，所以要知道 d 是多少就得知道 e 和模數是多少，
e 跟 n 已經被我們公開了，那就要看光有n 的話能不能把 算出來。

要想算出，看第三步就知道，我們需要 p 跟 q。
而昨天解釋過了，光是知道 n 是很難推得 p 跟 q 的，
所以公鑰的公開並不會威脅到私鑰的隱蔽性。

加解密

RSA 的加解密是做指數運算，所有的運算都要 mod n

我們知道 ，也可以很輕易的推論出
但是跟你說要你推回 x 等於多少的話是困難的。
當然如果你推出來的話，那是因為數字很小很方便計算。
我們要加密的東西絕對不是2這麼簡單的數字。

另外要看到，

看到最後一個等號必須使用尤拉定理*來證明，
不過可以簡單看成是「d 是 e 的乘法反元素」的結論。

*Euler's Theorem : if a ⊥ n, then .

數位簽章

RSA有數位簽章功能，其算法就是將加密演算法倒過來，
用私鑰加密，用公鑰解密。

其中 s 是簽章後的結果，x'則是解密後的解果，
驗章的方式是確認x和x'是否相同，
如果相同就認定是本人所簽署。
因此簽章者必須傳送一份簽章前的文件供收件者驗章。

以上就是 RSA 的介紹，
而實務上 RSA 若要足夠安全，建議使用 2048 或 3072 位元的 n。

圖片來源：
http://www.quickmeme.com/meme/3u5s2c