密码学基础密码(古典密码)

第一章 古典密码密码学的意义密码学的历史、现状和未来基本术语和定义古典密码和相关基础数学理论如何用精确的数学语言定义和分析古典密码2密码学的重要性密码学是信息安全技术的核心和基石，在信息安全领域起着基本的、无可替代的作用。这方面的任何重大进展，都会有可能改变信息安全技术的走向密码技术和理论的发展始终深刻影响着信息安全技术的发展和突破密码学的地位信息安全大厦安全的密码算法安全协议网络安全系统安全应用安全密码学密码学学习密码学的意义密码学相关理论和技术，是进一步学习和运用安全技术的基本功数据保密身份鉴别数字签名数字水印密码学的发展历史起源(4000年以前)有意识地隐藏信息古代密码(1900年以前)纯手工或采用简单机械古典密码(1900-1949)采用复杂机械或机电设备也有学者将1949年以前统称为古典密码传统密码(1950-1975)采用计算机技术安全基于密钥现代密码(1976以后)出现公钥密码6密码学的起源密码学(Cryptology)一词来源于两个希腊语单词隐藏(Kryptos)和书写(Graphen)隐写术(Steganography)：通过隐藏消息的存在来保护消息。常用的手段包括：隐形墨水、字符格式的变化、图形图像(水印)。7A B Apparently neutrals protest is thoroughly discounted and ignored.Isman hard hit.Blockade issue affects pretext for embargo on by products,ejecting suets and vegetable oils.:;b(Y(m=4$1m=dQg&_;c?VdStC 和dk:C-P分别为加密解密函数，满足dk(ek(x)=x，这里xP。*加密函数必须是单射函数密码算法的分类按照明文的处理方法可分为分组密码(block cipher)和流密码(stream cipher)分组密码将明文分成固定长度的组块，用同一密钥和算法对每一块加密，每块输出也是固定长度的密文。流密码又称序列密码。序列密码每次加密一位或一字节的明文，是手工和机械密码时代的主流。密码算法的分类 按照保密的条件可分为受限制的（Restricted）算法和基于密钥（key-based）的算法如果加脱密的保密性是基于保持算法的秘密，这种算法称为受限制的算法。缺陷：无法用于大的或经常变换的用户组织。如果加脱密的保密性是基于保持密钥的秘密，而算法本身可以完全公开，则称为基于密钥的算法。基于密钥的算法通常有两类：对称算法和公开密钥算法。密码算法的分类对称算法(Symmetric Algorithm)就是加密密钥和解密密钥相同或能相互推导的密码算法。秘密密钥算法或单密钥算法，要求发送者和接收者在安全通信之前，商定一个密钥。对称算法的安全性完全依赖于密钥，加密和解密表示为：EK(M)=CDK(C)=M密码算法的分类公开密钥算法(Public Key Algorithm)就是加密密钥和解密密钥无法相互推导（至少在假定的长时间内）的密码算法。加密密钥可以公开，任何人能用加密密钥加密信息，但只有相应的解密密钥才能解密信息。这里，加密密钥叫做公开密钥(Public Key)，用PuK表示EPuK(M)=C解密密钥不可公开，只为解密者(接收方)个人所持有，因此叫做私人密钥(Private Key)或秘密密钥，用PrK表示DPrK(C)=M密码算法的分类有些算法用私人密钥加密而用公开密钥解密，这种算法通常叫数字签名算法，可以表示为：EPrK(M)=CDPuK(C)=M移位密码基本思路将字母表中的每个字母向后移动若干位代替明文字母直观方便，操作简单移位密码移位密码体制的数学描述对于密码体制的五元组（P,C,K,E,D）有P=C=K=Z26对k,x,y Z26，定义ek(x)=(x+k)mod26dk(y)=(y-k)mod26mod称为“模运算模运算”如果k=3，则此密码体制为凯撒密码模运算生活中的求模运算现在是3点钟，25小时以后是几点钟？52小时以后呢？(52+3)24余7，52小时后应该是7点钟今天是星期二，9天以后是星期几？90天以后呢？(90+2)7余1，90天以后应该是星期一模运算的作用为什么引入模运算模运算可将很大的数变成较小的数，同时保持数的某些周期性的性质不变比如1和32085在26下同余，都可以表示字母B从某种意义上看，1=32085可称32085被模26约化为1密码运算涉及指数、对数等大数的运算，模运算将运算的数值始终限定在一定范围内，利于计算机快速处理模运算和同余给定任意整数a和q，以q除a，余数是r，则可以表示为a=sq+r,0rq称q为模数，r为a模q的剩余，记为 ra mod q若整数a和b有(a mod q)=(b mod q)，则称a与b在模q下同余。(即a和b的差是q的倍数)例如11和19在模4下同余(3)。模运算举例14342,2是14模4的余，214 mod 4（2也是14模3的余）通常对rq的条件并不严格要求，如 19347，7 19 mod 4负数亦可参与求模（保证余数大于零即可)(-13)(-4)43，3 (-13)mod 4 7(-3)419，19 7 mod 4 1(-1)1112，12 1 mod 11模运算的性质模运算的基本性质：若q|(a-b)，则ba mod q。如113能被4整除，则3是11模4的余；(a mod q)=(b mod q)意味着ab mod q。如3 mod 4=11 mod 4，则3是11模4的余；ab mod q等价于ba mod q。如3是11模4的余，同时4是11模3的余；若ab mod q且bc mod q，则ac mod q。如37 mod 4且711 mod 4，则311 mod 4模运算的性质模算术（不要求r 1)iinee-1iii=1(m)=(p-p)66课堂练习已知仿射密码的密钥为k=(3,10)试解密XICFP67维吉尼亚密码16世纪晚期，法国外交官维吉尼亚(Vigenere)发明，引入了“密钥”的概念68维吉尼亚密码维吉尼亚密码体制的数学描述对于密码体制的五元组（P,C,K,E,D）有P=C=K=(Z26)m，m是一个正整数对任意的k=(k1,k2,.,km)K,x=(x1,x2,.,xm)P,y=(y1,y2,.,ym)C，定义ek(x)=(x1+k1,x2+k2,.,xm+km)dk(y)=(y1-k1,y2-k2,.,ym-km)以上运算均在Z26上运行(模26)69维吉尼亚密码举例假设m=6，密钥字为CIPHER，加密明文thiscryptosystemisnotsecure密钥字对应的数字串为k=(2,8,15,7,4,17)将明文转化为对应的数字，每6个为一组19 7 8 18 2 17 24 15 19 14 18 2418 19 4 12 8 18 13 14 19 18 4 220 17 4维吉尼亚密码举例使用密钥字进行模26下的加法运算19 7 8 18 2 17 24 15 19 14 18 24 2 8 15 7 4 17 2 8 15 7 4 17 +(mod26)21 15 23 25 6 8 0 23 8 21 22 1518 19 4 12 8 18 13 14 19 18 4 2 2 8 15 7 4 17 2 8 15 7 4 17 +(mod26)20 1 19 19 12 9 15 22 8 25 8 1920 17 4 2 8 15+(mod26)22 25 19得到相应的密文为VPXZGIAXIVWPUBTTMJPWIZITWZT维吉尼亚密码的安全性密钥空间大小为26m当m=5时，密钥空间大小超过1.1107，已经不可能采用手工方法穷举搜索采用计算机穷举搜索可能不到1秒钟希尔(Hill)密码希尔密码体制的数学描述对于密码体制的五元组（P,C,K,E,D）有P=C=(Z26)m，m是一个不小于2的正整数K是定义在Z26上的mm可逆矩阵的集合取密钥kK，k为一个mm矩阵，记为(kij)，对 x=(x1,x2,.,xm)P,y=(y1,y2,.,ym)C，定义ek(x)=xkdk(y)=yk-1k-1表示k的逆矩阵以上运算均在Z26上运行(模26)73希尔密码举例设m=2，取密钥k=每个明文单元使用x=(x1,x2)来表示，对应的密文单元用y=(y1,y2)表示，则有y=xk，即(y1,y2)=(x1,x2)即y1=(11x1+3x2)mod26y2=(8x1+7x2)mod261183711837希尔密码加密假设需要加密明文july，则可将明文划分为如下两个加密单元(9,20)和(11,24)，分别进行加密变换如下(9,20)=(99+60,72+140)=(3,4)(11,24)=(121+72,88+168)=(11,22)因此密文为DELW1183711837希尔密码解密k的逆矩阵k-1=有x=yk-1，即(x1,x2)=(y1,y2)即x1=(7y1+23y2)mod26x2=(18y1+11y2)mod2671823117182311希尔密码解密对密文DELW进行解密即做如下运算(3,4)=(21+92,54+44)=(9,20)(11,22)=(77+506,198+242)=(11,24)如何计算逆矩阵？71823117182311矩阵运算矩阵的乘法设A=(ai,j)是一个lm矩阵，B=(bj,k)是一个mn矩阵，则定义矩阵的乘法AB=C=(ci,k)C是一个ln矩阵矩阵乘法不满足交换律但满足结合律mi,ki,jj,kj=1c=a b矩阵运算单位矩阵mm的矩阵中，主对角线上的元素均为1，其余元素均为0的矩阵称为单位矩阵，记为Im对任意lm矩阵A，有AIm=A；对任意mn矩阵B，有ImB=B逆矩阵mm矩阵A的逆矩阵记为A-1，满足AA-1=A-1A=Im逆矩阵具有唯一性(但不一定存在)210I01矩阵运算mm阶矩阵A=(ai,j)的行列式记为|A|或detA如果A为22阶矩阵，则detA=a1,1a2,2-a1,2a2,1如果A为33阶矩阵，则detA=a1,1a2,2a3,3+a1,2a2,3a3,1+a1,3a2,1a3,2-(a1,1a2,3a3,2+a1,2a2,1a3,3+a1,3a2,2a3,1)矩阵运算推广到一般情况如果A为mm阶矩阵，则其中i1i2.im是整数1到m的一个排列i1i2.im表示这个排列的逆序数递归法计算，定义Ai,j表示从A中删除第i行第j列所得的(m-1)(m-1)阶矩阵，则mi+ji,ji,jj=1detA=(-1)a detA1 2m12m1 2mi i Li 1i2imii i Li detA=(-1)a aa81矩阵求逆矩阵K的逆矩阵存在的充要条件是|K|非零；在模26下，逆矩阵存在的充要条件是|K|与26互素，即gcd(detK,26)=1矩阵求逆方法一：利用矩阵的初等行变换求逆矩阵如1初等行变换()A IIA 1051210010021151731421010010232168911001001254382矩阵求逆矩阵求逆方法二：K-1=(detK)-1K*K*表示K的伴随矩阵K*的第i行第j列取值为(-1)i+jdetKji，Kji是删除K的第j行第i列后形成的矩阵对二阶矩阵 有 1,11,22,12,2kkK=kk2,21,2-1-12,11,1k-kK=(detK)-kk2,21,2*2,11,1k-kK=-kk83矩阵求逆举例设矩阵是定义在Z26上的矩阵，可计算detK=7，且(detK)-1=15K的伴随矩阵为因此K-1存在且为*17115K=51481922110512K=314218911-1*211517K=15K=232162543*利用matlab进行矩阵运算定义矩阵，命令行输入：A=10,5,12;3,14,21;8,9,11求矩阵的行列式值，命令行输入：det(A)求矩阵的逆(非模运算)，命令行输入：inv(A)求伴随矩阵，命令行输入：det(A)*inv(A)mod(det(A)*inv(A),26)85课堂练习已知希尔密码的解密函数为试加密明文X=text121252(x,x)=(y,y)23置换密码置换密码体制密码体制的数学描述对于密码体制的五元组（P,C,K,E,D）有P=C=(Z26)m，m是一个正整数K是由所有定义在集合1,2,.,m上的置换组成对任意的密钥(即置换)，定义其中-1为置换的逆置换-1-1-112m(1)(2)(m)12m(1)(2)(m)e(x,x,x)=(x,x,x)d(y,y,y)=(y,y,y)87置换密码置换和逆置换的定义置换是定义在有限集X上的双射函数:XX,对任意的xX，存在唯一的xX，使得(x)=x置换的逆置换定义为-1:XX-1(x)=x 当且仅当(x)=x-1也是X上的一个置换置换密码举例设m=6，密钥为如下的置换将两行对调并重新排序可得逆置换-1如下即x123456(x)351642y123456-1(y)361524123456351642123456361524e(x,x,x,x,x,x)=(x,x,x,x,x,x)d(y,y,y,y,y,y)=(y,y,y,y,y,y)置换密码举例使用该密码加密明文shesellsseashellsbytheseashore首先将明文字母每六个分为一组：shesel|lsseas|hellsb|ythese|ashore对每组字母使用加密变换可得EESLSH|SALSES|LSHBLE|HSYEET|HRAEOS即密文为EESLSHSALSESLSHBLEHSYEETHRAEOS置换密码的特性置换密码实际上是希尔密码的特殊形式给定集合1,2,.,m的一个置换，定义置换的关联置换矩阵K=(Ki,j)mm，其元素值为使用矩阵K为密钥的希尔密码等价于使用置换为密钥的置换密码，且则i,j若i=(j)1k=否0-1-1K=K置换密码的特性前面置换密码的例子中，等价的希尔密码加密密钥为加密函数为e(x)=xK=(x1,x2,x3,x4,x5,x6)=(x3,x5,x1,x6,x4,x2)001000000001100000K=000010010000000100001000000001100000000010010000000100置换密码的特性解密密钥为解密函数为d(y)=yK-1=(y1,y2,y3,y4,y5,y6)=(y3,y6,y1,y5,y2,y4)-1001000000010100000K=000001000100010000001000000010100000000001000100010000流密码前面的密码体制中，连续的明文元素使用相同的密钥K来加密y=y1y2.=ek(x1)ek(x2).这种类型的密码体制称为分组密码分组密码的不足需要设计复杂的加密函数以提高安全性经常需要对明文进行填充(padding)操作以确保分组长度完整如果k较短，则容易遭到穷举攻击流密码设计思路将明文看作字符串或比特串，并逐字符或者逐位进行加密为了防止密钥穷举，使用和明文信息一样长的密钥(无限)流z=z1,z2.进行加密这种密码体制称为流密码(或序列密码)可以使用非常简单的加密算法(如简单的异或运算)关键是如何生成密钥流1212z1z2y=y y=e(x)e(x)流密码的代表弗纳姆(Vernam)密码1918年，Gillbert Vernam建议密钥与明文一样长并且没有统计关系的密钥内容，他采用的是二进制数据：加密：Ci=PiKi 解密：Pi=CiKi关键：构造和消息一样长的随机密钥异或运算位的异或运算00=0,01=1,101,11=0异或运算等价模2加法运算特性：两次异或运算以后还原，可设计加密和脱密完全相同的函数。97流密码特点运算简单实时性强安全性依赖与密钥流的产生方法流密码的分类按密钥的周期性分类周期流密码；存在某个固定的正整数r，使得密钥流每隔r个字符（或者比特）以后重复非周期流密码对任何正整数密钥流都不重复如一次一密乱码本流密码的分类按密钥的产生方式分类同步流密码密钥流的产生独立于消息流;例如分组密码的OFB(输出反馈)模式异步流密码每一个密钥字符是由前面n个明文或密文字符推导出来的，其中n为定值。例如分组密码的CFB(密码反馈)模式同步流密码使用某种算法，由一个初始密钥变换出和明文串相互独立的密钥流。定义如下：同步流密码是一个六元组(P,C,K,L,E,D)和一个函数g，且满足如下条件1 P,C,K分别是明文、密文、密钥的有限集2 L是密钥流字母表有限集3 g是密钥流生成器，g使用密钥kK作为输入，产生无限长的密钥流Z=z1z2.，其中ziL4 对任意的zL，都有一个加密规则(函数)ez:PCE和相应的解密规则(函数)dz:CPD，并且对每个明文xP满足dz(ez(x)=x流密码和分组密码的关系分组密码可以看做流密码的特殊情况如维吉尼亚密码，可以看做是一种短周期的同步流密码ek(x)=(x1+k1,x2+k2,.,xm+km)dk(y)=(y1-k1,y2-k2,.,ym-km)密钥流定义为即密钥流是周期为m的密钥序列k1k2.kmk1k2.kmk1k2.km.分组密码可以用于生成密钥序列11iiimkimzzim密钥流的产生理想的密钥流是随机不重复的真随机抛硬币、掷骰子、噪声发生器收发双方难以同步无周期性密钥和密文等长一次一密乱码本难以在高带宽的信道上使用103密钥流的产生真正的随机序列往往难以实用，实际多用线性递归关系产生伪随机序列例如设m=4，(a1,a2,a3,a4)为(0,0,0,1)密钥流按如下线性递归关系产生：ai+4=(ai+ai+3)mod2(等价于ai+4=aiai+1)产生的密钥序列为a1a2a3a4a5.，即0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1.周期为24-1=15(a1,a2,a3,a4)通常被称为初始向量密钥流的产生这种方式可以使用硬件轻易实现，此硬件称为线性反馈移位寄存器(LFSR,Linear Feedback Shift Register)anan-1a2a1.c1c2cn-=1c0=1输出ak（a1，a2，.，an）输出序列为输出序列为ak a1 a2.an.ai(t+1)=ai+1(t)an(t+1)=cna1(t)cn-1a2(t).c1an(t)ai(t+1)=ai+1(t)a4(t+1)=a1(t)a4(t)ta4a3a2a1ta4a3a2a101000901101110010001121110111001311111201004011113001051011140001601011510007101016110081101.a4a3a2a1输出akc4=1c1=1返回106 LFSRLFSR示例说明示例说明周期为24115cn1的n级LFSR其输出序列为周期序列，且周期数r满足r2n1若n级LFSR的输出序列的周期达到最大2n1，则称之为m序列f(x)=c0+c1x+c2x2+.+cnxn描述LFSR的反馈连接状态，称为特征多项式可以证明，一个n级LFSR能产生m序列的充要条件是它的特征多项式为一个n次本原多项式107本原多项式若一个n次多项式f(x)的阶为2n1，即满足条件：f(x)为既约多项式f(x)可整除（x2n-11)f(x)不能整除（xp1)，其中p 2，设，设r为不超过为不超过n-2的任一正整数，则任何的任一正整数，则任何1的的r游程表示存在串游程表示存在串01.10（r+2位位），其游程数目为），其游程数目为2n-r-2，于是，在每一周期中出现，于是，在每一周期中出现1的游程个数为的游程个数为 1 2n-2 同样，出现同样，出现0的游程个数为的游程个数为2n-2，游程总数为，游程总数为2n-1 eg.n=4，000111101011001；2212nn rr m序列的特性位移相加特性 m序列和它的位移序列模2相加后所得序列仍是该m序列的某个位移序列。设序列ak为m序列，且满足递推关系：ah+n=cnah cn-1ah+1 .c1ah+n-1 位移位：ah+n+=cnah+cn-1ah+1+.c1ah+n-1+，则ah+n ah+n+cn（ah ah+）cn-1（ah+1 ah+1+）.c1（ah+n-1 ah+n-1+）自相关特性 设两子串为at和at+，则at at+中为0的位的数目正好是两个子串中对应位相同的位数，则：R（）（n d ）/r1/2n1 （0)当0时，R（）1 利用LFSR设计加密算法同步序列密码实现anan-1a2a1.c1c2cn-=1c0=1输出ak密钥流明文密文异步流密码同步流密码存在周期问题异步流密码思路密钥流z的产生不但与密钥K有关，而且还与明文元素(x1,x2,.,xi-1)或密文元素(y1,y2,.,yi-1)有关自动密钥密码通过K和明文产生密钥流115自动密钥密码自动密钥密码体制的数学描述自动密钥密码是一个六元组(P,C,K,L,E,D)，满足以下条件P=C=K=L=Z26密钥流定义：z1=k K，zi=xi-1，i 2对任意的 z K，x,y Z26，定义ez(x)=(x+z)mod26dz(y)=(y-z)mod26自动密钥密码举例假设k=8，明文为rendezvous加密过程如下：首先将明文转换为整数序列:17 4 13 3 4 25 21 14 20 18根据z1=k=8，zi=xi-1得到密钥流为：8 17 4 13 3 4 25 21 14 20将对应的元素相加并模26得到：25 21 17 16 7 3 20 9 8 12字母形式的密文为ZVRQHDUJIM解密过程略 利用LFSR设计加密算法序列密码密码反馈加密anan-1a2a1.c1c2cn-=1明文m密文c加密过程：加密过程：e1m1 ，e2m2 c1e1，.ekmk 1 knkn en+1mn+1 ，en+hmn+h 11niniica22niniicaniniki kca11ki kice11ni niice1ni nihice 利用LFSR设计加密算法序列密码密码反馈解密anan-1a2a1.c1c2cn-=1明文m密文c解密密钥和加密密钥相同，都是系数c1，c2，.，cn和初始状态(a1，a2，.an）密码分析前面从穷举密钥的角度简单分析了各类密码体制的安全性，其前提是分析者知道使用的密码体制(密码算法)。如果不知道密码体制，分析工作将困难得多将安全性建立在保持算法的秘密基础之上，这类算法称为受限制的算法缺陷：无法用于大的或经常变换用户的组织。如果加脱密的保密性是基于保持密钥的秘密，而算法本身可以完全公开，则称为基于密钥的算法密码分析目标密码分析学是在不知道密钥的情况下，恢复出明文的科学。分析者是在已知密码体制（密码算法及其实现的全部详细资料）的前提下来破译使用的密钥。从分析者掌握的条件区分，常用的密码分析攻击有四类密码分析方法四类常用的密码分析攻击方式唯密文攻击(Ciphertext-only Attack)分析者有一些消息的密文，这些密文都用同一加密算法加密，任务是尽可能恢复这些密文，或推算出加密的密钥。已知明文攻击(Known-plaintext Attack)分析者不但有一些消息的密文，还知道这些密文对应的明文，任务是推算出加密的密钥，或推导出可以对新密文进行解密的算法密码分析方法四类常用的密码分析攻击方式选择明文攻击(Chosen-plaintext Attack)分析者可获得对加密机的暂时访问，因此他能自由选择明文串并构造出相应的密文串，任务是推算出加密的密钥，或推导出可以对新密文进行解密的算法选择密文攻击(Chosen-ciphertext Attack)分析者可获得对解密机的暂时访问，因此他能自由选择密文串并构造出相应的明文串，任务是推算出加密的密钥，或推导出可以对新密文进行解密的算法课堂练习截获使用移位密码加密的密文如下MQTSVXERXQIWWEKI试分析其对应的明文124唯密文攻击分析古典密码最困难的分析条件在密文片段足够长的情况下，能分析大多数古典密码通常需要用到英文字母的频率分析和反复猜测能有效分析单表替代密码多表替代难度加大只能分析可阅读的文本数据借助计算机能大大提高分析效率125英文字母频率分析利用26个字母在英文文字出现的不同频率猜测单表替代字母英文字母频率分析26个字母在英文语言中出现的频率排序E出现的频率远高于其他字母其次为T、A、O、I、N、S、H、R再次为D、L更次为C、U、M、W、F、G、Y、P、B最次为V、K、J、X、Q、Z许多双字母的固定序列经常出现TH、HE、IN、ER、AN、RE、ED、ON、ES、ST、EN、AT、TO、NT、HA、ND、OU、EA、NG、AS、OR、TI、IS、ET、IT、AR、TE、SE、HI、OF127英文字母频率分析还有一些经常出现的3字母固定序列THE、ING、AND、HER、ERE、ENT、THA、NTH、WAS、ETH、FOR、DTH根据经验，有些字母不可能组合出现在一个单词中，如果出现可作为单词边界进行分析简单代替密码的分析原理根据密文字母出现频率的高低进行猜测和验证得到的密文越长，越符合统计规律仿射密码的密码分析仿射密码体制的数学描述对于密码体制的五元组（P,C,K,E,D）有P=C=Z26K=(a,b)Z26Z26:gcd(a,26)=1对任意的k=(a,b)K,x,yZ26，定义ek(x)=(ax+b)mod26dk(y)=a-1(y-b)mod26gcd(a,26)=1意味着a和26互质a-1是a关于模26乘法的逆分析目标：根据密文得到a和b的值分析方法：首先分析出现频率最高的字符，只需要猜中两个字母的代替，就能解出a和b仿射密码分析举例得到仿射密码的密文如下FMXVEDKAPHEFRBNDKRXRSREFMORUDSDKDVSHVUFEDKAPRKDLYEVLRHHRH分析密文中每个字母的出现频数记录如下字母字母频数频数字母字母频数频数字母字母频数频数字母字母频数频数字母字母频数频数A2B1C0D7E5F4G0H5I,J0K5L2M2N1O1P2Q0R8S3T0U2V4W0X2Y1Z0仿射密码分析举例以上密文中出现的最大频数的几个密文字母依次是R、D、E、H、K、S、F、V假设R是e的加密，D是t的加密即ek(4)=17,ek(19)=3，因为ek(x)=ax+b，得到方程组解方程组可知a=6,b=19，因为a不满足与26互质的条件，因此猜测错误4a+b=1719a+b=13仿射密码分析举例以上密文中出现的最大频数的几个密文字母依次是R、D、E、H、K、S、F、V再假设R是e的加密，E是t的加密，继续使用该方法得到a=13仍不满足与26互质的条件再假设H是t的加密，得到a=8仍无效再假设K是t的加密，得到a=3,b=5，使用此密钥尝试解密得到可阅读的明文为algorithmsarequitegeneraldefinitionsofarithmeticprocesses代换密码的密码分析代换密码体制的数学描述对于密码体制的五元组（P,C,K,E,D）有P=C=Z26K是由26个数字0,1,2,.,25的所有可能的置换组成对任意的置换K，定义e(x)=(x)d(y)=-1(y)-1表示置换的逆置换分析目标：根据密文得到置换分析技巧：先分析频率高的密文，再根据英文单词中的字母组合规律进行分析代换密码分析举例得到代换密码的密文如下YIFQFMZRWQFYVECFMDZPCVMRZWNMDZVEJBTXCDDUMJNDIFEFMDZCDMQZKCEYFCJMYRNCWJCSZREXCHZUNMXZNZUCDRJXYYSMRTMEYIFZWDYVZVYFZUMRZCRWNZDZJJXZWGCHSMRNMDHNCMFQCHZJMXJZWIEJYUCFWDJNZDIR代换密码分析举例分析密文中各字母出现的频数Z出现频率最高其次是C,D,F,J,M,R,Y字母字母频数频数字母字母频数频数字母字母频数频数字母字母频数频数字母字母频数频数A0B1C15D13E7F11G1H4I5J11K1L0M16N9O0P1Q4R10S3T2U,V5W8X6Y10Z20代换密码分析举例Z出现的频率远高于其他字母，推测dk(Z)=e以Z开头的双字母中，ZW出现的次数最多，推测dk(W)=d；以W结尾的双字母中，RW出现数次且R也多次出现，推测dk(R)=n；NZ出现多次而ZN未出现，推测dk(N)=h根据以上猜测得到一些残缺的明文如ne?ndhe(其密文为RZCRWNZ)，在英语字典中搜索不到匹配的单词，猜测?为a，即dk(C)=a代换密码分析举例nh(对应密文为RN)不可能出现在一个单词中，因此密文中的RNM解密为nh?，其中h是单词的开头且后面应该是一个元音字母M在密文中出现的频率很高，因此对应i或o；考虑到ai出现的频率高于ao，推测dk(M)=io是较常出现的字母，对应的密文应该是D,F,J,Y中的一个，因为密文中出现了CDM/CFM/CJM这样的组合，推测dk(Y)=o(单词中不会出现aoi)代换密码分析举例剩下的三个高频密文字母D,F,J，应该是明文r,s,t的某种映射密文组合NMD(hi?)多次出现，猜测dk(D)=s密文组合HCMF(hai?)出现，猜测dk(F)=r剩下dk(J)=t密文组合HNCMF(?hair)出现，猜测dk(H)=c代换密码分析举例目前猜测出的代替规则有Z-e，W-d，R-n，N-h，C-a，M-i，Y-o，D-s，F-r，J-t，H-c根据该规则部分解密密文如下o-r-riend-ro-arise-a-inedhise-t-ass-itYIFQFMZRWQFYVECFMDZPCVMRZWNMDZVEJBTXCDDUMJhs-r-riseasi-d-a-orationhadta-en-ace-hi-eNDIFEFMDZCDMQZKCEYFCJMYRNCWJCSZREXCHZUNMXZhe-asnt-oo-in-i-o-redso-e-ore-ineandhesettNZUCDRJXYYSMRTMEYIFZWDYVZVYFZUMRZCRWNZDZJJ-ed-ac-inhischair-aceti-ted-to-ardsthes-nXZWGCHSMRNMDHNCMFQCHZJMXJZWIEJYUCFWDJNZDIR代换密码分析举例最后从英文单词、语法等语言规律猜测其他代替规则，最终得到明文Our friend from Paris examined his empty glass with surprise,as if evaporation had taken place while he wasnt looking.I poured some more wine and he settled back in his chair,face tilted up towards the sun 维吉尼亚密码的密码分析维吉尼亚密码体制的数学描述对于密码体制的五元组（P,C,K,E,D）有P=C=K=(Z26)m，m是一个正整数对任意的k=(k1,k2,.,km)K,x=(x1,x2,.,xm)P,y=(y1,y2,.,ym)C，定义ek(x)=(x1+k1,x2+k2,.,xm+km)dk(y)=(y1-k1,y2-k2,.,ym-km)以上运算均在Z26上运行(模26)分析目标：根据密文得到k1,k2,.,km141维吉尼亚密码的密码分析维吉尼亚密码的分析难点多表替代，使简单的频率分析方法失效如果知道密钥字长度m，可以分解为m个单表替代密码分析任务确认密钥字长度m是关键Kasiski法重合指数法142维吉尼亚密码的密码分析Kasiski测试法确定密钥字长度m19世纪普鲁士少校Kasiski提出可粗略猜测m，密文越长越准确基本步骤1.在密文中标出重复的三个或多个字符结构；2.对每一个字符结构，记下结构的起始位置；3.计算相邻的起始点的距离；4.对每个距离求出所有因数；5.密钥的长度为步骤4中出现的某一因数143维吉尼亚密码的密码分析Kasiski测试法举例明文：wearediscoveredsaveyourself密钥：deceptive密文：ZICVTWQNGRZGVTWAVZHCQYGLMGJ测试过程：1.在密文中标出重复的字符结构VTW；2.两个字符结构的起始位置分别为4和13；3.两个起始点的距离是9；4.9的因数有3和9；5.根据步骤4出现的因数，确定密钥的可能长度是3位或9位。维吉尼亚密码的密码分析重合指数法确定密钥字长度m重合指数的定义一个字母串X中随机取出两个字母，这两个字母恰好相同的概率，记为Ic(X)对于完全随机的字母串，Ic(X)=26*(1/26)2=1/260.038对于英文文本，其中pi是字母表中第i个字母在英文中出现的概率重合指数的特点单表代替密码中，密文的重合指数和明文相同252cii=0I(X)=p0.065145维吉尼亚密码的密码分析重合指数法确定密钥字长度m密文重合指数的计算方法对于长度为n的密文串X，首先统计密文字母A,B,C,.,Z出现的频数(次数)，记为f0,f1,f2,.,f25计算25iii=0cf(f-1)I(X)=n(n-1)维吉尼亚密码的密码分析重合指数法确定密钥字长度m分析原理假设密文串为Y=y1y2.yn，m是密钥字长度将Y分割成m个子串Y1=y1y1+my1+2m.Y2=y2y2+my2+2m.Ym=ymy2my3m.对于每个Yi，其密文采用的是单表代替方法(相同的密文对应相同的明文)，其重合指数Ic(Yi)应接近0.065通过尝试不同的m，找到重合指数最接近0.065的那个维吉尼亚密码分析举例得到维吉尼亚密码加密的密文如下CHREEVOAHMAERATBIAXXWTNXBEEOPHBSBQMQEQERBWRVXUOAKXAOSXXWEAHBWGJMMQMNKGRFVGXWTRZXWIAKLXFPSKAUTEMNDCMGTSXMXBTUIADNGMGPSRELXNJELXVRVPRTULHDNQWTWDTYGBPHXTFALJHASVBFXNGLLCHRZBWELEKMSJIKNBHWRJGNMGJSGLXFEYPHAGNRBIEQJTAMRVLCRREMNDGLXRRIMGNSNRWCHRQHAEYEVTAQEBBIPEEWEVKAKOEWADREMXMTBHHCHRTKDNVRZCHRCLQOHPWQAIIWXNRMGWOIIFKEE148维吉尼亚密码分析举例Kasiski测试法分析密文串CHR出现在1,166,236,276,286这几个位置，到第一个位置的距离分别是165,235,275,285，他们只有一个公因子5，故猜测密钥字长度为5149维吉尼亚密码分析举例重合指数法分析尝试不同的密钥字长度，计算密文的重合指数mIc(Y1)Ic(Y2)Ic(Y3)Ic(Y4)IcY510.04520.0460.04130.0430.0500.04740.0420.03900450.04050.0630.0680.0690.0610.072维吉尼亚密码分析举例分析密钥字确定密钥字长度后，可以使用频率分析方法分别解密Y1,Y2,.,YmY1=CVABWEBQBUAWWQRWWXANTBDPXXRDWBFAXCWMNJJFAIACNRNCATBWKDMCDCQQXWKY2=HOEITESEWOOEGMFTIFUDSTNSNVTNDPASNHESBGSEGEMRDRSHEAIEORTHNHOANOEY3=RARANOBQRASAJNVRAPTCXUGRJRUQTHLVGRLJHNGYNQRRGINRYQPVEEBRVRHIRIEY4=EHAXXPQEVKXHMKGZKSEMMIMEEVLWYXJBLZEIWMLPRJVELMRQEEEKWMHTRCPIMIY5=EMTXBHMRXXXBMGXXLKMGXAGLLPHTGTHFLBKKRGXHBTLMXGWHVBEAAXHKZLWWGF维吉尼亚密码分析举例分析密钥字方法对每一个Yi，猜测不同的ki值，计算其中p0,p1,.p25是字母a,b,.,z在英文中出现的概率其中f0,f1,.f25是字母A,B,.,Z在密文中出现的次数n是Yi的长度(即n/m)当g=ki时，pi fi+g/n，Mg 0.06525i+ggii=0fM=pn维吉尼亚密码分析举例建立Mg分析表iMg(Yi),g=0,1,2,.,2510.035 0.031 0.036 0.037 0.035 0.039 0.028 0.028 0.048 0.061 0.039 0.032 0.0400.038 0.038 0.044 0.036 0.030 0.042 0.043 0.036 0.033 0.049 0.043 0.041 0.03620.069 0.044 0.032 0.035 0.044 0.034 0.036 0.033 0.029 0.031 0.042 0.045 0.040 0.045 0.046 0.042 0.037 0.032 0.034 0.037 0.032 0.034 0.043 0.032 0.026 0.0473 0.048 0.029 0.042 0.043 0.044 0.034 0.038 0.035 0.032 0.049 0.035 0.031 0.0350.066 0.035 0.038 0.036 0.045 0.027 0.035 0.034 0.034 0.036 0.035 0.046 0.04040.045 0.032 0.033 0.038 0.060 0.034 0.034 0.034 0.050 0.033 0.033 0.043 0.040 0.033 0.029 0.036 0.040 0.044 0.037 0.050 0.034 0.034 0.039 0.044 0.038 0.03550.034 0.031 0.035 0.044 0.047 0.037 0.043 0.038 0.042 0.037 0.033 0.032 0.0360.037 0.036 0.045 0.032 0.029 0.044 0.072 0.037 0.027 0.031 0.048 0.036 0.037维吉尼亚密码分析举例分析结果k1=9,k2=0,k3=13,k4=4,k5=19，对应密钥串为K=JANET明文为The almond tree was in tentative blossom.The days were longer,often ending with magnificent evenings of corrugated pink skies.The hunting season was over,with hounds and guns put away for six months.The vineyards were busy again as the well-organized farmers treated their wines and the more lackadaisical neighbors hurried to do the pruning they should have done in Nonvember重合指数法的推广用法希尔密码的密码分析希尔密码体制的数学描述对于密码体制的五元组（P,C,K,E,D）有P=C=(Z26)m，m是一个不小于2的正整数K是定义在Z26上的mm可逆矩阵的集合取密钥kK，k为一个mm矩阵，记为(kij)，对 x=(x1,x2,.,xm)P,y=(y1,y2,.,ym)C，定义ek(x)=xkdk(y)=yk-1k-1表示k的逆矩阵以上运算均在Z26上运行(模26)分析目标：获得矩阵kij155希尔密码的密码分析希尔密码使得明密文之间呈现复杂的线性关系，较难采用唯密文攻击进行分析如果能获得一些明密文对，则较容易破解出密钥KY=XKK=X-1Y条件：X可逆156希尔密码分析举例假设明文friday利用m=2的希尔密码加密，得到的密文为PQCFKU根据字母编码关系可知，ek(5,17)=(15,16)，ek(8,3)=(2,5)，ek(0,24)=(10,20)由前两个等式可得到矩阵方程521615K38175157希尔密码分析举例计算X的逆矩阵有因此可用ek(0,24)=(10,20)对K进行验证如果不知道m，可采用尝试法15219381751 -1911516719K=X Y=2152583158LFSR流密码的密码分析LFSR流密码加密过程yi=(xi+zi)mod 2(z1,z2,.,zm)是LFSR初态密钥流产生的递归公式分析目标：获得LFSR的结构LFSR的初态z1,z2,.,zm产生密钥流的递归公式(或抽头序列c0,c1,.,cm-1)m-1m+ij i+jj2j=0z=c zmod2,i1,cZLFSR流密码的密码分析和希尔密码一样，唯密文攻击LFSR流密码有较大难度已知明文攻击可以有效分析此类密码如果能得到长度不小于2m的明文-密文对，可以轻易求出LFSR初态和抽头序(假设m已知)初态可直接将明密文求和(模2)得到LFSR流密码的密码分析由密钥序列产生方式可知m-1m+ij i+jj2j=0z=c zmod2,i1,cZ12m23m+1m+1m+22m01m-1mm+12m-1zz.zzz.z(z,z,.,z)=(c,c,.,c).zz.zLFSR流密码的密码分析可得到-112m23m+101m-1m+1m+22mmm+12m-1zz.zzz.z(c,c,.,c)=(z,z,.,z).zz.zLFSR流密码分析举例获得5级LFSR流密码加密的密文串101101011110010和相应的明文串011001111111000首先将明密文相加(模2)得到密钥比特流11010 01000 01010可知LFSR初态为11010，抽头序为c0,c1,c2,c3,c4LFSR流密码分析举例可知计算012341101010100(0,1,0,0,0)=(c,c,c,c,c)010011001000100111010010011010010010010010000110010010110010010110LFSR流密码分析举例可得到因此密钥流递归公式为zi+5=(zi+zi+3)mod2LFSR结构为初态为11010012340100110010(c,c,c,c,c)=(0,1,0,0,0)=(1,0,0,1,0)000010101110110k1k3k4k5移位输出异或(模2加法)k2本章习题本章习题解答