iT邦幫忙

2021 iThome 鐵人賽

DAY 14
0
Security

學密碼學也猜不到你的手機密碼系列 第 14

DAY 14- 《公鑰密碼》-RSA(2)

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

RSA演算法

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

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

設定的步驟如下:

1.選擇兩個大質數,分別是 pq
2. n = p×q
3. https://chart.googleapis.com/chart?cht=tx&chl=%5Cphi(n)%3D(p-1)(q-1)
4. 選擇一個 e ∈{1, 2 , ... , https://chart.googleapis.com/chart?cht=tx&chl=phi(n)-1},使得e 跟https://chart.googleapis.com/chart?cht=tx&chl=%5Cphi(n) 互質。
5.d×e ≡1(mod https://chart.googleapis.com/chart?cht=tx&chl=%5Cphi(n))

舉個例子來說,

  1. p = 11, q = 7
  2. n = 11×7 = 77
  3. https://chart.googleapis.com/chart?cht=tx&chl=%5Cphi(35)%20%3D%20(11-1)(7-1)%3D60
  4. 挑選1到59中跟60互質的數,我挑e = 17
  5. 找到 e ( =17 ) 的乘法反元素 d = 53

公私鑰

算完以上的數字之後,

https://chart.googleapis.com/chart?cht=tx&chl=k_%7Bpr%7D%3Dd%2C%5C%20k_%7Bpub%7D%20%3D(n%2C%20e)

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

來看一下要推導出公鑰 d 需要哪些東西。
看到第五步,d 是 e 的乘法反元素,所以要知道 d 是多少就得知道 e 和模數https://chart.googleapis.com/chart?cht=tx&chl=%5Cphi(n)是多少,
e 跟 n 已經被我們公開了,那就要看光有n 的話能不能把 https://chart.googleapis.com/chart?cht=tx&chl=%5Cphi(n) 算出來。

要想算出https://chart.googleapis.com/chart?cht=tx&chl=%5Cphi(n),看第三步就知道,我們需要 p 跟 q。
而昨天解釋過了,光是知道 n 是很難推得 p 跟 q 的,
所以公鑰的公開並不會威脅到私鑰的隱蔽性。

加解密

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

https://chart.googleapis.com/chart?cht=tx&chl=y%20%3D%20x%5Ee%20%20mod%20n
https://chart.googleapis.com/chart?cht=tx&chl=x%20%3D%20y%5Ed%20mod%20n

我們知道https://chart.googleapis.com/chart?cht=tx&chl=2%5E5%3D32 ,也可以很輕易的推論出https://chart.googleapis.com/chart?cht=tx&chl=2%5E5%3D2%5C%20(mod%5C%205)
但是跟你說https://chart.googleapis.com/chart?cht=tx&chl=2%5Ex%3D2%5C%20(mod%5C%205)要你推回 x 等於多少的話是困難的。
當然如果你推出來的話,那是因為數字很小很方便計算。
我們要加密的東西絕對不是2這麼簡單的數字。

另外要看到,
https://chart.googleapis.com/chart?cht=tx&chl=x%20%3Dy%5Ed%20%3D(x%5Ee)%5Ed%3Dx%5E%7Bed%7D%3Dx(mod%5C%20n)
看到最後一個等號必須使用尤拉定理*來證明,
不過可以簡單看成是「d 是 e 的乘法反元素」的結論。

*Euler's Theorem : if a ⊥ n, then https://chart.googleapis.com/chart?cht=tx&chl=a%5E%7B%5Cphi(n)%7D%3D1(mod%5C%20n).

數位簽章

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

https://chart.googleapis.com/chart?cht=tx&chl=s%20%3D%20x%5Ed%20mod%20n
https://chart.googleapis.com/chart?cht=tx&chl=x'%20%3D%20s%5Ee%20mod%20n

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


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

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


上一篇
DAY 13- 《公鑰密碼》-RSA(1)
下一篇
DAY 15- 《公鑰密碼》-ECC
系列文
學密碼學也猜不到你的手機密碼30

尚未有邦友留言

立即登入留言