现代密码学理论第二讲古典密码学

1、现代密码学理论Modern Cryptography第二讲 古典密码学代换密码及其密码分析单表代换密码与频率分析多表代换密码置换密码及其密码分析古典密码学的意义现代密码学与古典密码学的区别古典密码（Classical Cipher） 古典密码是密码学的渊源，这些密码大都比较简单，可用手工或机械操作实现加解密，现在已很少采用了。然而，研究这些密码的原理，对于理解、构造和分析现代密码都是十分有益的。代换密码和置换密码代换密码（Substitution Cipher)是明文中的每一个字符被替换成密文中的另一个字符。接收者对密文做反向替换就可以恢复出明文。置换密码(Permutation Cipher

2、)又称换位密码（Transposition Cipher)，加密过程中明文的字母保持相同，但顺序被打乱了。代换密码(Substitution Cipher) 明文字母表A ： Zq=0, 1, , q-1 明文消息是长为L个字母串，称为明文组，以m表示， m=(m0 m1, mL-1) miZq m也称作L-报文(L-gram)，它是定义在ZqL上的随机变量，ZqL是Zq上的L维矢量空间。L=1为单字母报(1-gram)，L=2为双字母报(Digrams)，L=3为三字母报(Trigrams)。明文空间m，mZqL。 密文字母集A ：Zq=(0, 1, q-1)表示。密文组 c=(c0, c1

3、, ., cL-1) cZqc是定义在L维矢量空间ZqL上的随机变量。密文空间C=c, cZqL。一般当A = A时有C =c, cZqL，即明文和密文由同一字母表构成。代换密码加密变换：明文空间到密文空间的映射： f：mc mM， c C在11的映射下，存在有逆映射f-1，使 f-1(c)=f-1f(m)=m m M ，c C加密变换通常是在密钥控制下变化的，即 c=f(m, k)=Ek(m)式中，k K ， K为密钥空间。一个密码系统就是在f和密钥k作用下，由ZqLZqL的映射，或以ZqL中的元素代换ZqL中的元素，在这意义下，称这种密码为代换密码(Substitution Cipher)

4、。L=1时，称作单字母或单码代换(Monogram Substition)，也称为流密码(Stream Cipher)。L1时称作多字母或多码代换(Polygram Substition)，也称为分组密码。代换密码代换网络 m=(m0, m1,mL-1) c=(c0, c1,cL-1) 明文源 k密钥源代换密码 一般选择q=q，即明文和密文字母表相同。此时， L=L， f可以构造成11的映射，密码没有数据扩展。 LL，则明文数据将被压缩(Compression)。函数f不是可逆的，保密通信LL。LL 可用在数据认证系统中。 单表代换(Monoalphabetic Substitution)：在

5、A = A 、q=q和L=1时，对所有明文字母，都用一个固定的代换进行加密。 多表代换(Polyalphabetic Substitution) ：在A = A 、q=q和L=1时，用一个以上的代换表进行加密。， 这是古典密码中的两种重要体制，曾得到过广泛的应用。单表代换密码单表代换密码：明文字母表到密文字母表的固定映射， f：ZqZq令明文m=m0m1.，则相应密文为 c=Ek(m)=c0c1.=f(m0)f(m1). 1移位代换密码 (Shift Substitution Cipher) 加密变换：Ek (i)=(i+k)j mod q 0 i , j q K=k0k1个字母进行代换， 。

6、优点：隐蔽或均匀化字母的自然频度，利于抗击统计分析。 矩阵变换密码，利用矩阵变换描述的多字母代换密码， f：ZLqZLq f是线性变换时可用一个Zq上的LL阶矩阵K表示，K=(kij)为密钥。若K是满秩的，则变换为一一映射，且存在有逆变换K-1，使KK-1=K-1 K=I(LL阶单位方阵)。 明文矢量： m=(m1, m2, , mL)， 密文矢量： c=(c1, c2, , cL)=mK=c 解密变换： cK-1=m.1，希尔密码Hill 1929 明文组： m=(m1, m2, , mL) 密文组： cmK+b mod q b=(b1, b2, , bL)是Zq上的L维矢量，K是Zq上的L

7、L阶满秩矩阵。式中，“”为矢量相加。： 解密运算： m(c-b)K-1 mod q 当K是单位方阵时，就退化为前面介绍的维吉尼亚密码。Hill密码的例子例子：当q=26, l=2, b=(0,0)时，Hill密码分析完全隐藏了字符(对)的频率信息惟密文攻击相对较难线性变换的安全性很脆弱，易被已知明文攻击击破。对于一个mxm的hill密码，假定有m个明文-密文对，明文和密文的长度都是m.可以把明文和密文对记为：Pj=(p1j,p2j,.pmj)和Cj=(C1j,C2j,Cmj), Cj=PjK,1j m 定义mxm的方阵X=（Pij) Y=(Cij),得到Y=XK，K=X-1Y例子：2， Pla

8、yfair Playfair在1854年发明了Playfair密码。在第一次世界大战中英国人就使用这种密码。（ invented by Charles Wheatstone in 1854, but named after his friend Baron Playfair ） Playfair将明文中的双字母组合作为一个单元对待，并将这些单元转换为密文的双字母组合。I与J视为同一字符，55变换矩阵为CIPHERABDFGKLM NOQSTUVWXYZ加密规则是按成对字母加密，规则为“相同对中的字母加分隔符(如x)，同行取右边，同列取下边，其他取交叉”，例如下面的分组加密方法。明文：ballo

9、on 单词中的ll为相同字符，所以分组为：ba lx lo on明文：he，h和e在矩阵中同一行，都取右边的字符，密文为：EC明文：dm，d和m在矩阵中同一列，都取下面的字符，密文为：MT明文：kt，k和t在矩阵中不同行也不同列，取交叉顶点上的字符，密文为：MQ明文：OD ，O和D在矩阵中不同行也不同列，取交叉顶点上的字符，密文为：TR以这个55变换矩阵为例，可以对单词进行加密，加密结果如下表所示。明文分组密文balloonba lx lo ondb sp gs ugbookbo oksr qgfillfi lx lxae sp sp Playfair密码算法有2626=676种字母对组合，字

10、符出现几率一定程度上被均匀化，基于字母频率的攻击比较困难，但依然保留了相当的结构信息。古典密码 置换密码(Permutation Cipher)。当矩阵变换密码的变换矩阵为一置换阵时，相应密码就是置换密码。亦称换位密码(Transposition Cipher)。它是对明文L长字母组中的字母位置进行重新排列，而每个字母本身并不改变。 明文：m=m1 m2,mL。， 加密变换：c=(c1,c2,cL)=E(m)=m(1) m(2) m(L)。 置换矩阵所决定置换为 解密变换： Because the cipher doesnt change any of the characters, the

11、ciphertext will have exactly the same letter frequencies as the underlying plaintext. This means that the cipher can in many cases be identified as a transposition by the close similarity of its letter statistics with the letter frequencies of the underlying language Breaking the permutation cipher

12、Because the cipher operates on blocks of size e, the plaintext and the ciphertext have to have a length which is some multiple of L. This causes two weaknesses in the system: first, the plaintext may have to be padded (if the padding is identifiable then part of the key is revealed) and second, info

13、rmation relating to the length of the key is revealed by the length of the ciphertext. To see this, note that if the ciphertext is of length i then L must be one of the divisors of i. With the different possible key sizes different possible permutations are tried to find the permutation which results in the highest number of frequent bigrams and trigrams as found in the underlying language of the plaintext. 对称密码体制主要分为分组密码和流密码对称密码的两个基本运算代换和置换(Su