02密码学---古典密码学

1 .密码学 导论 ˙第 2 章 经典 密码学 李卫海

2 .本章目录 密码学导论 -- 中国科学技术大学 2

3 .经典对称密码体制 对称加密系统由五部分组成： Plaintext (Message) ：明文 Encryption algorithm ：加密算法 Secret Key ：密钥 Ciphertext ：密文 Decryption algorithm ：解密算法 信源 密钥源 加密器 E 解密器 D 明文 M 密钥 K 密文 C 明文 M 密码分析员 公开信道 秘密信道 密码学导论 -- 中国科学技术大学 3

4 .经典加密技术 代换（ Substitution ） 明文内容的表示形式改变，内容元素之间相对位置不变 明文字母用密文中对应字母代替 置换（ Transposition or Permutation ） 明文内容元素的相对位置改变，内容的表示形式不变 乘积密码（ Product Ciphers ） 多个加密技术的叠加 几个习惯 约定 ： 为便于区分，约定小写字母表示明文，大写字母表示密文 加密时通常舍弃标点、空格（普通文本中 17%-18% 是空格，频率太高，会泄露信息） 密码学导论 -- 中国科学技术大学 4

5 .第一节 代换技术 密码学导论 -- 中国科学技术大学 5

6 .一、算术密码 1. 移位密码（ Shift Cipher ）：凯撒密码 Caesar Cipher Julius Caesar ，最早的代换密码 算法： 将每个字母用字母表中它之后的第 k 个字母替代 C = E( k, p ) = ( p +k) mod 26 ， p = D(k, C) = (C-k) mod 26 一些文献中认为 Caesar 固定使用 k=3 例： k=3 密钥： 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 E F G H I J K L M N O P Q R S T U V W X Y Z A B C 明文： meet me after the toga party 密文： PHHW PH DIWHU WKH WRJD SDUWB 密码学导论 -- 中国科学技术大学 6

7 .安全性： 26 个可能的密钥，只有 25 个可用 密钥 0 不可用。否则密文与明文等同。 密码分析基本规则：加密算法不会误将明文直接输出 如果有一个算法能够将一段明文映射为另一段可解释的明文，则该算法具有很强的伪装性和安全性。 可以使用穷举攻击，依次尝试便可 最坏情况需要尝试 25 次 平均需要尝试 25/2=12.5 次 密码学导论 -- 中国科学技术大学 7

8 .例： 密码学导论 -- 中国科学技术大学 8

9 .进一步的安全性分析 破译结果需要辨别选择，这要求：明文可以理解 对破译者的语言能力要求较高 编码或压缩会使得明文难以辨别，增加破译工作量 采用并行运算可以同时尝试多个甚至全部的可能密钥，但每一个尝试结果都需要后续判断 当前，机器可以准确判断单词拼写，语法检查则较为勉强，语义理解远不能达到要求 需要更好的办法 —— 频率统计分析，稍后介绍 密码学导论 -- 中国科学技术大学 9

10 .一种思路：在解密过程中，加入强制性的人工参与。虽然会增加解密人员的工作量，但对于抵抗穷举攻击非常有效（ CAPTCHA ，区分人与 机器的全自动公开图灵测试） 验证码： 密码学导论 -- 中国科学技术大学 10 Easy for human, and hard for computer

11 .2. 仿 射密码（ Affine Cipher ） 目的： 扩大密钥空间 映射关系简单 算法： 密钥： a,b 加密： C = E([ a,b ], p ) = ( ap +b) mod 26 解密： p = D([ a,b ], C) = ((C- b ) /a) mod 26 密码学导论 -- 中国科学技术大学 11

12 .密钥的选取： a=1 时，蜕化为凯撒密码。这里不考虑。 a ≠0 时， b 无限制。 相当于 b=0 的仿射加密后，再叠加一次凯撒加密。 a 的取值有限制： gcd (a,26)=1 a=3,5,7,9,11,15,17,19,21,23,25 否则不能保证一一映射 例： a=2, b=1 时， p=3->C=7; p=16->C=7 不同的明文对应同一密文，无法解密 密钥空间大小为 11*26=286 讨论：当 gcd (a,26)≠1 时，是否可用？ 密码学导论 -- 中国科学技术大学 12

13 .3 、 Hill 密码 密钥： m  m 个密钥 加密过程： 每次处理 m 个明文字母 加密规则： 密码学导论 -- 中国科学技术大学 13

14 .解密过程： 要求 K 矩阵可逆 安全性： 对单字母的频率特性掩盖得很好 m 越大，掩盖的频率信息越多 可以很好地 抵抗唯密文攻击 易受已知明文攻击！ 密码学导论 -- 中国科学技术大学 14

15 .二 、代换密码 (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×10 26 部分密钥存在部分不动点，不可用 密码学导论 -- 中国科学技术大学 15

16 .辅助工具 16 密码学导论 -- 中国科学技术大学 惠斯通 (Wheatstone) 密码 钟表形式设备，首次露相于 1867 年巴黎世纪博览会。顺时针旋转指针指向下一明文字母，圆盘也随着混合的密文字母旋转。 双密码盘 估计始于 18 或 19 世纪。外层圆盘上有类似词汇表的明文，包括字母、和常用单词密文由两位十进制数组成。

17 .安全性 对短信息（长度小于密钥）， 穷举攻击可行 ? 例： 密文： ABC DEF GHIJ 密钥： a-E, e-H, f-A, n-F, o-B, 　　　 r-D, s-I, t-J, w-G, x-C 明文： fox ran west 密钥： a-I, d-E, e-H, f-A, h-D, 　　　 i -E, n-G, o-B, r-J, x-C 明文： fox hid near 对长信息，穷举攻击可行！ 单表替换不改变相应字母的出现频率 密码学导论 -- 中国科学技术大学 17

18 .英语字母的频率统计 自然语言存在高冗余，字母出现频率不同 e 的频率最高 其次是 t,a,o,i , n,s,h,r z,q,x,j 频率近似为 0 密码学导论 -- 中国科学技术大学 18

19 .英语字母的频率统计 英文单（双、三）字母（组）出现频率很重要 双字母组合 th,he,in,er,an , re,ed,on,es,st , en,at,to,nt,ha ,… 三字母组合 the,ing,and,her , ere,ent,tha,nth ,… 密码学导论 -- 中国科学技术大学 19

20 .经典密码破译的三大要素 频率特征 各种语言中，各个字母的使用次数是不一样的 连接特征 前后字母存在一定关联性 英语中， q 后几乎百分之百连接着 u x 前几乎总是 i 和 e ，只在极个别情况下是 o 和 a e 和 e 之间， r 的出现频率很高 重复特征 两个字符以上的字符串重复出现的现象 英语中， th,tion,tious 等经常出现 密码学导论 -- 中国科学技术大学 20

21 .字频统计攻击 对凯撒密码，通过识别 a-e- i 或 r-s-t 三元组的峰，或 jk 和 xyz 的特征，可以获得密钥 对单表替换 密码，破译步骤： 统计密文字母出现频率 将统计结果与自然语言频率表对比，确定部分密钥 结合连接特征和重复特征，确定部分密钥 双、三字母的频率统计表往往很有帮助 从语义上，猜测其它密钥 密码学导论 -- 中国科学技术大学 21

22 .字频统计攻击例 密文： UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZ VUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSX EPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ 频率最高的 P （ 15 次）和 Z （ 14 次）可能对应 e 和 t 猜 ZW 是 th （最常用二字组合）， ZWP 是 the （最常用三字组合） t e e te th t e e t e t t t h e ee e th t e e e t t e the et 密码学导论 -- 中国科学技术大学 22 UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZ VUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSX EPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ

23 .字频统计攻击例 {S 、 U 、 O 、 M 、 H} 可能对应 {a 、 h 、 i 、 n 、 o 、 r 、 s} {A 、 B 、 G 、 Y 、 I 、 J} 可能对应 {b 、 j 、 k 、 q 、 v 、 x 、 z} t a e e te a that e e a a t e t ta t ha e ee a e th t a e e e tat e the et 密码学导论 -- 中国科学技术大学 23 UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZ VUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSX EPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZ VUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSX EPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ itwasdiscolsedyesterdaythatseveralinformalbut directcontactshavebeenmadewithpolitical representativesofthevietconginmoscow

24 .2 、 Playfair 密码 —— 二维单表代换 由 Charles Wheatstone 于 1854 年发明 , 用他的朋友 Baron Playfair 命名。 该密码曾在二战期间广泛被美英军方使用 密钥矩阵：以 MONARCHY 为例 5×5 矩阵 先填入密钥字母（不重复） 再在剩余位置填入其它字母 U V W X Z M O N A R C H Y B D L P Q S T E F G I/J K 密码学导论 -- 中国科学技术大学 24

25 .加密过程： 每次加密或解密两个字母 加密 规则 ： 如果两字母是 重复 的，则在其中插入字母 x 。 例如 balloon 划分为 ba l x lo on 如果两字母位于 同一行 ，则各自用右侧字母代换。 例如 ar ->RM 如果两字母位于 同一列 ，则各自用下侧字母代换。 例如 mu->CM 否则各自用同行异列字母代换。 例如 hs ->BP ； ea->IM 或 JM 解密过程： 加密过程的逆 有 26×26 ＝ 676 个字母对，单个字母的统计规律有 改善 频率统计表需 676 个表项，需要更多密文才能有效统计 M O N A R C H Y B D E F G I/J K L P Q S T U V W X Z 密码学导论 -- 中国科学技术大学 25

26 .3 、多表代换加密（ Poly alphabetic Cipher ） 为抵抗字频统计攻击，可以采用多个单表，明文消息采用不同的单表代换。 单表 1 单表 2 · · · 单表 s 代换 逆代换 单表 1 单表 2 · · · 单表 s 明文 p 明文 p 密钥 k 密钥 k 单表 k 单表 k 密文 C 密码学导论 -- 中国科学技术大学 26

27 .辅助工具 27 密码学导论 -- 中国科学技术大学 杰斐逊的轮子密码机 M-94 1942 年前被美国陆军广泛使用，主要针对低级军事通信安全。共有 25 个直径 35mm 的铝盘，外缘上可有字母。 条形密码设备 M-138-T4 二战中美国陆军和海军使用。 25 个可选取的纸条按预先编排的顺序编号和使用。加密强度相当于 M-94 。 Kryha 密码机 1926 年由 Alexander von Kryha 发明，密钥长度 442 ，周期固定，一个有数量不等的齿的轮子引导密文轮不规则地运动。

28 .4 、维吉尼亚密码（ Vigenère Cipher ） 是最简单的多表替换密钥，由多个凯撒替换表循环构成 密钥： k ＝ k 0 k 1 …k d-1 第 i 位密钥 k i 表示采用 k= k i 的凯撒替换表 密钥重复使用 加密算法： C i = E(k, p i ) = ( p i + k i mod d ) mod 26 解密算法： p i = D(k, C i ) = (C i - k i mod d ) mod 26 密码学导论 -- 中国科学技术大学 28

29 .例如： 密钥 deceptive 密钥： deceptivedeceptivedeceptive 明文： wearediscoveredsaveyourself 密文： ZICVTWQNGRZGVTWAVZHCQYGLMGJ 密码学导论 -- 中国科学技术大学 29