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