- 專欄
文章專區
2019-12-01破解公鑰密碼學─ 死胡同變活巷弄
600 期
Author 作者
沈淵源 ／燕巢、路竹、南一、東海、 馬利蘭數學博士；曾任教美國天主教大學助理、副教授，現為東海數學系教授。
傳統密碼信息的安全性，完全掌控在加密鑰匙的秘密性。所以超越傳統的關鍵就在信息的安全性必須獨立於鑰匙的秘密性，且必須打破加密鑰匙與解密鑰匙的對稱性。
尋幽探勝是狄費
在公鑰密碼學上，最關鍵的人物是狄費（Whitfield Diffie）。當年，狄費所思考的問題主要有二，一個是鑰匙的發送問題。未曾謀面的二人想密通信息，必定事先同意使用鑰匙，且別無他人知道。另一個是簽名問題，聰明的你，是否能獻策，提供給純數位信息的接收者，透過某種管道讓他足以向別人證明所收到的信息確實來自某人，如同此人親自在信息中簽上大名一般？
這兩問題看起來就像是不可能的任務。在第一種情況，若未曾謀面的兩個人既然有辦法互通其秘密鑰匙，那為什麼沒有辦法秘密地彼此互通信息呢？而第二種情況也不會更好。為求有效，簽名必須是難以複製。然而，如何在一個可複製的跟原版完全一樣的數位信息當中簽上名呢？
傻勁執著真智慧
鑰匙發送問題，狄費早先論述為「不可能的任務」；但問題是鑰匙發送這個動作，真的無法省下來嗎？ 2000 年來被視為密碼學的公理，一個無需爭議的真理。可是，狄費、黑爾曼（Martin Hellman）和默克（Ralph Merkle）想到一個有趣的小故事，似乎打破此公理。
假設A 送秘密訊息給B，A 把訊息放進鐵盒，蓋起來加 上鎖；再透過郵局寄給B，鑰匙由A 保管；B 收到後當 然無法打開，因為沒有鑰匙。若如法炮製將鑰匙放進另一鐵盒，再透過郵局寄出；但問題依舊，因為沒有另一鐵盒的鑰匙，B 就拿不到第一個鐵盒的鑰匙。要解決這個問題的唯一辦法似乎是：A 約 B 喝咖啡時將鑰匙交給他。如此一來，實際上只是換個腳本重述那老掉牙的問題而已；難怪狄費長久以來把這個問題列為「不可能的任務」，因為問題就出在這把鑰匙的死胡同上。
要解決此死胡同，唯一的方法是轉移焦點，徹底忘掉那把鑰匙。當焦點被轉移時，讀者或許會問：為什麼B 不能擁有自己的鑰匙？所以，解決之道為：B 把收到的鐵盒，不僅不打開，反而加上另一道鎖，再寄回，鑰匙由 B 保管。A 收到寄回的鐵盒，有兩道鎖在上面；用鑰匙 解除自己上的鎖，再寄給B。現在，B 就能毫無困難的打開，因為B 擁有自己鎖上的鑰匙。
由此小故事顯示，鑰匙發送的動作，不見得是無法省略。若以密碼學的角度重述故事，就變成：A 用鎖加密訊息給B，B 用另一道鎖再加密一次，然後送回給A。 A 收到這雙重加密後的訊息時，先解開自己的加密，再送回去給B。B 收到後解開自己的加密，即可閱讀A 原先送的訊息了。
看來，鑰匙發送問題已經解決了，因為雙重加密不需要交換鑰匙。然而，故事歸故事，在實作上，果真如此？在有些情況下次序是重要的，必須遵守「後上，先下」的格言，即鞋襪原理。
鑰匙交換狄黑默
儘管上面的方法無法實際應用在密碼術上，但狄費跟黑爾曼依舊能從其中汲取靈感，尋找可行的方法來規避鑰匙發送問題。他們研究著重在檢驗各類數學函數，並將焦點放在所謂的單向函數（one-way function，〔註一〕）上。所謂單向函數，就像將黃色顏料和藍色顏料調和成綠色顏料、把蛋敲破等無法恢復原狀的原理。
所以，模算術（modular arithmetic）也理所當然成為他們研究的白老鼠。先觀察模11下（mod 11）〔註二〕 2x：在自然數中，2x 隨著x 急速增長；因此從函數值反求 x 值，易如反掌。如函數值65536，讀者可能會猜 x=15，但結果得32768。雖然猜錯但知道x值太小，改成大一點的數，如16，就得到正確答案了。即使猜錯， 還可以得到指引、調整腳步，知道往哪一個方向可以得到正確的答案。……【更多內容請閱讀科學月刊第600期】