56 數 學 傳 播 30 卷 2 期 民 95 年 6 月 因 為 在 模 26 之 下 3 是 9 的 乘 法 反 元 素, 所 以 將 用 3 來 取 代, 乘 開 並 在 模 26 之 下 縮 簡 得 M = M 1 = 在 Mathema

數 學 傳 播 30 卷 2 期, pp. 55-76 八. 希 爾 密 碼 (Hill Ciphers) 傳 統 密 碼 之 旅 ( 下 ) 沈 淵 源 上 面 介 紹 過 的 每 一 個 密 碼 系 統 中, 改 變 明 文 中 的 一 個 字 母, 在 密 文 中 也 有 一 個 字 母 隨 著 改 變 在 位 移 仿 射 與 代 換 ( 下 一 節 ) 密 碼 系 統 中, 密 文 中 的 一 個 字 母 來 自 明 文 中 唯 一 的 一 個 字 母 如 此 一 來, 頻 率 分 析 法 在 這 些 系 統 中 尋 找 鑰 匙 時 就 無 往 不 利 了 在 維 吉 內 爾 密 碼 中, 由 於 使 用 了 與 鑰 匙 等 長 的 字 母 區 塊, 以 致 直 接 頻 率 分 析 困 難 重 重 ; 然 而 一 旦 算 出 鑰 匙 長 度 之 後, 再 分 頭 用 頻 率 分 析 予 以 各 個 擊 破, 仍 有 機 會 破 解, 此 乃 因 為 在 每 一 個 字 母 區 塊 當 中 的 字 母 彼 此 之 間 並 沒 有 任 何 的 互 動 雷 斯 特. 希 爾 (Lester Hill) 在 1929 年 所 發 明 的 密 碼 法 [4] 當 中, 巧 妙 的 運 用 了 線 性 代 數 的 技 巧 讓 字 母 彼 此 之 間 開 始 互 動 起 來, 藉 以 增 加 系 統 的 安 全 等 級, 因 而 得 到 更 好 更 實 用 的 一 個 密 碼 系 統 如, 令 首 先, 我 們 選 取 一 個 正 整 數 n, 如 n = 3 鑰 匙 是 一 個 在 模 26 之 下 的 n 階 方 陣 M 例 1 2 3 M = 4 5 6 0 7 11 信 息 可 寫 成 一 長 度 為 n 的 列 向 量 序 列 如 信 息 為 abc, 先 轉 換 成 列 向 量 (0, 1, 2) 怎 麼 加 密 呢? 只 要 在 列 向 量 (0, 1, 2) 的 右 邊 乘 上 方 陣 M 並 在 模 26 之 下 縮 簡 即 可, 如 下 : 1 2 3 (0, 1, 2)M = (0, 1, 2) 4 5 6 (4, 19, 2) (mod 26), 0 7 11 所 以 得 到 密 文 就 是 ETC In[52]:= M={{1,2,3},{4,5,6},{0,7,11}};Mod[{0,1,2}.M,26] Out[52]= {4,19,2} 方 陣 就 是 為 了 解 密, 我 們 需 要 M 的 行 列 式 值 與 26 互 質 在 上 例 中, det(m) = 9, 所 以 M 的 逆 1 9 13 1 3 44 11 6 28 7 3 55

56 數 學 傳 播 30 卷 2 期 民 95 年 6 月 因 為 在 模 26 之 下 3 是 9 的 乘 法 反 元 素, 所 以 將 用 3 來 取 代, 乘 開 並 在 模 26 之 下 縮 簡 得 9 13 23 17 M = M 1 = 24 7 18 6 5 17 在 Mathematica 中, 上 面 兩 個 步 驟 可 合 併 如 下 ; 但 需 注 意 必 須 使 用 指 令 PolynomialMod 才 行 得 通 In[53]:= M =PolynomialMod[Inverse[M],26] 1 Out[53]= {{13,23,17},{24,7,18},{6,5,17}} 解 密 時, 可 在 密 文 的 右 邊 乘 上 M 的 逆 方 陣, 也 就 是 它 的 乘 法 反 元 素 M = M 1, 並 在 模 26 之 下 縮 簡 即 可, 如 下 : 13 23 17 (4, 19, 2)M = (4, 19, 2) 24 7 18 (0, 1, 2) (mod 26) 6 5 17 In[54]:= Mod[{4,19,2}.M,26] Out[54]= {0,1,2} 一 般 而 言, 將 明 文 分 割 成 含 n 個 字 的 區 塊 並 用 a = 0, b = 1,, z = 25 轉 換 成 長 度 為 n 的 列 向 量 如 上 例 的 方 陣 M, 假 設 我 們 的 明 文 ma 是 hihappybirthdaytoyou 在 此 信 息 附 加 一 個 x 使 得 長 度 變 成 n = 3 的 倍 數, 以 符 號 mx 表 示 之 所 以 區 塊 變 成 列 向 量, 而 信 息 mx 則 變 成 一 個 n k 的 矩 陣 加 密 時, 在 明 文 矩 陣 m 右 方 乘 加 密 矩 陣 M, 可 得 密 文 矩 陣 c 如 下 : In[55]:= abc="abcdefghijklmnopqrstuvwxyz"; num="0001020304050607080910111213141516171819202122232425"; digitalize=table[stringtake[abc,{i}]->stringtake[num,{2*i-1,2*i}],{i,1,26}]; alphabetize=table[stringtake[num,{2*i-1,2*i}]->stringtake[abc,{i}],{i,1,26}]; Q0[plaintext_]:=StringReplace[plaintext,digitalize]; A[digit_]:=StringReplace[digit,alphabetize]; In[60]:= ma="hihappybirthdaytoyou"; mx=ma<>"x"; m0=table[stringtake[q0[mx],{i,i+1}],{i,1,2stringlength[mx],2}]//toexpression; m=table[{m0[[i]],m0[[i+1]],m0[[i+2]]},{i,1,stringlength[mx],3}] Out[60]= hihappybirthdaytoyoux Out[62]= {{7,8,7}, {0,15,15}, {24,1,8}, {17,19,7},{3,0,24},{19,14,24},{14,20,23}}hihappybirthdaytoyoux In[63]:= c=mod[m.m,26] Out[63]= {{13,25,16},{8,24,21},{2,5,10},{15,22,8},{3,18,13},{23,16,15},{16,3,25}} 最 後, 將 每 一 列 向 量 轉 換 回 到 字 母 區 塊, 再 將 區 塊 合 併 之 可 得 密 文 NZQIYVCFKPWIDSNNQPQDZ

傳 統 密 碼 之 旅 ( 下 ) 57 In[64]:= cf=flatten[c]; cs=table[if[cf[[i]]<10,"0"<>tostring[cf[[i]]],tostring[cf[[i]]]],{i,stringlength[mx]}] Out[64]= {13,25,16,08,24,21,02,05,10,15,22,08,03,18,13,23,16,15,16,03,25} In[65]:= ca=a[cs]//stringjoin//touppercase Out[65]= NZQIYVCFKPWIDSNXQPQDZ 解 密 時, 先 逆 向 轉 換 成 密 文 矩 陣 c, 然 後 在 c 右 邊 乘 以 M = M 1 (mod 26), 如 此 得 回 明 文 矩 陣 m, 最 後 再 轉 換 為 原 信 息 In[66]:= cl=tolowercase[ca]; cm=table[stringtake[cl,{i}],{i,stringlength[cl]}]; d=q0[cm]//toexpression; Table[{d[[i]],d[[i+1]],d[[i+2]]},{i,1,StringLength[cl],3}] Out[67]= {{13,25,16},{8,24,21},{2,5,10},{15,22,8},{3,18,13},{23,16,15},{16,3,25}} In[68]:= %==c Out[68]= True In[69]:= mf=mod[c.m,26]//flatten; ms=table[if[mf[[i]]<10,"0"<>tostring[mf[[i]]],tostring[mf[[i]]]],{i,stringlength[cl]}]//a//stringjoin Out[70]= hihappybirthdaytoyoux In[71]:= StringDrop[ms,-1]==ma Out[71]= True 很 顯 然 的, 變 更 明 文 中 的 一 個 字 母, 通 常 會 導 致 密 文 中 n 個 字 母 的 改 變 例 如, 若 將 block = (1, 11, 14,...) 改 成 clock = (2, 11, 14,...), 則 密 文 中 前 三 個 字 母 由 TZP 變 為 UBS 1 2 3 blo = (1, 11, 14) (1, 11, 14) 4 5 6 = (19, 25, 15) = TZP 0 7 11 1 2 3 clo = (2, 11, 14) (2, 11, 14) 4 5 6 = (20, 1, 18) = UBS 0 7 11 這 使 得 頻 率 分 析 的 效 率 降 低 許 多 雖 然 如 此, 對 小 的 n 值 而 言, 用 頻 率 分 析 來 破 解 並 非 不 可 能 二 字 串 及 三 字 串 已 經 有 人 計 算 而 且 統 計 出 來 其 出 現 之 頻 率 三 字 串 以 上 則 因 其 可 能 數 目 變 得 太 大 了, 且 若 沒 有 提 供 大 量 的 密 文, 各 種 字 串 的 數 目 會 低 到 很 難 從 其 中 獲 取 有 意 義 的 資 訊 如 此 一 來, 頻 率 分 析 更 是 英 雄 無 用 武 之 地 下 面 我 們 一 起 來 思 考 那 四 種 攻 擊 法 如 何 進 行 1. 密 文 攻 擊 法 : 用 密 文 攻 擊 法 要 破 解 希 爾 密 碼 是 困 難 的, 但 希 爾 密 碼 卻 俯 首 稱 臣 於 其 他 幾 個 攻 擊 法 之 下 2. 已 知 明 文 攻 擊 法 : 如 果 我 們 不 知 道 n, 那 麼 就 試 幾 個 不 同 的 n 值, 直 等 到 找 到 正 確 的 為 止 所 以 假 設 n 為 已 知 如 果 我 們 有 n 個 長 度 為 n 的 明 文 區 塊, 則 我 們 可 使 用 明 文 及 其 對 應 的 密 文 得 到 一 個 關 於 M ( 或 是 它 的 乘 法 反 元 素, 這 可 能 還 更 有 用 ) 的 矩 陣 方 程 式 例 如, 假 設 我 們 現 在 已 經 知 道 n = 2 而 且 我 們 有 明 文 howareyoutoday = 7 14 22 0 17 4 24 14 20 19 14 3 0 24

58 數 學 傳 播 30 卷 2 期 民 95 年 6 月 其 對 應 的 密 文 為 ZWSENIUSPLJVEU = 25 22 18 4 13 8 20 18 15 11 9 21 4 20 前 兩 個 區 塊 得 到 矩 陣 方 程 式 ( )( ) ( ) 7 14 a b 25 22 22 0 c d 18 4 (mod 26) ( ) 7 14 可 惜 矩 陣 的 行 列 式 值 為 308, 此 數 在 模 26 之 下 沒 有 乘 法 反 元 素 ( 雖 然 這 個 22 0 矩 陣 可 用 來 大 大 的 縮 減 可 能 的 加 密 矩 陣 之 數 目 ) 因 此 我 們 將 方 程 式 最 後 一 列 取 代 為, 譬 如 說, 第 五 區 塊 而 得 到 ( )( ) ( ) 7 14 a b 25 22 20 19 c d 15 11 ( ) 7 14 這 一 次, 矩 陣 在 模 26 之 下 是 可 逆 的 : 20 19 ( ) 1 ( ) 7 14 5 10 20 19 18 21 In[72]:= PolynomialMod[Inverse[{{7,14},{20,19}}],26] Out[72]= {{5,10},{18,21}} (mod 26) (mod 26) 我 們 得 到 ( ) ( ) ( ) 5 10 25 22 15 12 M 18 21 15 11 11 3 (mod 26) In[73]:= Mod[{{5,10},{18,21}}.{{25,22},{15,11}},26] Out[73]= {{15,12},{11,3}} 因 希 爾 密 碼 難 於 防 守 此 種 攻 擊, 所 以 就 不 能 看 成 是 非 常 強 的 密 碼 3. 選 擇 明 文 攻 擊 法 : 選 擇 明 文 攻 擊 法 可 採 取 相 同 的 策 略 來 進 行, 不 過 會 快 一 些 再 一 次 地, 如 果 你 不 知 道 n, 試 幾 個 不 同 的 n 值, 直 到 行 的 通 為 止 所 以 假 設 n 為 已 知 選 擇 明 文 的 第 一 區 塊 為 baaa = 1000, 第 二 區 塊 為 abaa = 0100, 如 此 繼 續 至 第 n 區 塊 為 aaab = 0001 密 文 區 塊 就 是 加 密 矩 陣 M 的 列 向 量 4. 選 擇 密 文 攻 擊 法 : 至 於 選 擇 密 文 攻 擊 法, 則 採 用 跟 選 擇 明 文 攻 擊 法 完 全 一 樣 的 策 略 來 進 行, 但 明 文 與 密 文 的 角 色 對 調 如 此 所 得 到 的 明 文 區 塊 將 會 是 加 密 矩 陣 M 之 反 元 素 ( 即 解 密 矩 陣 ) 的 列 向 量

傳 統 密 碼 之 旅 ( 下 ) 59 九. 代 換 密 碼 (Substitution Ciphers) 代 換 密 碼 是 更 大 眾 化 的 密 碼 系 統 之 一 常 見 於 週 末 報 紙 的 謎 題 專 欄 其 原 理 甚 簡 單 : 將 每 一 個 字 母 用 另 一 個 ( 可 能 會 同 一 個 ) 字 母 來 取 代, 但 不 重 複 更 明 確 的 說, 選 取 26 個 英 文 字 母 的 一 個 排 列 然 後 施 之 於 明 文 即 得 密 文 字 與 字 中 間 的 空 白 在 謎 題 專 欄 中 通 常 被 保 留, 這 對 解 謎 題 者 當 然 是 一 大 助 益 ; 因 為 字 的 結 構 是 猜 測 的 一 大 提 示 ( 電 腦 習 題 第 三 題 是 很 好 的 一 個 例 子 ) 所 以, 為 了 增 加 安 全 性, 將 這 些 空 白 省 略 會 比 較 好 位 移 密 碼 與 仿 射 密 碼 都 是 代 換 密 碼 的 簡 單 例 子 維 吉 內 爾 密 碼 與 希 爾 密 碼 則 不 是, 因 為 他 們 是 將 一 個 區 塊 的 字 母 排 列 成 另 一 個 區 塊 的 字 母 而 非 一 次 一 個 字 母 眾 所 周 知, 代 換 密 碼 可 由 頻 率 分 析 來 破 解 然 其 過 程 遠 比 我 們 所 想 像 的 還 複 雜 許 多 從 下 面 的 例 子 即 可 窺 見 一 二 林 9 湯 姆 士. 傑 弗 遜 8 (Thomas Jefferson) 有 一 潛 在 性 叛 逆 的 信 息 要 傳 遞 給 班 傑 明. 富 蘭 克 (Benjamin Franklin) 很 明 顯 地, 他 不 要 英 國 人 截 取 此 信 息 並 知 悉 其 內 容, 所 以 他 就 用 代 換 密 碼 器 將 此 信 息 加 密 還 好, 富 蘭 克 林 知 道 所 用 的 排 列, 所 以 他 僅 需 逆 向 推 導 回 去 即 可 得 到 原 信 息 ( 當 然, 班 傑 明 是 相 當 聰 明 的, 所 以 可 能 他 不 用 事 先 知 道 鑰 匙 就 已 經 將 信 息 解 密 了 ) 現 在 假 設 我 們 在 1776 年 時 任 職 於 英 格 蘭 的 政 府 代 碼 與 密 碼 學 校 而 且 上 級 交 辦 下 來 破 解 此 一 截 取 到 的 信 息 In[74]:= lwn="lwnsozbnwvwbaybnvbsqwvwohwdizwrbbnpbpoouwrpawxawpbwzwmypobnpbbnwjpawwrzslwzqjbnwiaxawpbsalibnxwa\ BPIRYRPOIWRPQOWAIENBVBNPBPUSREBNWVWPAWOIHWOIQWABJPRZBNWFYAVYIBSHNPFFIRWVVBNPBBSVWXYAWBNWVWAIENBV\ ESDWARUWRBVPAWIRVBIBYBWZPUSREUWRZWAIDIREBNWIATYVBFSLWAVHASUBNWXSRVWRBSHBNWESDWARWZBNPBLNWRWDWAPR\ JHSAUSHESDWARUWRBQWXSUWVZWVBAYXBIDWSHBNWVWWRZVIBIVBNWAIENBSHBNWFWSFOWBSPOBWASABSPQSOIVNIBPRZBSIR\ VBIBYBWRWLESDWARUWRBOPJIREIBVHSYRZPBISRSRVYXNFAIRXIFOWVPRZSAEPRIKIREIBVFSLWAVIRVYXNHSAUPVBSVWWUU\ SVBOICWOJBSWHHWXBBNWIAVPHWBJPRZNPFFIRWVV"; 數 算 各 字 母 出 現 的 次 數 如 下 ( 總 共 520 個 字 ): W B R S I V A P N O 76 64 39 36 36 35 34 32 30 16 In[75]:= cap="abcdefghijklmnopqrstuvwxyz"; frequency[txt_]:= Array[Function[i,{Count[Characters[txt],Characters[cap][[i]]],Characters[cap][[i]]}],26]; StringLength[lwn] frequency[lwn]//sort Out[77]= 520 Out[78]= {{0,G},{1,C},{1,K},{1,M},{1,T},{6,Q},{7,J},{7,L},{8,D},{11,F},{11,X},{13,E},{13,U},{13,Y},{14,H}, {15,Z},{16,O},{30,N},{32,P},{34,A},{35,V},{36,I},{36,S},{39,R},{64,B},{76,W}} 英 文 字 母 的 頻 率 在 上 一 章 已 介 紹 過, 我 們 再 次 把 最 常 出 現 的 九 個 列 在 此 : 8 傑 弗 遜 (1743-1826) 美 國 政 治 家 1801 年 被 選 為 第 三 任 總 統, 1804 年 連 任 曾 起 草 獨 立 宣 言, 主 張 民 權 自 由, 尊 重 各 州 自 治, 禁 止 奴 隸 買 賣 總 統 卸 任 後, 致 力 於 教 育 工 作, 並 創 立 維 吉 尼 亞 大 學 9 富 蘭 克 林 (1706-1790) 美 國 科 學 家 發 明 家 政 治 家 出 版 家 哲 學 家 音 樂 家 及 經 濟 學 家 他 設 立 了 北 美 第 一 個 公 共 圖 書 館, 創 辦 賓 夕 凡 尼 亞 大 學 五 十 歲 以 後, 致 力 於 獨 立 活 動, 在 獨 立 戰 爭 中, 曾 當 選 為 第 二 屆 大 陸 會 議 代 表, 參 與 起 草 獨 立 宣 言

60 數 學 傳 播 30 卷 2 期 民 95 年 6 月 英 文 字 母 最 常 出 現 的 前 九 個 e t a o i n s h r.127.091.082.075.070.067.063.061.060 因 為 次 高 頻 率 的 B 與 第 三 高 頻 率 的 R 差 距 挺 大 的, 這 提 供 了 一 個 合 乎 我 們 理 性 的 信 心, 據 此 來 猜 測 W, B 有 可 能 就 是 e, t 但 其 他 的 字 母 又 如 何 呢? 接 下 來 頻 率 差 距 不 大 的 七 個 R, S, I, V, A, P, N 除 了 一 個 或 兩 個 外, 在 某 種 程 度 上 我 們 會 猜 測 可 能 就 是 明 文 字 母 a, o, i, n, s, h, r 但 要 判 斷 那 一 個 對 應 那 一 個, 就 有 些 困 難 了 所 以 一 個 陽 春 的 單 一 字 母 頻 率 數 算, 不 足 以 成 就 大 事 因 此 我 們 必 須 作 二 字 串 的 頻 率 分 析 我 們 從 密 文 中 最 常 出 現 的 前 九 個 字 母, 數 算 所 組 合 而 成 之 二 字 串 出 現 的 次 數, 列 表 如 下 : W B R S I V A P N W 3 4 12 2 4 10 14 3 1 B 4 4 0 11 5 5 2 4 20 R 5 5 0 1 1 5 0 3 0 S 1 0 5 0 1 3 5 2 0 I 1 8 10 1 0 2 3 0 0 V 8 10 0 0 2 2 0 3 1 A 7 3 4 2 5 4 0 1 0 P 0 8 6 0 1 1 4 0 0 N 14 3 0 1 1 1 0 7 0 位 於 W 列 N 行 之 項 目 1 表 示 二 字 串 WN 在 內 文 中 出 現 1 次 位 於 N 列 W 行 之 項 目 14 表 示 二 字 串 NW 在 內 文 中 出 現 14 次 二 字 串 出 現 頻 率 的 排 序, 在 上 一 章 也 介 紹 過 了, 我 們 再 一 次 地 把 最 常 出 現 的 前 15 個 列 在 此 : th he in er an re ed on es st en at to nt ha 從 這 兩 個 表, 我 們 馬 上 得 到 一 個 結 論 :BN 極 有 可 能 就 是 th 若 與 上 面 的 猜 測 W, B 有 可 能 就 是 e, t 合 起 來 考 慮, 我 們 有 W = e, B = t, N = h 如 果 我 們 將 上 上 表 延 伸 至 包 括 低 頻 率 的 字 母, 我 們 會 看 到 W 也 和 許 多 其 他 的 字 母 接 觸, 此 乃 e 的 另 一 個 特 性 這 幫 助 我 們 確 認 上 述 的 猜 測 另 外, 透 過 第 二 高 票 的 he 所 對 應 之 NW

傳 統 密 碼 之 旅 ( 下 ) 61 在 此 例 中 與 WA 並 列 亞 軍 的 事 實 ; 一 方 面 可 確 認 W = e, N = h, 另 一 方 面 也 可 猜 測 A 很 有 可 能 就 是 r 到 目 前 為 止, 我 們 也 有 {R, S, I, V, P} = {a, o, i, n, s} 母 音 a, o, i 傾 向 於 彼 此 互 相 排 斥 我 們 若 看 看 R 列, 我 們 看 到 R 並 不 常 出 現 在 S, I, A, N 之 前 但 瞄 一 下 R 行 顯 示 出 R 頗 常 出 現 在 S, I, A 之 後 所 以, 我 們 懷 疑 R {a, o, i} 因 為 V 在 W=e 之 前 的 次 數 不 少, 但 {a, o, i} 在 e 之 前 的 次 數 不 多, 甚 至 落 在 30 名 之 外 ; 所 以 我 們 也 同 樣 懷 疑 V {a, o, i} 繼 續 下 去, 我 們 看 到 最 有 可 能 的 是 {S, I, P} = {a, o, i} 與 {R, V} = {n, s} 字 母 n 的 特 性 是, 大 約 有 80% 在 n 之 前 的 字 母 為 母 音 看 看 前 30 名 之 內 的 二 字 串 中 in, an, on, en 分 別 位 居 第 3, 5, 8, 11 名, 即 可 感 受 一 二 目 前 我 們 已 經 認 出 W, S, I, P 是 母 音, 所 以 滿 足 上 述 性 質 最 有 可 能 的 字 就 屬 R 與 A 了, 但 上 面 提 到 過 A 很 有 可 能 是 r, 如 此 一 來 R 就 是 n 的 最 佳 候 選 人 因 此 之 故, 我 們 也 附 帶 得 到 了 V=s, 因 為 {R, V} = {n, s} 最 後, {S, I, P} = {a, o, i} 當 中 如 何 分 辨 那 一 個 是 那 一 個 呢? 先 看 o, 我 們 知 道 to 遠 比 ot 多 得 多 比 較 BS, BI, BP 及 SB, IB, PB 出 現 的 次 數, 不 難 看 出 S=o 再 看 i, 我 們 知 道 in 遠 比 ni 多 得 多 比 較 IR, PR 及 RI, RP 出 現 的 次 數, 得 知 I=i, 因 而 P=a 所 以, 經 過 合 理 猜 測 而 決 定 的 前 9 個 字 母 分 別 如 下 : W = e, B = t, R = n, S = o, I = i, V = s, A = r, P = a, N = h 這 些 字 母 在 內 文 520 個 字 當 中 佔 有 382 個 LehoOZ these tryths to QeseOHeDiZent that aoouen 在 這 個 時 候, 關 於 這 個 語 言 的 知 識 中 間 頻 率 的 字 母 (l, d, ) 及 有 根 據 的 猜 測 可 用 來 填 滿 剩 餘 的 字 母 例 如, 在 第 一 行 的 前 面 一 小 段 中, 一 看 即 知 Y=u 是 一 好 的 猜 測, 因 為 真 理 truth 出 現 在 眼 前 當 然, 仍 有 許 多 猜 測 的 工 作 以 及 各 式 各 樣 的 假 設 需 要 測 試, 直 到 一 切 都 沒 問 題 才 行 到 此 為 止, 我 們 已 將 此 方 法 的 精 神 傳 達 清 楚, 所 以 就 略 過 剩 下 的 細 節 解 密 之 後 的 信 息 將 空 格 恢 復, 如 下 所 示 : We hold these truths to be self-evident, that all men are created equal, that they are endowed by their Creator with certain unalienable Rights, that among these are Life, Liberty, and the pursuit of Happiness.

62 數 學 傳 播 30 卷 2 期 民 95 年 6 月 That to secure these rights, Governments are instituted among Men, deriving their just powers from the consent of the governed. That whenever any Form of Government becomes destructive of these ends, it is the Right of the People to alter or to abolish it, and to institute new Government, laying its foundation on such principles and organizing its powers in such form, as to seem most likely to effect their Safety and Happiness. 來 自 美 國 獨 立 宣 言 [5] (the Declaration of Independence) 內 文 中 間 的 一 段 十. 福 爾 摩 斯 與 跳 舞 的 人 密 碼 與 文 學 密 碼 術 在 多 處 文 學 的 舞 台 上 出 現 過 她 的 芳 蹤 這 個 舞 台 當 然 不 會 是 武 俠 小 說, 因 為 武 俠 小 說 中 的 人 物 都 太 厲 害 了, 密 碼 術 派 不 上 場 在 居 勒. 凡 爾 納 10 (Jules Verne) 的 地 心 之 旅 (Voyage au centre de la Terre, 1864), 引 發 這 一 趟 偉 大 旅 程 的 就 是 一 張 滿 是 古 冰 島 文 字 的 羊 皮 紙 被 破 解 的 結 果 在 英 國, 最 有 名 的 偵 探 小 說 家 亞 瑟. 柯 南 道 爾 (Sir Arthur Conan Doyle) 所 寫 的 福 爾 摩 斯 探 案 全 集, 其 中 歸 來 記 裡 的 跳 舞 的 人 就 是 一 篇 以 密 碼 為 主 題 的 短 篇 小 說 在 大 西 洋 彼 岸, 美 國 大 文 豪 艾 德 格. 愛 倫 坡 (Edgar Allan Poe) 也 對 密 碼 分 析 學 產 生 興 趣 他 寫 了 一 篇 與 密 碼 有 關 的 短 篇 小 說 金 甲 蟲 (The Gold Bug) 這 篇 小 說 廣 受 密 碼 專 家 的 禮 讚, 稱 之 為 最 佳 密 碼 創 作 文 學 另 外 還 有 威 廉. 契 可 瑞 (William Thackeray) 的 亨 利. 艾 斯 曼 的 歷 史 (The History of Henry Esmond) 及 阿 嘎 他. 克 里 斯 堤 (Agatha Christie) 的 四 嫌 疑 犯 (The Four Suspects) 也 值 得 一 看 現 在 我 們 扼 要 地 來 看 一 下 福 爾 摩 斯 在 跳 舞 的 人 中 破 解 一 密 碼 系 統 所 展 現 的 智 慧 與 才 華 此 處 僅 提 及 與 密 碼 術 有 關 的 情 節, 欲 知 詳 情, 請 上 網 [2] 閱 讀 其 全 文, 約 有 20 頁, 花 兩 個 小 時 即 可 欣 賞 完 畢 也 可 觀 賞 由 Simon & Schuster 公 司 所 拍 成 的 影 片, 片 長 才 52 分 鐘 [10] 跳 舞 的 人 一 年 前 才 與 艾 爾 西. 帕 翠 克 (Elsie Patrick) 結 為 連 理 的 希 爾 頓. 丘 比 特 (Hilton Cubitt) 寫 了 一 封 信 給 福 爾 摩 斯, 信 內 附 了 一 張 紙 條, 在 紙 上 橫 著 畫 了 些 在 跳 舞 的 奇 形 怪 狀 的 小 人, 這 是 丘 比 特 在 他 的 花 園 日 晷 儀 上 找 到 的, 如 圖 1 所 示 10 凡 爾 納 (1828-1905) 法 國 十 九 世 紀 後 半 葉 的 著 名 小 說 家, 寫 過 許 多 科 幻 小 說, 如 從 地 球 到 月 球 海 底 兩 萬 里 神 秘 島 以 及 環 遊 世 界 八 十 天 等

傳 統 密 碼 之 旅 ( 下 ) 63 圖 1. 艾 爾 西 一 看 上 面 這 張 紙 條, 立 刻 昏 倒 了 艾 爾 西 一 看 上 面 這 張 紙 條, 立 刻 昏 倒 了 之 後 她 就 像 在 做 夢 一 樣, 精 神 恍 惚, 眼 睛 裡 一 直 充 滿 了 恐 懼 就 在 那 個 時 候, 丘 比 特 寫 了 上 面 那 一 封 信 給 福 爾 摩 斯 並 於 次 日 到 倫 敦 拜 訪 福 爾 摩 斯 在 這 之 前 一 星 期 左 右, 丘 比 特 第 一 次 發 現 在 一 個 窗 臺 上 畫 了 一 些 跳 舞 的 滑 稽 小 人, 跟 那 張 紙 上 的 一 模 一 樣, 是 粉 筆 畫 的, 可 惜 沒 有 保 留 就 擦 掉 了 跟 福 爾 摩 斯 會 面 後 的 隔 天 早 上, 發 現 另 一 系 列 跳 舞 的 小 人 用 粉 筆 寫 在 工 具 房 門 上, 如 圖 2 所 示 圖 2. 用 粉 筆 寫 在 工 具 房 門 上 的 另 一 系 列 跳 舞 的 小 人 過 了 兩 個 早 上, 又 出 現 了 新 的, 如 圖 3 所 示 圖 3. 出 現 過 三 次 的 第 三 系 列 跳 舞 的 小 人 三 天 後, 在 日 晷 儀 上 找 到 一 張 紙 條, 很 潦 草 地 畫 了 一 行 小 人, 跟 上 一 次 的 完 全 一 樣 那 夜 在 工 具 房 門 上 又 有 人 畫 了 一 行 跳 舞 的 人, 排 列 跟 前 兩 次 的 完 全 相 同 隔 天 早 上 那 扇 門 除 了 已 經 有 過 的 那 行 小 人 外, 又 添 了 幾 個 新 畫 的, 如 圖 4 所 示 圖 4. 在 工 具 房 門 上 除 已 有 的 那 行 小 人 外, 又 添 了 幾 個 新 畫 的

64 數 學 傳 播 30 卷 2 期 民 95 年 6 月 圖 2 到 圖 4 是 第 二 次 拜 訪 福 爾 摩 斯 時 提 供 的 當 然 福 爾 摩 斯 心 裡 是 十 分 興 奮 丘 比 特 的 背 影 一 消 失, 他 就 急 急 忙 忙 跑 到 桌 邊, 把 所 有 的 紙 條 都 擺 在 自 己 面 前, 開 始 進 行 繁 瑣 的 分 析 一 連 兩 個 小 時 他 把 畫 著 小 人 和 寫 上 字 母 的 紙 條, 一 張 張 來 回 掉 換 他 全 神 貫 注 在 這 工 作 上, 完 全 忘 了 華 生 就 在 旁 邊 順 手 的 時 候, 便 一 會 兒 吹 口 哨, 一 會 兒 哼 著 小 調 ; 有 時 給 難 住 了, 就 好 一 陣 子 皺 著 眉 頭 兩 眼 發 呆 最 後, 他 滿 意 地 叫 了 一 聲, 從 椅 子 上 跳 起 在 屋 裡 走 來 走 去, 不 住 地 搓 著 兩 隻 手 顯 然 已 有 重 大 的 突 破 後 來, 他 打 了 一 通 很 長 的 電 報 給 某 人, 然 後 就 等 著 回 電 但 遲 遲 不 見 回 電, 如 此 耐 著 性 子 等 了 兩 天 在 這 兩 天 裡, 只 要 門 鈴 一 響, 福 爾 摩 斯 就 側 著 耳 朵 聽 第 二 天 晚 上, 來 了 一 封 信, 丘 比 特 說 他 家 裡 平 靜 無 事, 只 是 那 天 清 早 又 看 到 一 長 行 跳 舞 的 人 畫 在 日 晷 儀 上 他 臨 摹 了 一 張, 附 在 信 裡 寄 了 來, 如 圖 5 所 示 圖 5. 福 爾 摩 斯 伏 在 桌 上, 對 著 這 張 怪 誕 的 圖 案 看 了 幾 分 鐘, 猛 然 站 起 來, 發 出 一 聲 驚 異 沮 喪 的 喊 叫 焦 急 使 他 臉 色 憔 悴 福 爾 摩 斯 伏 在 桌 上, 對 著 這 張 怪 誕 的 圖 案 看 了 幾 分 鐘, 猛 然 站 起 來, 發 出 一 聲 驚 異 沮 喪 的 喊 叫 焦 急 使 他 臉 色 憔 悴 接 著 對 華 生 表 示 他 們 應 該 盡 快 趕 到 馬 場 村 莊 園 (Riding Thorpe Manor) 過 沒 多 久 他 所 盼 著 的 電 報 來 了, 看 完 後 並 表 示 急 需 讓 丘 比 特 知 道 目 前 的 情 況, 多 耽 誤 一 分 鐘 都 不 應 該, 因 為 這 位 諾 福 克 的 糊 塗 紳 士 已 陷 入 了 危 險 的 羅 網 隔 天 一 早, 他 與 華 生 抵 達 馬 場 村 莊 園 時, 發 現 警 察 已 在 那 兒 了 丘 比 特 先 生 已 中 彈 身 亡, 而 他 太 太 艾 爾 西 也 中 彈 且 情 況 相 當 危 險 福 爾 摩 斯 問 了 一 些 問 題 後, 就 叫 人 送 了 一 則 短 訊 息 給 附 近 艾 爾 裡 奇 斯 (Elriges) 農 場 的 阿 貝. 斯 蘭 尼 (Abe Slaney) 先 生 處 理 完 這 一 切, 他 們 等 著 犯 人 前 來 的 空 檔, 福 爾 摩 斯 就 向 華 生 與 警 長 解 釋 他 如 何 破 解 那 幾 張 畫 著 滑 稽 小 人 的 紙 條 他 說 道 : 在 我 面 前 擺 著 的 就 是 這 些 罕 見 的 作 品, 要 不 是 它 們 成 了 這 麼 一 場 悲 劇 的 前 兆, 那 麼 誰 見 了 也 會 一 笑 置 之 我 比 較 熟 悉 各 種 形 式 的 秘 密 文 字, 也 寫 過 一 篇 關 於 這 個 問 題 的 粗 淺 論 文, 其 中 分 析 了 一 百 六 十 種 不 同 的 密 碼 但 是 這 一 種 我 還 是 第 一 次 見 到 想 出 這 一 套 方 法 的 人, 顯 然 是 為 了 使 別 人 以 為 它 是 隨 手 塗 抹 的 兒 童 畫, 看 不 出 這 些 符 號 傳 達 的 資 訊 然 而, 只 要 看 出 這 些 符 號 是 代 表 字 母, 再 應 用 秘 密 文 字 的 規 律 來 分 析, 就 不 難 找 到 答 案 在 交 給 我 的 第 一 張 紙 條 上 那 句 話 很 短, 我 只 能 稍 有 把 握 假 定 圖 6 代 表 E 你 們 也 知 道, 在 英 文 字 母 中 E 最 常 見, 它 出 現 的 次 數 多 到 即 使 在 一 個 短 的 句 子 中 也 是 最 常 見 的 第 一 張 紙 條 上 的 十 五 個 符

傳 統 密 碼 之 旅 ( 下 ) 65 號, 其 中 有 四 個 完 全 一 樣, 因 此 把 它 看 成 E 是 合 理 的 這 些 圖 形 中, 有 的 還 帶 一 面 小 旗, 有 的 沒 有 小 旗 從 小 旗 的 分 佈 來 看, 帶 旗 的 圖 形 可 能 是 用 來 把 這 個 句 子 分 成 一 個 個 的 單 詞 我 把 這 看 作 一 個 可 以 接 受 的 假 設, 同 時 記 下 E 是 用 圖 6 來 代 表 的 圖 6. 這 就 是 E 可 是, 現 在 最 難 的 問 題 來 了 因 為, 除 了 E 以 外, 英 文 字 母 出 現 次 數 的 順 序 並 不 很 清 楚 這 種 順 序, 在 平 常 印 出 的 一 頁 文 字 裡 和 一 個 短 句 裡, 有 可 能 正 好 相 反 大 致 說 來, 按 出 現 次 數 其 順 序 為 T, A, O, I, N, S, H, R, D, L; 但 是 T, A, O, I 出 現 的 次 數 幾 乎 不 相 上 下 要 是 把 每 一 種 組 合 都 試 一 遍, 直 到 得 出 一 個 意 思 來, 那 會 是 一 項 沒 完 沒 了 的 工 作 所 以, 只 好 等 新 材 料 來 了 再 說 丘 比 特 先 生 第 二 次 來 訪 的 時 候, 果 真 給 了 我 另 外 兩 個 短 句 和 似 乎 只 有 一 個 單 詞 的 話, 就 是 這 幾 個 不 帶 小 旗 的 符 號 在 這 個 由 五 個 符 號 組 合 的 單 字 中, 我 找 出 了 第 二 和 第 四 個 都 是 E 這 個 單 詞 可 能 是 sever( 切 斷 ), 也 可 能 是 lever( 槓 桿 ), 或 者 never( 決 不 ) 毫 無 疑 問, 使 用 末 了 這 個 詞 來 回 答 一 項 請 求 的 可 能 性 極 大, 而 且 種 種 情 況 都 表 明 這 是 丘 比 特 太 太 寫 的 答 復 假 如 這 個 判 斷 正 確, 那 現 在 就 多 了 三 個 符 號 分 別 代 表 N, V 和 R 然 而 此 時 我 的 困 難 仍 很 大, 但 一 個 很 妙 的 想 法 使 我 知 道 了 另 外 幾 個 字 母 我 想 如 果 這 些 懇 求 是 來 自 一 個 在 丘 比 特 太 太 年 輕 時 就 跟 她 親 近 的 人, 那 麼 一 個 兩 頭 是 E, 當 中 有 三 個 別 的 字 母 的 組 合 很 可 能 就 是 ELSIE 這 個 名 字 我 一 檢 查, 發 現 這 個 組 合 曾 經 三 次 構 成 一 句 話 的 結 尾 這 樣 的 一 句 話 肯 定 是 對 ELSIE 提 出 的 懇 求 這 一 來 我 就 找 出 了 L, S 和 I 可 是, 究 竟 懇 求 什 麼 呢? 在 ELSIE 前 面 的 一 個 詞, 只 有 四 個 字 母, 末 了 是 E 這 個 詞 必 定 是 COME( 來 ) 我 試 過 其 他 各 種 以 E 結 尾 的 四 個 字 母, 都 不 符 合 情 況 這 樣 我 就 找 出 了 C, O 和 M, 而 現 在 我 可 以 回 頭 再 分 析 第 一 句 話, 把 它 分 成 單 詞, 還 不 知 道 的 字 母 就 用 點 代 替 經 過 這 樣 的 處 理, 這 句 話 就 變 成 :. M. ERE.. ESLNE. 現 在, 第 一 個 字 母 只 能 是 A 這 是 最 有 幫 助 的 發 現, 因 為 在 這 短 句 中 出 現 三 次 第 二 個 詞 開 頭 是 H 也 是 顯 而 易 見 的 這 句 話 現 在 變 成 了 : AMHEREA. ESLANEY 再 把 名 字 中 所 缺 的 字 母 添 上 :

66 數 學 傳 播 30 卷 2 期 民 95 年 6 月 AMHEREABESLANEY ( 我 來 了, 阿 貝. 斯 蘭 尼 ) 現 在 有 了 這 麼 多 字 母, 我 能 夠 很 有 把 握 地 解 釋 第 二 句 話 了 這 一 句 讀 出 來 是 這 樣 的 : A. ELRI. ES 我 看 這 一 句 中, 我 只 能 在 缺 字 母 的 地 方 加 上 T 和 G 才 有 意 義 ( 意 為 住 在 艾 爾 裡 奇 斯 Elriges), 並 且 假 定 這 名 字 是 寫 信 人 住 的 地 方 或 旅 店 馬 丁 警 長 和 華 生 很 有 興 趣 的 聽 著 福 爾 摩 斯 詳 細 講 他 如 何 找 到 答 案 的 經 過, 這 解 答 了 他 們 所 有 的 疑 問 後 來 你 怎 麼 辦, 先 生? 警 長 問 我 有 充 分 理 由 猜 想 阿 貝. 斯 蘭 尼 是 美 國 人, 因 為 阿 貝 是 美 國 式 的 編 寫, 而 這 些 麻 煩 的 起 因 又 是 從 美 國 來 的 一 封 信 我 也 有 充 分 理 由 認 為 這 件 事 帶 有 犯 罪 的 內 情 女 主 人 說 的 那 些 暗 示 她 過 去 的 話 和 她 拒 絕 把 實 情 告 訴 她 丈 夫, 都 使 我 往 這 方 面 去 想 所 以 我 才 給 紐 約 警 察 局 一 個 叫 威 爾 遜. 哈 格 裡 夫 的 朋 友 發 了 一 個 電 報, 問 他 是 否 知 道 阿 貝. 斯 蘭 尼 這 個 名 字 他 的 回 電 說 : 此 人 是 芝 加 哥 最 危 險 的 騙 子 就 在 我 接 到 回 電 的 那 天 晚 上, 丘 比 特 寄 來 了 阿 貝. 斯 蘭 尼 最 後 畫 的 一 行 小 人 用 已 知 道 的 這 些 字 母 譯 出 來 就 成 了 這 樣 的 一 句 話 : ELSIE. RE. ARETOMEETTHYGO. 再 添 上 P 和 D, 這 句 話 就 完 整 了 ( 意 為, 艾 爾 西 準 備 見 上 帝 ), 這 說 明 了 這 個 流 氓 已 從 勸 誘 改 為 恐 嚇 對 芝 加 哥 的 那 幫 歹 徒 我 很 瞭 解, 所 以 我 想 他 可 能 會 很 快 把 恐 嚇 的 話 付 諸 行 動 於 是 和 華 生 醫 生 立 刻 趕 來 諾 福 克, 但 不 幸 的 是, 我 們 趕 到 這 裡 的 時 候, 最 壞 的 情 況 已 經 發 生 了 福 爾 摩 斯 一 解 釋 完, 警 長 就 急 著 要 帶 人 去 艾 爾 裡 奇 斯 (Elriges) 農 場 即 刻 展 開 逮 捕 斯 蘭 尼 的 行 動 福 爾 摩 斯 說 沒 有 這 個 必 要, 斯 蘭 尼 很 快 就 會 自 己 送 上 門 來 果 真 如 福 爾 摩 斯 所 說 的, 斯 蘭 尼 來 了, 但 一 進 門 馬 上 就 被 警 長 帶 上 手 銬 在 等 待 被 押 走 的 時 候, 斯 蘭 尼 坦 承 認 罪 ( 但 聲 稱 他 開 槍 乃 是 自 衛 ), 並 說 到 這 種 秘 密 文 字 是 艾 爾 西 的 父 親 發 明 給 他 們 在 芝 加 哥 的 幫 派 聯 幫 所 使 用 的 斯 蘭 尼 已 經 和 艾 爾 西 訂 過 婚, 但 艾 爾 西 無 法 容 忍 他 們 幫 派 世 界 的 行 當, 於 是 她 就 趁 他 們 都 不 防 備 的 時 候 溜 走 逃 到 倫 敦 斯 蘭 尼 最 後 終 於 找 到 了 艾 爾 西 的 住 處, 並 送 出 秘 密 訊 息 奇 怪 的 是 為 何 斯 蘭 尼 會 走 進 福 爾 摩 斯 所 設 好 的 圈 套 呢? 福 爾 摩 斯 所 寫 的 信 息 如 圖 7 所 示 從 前 面 所 推 導 出 的 字 母, 你 會 發 現 它 的 意 思 不 過 是 馬 上 到 這 裡 來 (COME HERE AT ONCE) 斯 蘭 尼 當 然 會 確 信 這 必 定 是 從 艾 爾 西 來 的, 因 為 在 他 們 幫 派 之 外 不 會 有 人 知 道 這 種 秘 密 文 字 的 書 寫 因 此, 他 就 來 了 並 走 進 這 個 羅 網 圖 7. 為 什 麼 斯 蘭 尼 會 走 進 福 爾 摩 斯 所 設 好 的 圈 套 呢?

傳 統 密 碼 之 旅 ( 下 ) 67 評 論 福 爾 摩 斯 雖 然 以 非 常 少 的 資 料 就 可 完 成 任 務, 但 他 所 做 的 其 實 就 是 破 解 一 簡 單 的 代 換 密 碼 系 統 而 已 跟 多 數 此 類 的 密 碼 系 統 一 樣, 頻 率 分 析 及 對 該 語 言 的 知 識 兩 者 都 非 常 有 用 好 運 氣 當 然 也 不 錯, 不 管 是 幸 運 的 猜 測 或 是 具 有 良 好 的 字 母 分 佈 都 好 注 意 到 E 是 如 何 勢 不 可 當 的 成 為 最 常 出 現 的 字 母 實 際 上, 在 前 四 個 信 息 共 38 個 字 母 中, E 就 佔 了 11 席 之 多 這 給 了 福 爾 摩 斯 一 個 好 的 開 始 認 證 在 密 碼 術 中 是 相 當 重 要 的 一 環 假 如 五 爺 破 解 了 三 毛 的 密 碼 系 統, 那 麼 五 爺 就 能 經 常 偽 裝 成 三 毛 來 與 四 郎 通 訊 所 以 採 取 預 防 措 施 是 重 要 無 比 的 法 官 帶 給 了 斯 蘭 尼 許 許 多 多 的 時 間 足 以 來 好 好 思 考 這 方 面 的 議 題 聰 明 而 又 機 敏 的 你, 或 許 已 注 意 到 在 解 密 的 過 程 中, 我 們 有 一 點 在 作 弊 同 一 符 號 代 表 NEVER 中 的 V 也 代 表 PREPARE 中 的 P 據 推 測 這 有 可 能 是 誤 印 且 發 生 在 每 一 個 印 刷 過 的 版 本 當 中, 甚 至 可 追 溯 到 該 小 說 於 1903 年 的 第 一 次 印 刷 倘 若 這 錯 誤 發 生 在 福 爾 摩 斯 身 上, 那 麼 他 的 解 密 過 程 就 會 更 加 艱 辛, 而 且 有 可 能 馬 上 得 到 一 個 結 論 : 聯 幫 需 要 錯 誤 更 正 的 技 術 來 傳 達 他 們 的 信 息 實 際 上, 某 種 型 態 的 錯 誤 更 正 技 術 應 該 與 大 部 分 的 密 碼 協 定 同 時 使 用 才 行 十 一. 二 進 位 數 與 ASCII 眾 所 週 知, 在 電 腦 的 世 界 中, 用 0 與 1 的 字 串 來 表 示 資 料 遠 比 用 英 文 字 母 及 數 字 來 得 自 然 些 數 字 可 以 轉 換 為 二 進 位 數 標 準 方 式 是 以 10 為 底 來 表 示 一 個 數 例 如, 711 表 示 7 10 2 + 1 10 1 + 1 10 0 二 進 制 用 2 來 代 替 10 且 僅 需 數 字 0 與 1 例 如,1011000111 表 示 1 2 9 + 0 2 8 + 1 2 7 + 1 2 6 + 0 2 5 + 0 2 4 + 0 2 3 + 1 2 2 + 1 2 1 + 1 2 0 ( 這 等 於 十 進 制 中 的 711) 每 一 個 0 或 1 就 稱 為 一 個 二 進 位 數 字 (binary digits), 簡 稱 位 元 (bit) 用 到 八 個 位 元 來 表 示 的 數 就 稱 為 一 個 八 位 元 數 (8-bit number), 或 一 個 位 元 組 (byte) 最 大 的 八 位 元 數 為 255, 而 最 大 的 十 六 位 元 數 為 65535 我 們 經 常 要 處 理 的 東 西 不 僅 僅 是 數 字 而 已 在 這 種 情 形 之 下, 所 有 的 符 號 字 母 與 數 字 就 得 先 轉 換 成 二 進 制 數 字 有 許 多 不 同 的 方 式 可 以 來 完 成 這 件 工 作, 其 中 之 一 就 是 所 謂 的 美 國 標 準 資 訊 交 換 碼 (American Standard Code for Information Interchange), 簡 稱 ASCII( 念 成 ass-key) 每 一 個 符 號 用 一 個 7 位 元 的 數 表 示 之, 這 一 來 就 有 128 個 可 能 的 符 號 但 電 腦 所 普 遍 使 用 的 是 8 位 元, 因 此 之 故, 一 個 符 號 經 常 就 用 8 位 元 來 表 示 第 8 個 位 元 可 用 來 當 成 傳 輸 時 的 錯 誤 更 正 碼, 或 經 常 拿 來 擴 張 表 列 之 符 號 包 括 像 ü 與 è 等 之 符 號 這 裡 就 是 ASCII 符 號 表 我 們 不 會 用 到, 之 所 以 放 在 此 處, 只 是 想 讓 你 看 一 下 文 字 是 怎 麼 編 碼 成 為 一 個 0 與 1 所 組 成 的 序 列

68 數 學 傳 播 30 卷 2 期 民 95 年 6 月 0 NUL 1 SOH 2 STX 3 ETX 4 EOT 5 ENQ 6 ACK 7 BEL 8 BS 9 HT 10 NL 11 VT 12 NP 13 CR 14 SO 15 SI 16 DLE 17 DC1 18 DC2 19 DC3 20 DC4 21 NAK 22 SYN 23 ETB 24 CAN 25 EM 26 SUB 27 ESC 28 FS 29 GS 30 RS 31 US 32 SP 33! 34 " 35 # 36 $ 37 % 38 & 39 40 ( 41 ) 42 * 43 + 44, 45-46. 47 / 48 0 49 1 50 2 51 3 52 4 53 5 54 6 55 7 56 8 57 9 58 : 59 ; 60 < 61 = 62 > 63? 64 @ 65 A 66 B 67 C 68 D 69 E 70 F 71 G 72 H 73 I 74 J 75 K 76 L 77 M 78 N 79 O 80 P 81 Q 82 R 83 S 84 T 85 U 86 V 87 W 88 X 89 Y 90 Z 91 [ 92 \ 93 ] 94 ^ 95 _ 96 97 a 98 b 99 c 100 d 101 e 102 f 103 g 104 h 105 i 106 j 107 k 108 l 109 m 110 n 111 o 112 p 113 q 114 r 115 s 116 t 117 u 118 v 119 w 120 x 121 y 122 z 123 { 124 125 } 126 ~ 127 DEL 十 二. 單 次 鑰 匙 簿 密 碼 (One -Time Pads) 這 個 無 法 破 解 的 密 碼 系 統 在 1919 年 由 吉 伯 特. 先 得 福. 維 念 (Gilbert Sandford Vernam) 取 得 美 專 利 權 1310719 號 [13] 將 明 文 信 息 透 過 二 進 制 或 ASCII 表 示 成 由 0 與 1 所 成 的 序 列 但 信 息 也 有 可 能 是 一 個 數 位 化 影 像 或 是 一 個 聲 音 訊 號 鑰 匙 是 一 由 0 與 1 所 構 成 的 隨 機 序 列, 其 長 度 與 明 文 信 息 相 等, 用 過 隨 即 丟 棄 且 絕 對 不 再 使 用 加 密 運 算 就 是 將 鑰 匙 加 到 信 息 上, 一 個 位 元 接 著 一 個 位 元 的 在 模 2 之 下 進 行 此 過 程 通 常 稱 之 為 XOR 換 句 話 說, 我 們 所 使 用 的 規 則 如 下 :0+0 = 0, 0+1 = 1+0 = 1, 1+1 = 0 例 如 明 文 信 息 是 0010010101 而 鑰 匙 為 1001001010, 則 得 到 密 文 如 下 : ( 明 文 ) 0 0 1 0 0 1 0 1 0 1 ( 鑰 匙 ) 1 0 0 1 0 0 1 0 1 0 ( 密 文 ) 1 0 1 1 0 1 1 1 1 1 解 密 動 作 與 加 密 完 全 一 樣, 用 同 一 個 鑰 匙 加 到 密 文 即 可, 如 下 : ( 密 文 ) 1 0 1 1 0 1 1 1 1 1 ( 鑰 匙 ) 1 0 0 1 0 0 1 0 1 0 ( 明 文 ) 0 0 1 0 0 1 0 1 0 1 當 然 明 文 及 鑰 匙 也 可 回 到 原 先 的 字 母 所 構 成 的 序 列 此 時 的 單 次 鑰 匙 簿 密 碼 其 實 就 是 一 種 維 吉 內 爾 密 碼, 其 鑰 匙 長 度 與 明 文 信 息 相 等 不 同 的 是 此 鑰 匙 的 選 擇 是 完 全 隨 機 的, 因 而 密 文 也 保 有 此 隨 機 性, 如 此 才 能 成 就 其 無 法 破 解 的 特 性 對 密 文 攻 擊 法 而 言, 這 個 加 密 的 方 法 是 完 全 無 法 破 解 的 例 如 若 密 文 為 LPRASQOB- DQRCZXKE, 則 明 文 可 能 是 iloveyouverymuch, 也 有 可 能 是 wonderfulweekend; 只 要 是 相 同 長 度 的 信 息 都 有 相 同 的 可 能 性 是 明 文 因 此, 除 了 長 度 外, 從 密 文 看 不 出 任 何 明 文 的 蛛 絲 馬 跡 這 在 解 藍 恩 (Shannon) 的 Entropy 理 論 中 可 以 講 得 更 明 確

傳 統 密 碼 之 旅 ( 下 ) 69 如 果 我 們 有 明 文 中 的 片 段, 那 麼 就 可 以 找 出 此 片 段 中 所 對 應 的 鑰 匙, 但 對 其 他 片 段 的 鑰 匙 卻 毫 無 用 處 可 言 在 大 多 數 的 情 況 中, 不 管 是 選 擇 明 文 攻 擊 或 是 選 擇 密 文 攻 擊 都 不 太 可 能 即 使 可 能 也 只 透 露 出 所 知 道 的 那 個 片 段 的 鑰 匙 而 已, 這 對 破 解 信 息 毫 無 助 益, 除 非 此 片 段 鑰 匙 又 被 再 用 一 次 那 麼 我 們 該 如 何 使 用 這 麼 樣 的 一 個 系 統 呢? 而 且 在 何 種 情 況 之 下 使 用 呢? 鑰 匙 當 然 可 以 事 先 產 生, 但 問 題 是 如 何 製 造 出 真 正 隨 機 的 0 與 1 之 序 列 呢? 你 可 叫 阿 貓 阿 狗 一 起 來 丟 銅 板, 並 且 邊 哼 著 丟 丟 銅 子 的 民 謠, 免 得 太 無 聊 ; 然 而 這 種 方 法 在 大 部 分 的 場 合 是 太 慢 了, 而 且 不 實 用 我 們 也 可 請 出 蓋 革 計 數 器, 並 計 算 在 一 小 週 期 內 喀 嚓 了 幾 聲 ; 若 是 偶 數 就 記 成 0, 若 是 奇 數 就 記 成 1 有 一 些 其 他 實 際 可 行 的 方 法, 速 度 較 快 但 隨 機 性 就 差 一 些 ; 但 不 難 看 出, 要 快 速 產 生 一 把 好 的 鑰 匙 是 困 難 的 一 旦 鑰 匙 出 爐, 經 由 信 得 過 的 密 使 交 給 接 收 方 這 樣 一 來, 有 需 要 的 時 候, 就 可 以 傳 送 信 息 了 據 報 導, 在 冷 戰 (Cold War) 期 間, 華 府 與 克 里 姆 林 宮 頭 頭 之 間 的 熱 線 (Hot Line) 就 是 採 用 單 次 鑰 匙 簿 密 碼 系 統 來 互 通 信 息 單 次 鑰 匙 簿 密 碼 的 缺 點 是 它 需 要 一 很 長 的 鑰 匙, 不 僅 製 造 昂 貴 而 且 傳 送 也 昂 貴 一 旦 鑰 匙 用 完 了, 若 再 使 用 於 第 二 個 信 息, 那 就 危 險 萬 分 ; 因 為 任 何 由 第 一 個 信 息 所 得 到 的 知 識, 都 會 反 映 到 第 二 個 信 息 當 中 所 以 在 大 部 分 的 情 況 裡, 有 好 幾 個 方 法 只 需 少 許 的 輸 入 即 可 用 來 產 生 一 合 理 的 0 與 1 之 隨 機 序 列, 因 而 可 看 成 是 一 近 似 的 單 次 鑰 匙 簿 如 此 一 來, 信 差 特 使 所 攜 帶 的 資 訊 量 就 比 原 先 要 送 出 去 的 信 息 少 了 好 多 下 面 我 們 描 述 一 個 速 度 快, 但 不 怎 麼 安 全 的 這 一 類 的 方 法 十 三. 線 性 回 饋 位 移 暫 存 器 序 列 在 涉 及 加 密 的 許 多 場 合 中, 有 一 介 於 速 度 與 安 全 性 之 間 的 平 衡 交 易 若 你 要 求 很 高 水 準 的 安 全 性, 那 就 得 犧 牲 速 度, 反 之 亦 然 例 如 在 有 線 電 視 方 面, 許 多 的 資 訊 要 傳 達, 所 以 速 度 是 重 要 的 ; 至 於 安 全 性 就 沒 那 麼 重 要, 因 為 不 值 得 投 下 昂 貴 的 設 備 來 攻 擊 此 一 系 統 在 這 裡 我 們 描 述 一 個 速 度 比 安 全 性 重 要 的 方 法 下 面 的 序 列 s 010000100101100111110001101110101000010010110011111 可 由 其 起 始 值 k = {0, 1, 0, 0, 0} x 1 = 0, x 2 = 1, x 3 = 0, x 4 = 0, x 5 = 0 及 下 面 的 線 性 遞 迴 關 係 式 得 到 : x n+5 = x n + x n+2 (mod 2)

70 數 學 傳 播 30 卷 2 期 民 95 年 6 月 這 個 序 列 在 第 31 項 後 開 始 重 複 更 一 般 地, 考 慮 一 長 度 為 m 的 線 性 遞 迴 關 係 式 x n+m c 0 x n + c 1 x n+1 + c 2 x n+2 + + c m 1 x n+m 1 (mod 2), 此 處 係 數 c = {c 0, c 1,..., c m 1 } 為 0 或 1 若 我 們 指 定 起 始 值 為 k = {x 1, x 2, x 3,, x m } 則 所 有 接 下 去 的 x n 值 可 由 遞 迴 關 係 式 求 出 我 們 定 義 如 下 指 令 來 執 行 製 造 此 等 所 謂 的 LFSR 序 列 ( 理 由 待 會 兒 說 明 ) 之 任 務 : lfsr[c,k,n] 將 係 數 為 c = {c 0, c 1,..., c m 1 } 之 遞 迴 關 係 式, 在 起 始 值 k = {x 1, x 2, x 3,...,x m } 之 下 所 生 成 的 序 列, 輸 出 其 前 面 n 項 上 述 指 令 之 程 式 如 下 : In[79]:=lfsr[c_,k_,n_]:=Module[{z},z=k;Do[AppendTo[z,Mod[Array[Function[i,z[[j-Length[k]-1+i]]],Length[k]].c,2]], {j,length[k]+1,n}];z]; 用 此 指 令 來 驗 證 上 述 序 列 s 如 下 : In[80]:= c5={1,0,1,0,0};k5={0,1,0,0,0}; s={0,1,0,0,0,0,1,0,0,1,0,1,1,0,0,1,1,1,1,1,0,0,0,1,1,0,1,1,1,0,1,0,1,0,0,0,0,1,0,0,1,0,1,1,0,0,1,1,1,1,1}; lfsr[c5,k5,length[s]] == s Out[82]= True 如 此 所 得 到 的 由 0 與 1 組 成 的 序 列 可 用 來 當 加 密 之 用 的 鑰 匙 將 明 文 寫 成 由 0 與 1 組 成 的 序 列, 然 後 在 模 2 之 下 把 鑰 匙 中 適 當 的 位 元, 一 個 位 元 接 著 一 個 位 元 地 加 在 明 文 上 例 如 明 文 信 息 是 1011001110001111 而 鑰 匙 序 列 為 上 面 的 序 列, 我 們 有 ( 明 文 ) 1 0 1 1 0 0 1 1 1 0 0 0 1 1 1 1 ( 鑰 匙 ) 0 1 0 0 0 0 1 0 0 1 0 1 1 0 0 1 ( 密 文 ) 1 1 1 1 0 0 0 1 1 1 0 1 0 1 1 0 解 密 則 與 加 密 完 全 一 樣, 將 鑰 匙 序 列 加 在 密 文 上 即 可 完 成 此 法 的 一 個 優 點 是 大 的 鑰 匙 週 期 僅 需 用 到 很 少 的 資 訊 長 週 期 對 維 吉 內 爾 密 碼 是 一 項 改 良, 因 為 短 週 期 一 下 子 就 會 被 找 到 鑰 匙 在 上 例, 指 定 起 始 向 量 {0, 1, 0, 0, 0} 及 係 數 {1, 0, 1, 0, 0} 得 到 一 週 期 為 31 的 序 列 所 以 10 個 位 元 可 用 來 製 造 31 個 位 元 的 序 列 同 樣 地, 可 證 明 遞 迴 關 係 式 x n+31 = x n + x n+3

傳 統 密 碼 之 旅 ( 下 ) 71 及 任 何 非 零 起 始 向 量 產 生 一 序 列, 其 週 期 為 2 31 1 = 2147483647 因 此 62 個 位 元 可 用 來 製 造 超 過 20 億 位 元 的 鑰 匙 這 是 凌 駕 於 單 次 鑰 匙 簿 的 一 大 優 點, 因 為 單 次 鑰 匙 簿 必 須 事 先 傳 送 20 億 位 元 的 鑰 匙 這 個 方 法 在 硬 體 方 面 非 常 容 易 付 諸 行 動, 就 是 所 謂 的 線 性 回 饋 位 移 暫 存 器 (Linear Feedback Shift Register), 簡 稱 為 LFSR, 而 且 速 度 非 常 快 這 也 是 為 什 麼 我 們 將 此 等 序 列 稱 之 為 LFSR 序 列 的 緣 由 考 慮 下 圖 :...... x m+2.. x m+1. x m..... 明 文.. 密 文 對 一 暫 存 器 的 下 一 階 段, 在 每 個 框 框 中 的 位 元 按 箭 頭 的 方 向 移 動 至 另 一 框 框 中, 如 圖 示 其 中 表 示 模 2 之 下 的 加 法, 圖 中 指 的 是 x m + x m+1 輸 出 之 位 元 x m 與 下 一 個 明 文 的 位 元 相 加 產 生 密 文 上 圖 代 表 遞 迴 關 係 式 x n+3 = x n + x n+1, 一 旦 給 定 起 始 值 {x 1, x 2, x 3 } 此 機 器 就 非 常 有 效 率 的 產 生 接 下 去 的 位 元 不 妙 的 是, 上 述 的 加 密 法 很 容 易 就 會 被 已 知 明 文 攻 擊 法 破 解 更 明 確 的 說, 若 我 們 只 知 道 幾 個 連 續 的 明 文 及 其 對 應 的 密 文, 則 我 們 可 用 此 來 決 定 其 遞 迴 關 係 式, 因 而 算 出 此 鑰 匙 接 下 去 的 位 元 將 明 文 從 密 文 中 減 掉 ( 或 加 上, 在 模 2 之 下 是 一 樣 的 ), 即 得 鑰 匙 之 位 元 因 此 在 下 面 的 討 論, 我 們 不 管 密 文 及 明 文 是 什 麼 ; 僅 專 注 在 鑰 匙 並 且 假 設 鑰 匙 序 列 的 片 段 已 被 發 現 例 題 01: 已 知 週 期 為 15 之 序 列 t = 0110101111000100110101111, 其 起 始 片 段 為 011010111100 且 已 知 是 從 一 個 線 性 遞 迴 關 係 式 所 產 生 的 如 何 決 定 此 遞 迴 關 係 式 的 係 數? 我 們 不 見 得 知 道 其 長 度, 所 以 就 從 長 度 2 開 始 ( 長 度 1 為 常 數 序 列 ) 假 設 遞 迴 關 係 式 為 x n+2 = c 0 x n + c 1 x n+1 令 n = 1, 2, 用 已 知 數 值 x 1 = 0, x 2 = 1, x 3 = 1, x 4 = 0 得 方 程 組 並 寫 成 矩 陣 的 形 式 如 下 : ( ) ( ) ( ) 0 1 c0 1 = 1 1 0 c 1 解 之 得 c 0 = 1 與 c 1 = 1, 所 以 猜 測 遞 迴 關 係 式 為 x n+2 = x n + x n+1 很 遺 憾 的 是, 這

72 數 學 傳 播 30 卷 2 期 民 95 年 6 月 個 猜 測 是 不 正 確 的, 由 於 x 6 x 4 + x 5 因 此 我 們 就 試 長 度 等 於 3, 得 到 矩 陣 方 程 式 0 1 1 c 0 0 1 1 0 c 1 = 1 1 0 1 0 c 2 這 個 係 數 矩 陣 的 行 列 式 值 為 0 (mod 2); 實 際 上, 此 方 程 式 無 解 這 也 可 透 過 觀 察 就 可 看 出 其 無 解 的 性 質, 因 為 左 邊 矩 陣 各 行 元 素 和 為 0 但 右 邊 向 量 則 否 現 在 考 慮 長 度 等 於 4, 得 到 矩 陣 方 程 式 0 1 1 0 1 1 0 1 1 0 1 0 0 1 0 1 解 之 得 到 c 0 = 1, c 1 = 1, c 2 = 0, c 3 = 0 c 0 c 1 c 2 c 3 1 = 0 1, In[83]:= A={{0,1,1,0},{1,1,0,1},{1,0,1,0},{0,1,0,1}}; B={{1}, {0}, {1}, {1}}; PolynomialMod[Inverse[A].B, 2] Out[84]= {{1}, {1}, {0}, {0}} 1 所 以 我 們 猜 測 可 能 的 遞 迴 關 係 式 為 x n+4 = x n + x n+1 ; 又 此 遞 迴 關 係 式 生 成 已 知 鑰 匙 片 段 的 其 餘 元 素, 因 而 這 是 從 現 有 資 訊 所 得 到 之 遞 迴 關 係 式 的 最 佳 猜 測 實 際 上, 很 快 的 算 一 下, 可 以 確 知 這 的 確 就 是 了 所 以 我 們 已 經 找 到 所 要 的 遞 迴 關 係 式 用 指 令 lfsr 來 驗 證 序 列 t 如 下 : In[85]:= c4={1,1,0,0}; k4={0,1,1,0}; t={0,1,1,0,1,0,1,1,1,1,0,0,0,1,0,0,1,1,0,1,0,1,1,1,1}; lfsr[c4, k4, Length[t]] == t Out[86]= True 在 一 般 的 情 況 如 下, 若 要 求 出 一 個 長 度 為 m 的 遞 迴 關 係 式, 我 們 得 先 知 道 前 2m 項 x 1, x 2, x 3,...,x 2m 如 上 得 到 矩 陣 方 程 式 x 1 x 2 x m x 2 x 3 x m+1...... x m x m+1 x 2m 1 c 0 c 1. c m 1 = x m+1 x m+2. x 2m 此 矩 陣 方 程 式 的 係 數 矩 陣 右 翼 行 向 量 及 其 解 可 經 由 下 列 三 指 令 分 別 計 算 之, 此 處 v 就 是 所 涉 及 的 LFSR 序 列 對 應 之 程 式 如 下 : In[87]:= lfsrmatx[v_,m_]:=array[function[{i,j},v[[i+j-1]]],{m,m}] lfsrrhs[v_, m_]:=array[function[i,v[[i+m]]],m] lfsrsoln[v_,m_]:=polynomialmod[inverse[lfsrmatx[v,m]].lfsrrhs[v,m],2]

傳 統 密 碼 之 旅 ( 下 ) 73 下 : 驗 證 上 述 的 LFSR 序 列 t, 當 m = 4 對 應 的 係 數 矩 陣 為 A ( 在 In[20] 之 中 ) 及 其 解 如 In[90]:= {lfsrmatx[t, 4] == A, lfsrsoln[t, 4]} Out[90]= {True, {1, 1, 0, 0}} 下 面 我 們 將 予 以 證 明 這 個 係 數 矩 陣 在 模 2 之 下 是 可 逆 的 充 分 而 且 必 要 條 件 為 x 1, x 2, x 3,...,x 2m 1 不 滿 足 長 度 小 於 m 的 任 何 線 性 遞 迴 關 係 式 這 意 味 著 其 線 性 遞 迴 關 係 式 的 長 度 至 少 是 m 因 此 尋 找 線 性 遞 迴 關 係 式 係 數 的 一 個 策 略 清 清 楚 楚 的 展 現 在 你 我 眼 前 假 設 我 們 知 道 鑰 匙 序 列 的 前 面 100 位 元 對 m = 2, 3, 4,..., 形 成 一 m m 的 矩 陣 如 上 並 計 算 其 行 列 式 值 若 連 續 有 好 幾 個 m 值, 其 對 應 之 矩 陣 的 行 列 式 值 為 0, 那 就 停 止 最 後 一 個 具 有 非 零 行 列 式 值 的 m, 有 可 能 就 是 遞 迴 關 係 式 的 長 度 解 此 矩 陣 方 程 式 得 到 係 數 c 0, c 1,, c m 1, 然 後 再 檢 查 有 這 個 線 性 遞 迴 關 係 式 所 生 成 的 序 列 是 否 與 原 鑰 匙 序 列 中 已 知 的 那 些 位 元 吻 合 若 否, 則 試 大 一 些 的 m 值 利 用 上 述 指 令 lfsrmatx[v,m], 定 義 指 令 lfsrlength[v,m] 來 計 算 前 m 個 行 列 式 值, 其 程 式 如 下 : In[91]:= lfsrlength[v_,m_]:=table[mod[det[lfsrmatx[v,k]],2],{k,min[m,1+floor[dimensions[v][[1]]/2]]}] 假 設 我 們 不 知 道 鑰 匙 序 列 起 始 的 100 位 元, 但 卻 知 道 在 某 處 連 續 的 100 個 位 元 利 用 這 些 位 元 為 起 始 點, 執 行 上 述 的 步 驟 實 際 上, 一 旦 我 們 找 到 遞 迴 關 係 式, 我 們 也 可 逆 向 追 溯 起 始 點 之 前 的 位 元 例 題 02: 假 設 我 們 有 100 位 元 的 LFSR 序 列 u 如 下 : In[92]:=u={1,0,0,1,1,0,0,1,0,0,1,1,1,0,0,0,1,1,0,0,0,1,0,1,0,0,0,1,1,1,1,0,1,1,0,0,1,1,1,1,1,0,1,0,1,0,1,0,0,1, 0,1,1,0,1,1,0,1,0,1,1,0,0,0,0,1,1,0,1,1,1,0,0,1,0,1,0,1,1,1,1,0,0,0,0,0,0,0,1,0,0,0,1,0,0,1,0,0,0,0}; 從 m = 1 開 始, 前 20 個 行 列 式 值 為 In[93]:= lfsrlength[u, 20] Out[93]= {1,0,1,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0} 一 個 合 理 的 猜 測 是 m = 8 乃 是 具 非 零 行 列 式 值 的 最 後 一 個 解 矩 陣 方 程 式, 得 到 係 數 為 In[94]:= lfsrsoln[u, 8] Out[94]= {1, 1, 0, 0, 1, 0, 0, 0} 所 以 我 們 猜 測 其 遞 迴 關 係 式 為 x n+8 = x n + x n+1 + x n+4 這 個 遞 迴 關 係 式 生 成 原 序 列 所 有 的 100 項, 所 以 至 少 根 據 我 們 現 有 的 知 識, 這 是 正 確 的 答 案

74 數 學 傳 播 30 卷 2 期 民 95 年 6 月 假 設 我 們 知 道 在 某 序 列 中 間 連 續 的 100 個 位 元, 且 我 們 想 知 道 在 這 之 前 的 位 元 例 如 序 列 從 x 17 開 始, 所 以 x 17 = 1, x 18 = 0, x 19 = 0,... 將 遞 迴 關 係 式 寫 成 x n = x n+1 + x n+4 + x n+8 令 n = 16 得 到 x 16 = x 17 + x 20 + x 24 = 1 + 1 + 1 = 1 如 此 繼 續 下 去, 我 們 可 依 序 決 定 x 15, x 14,, x 1 我 們 現 在 證 明 上 面 所 承 諾 要 證 明 的 結 果 定 理 : 令 矩 陣 M 為 x 1 x 2 x m x 2 x 3 x m+1 M =...... x m x m+1 x 2m 1 若 序 列 x 1, x 2, x 3,...,x 2m 1 滿 足 一 長 度 小 於 m 的 線 性 遞 迴 關 係 式, 則 det(m) = 0 反 之, 若 序 列 x 1, x 2, x 3,...,x 2m 1 滿 足 一 長 度 等 於 m 的 線 性 遞 迴 關 係 式 且 det(m) = 0, 則 此 序 列 也 會 滿 足 一 長 度 小 於 m 的 線 性 遞 迴 關 係 式 注 意 : 首 先 說 明 一 下 定 理 敘 述 中 關 於 線 性 遞 迴 關 係 式 長 度 的 問 題 一 個 序 列 可 能 滿 足 一 長 度 為 3 的 遞 迴 關 係 式, 如 x n+3 = x n+2 顯 然 地, 此 序 列 也 滿 足 一 長 度 更 短 的 遞 迴 關 係 式, 如 x n+1 = x n ( 至 少 對 m 2) 然 而 有 些 序 列 可 能 會 滿 足 一 長 度 比 所 期 待 者 小 的 遞 迴 關 係 式, 如 x n+4 = x n+3 +x n+1 +x n 假 設 起 始 值 為 1, 1, 0, 1, 則 利 用 遞 迴 關 係 式 可 算 出 接 下 去 的 12 項 為 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1,... 容 易 看 出 此 序 列 滿 足 遞 迴 關 係 式 x n+2 = x n + x n+1 證 明 : 若 有 一 長 度 小 於 m 的 線 性 遞 迴 關 係 式, 則 矩 陣 M 中 的 一 列 是 其 他 幾 列 的 線 性 組 合 如 遞 迴 關 係 式 為 x n+3 = x n + x n+2, 則 第 四 列 為 第 一 列 與 第 三 列 的 和 因 此 行 列 式 值 為 0 (mod 2) 反 之, 若 行 列 式 值 為 0 (mod 2) 則 存 在 一 非 零 向 量 b = (b0,...,b m 1 ) 使 得 bm = 0 這 給 了 我 們 一 遞 迴 關 係 式, 但 無 法 馬 上 看 出 此 遞 迴 關 係 式 可 一 路 延 伸 到 x 2m 1 如 M 的 前 面 兩 列 的 和 等 於 第 三 列, 即 x n+2 = x n + x n+1 n = 1, 2,..., m 我 們 需 將 此 一 路 延 伸 到 n = 2m 3 得 到 x 2m 1 = x 2m 3 + x 2m 2 記 得 嗎 我 們 也 假 設 有 一 長 度 為 m 的 線 性 遞 迴 關 係 式 x n+m = c 0 x n + + c m 1 x n+m 1, 1 n m 用 此 遞 迴 關 係 式 來 定 義

傳 統 密 碼 之 旅 ( 下 ) 75 x 2m, x 2m+1, x 2m+2,... 如 此 繼 續 延 伸 此 一 序 列 ( 當 然, 若 此 序 列 已 有 這 些 項 x n, n 2m, 那 可 能 與 我 們 在 證 明 當 中 所 暫 時 使 用 的 值 不 一 樣 ) 我 們 有 c 0 x n+1 x n+2 x n+m c 1 x n+2 x n+3 x n+m+1 M n =....... c m 1 x n+m x n+m+1 x n+2m 1 c 0 c 1. c m 1 = x n+m+1 x n+m+2. x n+2m ( 此 處 M n 就 是 在 式 子 中 間 的 m m 矩 陣 ) 當 n = 0, 這 就 是 原 來 的 矩 陣 方 程 式 對 較 大 的 n, 這 僅 僅 表 示 我 們 的 遞 迴 關 係 式 記 得 向 量 b 滿 足 bm = 0 在 上 面 方 程 式 中, 令 n = 0 並 在 兩 邊 的 左 方 乘 上 向 量 b 因 為 bm0 = bm = 0, 左 式 = 0, 故 右 式 也 = 0 這 意 味 著 b (xm+1,...,x 2m ) = 0 現 在 考 慮 n = 1 的 情 形 上 面 已 經 證 明 的 是 b 乘 上 M 1 的 最 後 一 行 等 於 0 但 是 M 1 的 其 他 行 來 自 M 0 的 行 向 量, 所 以 也 會 被 b 所 消 化 掉 因 此 bm1 = 0 如 上, 我 們 得 到 b 乘 上 M 2 的 最 後 一 行 等 於 0 如 此 這 般, 我 們 看 出 bmn = 0 n 顯 而 易 見, 這 成 就 了 一 長 度 小 於 m 的 遞 迴 關 係 式, 也 同 時 完 成 了 整 個 定 理 的 證 明 最 後, 我 們 對 序 列 的 週 期 做 一 些 評 論 假 設 一 遞 迴 關 係 式 的 長 度 為 m 任 何 此 序 列 中 連 續 的 m 項 決 定 所 有 後 面 的 元 素, 而 且 將 遞 迴 關 係 式 逆 向 書 寫, 則 也 可 求 出 所 有 前 面 的 值 顯 然 地, 若 我 們 連 續 有 m 個 0, 則 在 它 之 前 之 後 都 是 0 因 此 我 們 不 考 慮 此 種 情 況 長 度 為 m 的 不 全 為 0 的 0 與 1 所 構 成 的 數 串 總 共 有 2 m 1 個 所 以, 只 要 超 過 2 m 1 項, 某 一 個 長 度 為 m 的 數 串 必 定 會 出 現 兩 次, 因 而 此 序 列 會 開 始 重 複 其 週 期 頂 多 是 2 m 1 伴 隨 著 一 個 遞 迴 關 係 式 x n+m = c 0 x n + c 1 x n+1 + c 2 x n+2 + + c m 1 x n+m 1, 我 們 有 一 多 項 式 定 義 為 f(t) = T m c m 1 T m 1 c 0 若 f(t) 在 模 2 之 下 是 不 可 分 解 的, 則 可 證 明 其 週 期 整 除 2 m 1 一 個 有 趣 的 情 形 是 當 2 m 1 為 質 數 ( 亦 即 梅 仙 尼 質 數 ) 的 時 候 如 果 週 期 不 是 1 ( 亦 即 不 是 常 數 序 列 ) 時, 則 其 週 期 一 定 就 是 極 大 值 2 m 1 上 面 的 例 子 週 期 為 2 31 1 就 是 此 種 類 型 線 性 回 饋 位 移 暫 存 器 序 列 已 廣 泛 地 被 研 究 過 例 如, 可 參 考 所 羅 門. 郭 倫 (Solomon W. Golomb) 的 位 移 暫 存 器 序 列 [3] (Shift Register Sequences) 或 珍. 凡 德 路 比 (Jan. C. A. van der Lubbe) 的 密 碼 術 的 基 本 方 法 [12] 阻 撓 上 述 攻 擊 的 一 個 方 法 是 採 用 非 線 性 遞 迴 關 係 式, 如 x n+3 = x n+2 x n + x n+1 (mod 2)

76 數 學 傳 播 30 卷 2 期 民 95 年 6 月 一 般 而 言, 要 破 解 這 些 非 線 性 系 統 稍 困 難 些 不 過, 我 們 不 會 在 此 討 論 參 考 文 獻 1. Becker H./Piper, F., Cipher Systems: The Protection of Communication, Northwood Books, London, 1982. 2. Doyle, Arthur Conan, The Adventures of Sherlock Holmes, The Dancing Men, 1903. http://www. bookhome.net/zhentan/knde/glj-twdr.html 3. Golomb, Solomon, W., Shift Register Sequences, Aegean Park Press, Revised Edition, 1982. 4. Hill, Lester S., Cryptography in an Algebraic Alphabet, The American Mathematical Monthly 36, June-July 1929, pp.306-312. http://en.wikipedia.org/wiki/hill cipher 5. 美 國 獨 立 宣 言 http://usinfo.org/docs/deceng.htm 6. Kahn, David, The Codebreakers, The Story of Secret Writing, Scribner, Revised and Updated, 1996. 7. Kerckhoffs, Auguste, La cryptographie militaire, Journal des sciences militaires, vol. IX, pp.5-83, Jan. 1883, pp.161-191, Feb. 1883. http://www.petitcolas.net/fabien/kerckhoffs/la cryptographie militaire i.htm 8. Kessler, Gary C.: Hiding Data in Data, Windows &.NET Magazine, April 2002. http://www.garykessler.net/library/steganography.html 9. Saeednia, Shahrokh, How to Make the Hill Cipher Secure, Cryptologia, 24(4), October 2000, pp.353-360. 10. Simon & Schuster, Inc., The Adventures of Sherlock Holmes, The Dancing Men, Simon & Schuster Video, 1986. 11. Singh, Simon, The Code Book: The Science of Secrecy from Ancient Egypt to Quantum Cryptography, 1999. 12. van der Lubbe, Jan C. A., Basic Methods of Cryptography, Cambridge University Press, 1998. 13. Vernam, Gilbert S., Cipher Printing Telegraph Systems For Secret Wire and Radio Telegraphic Communications, Journal of the IEEE, Vol.55, pp.109-115 (1926). http://en.wikipedia.org/wiki/gilbert Vernam 14. Wright, Ernest Vincent: Gadsby, A Story of Over 50,000 Words Without Using the Letter E, 1937. http://spinelessbooks.org/gadsby/ 本 文 作 者 任 教 於 東 海 大 學 數 學 系