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

文：馬克・弗雷利（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（這個通量電容器能讓時光旅行成真）。