2022年7月22日 星期五

札記-工業-現編的密碼學故事※


現編故事當筆記...


A國想跟B國秘密交換訊息,於是A國使者Alice跟B國使者Bob會面商討這事。
一.維吉尼亞密碼(Vigenère cipher)
Bob就說:
「那我們就將來往訊息(message)加密吧。加密的方法是,
 1. 將26個字母不按大小寫,照順序逐一編號,A=1, B=2, C=3,...以此類推。
 2. 承1,訊息(message)+密碼文(key)=加密文(ciphertext),加密文-密碼文=訊息。
  比如當訊息是A時,密碼文B時,1+2=3,C=3,C就是加密文。
  又比如加密文是D時,密碼文是A,4(D) - 1(A) = 3,C=3,C就是訊息。
 3. 我們共用同一密碼文(Key)。加密,解密都用這組。
  
 再舉兩個例子。
 第一個例子,訊息(message)是London,密碼文(key)是abc。
 12,15,14,04,15,14,加密後,12+1,15+2,14+3,04+1,15+2,14+3,加密文(ciphertext)是mqqeqq。
 第二個例子,加密文是uclqgl, 密碼文仍是abc。
 21,03,12,17,07,12,解密後,21-1,03-2,12-3,17-1,07-2,12-3,訊息是taipei」


二.兩重鑰匙
安全顧慮,密碼文每隔一段時間就要更換,
而密碼不能透過訊息傳遞,Alice和Bob就必須見一面。

某天兩人見面時,Alice說:
「我覺得我們應該找個方法,省去"更換密碼文就得見面"的麻煩。」
Alice又說我曾聽過一個故事是這樣的。
 張三把要給李四的信件,裝箱後用自己的鎖a鎖上,寄給李四。
 李四收到後,鎖上自己的鎖b,寄還張三。張三收到後,解開鎖a,再寄給李四。
 李四再收到後,解開鎖b,即能看到張三信件。
 以此概念運作,我們就可以用各自的密碼文(2 keys)傳遞訊息。


三.迪菲-赫爾曼密鑰交換(Diffie–Hellman key exchange)
運作一陣子後,
Bob想:為了簡單加密解密,當初設計的加密文(ciphertext)是可逆的(invertibility)。
可是,一旦敵人拿到密碼文(key),就可以反推訊息。
因此,和Alice商量,在加密的某個環節加入模運算(modular arithmetic, 簡稱mod)。

什麼是模運算呢?簡單說,就是作除法,取餘數。
比如,某一公式是 X * 3 (mod 5),當X= 4時,得出來的結果是 4 * 3 (mod 5) = 12(mod5) = 2,
即便知道 答案是2,也無法反推出X是多少,譬如 X=9時,得出的答案也是2。
然而,讓別人無法竊取(不可逆),同時自己要能解密。
所以,他們引入有模運算的「迪菲-赫爾曼密鑰交換法」。

直接舉例說明數學概念。為了容易解說,假設密碼文(key)只有一個字。
首先,Alice和Bob先談好「獲得密碼(key)的公式」為5 ^X (mod 7),這是可以公開的。
接著,
Alice隨便想一字F(不公開),即6,5^6(mod 7),5的6次方,除以7取餘數,等於1,即A。
Bob也隨便想一字C(不公開),即3,5^3(mod 7),等於6,即F。

Alice寫信跟Bob講,她公式算出來值是A;
同樣地,Bob也跟Alice講,他公式得到的值是F。公式得到的值被偷看沒差。
因為縱然別人知道,他也不能回推出Alice和Bob原先想到的字。
關鍵在後面這計算:「對方公式值^自己的數值(mod 7)」,兩人將得到一致的答案。  
Alice這邊,6^6 (mod 7)= 1; Bob這邊, 1^3(mod 7) = 1。
而這個答案便能拿來當密碼文(key),再以最早的加密法加密。
如此,既能(1)免去見面協調密碼文,又(2)不可逆性。


四,非對稱加密:RSA加密法
一段時日後,Alice想起她從前講過張三、李四的故事。
她就問Bob說:
「降低風險,有沒有辦法讓我們不要用同一把鑰匙(symmetric key)加密、解密?」
Bob就說:
「那就改用RSA加密法了。他是模運算,符合不可逆。
 每個人有兩把鑰匙,通常叫公鑰(public key/certificate),跟私鑰(private key)。
 用公鑰加密的加密文(ciphertext),要用私鑰才能解密;
 而私鑰加密的加密文,可以用公鑰解密。
 依然因為模運算,公鑰可以公開,但私鑰則獨自持有,不可以讓任何人知道。」

Alice就說:
「聽起來不錯,但我有一個問題,把公鑰公開,
 如果別人假裝你(Bob),用我(Alice)的公鑰發訊息給我,我怎麼區別?」

Bob說:
「可利用「私鑰加密的加密文,可以用公鑰解密」的特性。
 我先用我(Bob)的私鑰加密,再用你(Alice)的公鑰加密。
 用你的公鑰加密是保證除了你以外,別人看不到,所以,第一步,用你的私鑰解密。
 第二步,用我(Bob)的公鑰解密,假如解得開,
 不就可以證明訊息是我Bob所發出的(數位簽章Digital Signature)嗎?」

方法

Alice密碼本、Bob密碼本

來往郵件(可能被截取)

維吉尼亞密碼(Vigenère cipher)

兩人共用同一份密碼本

由同一份密碼本加密之加密文(ciphertext)

兩重鑰匙

兩人有各自密碼本

Alice寫機密信件給Bob,得跑三趟。
第一趟 To BobAlice加密送出;

第二趟 To AliceAlice加密 + Bob加密,送出;

第三趟 To BobAlice解密送出。
Bob加密,Bob解密後讀到。

迪菲-赫爾曼密鑰交換(DiffieHellman key exchange)

兩人共用同一份密碼本

Alice寫機密信件給Bob,得跑三趟。
第一趟 To Bob
Alice
送出(1)公式,(2)「公式算出數值」本;

第二趟 To Alice
Bob
得到公式後計算,送出他的「公式算出數值」本。

第三趟 To Bob
Alice
用密碼本加密機密信件(ciphertext)送出給Bob
Bob
用同一密碼本解密。

非對稱加密:RSA加密法

Alice有自己的公鑰、私鑰;
Bob
有自己的公鑰、私鑰。
所以,共4把,而公鑰能公開。

To Alice的信,用Alice公鑰加密,Alice收到,用她私鑰解開;

To Bob的信,用Bob公鑰加密,Bob收到,用他私鑰解開。




---------------------------------------------------------------------------------------------------------------
現編故事當筆記:
1. 維吉尼亞密碼(Vigenère cipher)
2. 兩重鑰匙
3. 模運算,迪菲-赫爾曼密鑰交換(Diffie–Hellman key exchange)
4. 非對稱加密:RSA加密法,數位簽章
---------------------------------------------------------------------------------------------------------------



沒有留言:

張貼留言