2. 古典密碼

2.1 經典加密技術基礎

1. 分類
   • 代換（Substitution）：明文內容的表示形式改變（元素被替換），但元素相對位置不變（如明文字母被密文字母替代）。
   • 置換（Transposition/Permutation）：明文元素的相對位置改變，但內容表示形式不變（僅重排順序）。
   • 乘積密碼（Product Ciphers）：多個加密技術的疊加使用。
2. 約定
   • 小寫字母表示明文，大寫字母表示密文。
   • 加密時通常舍棄標點、空格（因普通文本中空格占比 17%-18%，頻率過高易泄露信息）。

2.2 代換技術

2.2.1 算術密碼

1. 移位密碼（凱撒密碼，Caesar Cipher）
   • 原理：由 Julius Caesar 提出，每個字母用字母表中其后第 k 個字母替代。
     • 加密：$C=E(k,p)=(p+k)mod26$
     • 解密：$p=D(k,C)=(C?k)mod26$
     • 部分文獻中凱撒密碼固定使用 k=3。
   • 示例：明文 “meet me after the toga party”，k=3 時，密文為 “PHHW PH DIWHU WKH WRJD SDUWB”。
   • 安全性：
     • 密鑰空間：26 個可能密鑰，僅 25 個可用（k=0 時密文與明文一致，無效）。
     • 易被窮舉攻擊：最壞需嘗試 25 次，平均 12.5 次。
2. 仿射密碼（Affine Cipher）
   • 目的：擴大密鑰空間，映射關系簡單。
   • 原理：
     • 密鑰：(a,b)
     • 加密：$C=E([a,b],p)=(ap+b)mod26$
     • 解密：$p=D([a,b],C)=((C?b)\times a^{?1})mod26（a^{?1}為a在模26下的逆元）$。
   • 密鑰選取：
     • $a\ne 1$（否則退化為凱撒密碼），且需滿足 $gcd(a,26)=1$（保證一一映射，否則不同明文可能對應同一密文）。
     • 有效 a 值：3,5,7,9,11,15,17,19,21,23,25（共 11 個）。
   • 密鑰空間：11×26=286。

2.2.2 代換密碼（Substitution Cipher）

1. 單表代換密碼（Monoalphabetic Cipher）
   • 原理：每個明文字母按固定密鑰（26 個字母的置換）替換為唯一密文字母。
   • 示例：
     • 明文：a b c d e f g h i j k l m n o p q r s t u v w x y z
     • 密鑰：D K V Q F I B J W P E S C X H T M Y A U O L R G Z N
     • 明文 “ifwewishtoreplaceletters” 加密后為 “WIRFRWAJUHYFTSDVFSFUUFYA”（忽略空格）。
   • 密鑰空間：26!≈4×1026（部分密鑰含不動點，不可用）。
   • 輔助工具：惠斯通（Wheatstone）密碼，一種鐘表形式設備，1867 年巴黎世紀博覽會首次出現，通過旋轉指針和圓盤實現加密。
   • 安全性：
     • 短信息（長度小于密鑰）可能被窮舉攻擊；長信息因字母頻率不變（單表替換不改變字母出現頻率），易被頻率統計攻擊。
2. 英語字母頻率特征（密碼破譯關鍵）
   • 單字母頻率：e 頻率最高（12.702%），其次為 t（9.056%）、a（8.167%）等；z、q、x、j 頻率接近 0。
   • 雙字母組合：最常見為 th、he、in、er、an 等。
   • 三字母組合：最常見為 the、ing、and、her 等。
   • 經典密碼破譯三要素：頻率特征（字母使用次數差異）、連接特征（前后字母關聯性，如 q 后幾乎必接 u）、重復特征（多字符字符串重復出現，如 th、tion）。
3. 多表代換加密（Polyalphabetic Cipher）
   • 原理：使用多個單表代換，明文不同位置的字母用不同單表加密，以抵抗頻率統計攻擊。
4. 維吉尼亞密碼（Vigenère Cipher）
   • 原理：最簡單的多表替換密碼，由多個凱撒替換表循環構成。
     • 密鑰：$k=k_0{k}_1\dots k_{d?1}（長度為d）$，第 i 位密鑰 $k_i$ 對應凱撒替換表 $k=k_i$，密鑰重復使用。
     • 加密：$C_i=E(k,p_i)=(p_i+k_{imodd})mod26$
     • 解密：$p_i=D(k,C_i)=(C_i?k_{imodd})mod26$
   • 示例：密鑰 “deceptive”（d=9），明文 “wearediscoveredsaveyourself”，密文為 “ZICVTWQNGRZGVTWAVZHCQYGLMGJ”。
   • 安全性：字母頻率被模糊但未完全消失，可通過分組統計破解。
   • 破解方法：
     • 第一步確定密鑰長度 d：使用 Kasiski 方法，通過尋找密文中重復字段，計算其間距的最大公約數，即為 d（重復字段間距為 d 的整數倍）。
     • 第二步分組攻擊：將密文按位置 i、i+d、i+2d… 分組，每組對應同一單表，再用頻率統計攻擊破解各分組密鑰。

2.3 置換技術

• 核心特點：通過重排字母順序隱藏信息，不改變字母表示形式（與代換技術的本質區別：代換改字母，置換改位置）。

1. 柵欄技術（Rail Fence Cipher）
   • 原理：將明文按對角線方向寫成若干行，再按行輸出作為密文。
   • 示例：明文 “meet me after the toga party”，寫成兩行（m e m a t r h t g p r y 和 e t e f e t e o a a t），密文為 “MEMATRHTGPRYETEFETEOAAT”。
2. 縱行換位（Row Transposition Cipher）
   • 原理：將明文按密鑰位數寫為若干列，再按密鑰順序輸出各列。
   • 示例：明文 “attack postponed until two am”，密鑰 “4 3 1 2 5 6 7”（7 位），明文按列排列后，按密鑰順序輸出列，密文為 “TTNAAPTMTSUOAODWCOIXKNLYPETZ”。

2.4 乘積密碼

1. 原理：單純代換或置換安全性不足，連續使用多種加密技術（如交替代換和置換）可大幅提高安全性，是現代密碼構造的基本技術之一。
2. 轉輪機（Rotor Machines）
   • 本質：機械時代最復雜的密碼機，核心是復雜的多表代換系統，通過多個轉輪實現，二戰廣泛應用（如德國 Enigma、盟軍 Hagelin、日本 Purple）。
   • 原理：包含多個圓柱體（轉輪），每個圓柱體代表一個代換表；每個字母加密后，轉輪旋轉，改變代換表。
   • 密鑰空間：3 個轉輪可提供263=17576個代換表。
3. Enigma（謎）密碼機
   • 發展歷程：1918 年由德國 Arthur Scherbius 提出專利，1923 年帶反射板的 Enigma-A 問世，1926 年德國海軍開始采購，后發展出多種型號。
   • 結構：包含鍵盤、指示燈板、密鑰輪、反射板、接插板等，需 3 人操作（輸入明文、讀指示燈、記錄密文）。
   • 破譯關鍵：
     • 波蘭貢獻：1928 年獲得商業型 Enigma，1931 年通過 “灰燼先生”（漢斯?蒂洛?施密特）獲得操作手冊等；馬里安?雷耶夫斯基利用指標組（隨機 3 字母連續加密兩遍）構造字母循環圈，開發 “循環測定機” 和 “炸彈機”（Bomba），1939 年向英、法贈送仿制 Enigma 及技術。
     • 英國貢獻：1938 年布萊奇利莊園成為國家破譯中心，阿蘭?圖靈 1940 年設計 Bombe 機，針對指標組不再重復加密的情況，通過密文全文尋找明文 - 密文關聯破解。
     • 美國貢獻：1942 年 Joseph Desch 設計可破解四轉輪 Enigma 的機器，1943 年起交付海軍，最終 121 臺 Bombe 機每日破譯德國 Enigma 密鑰。
   • 教訓：軍民混用、叛徒與間諜影響、使用規則錯誤（主密鑰更新周期長、轉輪進位點固定）、對安全性過于自負（未及時銷毀設備、低估對手）等。

2.5 歷史上的教訓

1. Kerckhoff 原則：密碼安全性不應依賴算法保密，而應依賴密鑰；敵方可能知曉算法，需假設算法公開下仍安全。
2. 不可低估對手能力：“不可能被攻破” 的密碼常被破譯（如 DES，1973 年預計需數十年破譯，1999 年 22.25 小時即可破解）。
3. 密碼安全性評估：
   • 僅靠密鑰組合數評估安全性是片面的（上限為窮舉攻擊難度），需公開接受全球研究和攻擊檢驗。
   • 表面復雜性可能降低安全性（如禁止字母加密為自身，反而減少攻擊者工作量）。
4. 隨機數重要性：隨機數生成是密碼關鍵，二戰日軍曾用編織籃抽紙條（寫四位數字）產生隨機數。