第2讲--古典密码

1第二章古典密码2补充内容－密码算法的分类保密内容受限制的（restricted)算法算法的保密性基于保持算法的秘密基于密钥（key-based)的算法算法的保密性基于对密钥的保密3补充内容－密码算法的分类密钥对称密码算法（symmetriccipher)加密密钥和解密密钥相同，或实质上等同，即从一个易于推出另一个，又称秘密密钥算法或单密钥算法非对称密钥算法（asymmetriccipher)加密密钥和解密密钥不相同，从一个很难推出另一个又称公开密钥算法（public-keycipher)。公开密钥算法用一个密钥进行加密,而用另一个进行解密其中的加密密钥可以公开,又称公开密钥（publickey)，简称公钥。解密密钥必须保密,又称私人密钥（privatekey)私钥，简称私钥4补充内容－密码算法的分类明文处理方式分组密码（blockcipher)将明文分成固定长度的组，用同一密钥和算法对每一块加密，输出也是固定长度的密文。流密码（streamcipher)又称序列密码。序列密码每次加密一位或一字节的明文。5密码学的目标（1）保密性完整性认证不可否认隐藏消息的真实含义和目的。典型的实现保密性方法：对称加密算法。分组密码流密码不存在一个活动的攻击者参与情况下确保信息和数据的正确性。单向散列函数单向性能避免冲突(碰撞)随机选取M计算散列值比较给定Y给定M1计算散列值比较随机选取M2计算散列值预映射碰撞约束第二预映射碰撞约束没有密钥6密码学的目标（2）保密性完整性认证不可否认指身份特征或者消息实体的代表的属性。在敌人可能会对消息进行伪造的前提下，采取额外的步骤以便接收者能够对消息的完整性进行验证。认证算法：消息认证码（MAC）需要秘密密钥来阻止任何人对标记进行伪造具有同意负责任的属性。不可否认和认证的性质十分相似，从实现角度上讲，它们大都使用了相同的基本原理。当使用者具备签名能力时，他的公钥签名才能称为不可否认性“设备”。7第二章古典密码学习本章目的：1.学习基本的密码编制原理;2.了解早期编制密码的基本方法;3.为进一步学习现代密码的编制打下基础。8基本编码技术的分类(1)代替密码利用预先设计的代替规则,对明文逐字符或逐字符组进行代替的密码.分为单表代替和多表代替两种(2)移位密码对各字符或字符组进行位置移动的密码.(3)加减密码将明文逐字符或逐字符组与乱数相加或相减的密码.9我们将重点介绍代替密码10一、单表代替密码：利用预先设计的固定代替规则,对明文逐字符或逐字符组进行代替的密码.字符组称为一个代替单位.这里代替规则又称为代替函数、代替表或S盒。它的固定性是指这个代替规则与密钥因素和被加密的明文字符的序号无关。即相同的明文字符组产生相同的密文字符组.不论明文字符在什么位置，同一个明文字符都用同一个密钥加密111980年，为了使每一个汉字有一个全国统一的代码，我国颁布了第一个汉字编码的国家标准：GB2312-80《信息交换用汉字编码字符集》基本集，这个字符集是我国中文信息处理技术的发展基础，也是目前国内所有汉字系统的统一标准。国标码是一个四位十六进制数，区位码是一个四位的十进制数，每个国标码或区位码都对应着一个唯一的汉字或符号，但因为十六进制数我们很少用到，所以大家常用的是区位码，它的前两位叫做区码，后两位叫做位码。汉字库分布情况如下：一级汉字16-55区二级汉字56-87区三级汉字1-9区空闲未用10-15区在区位码中，01-09区为特殊字符，10-55区为一级汉字(3755个最常用的汉字，按拼音字母的次序排列)，56-87区为二级汉字(3008个汉字，按部首次序排列)，在区位码汉字输入方法中,汉字编码无重码,在熟练掌握汉字的区位码后,录入汉字的速度是很快的，但若想记忆住全部区位码是相当困难的。区位码12例1:汉字和符号的区位码(单表代替)2211227713例2以十进值数为代替单位的代替函数则明文晨五点总攻先变换为区位码19314669216755601505再被加密成密文46241996849700954050单表代替的缺点:明文字符相同,则密文字符也相同}9,,2,1,0{}9,,2,1,0{:S[10]{5,4,8,2,1,0,9,7,3,6}S假设明文0123456789密文5482109736即代替表为:14qkmmEckmod)()(加密变换:}1,,2,1,0{qZq例3加法密码选定常数q和k.明文空间=密文空间=qkccDmkmod)()(脱密变换：其中读作n模q,它是n被q除后所得的余数.如18mod7=4上述加法称为模q加.qnmod1590,10mod)3()(3mmmEc加密变换为：特别地,若取q=10和k=3,则脱密变换为：90,10mod)3()(3cccDm此时,明文:晨五点总攻变换为区位码19314669216755601505后就被加密成密文42647992549088934838缺点:密文差=明文差10mod)(10mod)]3()3[(]10mod)3(10mod)3[(21212121mmmmmmcc16例4:Caesar密码(凯撒密码)这是一种对英文字母的典型逐字母加密的的加法密码,其密钥k=3。英文字母被编码为该字母的序号英文ABCD…XYZ数字0123…232425250,26mod)3()(3mmmEc加密变换为：脱密变换为：250,26mod)3()(3cccDm17例5:标准字头密码(又称密钥字密码)这是一种对英文字母的典型逐字母加密的密码,它利用一个密钥字来构造代替表。如:若选择cipher作为密钥字,则对应代替表为:明文ABCDEFGHIJKLMNOP…密文CIPHERABDFGJKLMN…18例6：仿射密码英文字母被编码为该字母的序号英文ABCD…XYZ数字0123…232425密钥为0~25之间的数字对(a,b)要求：a与26的最大公约数必须为1，即gcd(a,26)=1。加密变换：26mod)(bamc脱密变换：26mod)(1bcam25,0cma-1是a的逆元如：设(a,b)=(7,21)，对security加密。s=18,7*18+21(mod26)=17,sre=4,7*4+21(mod26)=23,exc=2,7*2+21(mod26)=9,cj……y=24,7*24+21(mod26)=7,yhsecurity对应的密文：rxjfkzyh19例6：仿射密码加密变换：26mod)(bamc脱密变换：26mod)(1bcam25,0cma-1是a的乘法逆元如：设(a,b)=(7,21)，对vlxijh脱密。a-1*a(mod26)=17-1mod26=?7*15mod26=17-1mod26=15v=21,15(21-21)mod26=0,val=11,15(11-21)mod26=6,lg……h=7,15(7-21)mod26=24,hyvlxijh对应的明文：agency20密钥为0~25之间的数字对(a,b)要求：a与26的最大公约数必须为1，即gcd(a,26)=1。加密变换：26mod)(bamc脱密变换：26mod)(1bcam25,0cma-1是a的乘法逆元讨论仿射密码中为什么gcd(a,26)=1？？1357911151719212325191537aa-12110mod)()(kmmEck例4：加密变换为:二、多表代替密码根据密钥的指示，来选择加密时使用的单表的方法，称为多表代替密码。但k不再是固定常数而是密钥。加密算法：明文：晨五点总攻明文序列：19314669216755601505密钥序列：43215378432231091107密文序列：52529937648986692602若密钥序列是随机的,该密码就是绝对安全的.随机就是指序列的信号相互独立且等概分布.2226mod)()(kmmEck将对英文字母的加密变换改为：当将明、密文空间均改为}25,,2,1,0{26Z这个密码就是一个著名的古典密码体制：维几尼亚密码（Vigenere密码体制）,,,,21tmmm若明文序列为:,,,,21tkkk密钥序列为：,,,,21tccc则密文序列为:其中：26mod)()(iiikikmmEci这也是序列密码的一般加密形式将英文字母编码为它的序号(0起算)23维几利亚密码的代替表为明文字母密钥字母密钥字母为d,明文字母为b时查表得密文字母为e2426mod)()(mkmEck将对英文字母的加密变换改为：当将明、密文空间均设为}25,,2,1,0{26Z,,,,21tmmm若明文序列为:,,,,21tkkk密钥序列为：,,,,21tccc则密文序列为:其中：26mod)()(iiikimkmEci该密码称为维福特密码（Beaufort密码体制）此时脱密变换与加密变换完全相同，也是：26mod)()(ckcEmk25如果将明、密文空间均改为}1,0{2Z将加密变换改为：kmkmmEck定义2mod)()(,,,,21tmmm若明文序列为：,,,,21tkkk密钥序列为：,,,,21tccc则密文序列为：其中：iiikikmmEci)(这是众所周知的完全保密的密码体制这个密码就是著名的Vernam密码体制一次一密26代替密码的安全性分析1.单表代替的优缺点优点:明文字符的形态一般将面目全非缺点:(A)明文的位置不变;(B)明文字符相同,则密文字符也相同;从而导致:(I)若明文字符e被加密成密文字符a,则明文中e的出现次数就是密文中字符a的出现次数;(II)明文的跟随关系反映在密文之中.因此,明文字符的统计规律就完全暴露在密文字符的统计规律之中.形态变但位置不变27单表代换密码分析以仿射密码为例已知：１）明文是标准英语。２）加密法为仿射密码。３）每个明文字母被唯一的密文字母代替。破解关键28e：出现的频率约为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.01•字母的分布依赖于明文文本的类型：诗歌、标语、科技等。•频率顺序：ETAONIRSHDLUCMPFYWGBVJKQZ•有用的经验：字母A，I，H不常作为单词的结尾；字母n前面的字母80%都是元音字母；“h”常出现在“e”的前面，几乎从不出现在其后；“e”,”n”,”r”出现在起始位置比终了位置更少；……29例假设从仿射密码获得的密文为：FMXVEDKAPHFERBNDKRXRSREFMORUDSDKDVSHVUFEDKAPRKDLYEVLRHHRH仅有57个密文字母，但足够分析仿射密码。统计：最高频的密文字母是：R(8次)，D（6次），E，H，K（各五次），F，S，V（各四次）。频率顺序：ETAONIRSHDLUCMPFYWGBVJKQZ假设：R是e的加密且D是t的加密，因为e和t分别是两个最常见的字母。26mod)(baxxe26mod)()(1byaydk),(26Zyx仿射密码：30继续假定R是e的加密且K是t的加密。这产生了a=3,b=5，至少是一个合法的密钥。剩下的事是计算相应于k＝（3，5）的解密函数，然后解密密文看是否得到了有意义的英文串。容易证明这是一个有效的密钥。最后的密文是：algorithmsarequitegeneraldefinitionsofarithmeticprocesses留给同学们练习！31代替密码的安全性分析2.多表代替的优缺点优点:只要(1)多表设计合理,即每行中元互不相同,每列中元互不相同.(这样的表称为拉丁方表)(2)密钥序列是随机序列，即具有等概性和独立性。这个多表代替就