1第二章古典密码王滨解放军信息工程大学电子技术学院二系2005年3月2日《应用密码学》课程幻灯片(电院24队)2联系方式E-mail:otto916@sina.comQQ:32874546Tel:38532(O)Adr:17013上节课内容复习明文、密文、密钥(概念)加密、解密(概念及函数的表示方法)密码体制加、脱密密钥,加、脱密函数破译攻击方法(穷举攻击中根据密钥量来推算攻击时间)4上节课补充内容-密码算法的分类保密内容受限制的(restricted)算法算法的保密性基于保持算法的秘密基于密钥(key-based)的算法算法的保密性基于对密钥的保密5上节课补充内容-密码算法的分类密钥对称密码算法(symmetriccipher)加密密钥和解密密钥相同,或实质上等同,即从一个易于推出另一个,又称秘密密钥算法或单密钥算法非对称密钥算法(asymmetriccipher)加密密钥和解密密钥不相同,从一个很难推出另一个又称公开密钥算法(public-keycipher)。公开密钥算法用一个密钥进行加密,而用另一个进行解密其中的加密密钥可以公开,又称公开密钥(publickey),简称公钥。解密密钥必须保密,又称私人密钥(privatekey)私钥,简称私钥6上节课补充内容-密码算法的分类明文处理方式分组密码(blockcipher)将明文分成固定长度的组,用同一密钥和算法对每一块加密,输出也是固定长度的密文。流密码(streamcipher)又称序列密码。序列密码每次加密一位或一字节的明文。7第二章古典密码学习本章目的:1.学习基本的密码编制原理;2.了解早期编制密码的基本方法;3.为进一步学习现代密码的编制打下基础。8基本编码技术的分类(1)代替密码利用预先设计的代替规则,对明文逐字符或逐字符组进行代替的密码.分为单表代替和多表代替两种(2)移位密码对各字符或字符组进行位置移动的密码.(3)加减密码将明文逐字符或逐字符组与乱数相加或相减的密码.9我们将重点介绍代替密码10一、单表代替密码:利用预先设计的固定代替规则,对明文逐字符或逐字符组进行代替的密码.字符组称为一个代替单位.这里代替规则又称为代替函数、代替表或S盒。它的固定性是指这个代替规则与密钥因素和被加密的明文字符的序号无关。即相同的明文字符组产生相同的密文字符组.11例1:汉字和符号的区位码(单表代替)2211227712例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即代替表为:13qkmmEckmod)()(加密变换:}1,,2,1,0{qZq例3加法密码选定常数q和k.明文空间=密文空间=qkccDmkmod)()(脱密变换:其中读作n模q,它是n被q除后所得的余数.如18mod7=4上述加法称为模q加.qnmod1490,10mod)3()(3mmmEc加密变换为:特别地,若取q=10和k=3,则脱密变换为:90,10mod)3()(3cccDm此时,明文:晨五点总攻变换为区位码19314669216755601505后就被加密成密文42647992549088934838缺点:密文差=明文差10mod)(10mod)]3()3[(]10mod)3(10mod)3[(21212121mmmmmmcc15例4:Caesar密码(凯撒密码)这是一种对英文字母的典型逐字母加密的的加法密码,其密钥k=3。英文字母被编码为该字母的序号英文ABCD…XYZ数字0123…232425250,26mod)3()(3mmmEc加密变换为:脱密变换为:250,26mod)3()(3cccDm16例5:标准字头密码(又称密钥字密码)这是一种对英文字母的典型逐字母加密的密码,它利用一个密钥字来构造代替表。如:若选择cipher作为密钥字,则对应代替表为:明文ABCDEFGHIJKLMNOP…密文CIPHERABDFGJKLMN…1710mod)()(kmmEck例4:加密变换为:二、多表代替密码根据密钥的指示,来选择加密时使用的单表的方法,称为多表代替密码。但k不再是固定常数而是密钥。加密算法:明文:晨五点总攻明文序列:19314669216755601505密钥序列:43215378432231091107密文序列:52529937648986692602若密钥序列是随机的,该密码就是绝对安全的.随机就是指序列的信号相互独立且等概分布.1826mod)()(kmmEck将对英文字母的加密变换改为:当将明、密文空间均改为}25,,2,1,0{26Z这个密码就是一个著名的古典密码体制:维几尼亚密码(Vigenere密码体制),,,,21tmmm若明文序列为:,,,,21tkkk密钥序列为:,,,,21tccc则密文序列为:其中:26mod)()(iiikikmmEci这也是序列密码的一般加密形式将英文字母编码为它的序号(0起算)19维几利亚密码的代替表为明文字母密钥字母密钥字母为d,明文字母为b时查表得密文字母为e2026mod)()(mkmEck将对英文字母的加密变换改为:当将明、密文空间均设为}25,,2,1,0{26Z,,,,21tmmm若明文序列为:,,,,21tkkk密钥序列为:,,,,21tccc则密文序列为:其中:26mod)()(iiikimkmEci该密码称为维福特密码(Beaufort密码体制)此时脱密变换与加密变换完全相同,也是:26mod)()(ckcEmk21如果将明、密文空间均改为}1,0{2Z将加密变换改为:kmkmmEck定义2mod)()(,,,,21tmmm若明文序列为:,,,,21tkkk密钥序列为:,,,,21tccc则密文序列为:其中:iiikikmmEci)(这是众所周知的完全保密的密码体制这个密码就是著名的Vernam密码体制22代替密码的安全性分析1.单表代替的优缺点优点:明文字符的形态一般将面目全非缺点:(A)明文的位置不变;(B)明文字符相同,则密文字符也相同;从而导致:(I)若明文字符e被加密成密文字符a,则明文中e的出现次数就是密文中字符a的出现次数;(II)明文的跟随关系反映在密文之中.因此,明文字符的统计规律就完全暴露在密文字符的统计规律之中.形态变但位置不变23e:出现的频率约为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.0124例:UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZVUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSXEPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ02468101214ABCDEFGHIJKLMNOPQRSTUVWXYZ频率密文字母频率25代替密码的安全性分析2.多表代替的优缺点优点:只要(1)多表设计合理,即每行中元互不相同,每列中元互不相同.(这样的表称为拉丁方表)(2)密钥序列是随机序列,即具有等概性和独立性。这个多表代替就是完全保密的。等概性:各位置的字符取可能字符的概率相同;独立性:在其它所有字符都知道时,也判断不出未知的字符取哪个的概率更大。26代替密码的安全性分析2.多表代替的优缺点密钥序列是随机序列意味着:(1)密钥序列不能周期重复;(2)密钥序列必须与明文序列等长;(3)这些序列必须在通信前分配完毕;(4)大量通信时不实用;(5)分配密钥和存储密钥时安全隐患大。缺点:周期较短时可以实现唯密文攻击。解决方案:密钥序列有少量真随机的数按固定的算法生成,只要它很像随机序列即可。这种序列称为伪随机序列。27移位密码对明文字符或字符组的进行位置移动的密码例:设明文为:解放军电子技术学院移位方式:S[9]={2,5,7,3,4,8,9,1,6}即:第i个密文汉字就是第S[i]个明文汉字.则密文为放子术军电学院解技移位也是现代密码中必用的一种编码技术28移位密码的安全性分析1.移位密码的优缺点优点:明文字符的位置发生变化;缺点:(A)明文字符的形态不变;从而导致:(I)密文字符e的出现频次也是明文字符e的出现次数;有时直接可破!(如密文字母全相同)目前也有现成的破译方法.移位密码优缺点总结:位置变但形态不变.代替密码优缺点总结:形态变但位置不变.29结论:将代替密码和移位密码轮番使用,必然可以发挥各自的长处,克服对方的缺点!必然可以设计出安全的密码体制!这就是现代密码的设计思想!30下节课的内容古典密码的统计分析31作业:P21第2.1题.