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

現編故事當筆記...

Ａ國想跟Ｂ國秘密交換訊息，於是Ａ國使者Alice跟Ｂ國使者Bob會面商討這事。

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

Bob就說：

「那我們就將來往訊息(message)加密吧。加密的方法是，

　1. 將26個字母不按大小寫，照順序逐一編號，A=1, B=2, C=3,...以此類推。

　2. 承1，訊息(message)＋密碼文(key)＝加密文(ciphertext)，加密文－密碼文＝訊息。

　　比如當訊息是Ａ時，密碼文Ｂ時，1+2=3,Ｃ=3，Ｃ就是加密文。

　　又比如加密文是Ｄ時，密碼文是Ａ，4(D) - 1(A) = 3，Ｃ=3，Ｃ就是訊息。

　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隨便想一字Ｆ(不公開)，即6，5^6(mod 7)，５的６次方，除以７取餘數，等於１，即Ａ。

Bob也隨便想一字Ｃ(不公開)，即3，5^3(mod 7)，等於6，即Ｆ。

Alice寫信跟Bob講，她公式算出來值是Ａ；

同樣地，Bob也跟Alice講，他公式得到的值是Ｆ。公式得到的值被偷看沒差。

因為縱然別人知道，他也不能回推出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 Bob，Alice加密送出； 第二趟 To Alice，Alice加密 + Bob加密，送出； 第三趟 To Bob，Alice解密送出。 剩Bob加密，Bob解密後讀到。
迪菲-赫爾曼密鑰交換(Diffie–Hellman 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加密法，數位簽章

---------------------------------------------------------------------------------------------------------------

圖片來源