第2讲古典密码

1、1第二章第二章 古典密码古典密码n1. 学习基本的密码编制原理;n2.了解早期编制密码的基本方法;n3. 为进一步学习现代密码的编制打下基础。23我们将重点介绍我们将重点介绍代替密码代替密码 4 一、单表代替密码：一、单表代替密码： 利用预先设计的利用预先设计的固定固定代替规则代替规则, ,对明对明文文逐逐字符字符或或逐逐字符组字符组进行代替的密码进行代替的密码. . 字符组称为一个代替单位字符组称为一个代替单位. . 这里这里代替规则代替规则又称为又称为代替函数代替函数、代替表代替表或或S S盒。盒。它的它的固定性固定性是指这个代替规则与是指这个代替规则与密密钥因素钥因素和被加密的明文字符的

2、和被加密的明文字符的序号序号无关。无关。 即即相同的相同的明文字符组产生明文字符组产生相同的相同的密文字密文字符组符组. .5 例例1: 1: 汉字和符号的区位码汉字和符号的区位码( (单表代替单表代替) ) 6例例2 2 以十进值数为代替单位的代替函数则明文则明文晨五点总攻晨五点总攻 先变换为区位码先变换为区位码 1931 4669 2167 5560 1505 再被加密成密文 4624 1996 8497 0095 4050单表代替的缺点:明文字符相同,则密文字符也相同9 , 2 , 1 , 09 , 2 , 1 , 0:S105,4,8,2,1, 0,9,7,3,6S假设明文 0 1 2

3、 3 4 5 6 7 8 9密文 5 4 8 2 1 0 9 7 3 6即代替表为即代替表为: :7qkmmEckmod)()(加密变换加密变换:1, 2 , 1 , 0qZq 例例3 3 加法密码加法密码 选定选定常数常数 q 和和 k. . 明文空间明文空间= =密文空间密文空间= =qkccDmkmod)()(脱密变换脱密变换： 其中其中 读作读作 n 模模q, ,它是它是n n被被q q除后所得的余数除后所得的余数. . 如如18 18 mod7 = 4 mod7 = 4 上述加法称为上述加法称为模模q加加.qn mod890,10mod) 3()(3mmmEc加密变换为加密变换为：

4、特别地特别地,若取若取q =10 和和 k=3, ,则则脱密变换为脱密变换为：90,10mod) 3()(3cccDm 此时此时, ,明文明文: :晨五点总攻晨五点总攻 变换为区位码变换为区位码1931 4669 2167 5560 1505后就被加密成密文4264 7992 5490 8893 4838 缺点: 密文差 = 明文差10mod)(10mod)3() 3(10mod) 3(10mod) 3(21212121mmmmmmcc9( (凯撒密码) ) 这是一种对英文字母的典型逐字母加密的的加法密码,其密钥k=3。 英文字母被编码为该字母的序号 英文 A B C D X Y Z 数字 0

5、 1 2 3 23 24 25250,26mod)3()(3mmmEc加密变换为加密变换为：脱密变换为脱密变换为：250,26mod)3()(3cccDm10 这是一种对英文字母的典型逐字母加密的密码,它利用一个密钥字来构造代替表。 如如: : 若选择cipher作为密钥字,则对应代替表为:明文明文 A B C D E F G H I J K L M N O P A B C D E F G H I J K L M N O P 密文密文 C I P H E RC I P H E R A B D F G J K L M N A B D F G J K L M N 1110mod)()(kmmEck

6、例例4 4：加密变换为加密变换为: : 二、多表代替密码二、多表代替密码 根据密钥的指示，来选择加密时使用的单根据密钥的指示，来选择加密时使用的单表的方法，称为表的方法，称为多表代替多表代替密码。密码。但但 k 不再是固定常数而是密钥。不再是固定常数而是密钥。加密算法：加密算法： 明明 文：文： 晨晨 五五 点点 总总 攻攻明文序列：明文序列： 1931 4669 2167 5560 1505密钥序列：密钥序列： 4321 5378 4322 3109 11074321 5378 4322 3109 1107密文序列：密文序列： 5252 9937 6489 8669 26025252 993

7、7 6489 8669 2602若密钥序列是随机的若密钥序列是随机的, ,该密码就是该密码就是绝对安全绝对安全的的. .随机随机就是指序列的信号相互就是指序列的信号相互独立独立且且等概等概分布分布. .1226mod)()(kmmEck将对英文字母的加密变换改为：将对英文字母的加密变换改为： 当将明、密文空间均改为当将明、密文空间均改为25, 2 , 1 , 026Z这个密码就是一个著名的古典密码体制：这个密码就是一个著名的古典密码体制：维几尼亚密码维几尼亚密码（VigenereVigenere密码体制）密码体制）,21tmmm若若明文序列明文序列为为: :,21tkkk密钥序列密钥序列为：为

8、：,21tccc则则密文序列密文序列为为: :其中：其中：26mod)()(iiikikmmEci这也是序列密码的一般加密形式这也是序列密码的一般加密形式将英文字母编码为它的序号(0起算)13维维几几利利亚亚密密码码的的代代替替表表为为明文字母密钥字母密钥字母为d,明文字母为b时查表得密文字母为e1426mod)()(mkmEck将对英文字母的加密变换改为：将对英文字母的加密变换改为： 当将明、密文空间均设为当将明、密文空间均设为25, 2 , 1 , 026Z,21tmmm若若明文序列明文序列为为: :,21tkkk密钥序列密钥序列为：为：,21tccc则则密文序列密文序列为为: :其中：其

9、中：26mod)()(iiikimkmEci该密码称为该密码称为维福特密码维福特密码（BeaufortBeaufort密码体制）密码体制）此时脱密变换与加密变换完全相同，也是：此时脱密变换与加密变换完全相同，也是：26mod)()(ckcEmk15 如果将明、密文空间均改为如果将明、密文空间均改为1 , 02Z将加密变换改为：将加密变换改为：kmkmmEck定义2mod)()(,21tmmm若若明文序列明文序列为为：,21tkkk密钥序列密钥序列为：为：,21tccc则则密文序列密文序列为：为：其中：其中：iiikikmmEci)(这是众所周知的完全保密的密码体制这是众所周知的完全保密的密码体

10、制这个密码就是著名的这个密码就是著名的VernamVernam密码体制密码体制16 代替密码的安全性分析代替密码的安全性分析 1. 单表代替的优缺点单表代替的优缺点 优点优点: 明文字符的形态一般将面目全非明文字符的形态一般将面目全非 缺点缺点: (A) 明文的位置不变明文的位置不变; (B) 明文字符明文字符相同相同,则则密文字符密文字符也相同也相同; 从而导致从而导致: (I) 若明文字符若明文字符e被加密成密文字符被加密成密文字符a,则明文则明文中中e的出现次数就是密文中字符的出现次数就是密文中字符a的出现次数的出现次数; (II) 明文的跟随关系反映在密文之中明文的跟随关系反映在密文之

11、中. 因此因此,明文字符的统计规律就完全暴露在明文字符的统计规律就完全暴露在密文字符的统计规律之中密文字符的统计规律之中.形态变但位置不变形态变但位置不变17e：出现的频率约为0.127t，a，o，i，n，s，h，r：出现的频率约在0.06到0.09之间d，l：的出现频率约为0.04c，u，m，w，f，g，y，p，b ：的出现频率约在0.015到0.028之间v，k，j，x，q，z：出现的频率小于0.011819 代替密码的安全性分析代替密码的安全性分析 2. 多表代替的优缺点多表代替的优缺点 优点优点: 只要只要 (1) 多表设计合理多表设计合理,即每行中元互不相同即每行中元互不相同,每列每

12、列中元互不相同中元互不相同.(这样的表称为拉丁方表这样的表称为拉丁方表) (2) 密钥序列是随机序列密钥序列是随机序列，即具有等概性和，即具有等概性和独立性。独立性。这个多表代替就是完全保密的。这个多表代替就是完全保密的。 等概性等概性:各位置的字符取可能字符的概率相同；各位置的字符取可能字符的概率相同； 独立性：独立性：在其它所有字符都知道时，也判断在其它所有字符都知道时，也判断不出未知的字符取哪个的概率更大。不出未知的字符取哪个的概率更大。20 代替密码的安全性分析代替密码的安全性分析 2. 多表代替的优缺点多表代替的优缺点 密钥序列是随机序列意味着：密钥序列是随机序列意味着： （1）密钥

13、序列不能周期重复；）密钥序列不能周期重复； （2）密钥序列必须与明文序列等长；）密钥序列必须与明文序列等长； （3）这些序列必须在通信前分配完毕；）这些序列必须在通信前分配完毕； （4）大量通信时不实用；）大量通信时不实用； （5）分配密钥和存储密钥时安全隐患大。）分配密钥和存储密钥时安全隐患大。 缺点：缺点：周期较短时可以实现唯密文攻击。周期较短时可以实现唯密文攻击。 解决方案：解决方案：密钥序列有少量真随机的数密钥序列有少量真随机的数按固定的算法生成，只要它很像随机序列即可。按固定的算法生成，只要它很像随机序列即可。这种序列称为伪随机序列。这种序列称为伪随机序列。 21移移 位位 密密 码

14、码 对明文字符或字符组的进行对明文字符或字符组的进行位置移动位置移动的密码的密码 例例：设：设明文明文为：为： 北京科技大学信息工程学院北京科技大学信息工程学院移位方式：移位方式：S9=2,11,5,10,7,3,4,8,9,1,12,6即即:第第 i 个密文汉字就是第个密文汉字就是第S i个明文汉字个明文汉字.则则密文密文为为京学大程信科技息工北院学京学大程信科技息工北院学移位也是现代密码中必用的一种编码技术移位也是现代密码中必用的一种编码技术 22 移位密码的安全性分析移位密码的安全性分析 1. 移位密码的优缺点移位密码的优缺点 优点优点: 明文字符的位置发生变化明文字符的位置发生变化;

15、缺点缺点: (A) 明文字符的形态不变明文字符的形态不变; 从而导致从而导致: (I) 密文字符密文字符e的出现频次的出现频次也是明文字符也是明文字符e的出现次的出现次数数; 有时直接可破有时直接可破! (如密文字母全相同如密文字母全相同) 目前也有现成的破译方法目前也有现成的破译方法.移位密码优缺点总结移位密码优缺点总结: 位置变位置变但但形态不变形态不变.代替密码优缺点总结代替密码优缺点总结: 形态变形态变但但位置不变位置不变.23 结论结论: : 将代替密码和移位密码轮番使用,必然可以发挥各自的长处,克服对方的缺点!必然可以设计出安全的密码体制! 这就是现代密码的设计思想!24单表古典密

16、码的统计分析单表古典密码的统计分析原理原理：明文的统计规律在密文中能够反映出：明文的统计规律在密文中能够反映出 来，故信息泄露大。来，故信息泄露大。多表古典密码的统计分析多表古典密码的统计分析原理原理：密钥相同时，相同的明文对应相同的：密钥相同时，相同的明文对应相同的 密文。密文。252627最常用，出现频率在百分之一以上的有14个音节，它们是：de shi yi bu you zhi le ji zhe wo yen li ta dao的是 一 不有之 了机 这我们 里 他 到次常用音节有33个，它们是：zhong zi guo shang ge men he wei ye da gong

17、jian jiu xiang zhu lai sheng di zai ni xiao ke yao wu yu jie jin chan zuo jia xian quan shuo 28从三亿汉字的母体材料中，抽样二千五百万字进行双音节词词频统计，结果是：频率在一万次以上的双音节词有33个：我们三万次以上可以 他们 二万次以上进行 没有 工作 人民 生产 这个 发展 就是 问题 国家 中国 这样 革命 自己 不能 由于 这些 所以 因此 作用 一般 什么 如果 情况 必须 方法 因为 主要 要求 社会29多表古典密码的统计分析多表古典密码的统计分析步骤步骤1：首先确定密钥的长度：利用：首先

18、确定密钥的长度：利用Kasiski测试法测试法和重合指数法和重合指数法(index of coincidence)步骤步骤2：确定具体的密钥内容：交互重合指数法：确定具体的密钥内容：交互重合指数法30 寻找密文中相同的片段对，计算每对相同密文片段对寻找密文中相同的片段对，计算每对相同密文片段对之间的距离，不妨记为之间的距离，不妨记为d1,d2,di，若令密钥字的长度为，若令密钥字的长度为m，则，则m=gcd(d1,d2,di)。 定理定理1 若两个相同的明文片段之间的距离是密钥长度若两个相同的明文片段之间的距离是密钥长度的倍数，则这两个明文段对应的密文一定相同。的倍数，则这两个明文段对应的密文

19、一定相同。 反之则不然。反之则不然。 若密文中出现两个相同的密文段若密文中出现两个相同的密文段(密文段的长度密文段的长度m2)，则它们对应的明文（及密钥）将以很大的概率相同。则它们对应的明文（及密钥）将以很大的概率相同。Kasiski测试法：测试法：Kasiski于于1863年提出年提出3130.9999991126 32进一步判断密钥字的长度是否为 m=gcd(d1,d2,di). 定义1设X=x1x2xn是一个长度为n的英文字母串，则x中任意选取两个字母相同的概率定义为重合指数，用 表示。)(xIc33定理1设英文字母A，B,，Z在X中出现的次数分别为：f0,f1,f25则从X中任意选取两

20、个字母相同的概率为 证明在X中任意选取两个字母共有种 选取的可能；在X中的每个相同的字母中选取两个元素共有 种选取的可能。故易证。证毕。) 1() 1()(250nnffXIiiic2) 1(2nnCn2) 1(2iifffCi34已知每个英文字母出现的期望概率，分别记为已知每个英文字母出现的期望概率，分别记为p0,p1,p25，那么，那么X中两个元素相同的概率中两个元素相同的概率为：为： =0.065 2502)(iicpXI35对于英文的一个随机字母串，每个英文字对于英文的一个随机字母串，每个英文字母出现的期望概率均为母出现的期望概率均为1/26，则在，则在X中任中任意选取两个元素相同的概率为意选取两个元素相同的概率为=0.038.2250261icI36根据根据Kasiski测试法得到的测试法得到的m，可以将密文，可以将密文Y按照下列形式排按照下列形式排列：列：表表1将将Y排列成排列成m行行n/m列的形式，设列的形式，设m=0(modn)nmmmmnmmnmmn