《密碼的故事》:密鑰與多重字符——什麼是「N元語法分析」?

《密碼的故事》:密鑰與多重字符——什麼是「N元語法分析」?
Photo Credit: Depositphotos

我們想讓你知道的是

書中蒐羅全世界45種最具影響力的密碼,包括凱薩移位密碼、復活島的倫哥倫哥文、二次大戰中德軍著名的Enigma密碼……以圖文並呈的方式讓讀者深入了解密碼製作所包含的技藝與科學。

文:馬克・弗雷利(Mark Frary)

【密鑰與多重字符】

進入西元第二個千年後,過去帝王、宗教領袖與軍事領袖使用的簡單替換式密碼似乎已不再那麼安全,因為解碼者開始知道肯迪的頻率分析法用來破譯機密訊息是多麼有效。也就是說,如果有人還想替訊息加密,他們就得找出方法來遮蓋那些會被簡易解碼術拿來利用的語言學隱微痕跡。新的技術應運而生,人們開始使用多重密文符號來替換單一明文字母,或是在加密過程中把一個字母替換成複數個字母,這下解碼者也就面臨更艱鉅的挑戰。

此外,信息保密發展史上最重大的進展也出現在這個時期,那就是使用密鑰(一個單字或一句短句)來指示密碼的起始點,密碼分析者如果不知道密鑰內容,那解密起來就有如瞎子摸象。再者,如果密鑰是出自明文訊息本身,那這對解碼的人來說也會更加棘手。雖然解碼者的技藝日益精進,但歷史上這段時期還是留下來一些至今無人能破解的訊息、銘文與加密技巧。

N元語法分析

有時候,只使用頻率分析法這門技術並不足以解碼,原因可能是由於密文長度太短,或是不符合該種語言的字母出現頻率分布。這種時候解碼者必須更仔細地研究密文,N元語法分析(n-gram analysis)在這種情況下就可以派上用場。

所謂「N元語法」是指一串長度為N個字母、N個音節或是N個單字的字串。舉例來說,一個「二元語法」長度就是兩個字母或兩個單字。它有可能是兩個字母的結合,比如TH或EE;也有可能是兩個音節結合,比如EN-TION或ATE-LY;還有可能是兩個單字結合,比如AFTER THE或是LESSTHAN。

這有什麼用呢?就像我們分析密文來找出代表E、T、A 的密文字母,我們也能利用預設語言的文獻集獲得一個該種語言的N元語法資料庫,然後分析密文中所有的N元語法來進行比對。下頁圖表就是一個例子,這是康乃爾大學分析一個四萬字資料庫所得的二元語法出現頻率。

據表中所示,英文裡最常見的二元語法是TH,HE,IN 和ER。要注意,這四種二元語法出現頻率高低在不同資料庫裡順序會有所不同。依據西北大學拿撒勒物理學教授威廉˙ 帕卡德(William Packard)的研究結果,英文裡最常出現的三元語法是THE,AND,THA,ENT,ION,TIO,FOR,NDE,HAS,NCE,TUS,OFT 和MEN。另一種有用的方法是找英文中最常見的連字(SS,EE,TT,FF,LL,MM和OO)以及最常見的兩字母或三字母單字。

至於實際應用這些資訊的方法,以下面這句密文為例: BASH SH MAYB QYVGH BSQG BCYNGT FZHHSWTG BAG DTXEOYFYOSBZC。第一步是對個別字母進行頻率分析,顯然出現最多的密文字母是B,然後是G。如果這段訊息的字母頻率分布與英文整體相同,那我們就能假設B代表的是明文中的「e」,而G就是「t」。這個答案有可能,但還不夠。

仔細瞧瞧,密文中出現了一組連字HH,而我們知道英文中最常見的連字是「ss」,所以密文中的H有可能代表明文的「s」。如果真是這樣,那我們就來看密文的頭兩個字BASH SH,依據常理推測,S很可能是「a」或者「i」。

現在再來看密文裡的BAG,這是訊息中唯一的三字母單字,它最有可能是「the」,也就是英文裡最常見的三字母單字。如果真是這樣,那密文第一個字解出來就會是「this」或「thas」;進一步考慮密文字母S可能代表的選項,那頭兩個字如果是「thiSis」看起來就很合理,這樣我們就比較確定密文的S代表明文的「i」。我們把目前推論出來的成果替換進去,得到的是:THISISMHYT QYVESTIQETCYNET FZSSIWTETHEDTXEOYFYOITZC。

密文的Y代表什麼? 如果用英文裡出現頻率很高的「a」來替換,得到的結果是:THISISMHAT QAVESTIQETCANET FZSSIWTETHEDTXEOAFAOITZC。密碼分析者此時要做的可能是找出那些還有未解字母的單字字母排列模式,常玩英文填字遊戲的人都會很熟悉這道步驟。

以最後一個單字為例:OAFAOITZC,英文裡只有一個單字的字母是以這種模式排列,第一個跟第五個字母相同, 那就是「capacitor」。這下子我們獲得更多對照組合,O、F、Z和C分別代表「c」、「p」、「o」和「r」。密文現在已經變成THISISMHAT QAVESTIQETRANET POSSIWTETHEDTXECAPACITOR。繼續如法炮製就會解出「possible」和「travel」兩個字,這樣看來TIQE很可能是「time」,那麼前一個字大概就是「makes」,而MHAT只有可能是「what」。

到這裡我們只剩下DTXE,但這句密文太短,很難推斷這個字是什麼。但如果你喜歡《回到未來》(Back to thEFuture)這部電影,你或許就知道缺的那個字是「flux」,而整個句子也就是:THISISWHAT MAKESTIMETRAVEL POSSIBLETHEFLUX CAPACITOR(這個通量電容器能讓時光旅行成真)。

密碼分析基本上是個抽絲剝繭的過程,各種工具都拿來試一試,看哪個有用。電腦能為某些大工程代勞,像是分析二元語法出現的頻率,但大部分工作還是要靠猜測與除錯。此時也有更井井有條使用N元語法分析的解碼方法,比如用來破解替換式密碼的雅各森「快速」解碼法。之所以說「快速」,是因為此法只需將密文內容分析一次來做出頻率分析直方圖和二元語法出現頻率棋盤格。

雅各森說,我們可以把二元語法頻率棋盤格的縱行或者橫行換來換去,並與標準英文的頻率棋盤格一再比對,直到我們找到「最佳」解答。這種方法用來破解單字符密碼(monoalphabetic cipher)非常有效, 針對字符表數量不多的多字符密碼(polyalphabetic cipher)也能起到很好的作用。


有一種密碼分析技術介於頻率分析與N元語法分析之間,叫做「接觸分析」(contact analysis)。接觸分析要看的不是個別字母的出現頻率,而是某種特定語言裡特定字母出現在另一種字母旁邊的頻率。

以英文為例,「q」後面接著「u」的機率超過百分之九十九,極少數的例外是像「Iraq」(伊拉克)這種單字,且這裡「q」後面接的是空格。我們也知道「v」後面接著「e」的機率超過三分之二,「h」後面也有百分之四十六的機率是接著「e」。網路上可以找到呈現這些機率分布的圖表。

要實地應用這個理論進行密碼分析,我們得先為密文中所有的字符做一個類似表格,一開始橫行縱行會很混亂,但我們要從找出某些比較有可能的排列順序開始,比如「q」後面幾乎一定會接著「u」,「t」後面經常接著「h」,而「k」後面很可能接著「e」。

書籍介紹

本文摘錄自《密碼的故事:人類史上最重要的45種密碼與破解之道》,遠足文化出版

作者:馬克・弗雷利(Mark Frary)
譯者:張毅瑄

  • momo網路書店
  • Readmoo讀墨電子書
  • Pubu電子書城結帳時輸入TNL83,可享全站83折優惠(部分商品除外,如實體、成人及指定優惠商品,不得與其他優惠併用)
  • 透過以上連結購書,《關鍵評論網》將由此獲得分潤收益。

三千七百年前的斐斯托斯圓盤藏著什麼密碼?
經歷四百多年,為何伏尼契手稿始終無解?
齊麥曼電報被破譯,一次大戰因此更早結束?
英國政府通信總部發展什麼系統來讓密碼通訊更安全?

橫跨六千年的古今密碼演進,
加密者與解密者永無停止的追逐,
帶來動人心魄、引人入勝的精采故事

從人類最早學會互通訊息之時,密碼製作的技藝就一直挑戰著、吸引著我們。數千年來,人們使用傳遞加密訊息的方法來達成各種目的,本書讓讀者深入看見密碼學世界中扣人心弦的景象,揭示背後的陰險詭詐與獨創靈感,並清楚呈現亞蘭・圖靈、「巨人」電腦以及更多更多著名解碼者的豐功偉業。

書中蒐羅全世界45種最具影響力的密碼,包括凱薩移位密碼、復活島的倫哥倫哥文、二次大戰中德軍著名的Enigma密碼……以圖文並呈的方式讓讀者深入了解密碼製作所包含的技藝與科學。
全書將這些引人入勝的密碼依照時代排列,讀起來像一本古今益智遊戲史,在解謎的同時也更全面認識這個變幻莫測的祕密世界。

getImage
Photo Credit: 遠足文化出版

責任編輯:翁世航
核稿編輯:潘柏翰


Tags: