5.2 古典密码系统
古典密码系统有2种基本类型： • 换位密码 • 替代密码
9
10
5.2.1 换位密码
• 换位密码（transposition cipher）通过重新编 排明文中的字母顺序得到密文，而所有的 字母并没有改变 • 例如光栅密码（Rail-Fence Cipher）
– 明文：HELLO WORLD – 重排为： HLOOL ELWRD – 密文：HLOOL ELWRD
• 按此替换密文得到： ADIYS RIUKB OCKKL IFTAG PAUEF VATAS BMTFV EGGOP CNEKI RWCXS ANSNP HHEUL AJEOC MIUAX
MIGHK CIITW HSSEW QONOF
AZOTO EOCNO NECSE EEGOS
EIOOL EIOOL DDAAA WLPCM
15 16
凯撒密码攻击实例
i 0 1 2 3 4 5 6 ϕ(i) 0.0482 0.0364 0.0410 0.0575 0.0252 0.0190 0.0660 i 7 8 9 10 11 12 ϕ(i) 0.0442 0.0202 0.0267 0.0635 0.0262 0.0325 i 13 14 15 16 17 18 ϕ(i) 0.0520 0.0535 0.0226 0.0322 0.0392 0.0299 i 19 20 21 22 23 24 25 ϕ(i) 0.0315 0.0302 0.0517 0.0380 0.0370 0.0316 0.0430
5.1 什么是密码学
• 攻击： 假设攻击者知道加密明文的算法，而不知道具体 的密钥（即知道D和E），可使用以下3种攻击方 法：
– 唯密文（ciphertext only）攻击，攻击者只拥有消息的 密文，目的是找出相应的明文，如果可能，也可能试 图寻找密钥； – 已知明文（known plaintext）攻击，攻击者拥有密文和 这些密文对应的明文，目的是找到以上明密文所用的 密钥； – 选择明文（chosen plaintext）攻击，攻击者可以对一些 特定的明文进行加密，可得到明文所对应的密文，目 的是找到以上明密文所用的密钥。
实例
• 以HE排列为线索重排密文：
HE LL OW OR LD
• 以H结尾的2字母频率
– WH 0.0026 – EH, LH, OH, RH, DH ≤ 0.0002
• 可以读出“HELLOWORLD”
• 假设E紧跟H
13 14
5.2.2 替代密码
• 替代密码（Substitution Ciphers）通过改变 明文中的字符产生密文 • 例如凯撒密码，假若密钥为3，则：
11
5.2.1 换位密码
• 换位密码攻击
– 如果单字母的出现频率与明文语言的一个模型 匹配，而双字母频率不匹配，那么该消息可能 使用换位密码 – 可能的攻击方式是按照n字母组合频率重排密 文，重复测试，直到找到换位密码的换位模式
12
2
实例
• 密文：HLOOLELWRD • 以H开头的2字母频率：
– HE 0.0305 – HO 0.0043 – HL, HW, HR, HD < 0.0010
Vigènere密码攻击实例
• 1 2 3 4 5 6 • 计算每列的每个字符出现次数，有以下结果： ABCDEFGHIJKLMNOPQRSTUVWXYZ 31004011301001300112000000 10022210013010000010404000 12000000201140004013021000 21102201000010431000000211 10500021200000500030020000 01110022311012100000030101 而原始字母表应具有的频率特征如下（H high, M medium, L low）： HMMMHMMHHMMMMHHMLHHHMLLLLL
26
• CI为0.043（暗示密钥长度大于5）
Vigènere密码攻击实例
• 将消息排为6列，得到6个字母表：
字母表1: 字母表2: 字母表3: 字母表4: 字母表5: 字母表6: AIKHOIATTOBGEEERNEOSAI DUKKEFUAWEMGKWDWSUFWJU QSTIQBMAMQBWQVLKVTMTMI YBMZOAFCOOFPHEAXPQEPOX SOIOOGVICOVCSVASHOGCC MXBOGKVDIGZINNVVCIJHH
21
22
5.2.2.1 Vigènere密码
• 根据英语模型的不同周期IC期望值：
周期 1 2 3 4 5 10 大周期 0.038
5.2.2.1 Vigènere密码
一个普鲁士骑兵军官Kaskski的发现：当密 钥字符序列重复出现在相同的字符上时， 密文字符会发生重复，重复字符序列之间 的字母数是密文周期的倍数。例如：
ϕ(i) = Σ0 ≤ c ≤ 25 f(c)p(c – i) = 0.1p(6 – i) + 0.1p(7 – i) + 0.1p(10 – i) + 0.3p(14 – i) + 0.2p(17 – i) + 0.1p(20 – i) + 0.1p(25 – i) – f(c)为字母c在密文中的出现频率，p(x)为字母x在英语中 的出现频率 – 所有算术计算均mod 26
key VIGVIGVIGVIGVIGV plain THEBOYHASTHEBALL cipher OPKWWECIYOPKWIRG 重复密文之间间隔9个字母，是密文周期3的倍数
23 24
期望IC值 0.066 0.052 0.047 0.045 0.044 0.041
4
Vigènere密码攻击实例
Vigènere密码攻击实例
• 最后一行中AJE可能意味着ARE，按此假设 则第2个字母表将A映射为S （密钥为S/18） • 对密文进行替换得到：
ALIYS INTAG BUTFV RECXS AREOC RICKB PACEF EGOOP ANANP MICAX OCKSL VATIS CNESI HHECL MIGHS CIITE HSSEE QONON AZOTO EOCNO NECSE EEGOS MIOOL MIOOL LDAAA ELPCM
29
30
5
Vigènere密码攻击实例
• 最后一个密文分组MICAX可能为MICAL， 意味着第4个字母表将A 映射为O （密钥为 O/14 ） • 对密文进行替换得到： ALIMS RICKP OCKSL AIGHS ANOTO MICOL INTOG PACET VATIS QIITE ECCNO MICOL BUTTV EGOOD CNESI VSSEE NSCSE LDOAA RECLS ANAND HHECL EONON ESGOS ELDCM ARECC MICAL
字母序列 MI OO OEQ O O G FV AA MOC QO PC NE SV CH
25
Vigènere密码攻击实例
• 字母重复情况如下：
开始 5 22 24 39 43 50 56 69 77 94 118 结束 15 27 54 63 87 122 105 117 83 97 124 间隔 10 2, 5 5 5 30 2, 3, 5 24 2, 2, 2, 3 44 2, 2, 11 72 2, 2, 2, 3, 3 49 7, 7 48 2, 2, 2, 2, 3 6 2, 3 3 3 6 2, 3 间隔因子 可能长度 … … 6… 6… … 6… … 6… 6… … 6…
17
凯撒密码攻击实例
• 基于ϕ最有可能的密钥:
– i = 6, ϕ(i) = 0.0660
• 明文：EBIIL TLOLA
– i = 10, ϕ(i) = 0.0635
• 明文： AXEEH PHKEW
– i = 3, ϕ(i) = 0.0575
• 明文：HELLO WORLD
– i = 14, ϕ(i) = 0.0535
28
• 重合指数CI如下：
#1 0.069 #2 0.078 #3 0.078 #4 0.056 #5 0.124 #6 0.043 除#4与#6外，均指向周期为1的CI期望值，暗示秘 密周期为6 27
Vigènere密码攻击实例
• 通过对照可得：
– 第1个字母表符合原始字母表特征（密钥为A/0） – 第3个字母表假若I移动到A符合此频率（密钥为I/8） – 第6个字母表假若V移动到A符合此频率（密钥为V/21）
• 考察密文：
ADQYS EQOOG MOCIO HSNEW HCEUT HIUIX MIUSB IFBAG EQOOG VECNE QOIOF OXKKT KAUMF BMBFV DLAAV MEGJS MIBHK VVTAA ZGGWP RWKXS WTPCH IZOOO CIDTW CIEKQ VNSVP AJMOC
• 明文：WTAAD LDGAS
• 只有当 i = 3时，明文为一英语短语，密钥 为3或D
18
3
5.2.2 替代密码
凯撒密码的主要问题： • 密钥太短！
– 可通过穷尽测试进行攻击 – e密码
• Vigènere密码是一多字母替换密码 • 实例：
– 明文：THE BOY HAS THE BALL – 密钥：VIG – 使用凯撒密码对每一字母加密： key VIGVIGVIGVIGVIGV plain THEBOYHASTHEBALL cipher OPKWWECIYOPKWIRG
– 明文：HELLO – 密文：KHOOR
凯撒密码攻击实例
凯撒密码很容易受到基于统计特征的唯密文攻击 • 考察密文 KHOOR ZUROG • 密文中字母出现频率：