古典密码技术

第1章密码学概述第2章古典密码技术第3章分组密码第4章公钥密码体制第5章散列函数与消息鉴别第6章数字签名技术第7章密钥管理技术第8章身份鉴别技术第9章序列密码基础第10章密码技术应用课程主要内容2/67第2章古典密码技术本章主要内容•替代密码•置换密码周期置换密码列置换密码•转轮机密码•古典密码的统计分析单表替代密码分析多表替代密码分析对Hill密码的已知明文分析这些密码算法大多都十分简单，现在已经很少在实际应用中使用了。但是研究这些密码的原理，对于理解、构造和分析现代实用的密码都是很有益的。3/67第2章古典密码技术2.1替代密码(substitutioncipher)•替代是古典密码中用到的最基本的处理技巧之一；•替代密码是指先建立一个替换表，加密时将需要加密的明文依次通过查表，替换为相应的字符，明文字符被逐个替换后，生成无任何意义的字符串，即密文，替代密码的密钥就是其替换表；•根据密码算法加解密时使用替换表多少的不同，替代密码又可分为单表替代密码和多表替代密码。单表替代密码:密码算法加解密时使用一个固定的替换表；多表替代密码:密码算法加解密时使用多个替换表。4/67第2章古典密码技术（1）一般单表替代密码一般单表替代密码的原理是以26个英文字母集合上的一个置换π为密钥，对明文消息中的每个字母依次进行变换。可描述为：明文空间M和密文空间C都是26个英文字母的集合，密钥空间K={π：Z26→Z26|π是置换}，是所有可能置换的集合。对任意π∈K，定义:加密变换：eπ(m)=π(m)=c解密变换：dπ(c)=π-1(c)=m，π-1是π的逆置换。2.1.1单表替代密码5/67第2章古典密码技术abcdefghijklmnopqrstuvwxyzDEFGHIJKLMNOPQRSTUVWXYZABCcaesarcipherFDHVDUFLSKHU明文密文明文a变成了密文D明文c变成了密文F明文e变成了密文H密码替代表6/67第2章古典密码技术一般单表替代密码算法特点：密钥空间K很大，|K|=26!=4×1026，破译者穷举搜索计算不可行，1微秒试一个密钥，遍历全部密钥需要1013年。移位密码体制是替换密码体制的一个特例，它仅含26个置换做为密钥空间。密钥π不便记忆。针对一般替换密码密钥π不便记忆的问题，又衍生出了各种形式单表替代密码。2.1.1单表替代密码（续）7/67第2章古典密码技术（2）移位密码明文空间M、密文空间C都是和密钥空间K满足260,1,2,...,25PCKZ2.1.1单表替代密码（续）表2.1字母数字映射表即把26个英文字母与整数0，1，2，…，25一一对应，如表：8/67第2章古典密码技术加密变换，E={E:Z26→Z26,Ek(m)=m+k(mod26)|m∈M,k∈K}解密变换，D={D:Z26→Z26,Dk(c)=c－k(mod26)|c∈C,k∈K}解密后再把Z26中的元素转换英文字母。显然，移位密码是前面一般单表替代密码的一个特例。当移位密码的密钥k=3时，就是历史上著名的凯撒密码（Caesar）。根据其加密函数特点，移位密码也称为加法密码。2.1.1单表替代密码（续）abcdefghijklmnopqrstuvwxyzDEFGHIJKLMNOPQRSTUVWXYZABCcaesarcipherFDHVDUFLSKHU明文密文9/67第2章古典密码技术（3）仿射密码仿射密码也是一般单表替代密码的一个特例，是一种线性变换。仿射密码的明文空间和密文空间与移位密码相同，但密钥空间为K={(k1，k2)|k1，k2∈Z26，gcd(k1，26)=1}对任意m∈M，c∈C，k=(k1，k2)∈K，定义加密变换为：c=Ek(m)=k1m+k2(mod26)相应解密变换为：m=Dk(c)=k1－1(c－k2)(mod26)2.1.1单表替代密码（续）其中，。很明显，k1=1时即为移位密码，而k2=0则称为乘法密码。1111mod26kk10/67第2章古典密码技术【例2.3】设明文消息为china，密钥k=(k1,k2)=(9,2)试用仿射密码对其进行加密，然后再进行解密。22207213()98222mod2613215022kunEmwcpc2.1.1单表替代密码（续）明文消息对应的数字序列为（2，7，8，13，0），用仿射密码对明文进行加密如下：112()()(mod26)3(2)(mod26)(36)(mod26)kcccckkD解密变换为：113k12()(mod26)92(mod26)kmmmkkE解：利用扩展的欧几里德算法可计算出加密变换为：11/67第2章古典密码技术密文消息为unwpc(20,13,22,15,2)。而解密过程如下：20621367()32268mod2615613260kchDmina2.1.1单表替代密码（续）即恢复明文消息为china。仿射密码要求(k1,26)=1，否则就会有多个明文字母对应一个密文字母的情况。由于与26互素的整数有12个，故仿射密码密钥空间大小为|K|=12×26=312。若将仿射密码的加密函数换为多项式函数时，即为多项式密码。12/67第2章古典密码技术（4）密钥短语密码选用一个英文短语或单词串作为密钥，去掉其中重复的字母得到一个无重复字母的字符串，然后再将字母表中的其它字母依次写于此字母串后，就可构造出一个字母替代表。如密钥为key时，替代表如表2.2所示。2.1.1单表替代密码（续）当选择上面的密钥进行加密时，若明文为“china”，则密文为“yfgmk”。显然，不同的密钥可以得到不同的替换表，对于明文为英文单词或短语的情况时，密钥短语密码最多可能有26!=4×1026个不同的替换表。13/67第2章古典密码技术最大问题：单表替代密码表现出明文中单字母出现的频率分布与密文中相同。英文单字母出现概率顺序：e,t,o,a,n,i,…….，th,er,re,an,……，the,ing,ion,…而单表代替密码算法的最大缺陷就在于具有单字母一一的对应关系，它没有将明文字母出现的概率掩藏起来，故在实际应用中，可利用自然语言的统计特性来破译这种密码。例如，破译者可以统计出所截获密文中的高频率出现的代码，与表中高频率字(字母)相对应，使用猜字法，找出其中的对应关系，推断出密钥，从而破解密码。（书P28，表2.4）（5）单表替换密码的安全性分析14/67英文字母出现频率(不同文献类略有差别)字母出现频率字母出现频率a③0.0856n⑤0.0707b0.0139o④0.0797c0.0279p0.0199d0.0378q0.0012e①0.1304r⑥0.0677f0.0289s0.0607g0.0199t②0.1045h0.0528u0.0249i⑦0.0627v0.0092j0.0013w0.0149k0.0042x0.0017l0.0339y0.0199m0.0249z0.0008第2章古典密码技术15/67英语字母中常见的组合第2章古典密码技术16/67第2章古典密码技术多表替代密码的特点是使用了两个或两个以上的替代表。著名的弗吉尼亚密码和Hill密码等均是多表替代密码。（1）弗吉尼亚密码（Vigenere）弗吉尼亚密码是最古老而且最著名的多表替代密码体制之一，与位移密码体制相似，但弗吉尼亚密码的密钥是动态周期变化的。该密码体制有一个参数n。在加解密时，同样把英文字母映射为0－25的数字再进行运算，并按n个字母一组进行变换。明文空间、密文空间及密钥空间都是长度为n的英文字母串的集合。因此可表示为：26nPCKZ2.1.2多表替代密码单表替换密码局限：明文字母(字)与密文字母(字)一一对应。17/67第2章古典密码技术加密变换定义如下：设密钥k=(k1,k2,…,kn),明文m=(m1,m2,…,mn),加密变换为：Ek(m)=(c1,c2,…,cn),其中ci=(mi+ki)(mod26)，i=1,2,…,n对密文c=(c1,c2,…,cn),解密变换为：Dk(c)=(m1,m2,…,mn),其中mi=(ci－ki)(mod26)，i=1,2,…,n2.1.2多表替代密码（续）18/67第2章古典密码技术【例2.4】设密钥k=cipher，明文消息appliedcryptosystem，试用弗吉尼亚密码对其进行加密，然后再进行解密。解：由密钥k=cipher，得n=6，密钥对应的数字序列为(2，8，15，7，4，17)。然后将明文按每6个字母进行分组，并转换这些明文字母为相应的数字，再用模26加上对应密钥数字，其加密过程如表2.3所示。2.1.2多表替代密码（续）密文为：CXTSMVFKGFTKQANZXVO。（解密，略）明文appliedcryptosystem01515118432172415191418241819412密钥cipherciphercipherc2815741728157417281574172密文22341812215106519101601325232114CXTSMVFKGFTKQANZXVO19/67（2）希尔（Hill）密码Hill密码算法的基本思想是将n个明文字母通过线性变换，将它们转换为n个密文字母。解密只需做一次逆变换即可。算法的密钥K=﹛Z26上的n×n可逆矩阵﹜，明文M与密文C均为n维向量，记为第2章古典密码技术1111121222112()nijnnnnnnnnmckkkmckMCKkmckkk，，＝2.1.2多表替代密码（续）加密运算：Ek(M)=K•M=C(mod26)解密运算：Dk(C)=K–1•C=M(mod26)其中，K–1称为K在模26上的逆矩阵，有：K•K–1=K–1•K=I；这里I为单位矩阵20/67第2章古典密码技术定理2.1：假设A=(ai,j)为一个定义在Z26上的n×n矩阵，若A在模26上可逆，则有：A–1=(detA)–1A*(mod26)；这里A*为矩阵A的伴随矩阵。11837K118det11738(mod26)7724(mod26)53(mod26)137例如，假设A=，是一个Z26上的2×2矩阵，它的行列式1,11,22,12,2aaaa1,12,21,22,1detAaaaa2,21,2112,11,1(det)mod26aaAAaa是可逆的，那么：在n=2的情况下，有下列推论：21/67第2章古典密码技术这时1－1mod26=1，所以K的逆矩阵为：111118787181mod26373112311K1122118617822(mod26)371411612cmwKcmm33441181417822(mod26)3736311cmwKcml2.1.2多表替代密码（续）【例2.5】设明文消息为good，试用n＝2，密钥的Hill密码对其进行加密，然后再进行解密。11837K解：将明文划分为两组：(g，o)和(o，d)，即（6，14）和（14，3）。加密过程如下：因此，good的加密结果是wmwl。显然，明文不同位置的字母“o”加密成的密文字母不同。22/67第2章古典密码技术为了解密，由前面