第2讲--古典密码.ppt

1、1,第二章 古典密码,2,补充内容密码算法的分类,保密内容 受限制的（restricted)算法 算法的保密性基于保持算法的秘密 基于密钥（key-based)的算法 算法的保密性基于对密钥的保密,3,补充内容密码算法的分类,密钥 对称密码算法（symmetric cipher) 加密密钥和解密密钥相同，或实质上等同，即从一个易于推出另一个，又称秘密密钥算法或单密钥算法 非对称密钥算法（asymmetric cipher) 加密密钥和解密密钥不相同，从一个很难推出另一个 又称公开密钥算法（public-key cipher) 。 公开密钥算法用一个密钥进行加密, 而用另一个进行解密其中的加密密

2、钥可以公开,又称公开密钥（public key)，简称公钥。解密密钥必须保密,又称私人密钥 （private key)私钥，简称私钥,4,补充内容密码算法的分类,明文处理方式 分组密码（block cipher) 将明文分成固定长度的组，用同一密钥和算法对每一块加密，输出也是固定长度的密文。 流密码（stream cipher) 又称序列密码。序列密码每次加密一位或一字节的明文。,5,密码学的目标（1）,保密性 完整性 认证 不可否认,隐藏消息的真实含义和目的。,典型的实现保密性方法：对称加密算法。,分组密码,流密码,不存在一个活动的攻击者参与情况下确保信息和数据的正确性。,单向散列函数,单向

3、性 能避免冲突(碰撞),随机选取M,计算散列值,比较,给定Y,给定M1,计算散列值,比较,随机选取M2,计算散列值,预映射碰撞约束,第二预映射碰撞约束,没有密钥,6,密码学的目标（2）,保密性 完整性 认证 不可否认,指身份特征或者消息实体的代表的属性。,在敌人可能会对消息进行伪造的前提下，采取额外的步骤以便接收者能够对消息的完整性进行验证。,认证算法：消息认证码（MAC）,需要秘密密钥来阻止任何人对标记进行伪造,具有同意负责任的属性。,不可否认和认证的性质十分相似，从实现角度上讲，它们大都使用了相同的基本原理。 当使用者具备签名能力时，他的公钥签名才能称为不可否认性“设备”。,7,第二章 古

4、典密码,学习本章目的： 1. 学习基本的密码编制原理; 2.了解早期编制密码的基本方法; 3. 为进一步学习现代密码的编制打下基础。,8,基本编码技术的分类 (1) 代替密码 利用预先设计的代替规则,对明文逐字符或逐字符组进行代替的密码. 分为单表代替和多表代替两种 (2) 移位密码 对各字符或字符组进行位置移动的密码. (3) 加减密码 将明文逐字符或逐字符组与乱数相加或相减的密码.,9,我们将重点介绍 代替密码,10,一、单表代替密码： 利用预先设计的固定代替规则,对明文逐字符或逐字符组进行代替的密码. 字符组称为一个代替单位.,这里代替规则又称为代替函数、代替表或S盒。它的固定性是指这个

5、代替规则与密钥因素和被加密的明文字符的序号无关。 即相同的明文字符组产生相同的密文字符组.,不论明文字符在什么位置，同一个明文字符都用同一个密钥加密,11,1980年，为了使每一个汉字有一个全国统一的代码，我国颁布了第一个汉字编码 的国家标准： GB2312-80信息交换用汉字编码字符集基本集，这个字符集是我国中文信息处理技术的发展基础，也是目前国内所有汉字系统的统一标准。 国标码是一个四位十六进制数，区位码是一个四位的十进制数，每个国标码或区位码都对应着一个唯一的汉字或符号，但因为十六进制数我们很少用到，所以大家常用的是区位码，它的前两位叫做区码，后两位叫做位码。 汉字库分布情况如下： 一级

6、汉字 16-55区 二级汉字 56-87区 三级汉字 1-9区 空闲未用 10-15区 在区位码中，01-09区为特殊字符，10-55区为一级汉字(3755个最常用的汉字，按拼音字母的次序排列)，56-87区为二级汉字(3008个汉字，按部首次序排列)， 在区位码汉字输入方法中,汉字编码无重码,在熟练掌握汉字的区位码后,录入汉字的速度是很快的，但若想记忆住全部区位码是相当困难的。,区位码,12,例1: 汉字和符号的区位码(单表代替),2211,2277,13,例2 以十进值数为代替单位的代替函数,则明文晨五点总攻 先变换为区位码 1931 4669 2167 5560 1505 再被加密成密文

7、 4624 1996 8497 0095 4050 单表代替的缺点:明文字符相同,则密文字符也相同,14,脱密变换：,其中 读作 n 模q,它是n被q除后所得的余数. 如18 mod7 = 4 上述加法称为模q加.,15,加密变换为：,特别地,若取q =10 和 k=3,则,脱密变换为：,此时,明文:晨五点总攻 变换为区位码 1931 4669 2167 5560 1505 后就被加密成密文 4264 7992 5490 8893 4838 缺点: 密文差 = 明文差,16,例4: Caesar密码(凯撒密码) 这是一种对英文字母的典型逐字母加密的的加法密码,其密钥k=3。 英文字母被编码为该

8、字母的序号 英文 A B C D X Y Z 数字 0 1 2 3 23 24 25,加密变换为：,脱密变换为：,17,例5:标准字头密码(又称密钥字密码) 这是一种对英文字母的典型逐字母加密的密码,它利用一个密钥字来构造代替表。,如: 若选择cipher作为密钥字,则对应代替表为: 明文 A B C D E F G H I J K L M N O P 密文 C I P H E R A B D F G J K L M N ,18,例6：仿射密码,英文字母被编码为该字母的序号 英文 A B C D X Y Z 数字 0 1 2 3 23 24 25,密钥为025之间的数字对(a,b) 要求：a与

9、26的最大公约数必须为1，即gcd(a,26)=1。,加密变换：,脱密变换：,a-1是a的逆元,如：设(a,b)=(7,21)，对security加密。,s=18, 7*18+21(mod26)=17, sr,e=4, 7*4+21(mod26)=23, ex,c=2, 7*2+21(mod26)=9, cj,y=24, 7*24+21(mod26)=7, yh,security对应的密文： rxjfkzyh,19,例6：仿射密码,如：设(a,b)=(7,21)，对vlxijh脱密。,a-1*a(mod26)=1,7-1mod26=?,7*15mod26=1,7-1mod26=15,v=21,

10、 15(21-21)mod26=0, va,l=11, 15(11-21)mod26=6, lg,h=7, 15(7-21)mod26=24, hy,vlxijh对应的明文：agency,20,密钥为025之间的数字对(a,b) 要求：a与26的最大公约数必须为1，即gcd(a,26)=1。,讨论仿射密码中为什么gcd(a,26)=1 ？,1 3 5 7 9 11 15 17 19 21 23 25,1 9 15 3 7,a,a-1,21,例4：加密变换为:,二、多表代替密码 根据密钥的指示，来选择加密时使用的单表的方法，称为多表代替密码。,但 k 不再是固定常数而是密钥。 加密算法： 明 文

11、： 晨 五 点 总 攻 明文序列： 1931 4669 2167 5560 1505 密钥序列： 4321 5378 4322 3109 1107 密文序列： 5252 9937 6489 8669 2602 若密钥序列是随机的,该密码就是绝对安全的. 随机就是指序列的信号相互独立且等概分布.,22,将对英文字母的加密变换改为：,当将明、密文空间均改为,这个密码就是一个著名的古典密码体制： 维几尼亚密码（Vigenere密码体制）,若明文序列为:,密钥序列为：,则密文序列为:,其中：,这也是序列密码的一般加密形式,将英文字母编码为它的序号(0起算),23,维几利亚密码的代替表为,明文字母,密钥

12、字母,密钥字母 为 d , 明文字母为 b 时,查表得密文字母 为 e,24,将对英文字母的加密变换改为：,当将明、密文空间均设为,则密文序列为:,其中：,该密码称为维福特密码（Beaufort密码体制）,此时脱密变换与加密变换完全相同，也是：,25,如果将明、密文空间均改为,将加密变换改为：,若明文序列为：,密钥序列为：,则密文序列为：,其中：,这是众所周知的完全保密的密码体制,这个密码就是著名的Vernam密码体制,一次一密,26,代替密码的安全性分析 1. 单表代替的优缺点 优点: 明文字符的形态一般将面目全非 缺点: (A) 明文的位置不变; (B) 明文字符相同,则密文字符也相同;

13、从而导致: (I) 若明文字符e被加密成密文字符a,则明文中e的出现次数就是密文中字符a的出现次数; (II) 明文的跟随关系反映在密文之中. 因此,明文字符的统计规律就完全暴露在密文字符的统计规律之中.形态变但位置不变,27,单表代换密码分析,以仿射密码为例 已知： ）明文是标准英语。 ）加密法为仿射密码。 ）每个明文字母被唯一的密文字母代替。,破解关键,28,e：出现的频率约为0.127 t，a，o，i，n，s，h，r：出现的频率约在0.06到0.09之间 d，l：的出现频率约为0.04 c，u，m，w，f，g，y，p，b ：的出现频率约在0.015到0.028之间 v，k，j，x，q，z

14、：出现的频率小于0.01,字母的分布依赖于明文文本的类型：诗歌、标语、科技等。 频率顺序：ETAONIRSHDLUCMPFYWGBVJKQZ 有用的经验： 字母A，I，H不常作为单词的结尾； 字母n前面的字母80%都是元音字母； “h”常出现在“e”的前面，几乎从不出现在其后； “e”,”n”,”r”出现在起始位置比终了位置更少； ,29,例 假设从仿射密码获得的密文为： FMXVEDKAPHFERBNDKRXRSREFMORUDSDKDVSHVUFEDKAPRKDLYEVLRHHRH 仅有57个密文字母，但足够分析仿射密码。,统计：最高频的密文字母是：R(8次)，D（6次），E，H，K（各五

15、次），F，S，V（各四次）。,频率顺序：ETAONIRSHDLUCMPFYWGBVJKQZ,假设： R是e的加密且D是t的加密，因为e和t分别是两个最常见的字母。,仿射密码：,30,继续假定R是e的加密且K是t的加密。这产生了a=3,b=5 ，至少是一个合法的密钥。剩下的事是计算相应于k（3，5）的解密函数，然后解密密文看是否得到了有意义的英文串。容易证明这是一个有效的密钥。 最后的密文是： algorithms are quite general definitions of arithmetic processes,留给同学们练习！,31,代替密码的安全性分析 2. 多表代替的优缺点 优点

16、: 只要 (1) 多表设计合理,即每行中元互不相同,每列中元互不相同.(这样的表称为拉丁方表) (2) 密钥序列是随机序列，即具有等概性和独立性。 这个多表代替就是完全保密的。 等概性:各位置的字符取可能字符的概率相同； 独立性：在其它所有字符都知道时，也判断不出未知的字符取哪个的概率更大。,32,代替密码的安全性分析 2. 多表代替的优缺点 密钥序列是随机序列意味着： （1）密钥序列不能周期重复； （2）密钥序列必须与明文序列等长； （3）这些序列必须在通信前分配完毕； （4）大量通信时不实用； （5）分配密钥和存储密钥时安全隐患大。 缺点：周期较短时可以实现唯密文攻击。 解决方案：密钥序列有少量真随机的数按固定的算法生成，只要它很像随机序列即可。这种序列称为伪随机序列。,分析Vigenre密码的方法,33,移 位 密 码 对明文字符或字符组的进行位置移动的密码 例：设明文为： 解放军电子技术学院 移位方式：S9=2,5,7,3,4,8,9,1,6 即:第 i 个密文汉字就是第S i个明文汉字. 则密文为 放子术军电学院解技 移位也是现代密码中必用的一种编码技术,34,移位密码的安全性分析 1.