iT邦幫忙

第 12 屆 iThome 鐵人賽

DAY 10
0
Security

無趣的密碼學,有趣的加密!系列 第 10

[Day 10] 010 - 非對稱式密碼學 - Asymmetric cryptography (一)(下)

非對稱式密碼學 - RSA

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

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

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

RSA

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

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

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

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

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

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

公鑰與私鑰生成流程

  1. 首先我們選擇兩個質數 q 跟 p,兩者相乘得到 N。
q=13
p=7
N=13*7=91
  1. 根據歐拉歐拉歐拉歐拉歐拉函數,求 r。
    公式為:r = (p-1)*(q-1)
r=(7-1)*(13-1)=72
  1. 接著選擇小於 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

擴展歐幾里得算法

模反元素


上一篇
[Day 9] 009 - 非對稱式密碼學 - Asymmetric cryptography (一)(上)
下一篇
[Day 11] 011 - 非對稱式密碼學 - Asymmetric cryptography (番外)(一)
系列文
無趣的密碼學,有趣的加密!30

尚未有邦友留言

立即登入留言