古典密碼學概述

1. 隱寫術 Steganography

隱寫術是指首先用傳統加密算法對數據進行加密,然后用某種方法將加密后的數據修改為一個偽裝文本。

2. 替換密碼 Substitution cipher

對數據中的每個字符用另一個字符進行替換。

• 替換密碼依賴與固定的替換結構
• 對于字母表中的每一個字母的替換都是固定的

【注】

1. 一次替換一個字符顯然會在密文中留下太多的明文結構
2. 如果已知明文的性質/結構,則可以通過統計攻擊輕松破解任何替換密碼

2.1 單字母單表密碼 Monoalphabetic cipher

• 凱撒密碼 Caesar cipher

1. 密鑰 k in {0,1,cdots,25},字母表{a,b,cdots,z} 與集合 {0,1,cdots,25} 對應。

• 明文空間 = 密文空間 = Sigma^+(其中Sigma 為字母表{a,b,cdots,z}
• 密鑰空間 = 26

1. 設密鑰為 k=3,明文為 m=are you ready,密文為 c。則:

• 加密

begin{array}{c} c_i = Enc(m_i,k) = (m_i+3) ,, mod ,, 26 end{array}

最終加密結果:

begin{array}{c} c = DUH BRX UHDGB end{array}

• 解密

begin{array}{c} m_i = Dec(c_i,k) = (c_i-3) ,, mod ,, 26 end{array}

最終解密結果:

begin{array}{c} m = are you ready end{array}

統計攻擊方法

• 原理:令 p_i指示在正常的英文內容中第 i 個字符出現的頻率。則有統計公式:

begin{array}{c} sum_{i=0}^{25} p_i^2 approx 0.065 end{array}

• 方法:

1. 定義

begin{array}{c} I_j = sum_{i=0}^{25} p_i cdot q_{i+j} end{array}

其中,p_i、q_{i+j}分別是對應明文字母表第 i 個字符的頻率、密文字符表中第i+j個字符的頻率。

1. 計算 in {0,1,cdots,25} 對應的 I_j的值。
2. 選擇 I_j? 值接近 0.065 的 j 值輸出,這些 j值很可能是密鑰 k 。
3. 對于每一個可能的 j 值,計算解密后的原文,看是否有實際意義,有則說明該 j 值即密鑰,無則說明不是。

• Mixed alphabetic cipher 字母表{a,b,cdots,z} 到字母表{A,B,cdots,Z}的映射是一個置換,每個小寫字母(代表明文)分別映射到一個唯一的大寫字母(表示密文)。

1. 密鑰空間 = 26!
2. 每個字母的映射是固定的
3. 已知語言中單個字母的概率分布

• 摩斯碼 Morse code 每個字母映射為一系列點和短橫線。

國際摩斯碼

1. 一條短橫線等于三個點。
2. 一個字母對應的系列點和短橫線間的空格間隔等于一個點長度
3. 兩個相鄰字母間的空格間隔等于三個點的長度
4. 兩個單詞間的空格間隔等于七個點的長度

2.2 單字母多表密碼 Polyalphabetic cipher

根據密鑰中的元素,替換規則從一個字母位置到下一個字母位置會發生改變。相同的明文字符可以對應不同的密文字符。

• 維吉尼亞密碼

1. 給定一定長度密鑰,重復密鑰直至密鑰流和明文長度相同。
2. 加密

begin{array}{c} c_i = (m_i + k_{i ,, mod ,, l}) ,, mod ,, 26 end{array}

1. 解密

begin{array}{c} m_i = (c_i - k_{i mod l}) mod 26 end{array}

1. 根據加解密公式可以構造出表格法: 假如明文為 asimpleexamplea simple exampleasimpleexample,密鑰為 battistabattistabattista,則表格法加密過程為:

• 生成密鑰流與明文字符一一對應:

• 參照表格(Tabula recta)計算密文。其中,明文字符對應行索引,密鑰字符對應列索引:

• 最終計算得到的密文為:

• 解密過程就是加密的逆過程。根據密鑰字符對應的列,尋找密文字符,則密文字符在表格中對應的行索引字符即明文字符。
• 一次性密碼本 OTP(One-time pad) OTP 是唯一一個達到完美加密的加密系統,無法被攻破。

要求

1. OTP 的安全性完全取決于密鑰的隨機性,即密鑰必須是隨機產生的。
2. 密鑰長度必須大于等于明文長度。
3. 密鑰只能使用一次,不能重復使用。
4. 密鑰必須完全保密。

示例 比如要加密的消息為「This is an example」,用于加密的密鑰(一次性密碼本)為「MASKL NSFLD FKJPQ」。

1. 將字母表{a,b,cdots,z} 映射到數字集合{0,1,cdots,25}。得到:

• This is an example → 19 7 8 18 8 18 0 13 4 23 0 12 15 11 4
• MASKL NSFLD FKJPQ → 12 0 18 10 11 13 18 5 11 3 5 10 9 15 16

1. 二者依序相加并模 26 得到密文消息如下:

• 5 7 0 2 19 5 18 18 15 0 5 22 24 0 20 → FHACTFSSPAFWYAU

1. 解密即反向操作即可。

2.3 多字母單表密碼 Multiple letter cipher

• 波雷費密碼 Playfair cipher Playfair 密碼是首種雙字母替換密碼。

原理

1. 選取一個 keyword 作為密鑰,去除密鑰中重復出現的字母,將密鑰的字母逐個從左到右,從上到下加入 5 times 5的矩陣中,剩下的空間將未加入的英文字母依照a-z順序加入,將字母將 I和 J視為同一字符(或將 Q去除)。
2. 將要加密的明文分成兩個一組。若組內的字母相同,將X(或Q)插入兩字母之間,重新分組(例如 HELLO 將分成 HE LX LO)。若剩下一個字,也加入X字。
3. 在每組中,找出兩個字母在矩陣中的地方。

• 若兩個字母不在同一直行或同一橫列,在矩陣中找出另外兩個字母,使這四個字母成為一個長方形的四個角(讀取按行對應,即兩個字母分別依次對應同行的那個字母)
• 若兩個字母在同一橫行,取這兩個字母右方的字母(若字母在最右方則取最左方的字母)。
• 若兩個字母在同一直列,取這兩個字母下方的字母(若字母在最下方則取最上方的字母)。

1. 新找到的兩個字母就是原本的兩個字母加密的結果。

• 希爾密碼 Hill cipher 希爾密碼是運用基本矩陣論原理的替換密碼,一次性替換三字母。

原理

1. 將字母表 {a,b,cdots,z} 映射到數字集合 {0,1,cdots,25}
2. 加密密鑰是一個 3 times 3的可逆矩陣(如果不可逆則無法解密):

begin{array}{c} K = left[ begin{matrix} k_{11} & k_{12} & k_{13} \ k_{21} & k_{22} & k_{23} \ k_{31} & k_{31} & k_{33} \ end{matrix} right] end{array}

1. 明文被排列為以下格式:

begin{array}{c} M = left[ begin{matrix} m_1 \ m_2 \ m_3 \ end{matrix} right] end{array}

1. 加密公式為:

begin{array}{c} C = left[ begin{matrix} c_1 \ c_2 \ c_3 \ end{matrix} right] = (K cdot M) mod 26 = (left[ begin{matrix} k_{11} & k_{12} & k_{13} \ k_{21} & k_{22} & k_{23} \ k_{31} & k_{31} & k_{33} \ end{matrix} right] cdot left[ begin{matrix} m_1 \ m_2 \ m_3 \ end{matrix} right]) mod 26 end{array}

1. 解密公式為:

begin{array}{c} M = (K^{-1}C) mod 26 = (K^{-1}KM) mod 26 = M end{array}

3. 置換密碼 Transposition cipher

對數據中的字符重新排列,但不改變它們本身。

• 籬笆密碼法 Rail Fence cipher 明文由上至下順序寫上,當到達最低部時,再回頭向上,一直重復直至整篇明文寫完為止。然后,再往右順序抄寫一次,即得到密文。

示例

1. 明文:WE ARE DISCOVERED. FLEE AT ONCE
2. 籬笆密碼法:

 W . . . E . . . C . . . R . . . L . . . T . . . E. E . R . D . S . O . E . E . F . E . A . O . C .. . A . . . I . . . V . . . D . . . E . . . N . .

1. 密文:WECRL TEERD SOEEF EAOCA IVDEN

• Column Transposition cipher 將明文按行順序排列,超過行長則另起一行。密鑰為一個置換,密鑰長度決定行的長度。根據密鑰指定的置換順序,一列一列讀取字符組在一起得到密文。

示例

1. 密鑰:4 3 1 2 5 6 7
2. 明文:attack postponed until two am
3. 置換:

1. 密文:TTNAAPTMTSUOAODWCOIXKNLYPETZ

4. 轉輪密碼機 Rotor machine

屬于單字母多表密碼加密,每次轉動輸出一個密文后,轉輪機內部布線發生改變,即改變了明文字符和密文字符之間的映射關系。

• German Enigma
• Allied Hagelin
• Japanese Purple