非對稱式密碼學 - RSA

那接下來，我將大家看死亡的數學深淵。

接下來我一樣拿一些目前經典的一些加密演算來介紹。

以便大家更理解目前對稱加密的方案。

RSA

RSA 的論文來說，實在過於硬核。

而解我們的重點也不是在『數學』上，所以我們簡單的來說明一些原理。

然後帶入一些公式與驗證法。

接著我們更加深入的去看現實的一些方式。

上一次把公鑰跟私鑰的名詞帶出來了，等等將會用這一些專有名詞。

然後我會一邊舉例一邊解釋，整個流程結束之後，我們再來談『原理』之類的東西。

公鑰與私鑰生成流程

1. 首先我們選擇兩個質數 q 跟 p，兩者相乘得到 N。

q＝13
p＝7
N=13*7=91

2. 根據歐拉歐拉歐拉歐拉歐拉函數，求 r。
   公式為：r = (p-1)*(q-1)

r=(7-1)*(13-1)=72

3. 接著選擇小於 r 的一整數 e，其中 e 跟 r 要互質。
   並求得 e 關於 r 的模反元素，命名為 d。
   公式為：e*d === 1 (mod r)

r=72
e=41(隨機)
d=65(算出來的)

這邊我為了方便，使用的方式是測試迴圈法：

[i for i in range(0,100) if 41*i % 72 == 1 ]

一般會使用『擴展歐幾里得算法』。

1. 把 Q 跟 P 銷毀。

公鑰：(N,e) = (91,41)
私鑰：(N,d) = (91,65)

加密方法

我們簡單的設『訊息為 m』，並且設定將 m 轉換為小於 N 的非負整數 n。
可以使用 UTF-8 或是利用 Base64 等來轉換成數字，再把數字連成一串。
如果訊息過長，是可以分段的，並將每一段都轉會成 n。
加密公式：c === n^e (mod N) （c 為 n 的 e 次方取 N 正餘數。）

n=4(假設)
公鑰(N=91,e=41)

c = 4^41 mod 91 = 23

而這個 c 就是加密過的訊息，將它傳輸出去。

解密方法

得到 c 的訊息後使用公式解密得到 n，然後再依照轉換的約定，轉換回 m。
解密公式：n === c^d (mod N) （n 為 c 的 d 次方取 N 正餘數。）

c = 23
私鑰(N=91,d=65)

n = 23^65 mod 91 = 4

安全性分析

如果知道了N跟e（公鑰）兩個值，還會很難知道d是什麼嗎？

我們能夠知道的訊息為：

1. e是比r還要小的，且跟r互質。
2. N 是由 p*q 算出來的。
3. d 是由 e*d === 1 (mod r) 算出來的。
4. r 是由 (p-1)*(q-1) = p*q - p - q + 1 算出來的。

如果從e跟N要算出d的話，必需要先得知一個條件，N是由哪兩個p跟q組合的。
才可得知e跟d相乘時，取正餘數等於1。

我們拿剛剛的過程來做測試：
公鑰：(N,e) = (91,41)
N 是由 p*q 的因此：

91以下的質數先列出來：
2、3、5、7、11、13、17、19、23、29、31、37、41、43、47、53、59、61、67、71、73、79、83、89
在測試相乘後的結果：
2*3、2*5、2*7...
C24取2 = 276種 結果

能看到 光是91這樣的數字就能做出276種結果。
你說應該要排除相乘後會大於91的數，是的，那這樣會少很多，但你要怎麼得知相乘後一定會小於91，還是必須拿去相乘（除非有特別的算法，但我不知道）。
如果數字更大，組合也會以指數增長。

這一次的數字其實是故意挑的很小很簡單。

而且其實p跟q必需要滿足特定條件才比較安全。

這部份我們留到後面再說（囤積稿量）。

加解密結論

大家應該都想過，這東西其實不難。
能看到生成『私鑰』跟『公鑰』後，其實加密跟解密不難。
利用的是數學的方式來做加解密。

但有幾個問題：

1. 要怎麼讓電腦高數計算次方取模（使用Python的pow）。
2. 怎麼求出 4096 位的質數，並確定它是質數。
3. 必需要使用擴展歐幾里得算法。

然後數學的公式證明跟數學相關資訊就交給其他大神好了。

我將要來帶領大家，解決上述的這些問題。

而證明的部分……我給一些文章，一樣放在最後。

短暫的結束

接下來我想花一個篇章的部分來拖稿（誤。

其實是想用一個篇章的時間來述說一下該如何真的實做出來。

尤其大家能看到的幾個困難的關鍵點。

那為何我會那麼執著地想要分享這部份呢？

其實我當初在上密碼學時，像是 DES、AES、RC5 之類的都能把程式寫出來。

唯獨 RSA 的質數、歐拉、次方沒有辦法。

除了需要數學上的基礎之外，必需要知道特定的演算法。

其實我這系列的文章不是單純的講解。

而是希望大家看完能把程式寫出來。

因此我想要帶大家來看一下如何實踐。

那麼明天見～

挑戰

大家可能覺得很簡單，所以我在這提出兩個挑戰，難度都還好。

我給你們一個簡單的公鑰，大家來嘗試解開。（沒有獎品，但你很棒！）

前提

我的訊息是先做utf-8的編碼後，用Python的int.from_bytes轉換成數字的。

還原的方法也不難：

plain_text_int（解密後的數字）.to_bytes(24, 'big').decode('utf-8')

挑戰一

第一個我給60位的數字，十進制。

公鑰（e） ＝ 65537
N：

641091003610145603533109025014687976828867562079447370195671

加密後的訊息：

570853233165838810998420420545432932805446830251965112262959

挑戰二

第一個我給90位的數字，十進制。

公鑰（e） ＝ 65537
N：

797430661687933668962313440826953900319733538682741945544930443876778191202269142009746307

加密後的訊息：

443177385386698162998877707626099118374364166758652552772143568784016056787680442272972302

參考資料

RSA 加密演算法 wiki

擴展歐幾里得算法

模反元素