(现代密码学课件）01古典密码

1、( (现代密码学课件现代密码学课件0101古典密码古典密码7同余和模运算同余和模运算n设设n n是一个正整数是一个正整数,a,a是整数是整数, ,假设假设n a=qn+r, 0rn, a=qn+r, 0rn, 那么记为那么记为 a mod n=r a mod n=rn假设假设n|(a-b)n|(a-b)，称，称a,ba,b模模n n同余，记为同余，记为ab ab (mod n)(mod n)nab (mod n) ab (mod n) 等价于等价于 (a mod n)=(b mod n) (a mod n)=(b mod n)n同余的性质同余的性质naa (mod n)aa (mod n)na

2、b (mod n) ab (mod n) ，那么，那么 ba (mod n) ba (mod n)nab (mod n) ab (mod n) ，bc (mod n) bc (mod n) ，那么，那么 ac ac (mod n)(mod n)8同余和模运算同余和模运算n求余运算求余运算a mod mod n将将a映射到集合映射到集合0,1,0,1, ,n-1,-1,求余运算称为求余运算称为模运算模运算n称与称与a模模n同余的数的全体为同余的数的全体为a的同余类，的同余类，记为记为 a ，a称为这个同余类的代表元素称为这个同余类的代表元素n定义定义Zn=0,1,.,=0,1,.,n-1-1为模

3、为模n n的同余的同余类集合。类集合。通常简记为通常简记为Zn=0,1,.,=0,1,.,n-1-1n在在Zn中可以定义模加法和模乘法中可以定义模加法和模乘法9同余和模运算同余和模运算n例：例：Z Z8 8=0,1,2,3,4,5,6,7,=0,1,2,3,4,5,6,7,模模8 8加法和乘法加法和乘法0123456700123456711234567022345670133456701244567012355670123466701234577012345601234567000000000101234567202460246303614725404040404505274163606420

4、64270765432110同余和模运算同余和模运算n模模n n的同余类集合的同余类集合Zn=0,1,.,n-1Zn=0,1,.,n-1对于模对于模加法和模乘法运算构成一个交换环。加法和模乘法运算构成一个交换环。nZnZn中并非所有中并非所有x x都有乘法逆元。都有乘法逆元。n定理定理: :设设aZn,gcd(a,n)=1,aZn,gcd(a,n)=1,那么那么a a在在ZnZn有逆有逆元元n设设p p为素数，为素数，ZpZp中每一个非零元素中每一个非零元素a a都与都与p p互互素，因此有乘法逆元，且有乘法消去律素，因此有乘法逆元，且有乘法消去律n 由由 ab=ac (mod n) ab=a

5、c (mod n) 可得可得 b=c b=c (mod n)(mod n)11模运算练习模运算练习n对于对于 mod 26 的同余类集合的同余类集合 Z26 求出所有可求出所有可逆元素的乘法逆元。逆元素的乘法逆元。a0123456789101112a-1a1314151617 18 19202122232425a-1 12二、单表代换密码二、单表代换密码n古典密码中常用的加密方法有换位和代换古典密码中常用的加密方法有换位和代换n换位密码：各个字母不变但是位置改变换位密码：各个字母不变但是位置改变略略n代换密码：每个字母用另一个字母代换代换密码：每个字母用另一个字母代换n代换密码又可以分为两种代

6、换密码又可以分为两种n单表代换密码：对单个字母逐个代换单表代换密码：对单个字母逐个代换n多表代换密码：对多个字母同时代换多表代换密码：对多个字母同时代换n单表代换密码：每个字母加密之后的结果单表代换密码：每个字母加密之后的结果总是固定的，例如总是固定的，例如 a 总是被加密为总是被加密为 w。13字母和十进制数字对应字母和十进制数字对应在加密之前我们首先需要将每个字母用等价的十进在加密之前我们首先需要将每个字母用等价的十进制数字对应：制数字对应：字母字母abcdefghijklm数字数字012345678910 1112字母字母nopqrstuvwxyz数字数字13 1415 16 17 18

7、 1920212223 24 2514凯撒密码凯撒密码n凯撒密码据传是由古罗马的凯撒大帝和前凯撒密码据传是由古罗马的凯撒大帝和前方将领联系时使用的方将领联系时使用的n加密：加密： c=E3(m) m+3 (mod 26), 0m 25n解密：解密： m=D3(c) c-3 (mod 26), 0c 2515凯撒密码凯撒密码n为方便起见，在古典密码中我们约定：明为方便起见，在古典密码中我们约定：明文用小写字母表示，而密文用大写字母表文用小写字母表示，而密文用大写字母表示。示。n因此，在凯撒密码中，字母因此，在凯撒密码中，字母 a 加密之后变加密之后变成成 D，而字母，而字母 b 加密之后变成加密

8、之后变成 E，等等。，等等。n明文明文: all of the gaul is divided into three parts n密文密文: DOO RI JDXO LV GLYLGHG LQWR WKUHH SDUWV16移位密码移位密码n凯撒密码可以推广成一般的移位密码凯撒密码可以推广成一般的移位密码n移位密码：每个字母往后移动移位密码：每个字母往后移动 k 位位n加密：加密： c=Ek(m)m+k (mod 26), 0m, k 25n解密：解密： m=Dk(c)c-k (mod 26), 0c, k 2517移位密码分析移位密码分析n移位密码的密钥空间只包含移位密码的密钥空间只包含2

9、5个密钥个密钥n很容易受到唯密文攻击穷举攻击法很容易受到唯密文攻击穷举攻击法n例如：例如：n密文：密文：PHHW PH DIWHU WKH WRJD SDUWBn依次尝试将密文中的字母分别后移依次尝试将密文中的字母分别后移1位，位，2位，位，3位，位，其中得到的有意义消息记为，其中得到的有意义消息记为明文明文nmeet me after the toga party18移位密码实例移位密码实例翻开翻开 Windows 电脑的注册表的如下目录：电脑的注册表的如下目录：HKEY_CURRENT_USERSoftwareMicrosoftWindowsCurrentVersionExplorerUs

10、erAssist75048700-EF1F-11D0-9888-006097DEACF9Count观察里面的英文内容，它是用移位密码加密观察里面的英文内容，它是用移位密码加密而成的，选出一些内容并将它解密出来。而成的，选出一些内容并将它解密出来。19仿射密码仿射密码n移位密码又可以推广成一般的仿射密码移位密码又可以推广成一般的仿射密码n加密：加密：c = Ea,b(m) am+b (mod 26)n解密：解密：m = Da,b(c) a-1(c-b) (mod 26)n其中其中na 和和 b是密钥，是密钥，0a, b 25，并且，并且gcd(a,26)=1，即即a和和26是互素的是互素的na-

11、1表示表示a的逆元，即的逆元，即a-1a1 (mod 26)20仿射密码例子仿射密码例子n假设假设a=7, b=21，那么，那么a-1=15n如果明文如果明文c为为security，那么加密之后的密，那么加密之后的密文文m为为rxjfkzyhn如果密文如果密文m为为vlxijh，那么解密之后的明文，那么解密之后的明文为为agency21对仿射密码的攻击对仿射密码的攻击n仿射密码是比较简单的密码类型，对它的仿射密码是比较简单的密码类型，对它的明文攻击都可以很轻易地成功。明文攻击都可以很轻易地成功。n如果你已经知道了两个明文字母的对应密如果你已经知道了两个明文字母的对应密文，那么你就可以从中求出密

12、钥文，那么你就可以从中求出密钥 a 和和 bn例如：道明文例如：道明文 s 和和 e 分别对应于明文分别对应于明文 R 和和 X，那么我们可以通过下式求得密钥，那么我们可以通过下式求得密钥 a 和和 b1817423abab 22一般单表密码一般单表密码n从仿射密码可以看出来，它的线性特征是从仿射密码可以看出来，它的线性特征是它的一个弱点，现在我们来看更一般的单它的一个弱点，现在我们来看更一般的单表密码表密码n它的原理是将它的原理是将26个字母作一个随机的一一个字母作一个随机的一一置换，这样得到了一个密钥置换，这样得到了一个密钥23一般单表密码例子一般单表密码例子n如果明文如果明文m是是 pl

13、ease send me the bookn那么密文那么密文c变成变成 yvsqus ustw ts jds abbf 字母字母abcdefghijklm替换替换qazwsxedcrfvt字母字母nopqrstuvw xyz替换替换gbyhnujmikolp24单字母频率表单字母频率表在某种语言中，某些字母出现的概率是根在某种语言中，某些字母出现的概率是根本固定的，例如，对于英语本固定的，例如，对于英语A 0.082B 0.015C 0.028D 0.043E 0.127F 0.022G 0.020H 0.061I 0.070J 0.002K 0.008L 0.040M 0.024N 0.06

14、7O 0.075P 0.019Q 0.001R 0.060S 0.063T 0.091U 0.028V 0.010W 0.023X 0.001Y 0.020Z 0.00125单字母频率图26频率分组表27频度最高的前30个双字母n TH HE IN ER AN RE ED ON ES STn EN AT TO NT HA ND OU EA NG ASn OR TI IS ET IT AR TE SE HI OF28其它频率特征n the 的使用频率最高，是ing的三倍，n 一半的单词以e s d t 结尾n 一半的单词以t a s w开头n y的使用频率90%都集中在单词的结尾29统计分析法统

15、计分析法n对于单表密码，虽然加密之后每个字母对于单表密码，虽然加密之后每个字母都变成了另外的字母，但是这样只是把都变成了另外的字母，但是这样只是把明文字母出现的概率转移到密文字母中明文字母出现的概率转移到密文字母中去去n因此，我们可以统计一定数目的密文中因此，我们可以统计一定数目的密文中的各字母出现的频率，出现频率最高的的各字母出现的频率，出现频率最高的几个密文字母，它所对应的明文字母就几个密文字母，它所对应的明文字母就很可能是很可能是 e 或者或者 t30统计分析法例子统计分析法例子LIVITCSWPIYVEWHEVSRIQMXLEYVEOIEWHRXEXIPFEMVEWHKVSTYLXZI

16、XLIKIIXPIJVSZEYPERRGERIMWQLMGLMXQERIWGPSRIHMXQEREKIETXMJTPRGEVEKEITREWHEXXLEXXMZITWAWSQWXSWEXTVEPMRXRSJGSTVRIEYVIEXCVMUIMWERGMIWXMJMGCSMWXSJOMIQXLIVIQIVIXQSVSTWHKPEGARCSXRWIEVSWIIBXVIZMXFSJXLIKEGAEWHEPSWYSWIWIEVXLISXLIVXLIRGEPIRQIVIIBGIIHMWYPFLEVHEWHYPSRRFQMXLEPPXLIECCIEVEWGISJKTVWMRLIHYSPHXLIQIMYLX

17、SJXLIMWRIGXQEROIVFVIZEVAEKPIEWHXEAMWYEPP XLMWYRMWXSGSWRMHIVEXMSWMGSTPHLEVHPFKPEZINTCMXIVJSVLMRSCMWMSWVIRCIGXMWYMX 31统计分析法例子统计分析法例子n统计密文字母出现次数，得到出现最统计密文字母出现次数，得到出现最高的几个高的几个n密文出现次数最多的密文出现次数最多的I应该对应明文应该对应明文中的中的 e 字母字母abcdefghijklm频率频率5290486161658992234字母字母nopqrstuvwxyz频率频率132112273012131354113632统计分析法

18、例子统计分析法例子n同样统计出同样统计出 XL 和和 XLI 分别是出现频率最分别是出现频率最高的密文双字母对和三字母对高的密文双字母对和三字母对n因此，因此，XL 对应的明文应该是对应的明文应该是 th，而，而 XLI 对应的明文应该是对应的明文应该是 then即到现在我们知道即到现在我们知道 I e，L h，X tn继续看密文中出现频率第二高字母为继续看密文中出现频率第二高字母为E，既然既然 e 和和 t 已经得到，已经得到，E 对应的明文应该对应的明文应该是是 an继续语言上的分析，最后可以得到明文继续语言上的分析，最后可以得到明文33统计分析法例子统计分析法例子 Hereupon Le

19、grand arose, with a grave and stately air, and brought me the beetle from a glass case in which it was enclosed. It was a beautiful scarabaeus, and, at that time, unknown to naturalists-of course a great prize in a scientific point of view. There were two round black spots near one extremity of the

20、back, and a long one near the other. The scales were exceedingly hard and glossy, with all the appearance of burnished gold. The weight of the insect was very remarkable, and, taking all things into consideration, I could hardly blame Jupiter for his opinion respecting it. 34三、多表代换密码三、多表代换密码n前面我们说到的

21、加密方法都是对单个字母前面我们说到的加密方法都是对单个字母来加密的，而且一个字母不管出现在什么来加密的，而且一个字母不管出现在什么位置，加密之后总是对应于同一个字母位置，加密之后总是对应于同一个字母n现在我们讲到的加密方法，对一个字母的现在我们讲到的加密方法，对一个字母的加密的结果是与该字母出现的位置有关，加密的结果是与该字母出现的位置有关，即我们需要多个密码表来加密明文即我们需要多个密码表来加密明文n包括维吉尼亚密码和博福特密码包括维吉尼亚密码和博福特密码等等35维吉尼亚密码维吉尼亚密码n选择选择n个字母作为密钥个字母作为密钥n用这用这n个字母循环地对明文加密得到密文个字母循环地对明文加密得

22、到密文36维吉尼亚密码维吉尼亚密码n步骤：步骤：n写出明文，在明文下重复写出密钥字；写出明文，在明文下重复写出密钥字；n依次使用每个字母作为移位密码的密钥，加密对应的依次使用每个字母作为移位密码的密钥，加密对应的明文字母。明文字母。n例如：密钥为例如：密钥为CIPHERn明文明文 THISPROCESSCANALSOBEEXPRESSEDTHISPROCESSCANALSOBEEXPRESSEDn密钥密钥 CIPHERCIPHERCIPHERCIPHERCIPHE CIPHERCIPHERCIPHERCIPHERCIPHE n密文密文 VPXZTIQKTZWTCVPSWFDMTETIGAHLH

23、VPXZTIQKTZWTCVPSWFDMTETIGAHLHn注意：同样的字母可以对应不同的密文注意：同样的字母可以对应不同的密文37维吉尼亚密码分析维吉尼亚密码分析n步骤步骤1：首先确定密钥的长度：首先确定密钥的长度nKasiski 测试法测试法n重合指数法重合指数法 (index of coincidence)n步骤步骤2：确定具体的密钥内容：确定具体的密钥内容38Kasiski测试法测试法n对一份用周期性多表密码加密的密文，确对一份用周期性多表密码加密的密文，确定其中所有的重复出现的字母串，计算他定其中所有的重复出现的字母串，计算他们之间的距离，并对这些距离进行因子分们之间的距离，并对这些距离进行因子分解，出现频率较高的因子很可能是密钥的解，出现频率较高的因子很可能是密钥的长度。长度。39重合指数法重合指数法n如果明文是近似随机的任意字母的排列，如果明文是近似随机的任意字母的排列，那么密文中随机两个字母的重合指数约为那么密文中随机两个字母的重合指数约为； n如果明文是正常的有意义文本，那么随机如果明文是正常的有意义文本，那么随机两