文章專區

2019-11-29破解公鑰密碼學─ 死胡同變活巷弄 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期】