在密碼學裡,有一種加密法叫做 Hill cipher, 方法如下:
假定我們要加密的文字都是由大寫字母 (A-Z)、小寫字母 (a-z) 及底線 () 共 53 種字元組成。我們先把這些字元這樣編號: 是 0, A 是 1, B 是 2, ..., Z 是 26, a 是 27, ..., z 是 52。如果我們要加密 "National_Problem_Solving_Contest" 這一段文字,我們先設定 block size 為 4,以 4 個字元為一組把原文切成很多個 block:"Nati", "onal", "_Pro", ..., "test"。另外,我們還有一組加密公式:
y1 = ( 3 x1 + 5 x2 + 2 x3 + 0 x4) mod 53
y2 = ( 1 x1 - 7 x2 + 6 x3 + 4 x4) mod 53
y3 = (- 5 x1 - 8 x2 + 0 x3 + 0 x4) mod 53
y4 = (- 1 x1 - 1 x2 - 1 x3 - 1 x4) mod 53
我們不妨把這組加密公式稱做「母體 (Matrix)」,其中 mod 53 代表除以 53 取餘數 (介於 0 到 52 之間),例如 61 mod 53 = 8, 而 -61 mod 53 = 45。
接下來,我們開始對每一個 block 來加密。以 "Nati" 為例,我們先按照上面的字元編號轉成一組數字 (14, 27, 46, 35), 然後把 (x1, x2, x3, x4) = (14, 27, 46, 35) 代入「母體」之中,得到 (y1, y2, y3, y4) = (4, 29, 32, 37),再把這一串數字轉成文字,就變成 "Dcfk"。用這個方法把每一個 block 都加密完成之後,就變成 "DcfkFVEMIyeERygWR_GHbPJCrNcVLRzr"。你也可以改變上面的各項的係數以產生不同的「母體」來加密。不過值得注意的是,不是所有的「母體」都能用來加密,因為有些母體加密出來的文件有可能解不出原來的內容。
當然,整個 Hill cipher 最重要的東西,就是所謂的「母體」了。如果不知道「母體」的內容,你就很難破解出原文來。但是這套加密法有個破綻,就是只要你拿到足夠數量的原文以及加密後的結果,你就可以分析出這個密碼系統的「母體」,進而破解 Hill cipher。身為情報部門幹員的你,偶然間攔截到了敵國的機密文件,以及這份文件加密後的文字,因此你必須寫一個程式來破解這個加密系統,以便當敵國日後再用這套系統加密傳送機密資料時,能夠立即破解出原文。
輸入檔的第一列包含一個數字 T, 代表輸入檔裡面有多少套 Hill cipher 系統等著你破解。在每一套系統裡的第一列是一個數字 n (1 ≤ n ≤ 100),代表 block size。接下來有三個部分:第一個部分是你得到的機密文件內容,第二部份是這個機密文件加密過後的結果,第三部份是你要破解的其他加密過後的資料。每一個部份都是由上述 53 種字元所組成。這三個部份字元數都是 n 的倍數,且不會超過 65536 個字元。一整套系統的格式如下:
針對輸入檔的每一套系統,輸出你破解出來的原文。請你把原文輸出成一列,不要隨便換行。因此你的輸出檔應該會有 T 列。如果因為攔截到的資訊不足,或是資料不正確 (說不定這是敵國故意放出來擾亂的訊息),導致無法分析出唯一一組「母體」,請你輸出 "Unable to crack the Matrix"。
原TIOJ1435 / NPSC2004初賽(prob E)
No. | Testdata Range | Score |
---|---|---|
1 | 0 | 100 |