《古典密码体制》PPT课件.ppt

1、2020/9/8,1,应 用 密 码 学,张仕斌 万武南 张金全 孙宣东编著,西安电子科技大学出版社,二00九年十二月,2020/9/8,2,第2章 古典密码体制,2学时,2020/9/8,3,知识点：, 隐写术 替换（代替）密码技术 换位密码技术 古典密码体制的安全性分析,2020/9/8,4,1. 隐写术,2020/9/8,5,诗情画意传“密语”,水洗尘埃道未甞，甘于名利两相忘。 心怀六洞丹霞客，口诵三清紫府章。 十里采莲歌达旦，一轮明月桂飘香。 日高公子还相觅，见得山中好酒浆。,洗尘埃道未甞于名利两相忘怀六洞丹霞客诵三清紫府章里采莲歌达旦轮明月桂飘香高公子还相觅得山中好酒浆,2020/9

2、/8,6,牛郎织女会佳期下弹琴又赋诗寺静惟闻钟鼓響停始觉星斗移多少黄冠归道观幾而作尽忘机几时得到桃源洞彼仙人下象棋,牛郎织女会佳期，月下弹琴又赋诗。寺静惟闻钟鼓響，音停始觉星斗移。多少黄冠归道观，见幾而作尽忘机。几时得到桃源洞，同彼仙人下象棋。,诗情画意传“密语”,2020/9/8,7,王先生： 来信收悉，你的盛情真是难以报答。我已在昨天抵达广州。秋雨连绵，每天需备伞一把方能上街，苦矣。大约本月中旬我才能返回，届时再见。,王先生： 来信收悉，你的盛情真是难以报答。我已在昨天抵达广州。秋雨连绵，每天需备伞一把方能上街，苦矣。大约本月中旬我才能返回，届时再见。,2020/9/8,8,隐写术（信息隐

3、藏）的另外一些例子,悠扬琴声奏响“进军号角” 显微镜里传递情报 魔术般的密写术 网络与数字幽灵 量子技术隐形传递信息,2020/9/8,9,隐写术的优点,能够被某些人使用而不容易被发现他们间在进行秘密通信 加密则很容易被发现谁与谁在进行秘密通信，这种发现本身可能具有某种意义或作用,2020/9/8,10,隐写术的缺点,形式简单但构造费时，要求有大量的开销来隐藏相对较少的信息 一旦该系统的构造方法被发现，就会变得完全没有价值 隐写术一般无稳健性,2020/9/8,11,替换密码技术是基于符号替换的密码技术，这种密码技术是以符号的置换来达到掩盖明文信息。这类密码技术有：单字符单表替换密码技术（比如

4、教材上：简单替代密码技术、多名码代替密码技术和多字母代替密码技术）、单字符多表替换密码技术（比如教材上：多表代替密码技术）等。,2. 替换密码技术,代替密码就是明文中每一个字符被替换成密文中的另外一个字符。,古典密码技术根据其基本原理大体上可以分为两类：替换密码技术和换位密码技术。,2020/9/8,12,（1）单字符单表替换密码技术：单字符单表替换密码技术是对明文中的所有字符都使用一个固定的映射。,典型的单字符单表替换密码技术有：, 乘法密码技术,设A=a0，a1 ，an-1为明文字母表，B=b0，b1 ，bn-1为密文字母表，单字符单表替换密码技术使用了A到B的映射关系：f：AB，f(ai

5、)= bj（一般情况下，为保证加密的可逆性，f是一一映射）将明文中的每一个字母替换为密文字母表中的一个字母。,单字符单表替换密码技术的密钥就是映射f或密文字母表（一般情况下明文字母表与密文字母表是相同的，这时的密钥就是映射f）。,2020/9/8,13,乘法密码技术的加密变换： Ek（ai）=aj，j=ik（mod n），gcd（k,n）=1,乘法密码技术的解密变换：Dk（aj）=ai，i=jk-1（mod n）,乘法密码技术的密钥是k。,若n是素数，则有n-2个密钥（k=1时加密变换是恒等变换，应该予以抛弃）；若n不是素数，则有(n)-1个密钥（其中(n)为欧拉函数的值）。,2020/9/8

6、,14, 移位替换密码技术：是最简单的一种替换密码。,- 移位密码的数学基础：,假设a和b都是整数，m是一个固定的正整数。若m整 除a-b，即ma-b时，称整数a，b关于模m同余，记作 a b ( mod m ) 若m不能整除a-b，则称a, b关于模m不同余。正整数m 称为模数。,明显地： 29 5 ( mod 8 ) 101 3 ( mod 7 ) -101 4 ( mod 7 ) 121 ，4关于模2不同余 易知 ：a b ( mod m ) a ( mod m ) b ( mod m ),2020/9/8,15,- 模的同余性质 ： (1) 自反性： a a ( mod m ) (2)

7、 对称性：若a b ( mod m ), 则b a ( mod m ) (3) 传递性：若 a b ( mod m),b c ( mod m ),则 a c ( mod m ) (4) ( a +b )( mod m ) a ( mod m )+ b ( mod m ) (5) ( ab )( mod m ) a ( mod m )b ( mod m ) (6) 若a b ( mod m)，c d ( mod m ), 则l，kZ(整数集合), 有la kc lb kd( mod m ) ，且ac bd ( mod m ) (7)设f(x)与g(x)分别是两个整系数多项式： f(x) = an

8、 xn+ an-1xn-1+ a, g(x) = bn xn+ bn-1xn-1+ b 则 ()若a b ( mod m )，那么f(a) f(b) ( mod m ) ()若a b( mod m )，且ak bk ( mod m )，k=0,n， 则f(a) g(b)( mod m ),2020/9/8,16,移位密码实质上是正整数m上模运算，特别用Zm=0,1,m-1表示模m的剩余类，定义Zm上的加法和乘法，它完全类似于普通的实数域上的数的加法和乘法，不同的仅是运算结果是取模以后的余数。,-定义（移位密码算法）: 设P = C = K = Z26，对0 k 25,即kK, x , yZ26

9、,定义 加密函数：Ek(x) = (x + k )( mod 26 ) 解密函数：Dk(y) = (y-k)( mod 26 ),2020/9/8,17,加密变换为： Ek（ai）=aj，j=（i + k）（mod n），0 k n 解密变换为： Dk（aj）=ai，i=（j - k）（mod n）=（j +（n- k）（mod n） 由于i=（j - k）（mod n）=（i + k - k）（mod n）=i （mod n），所以解密与加密是可逆的。从解密变换中可以看出：Dk= En-k。,2020/9/8,18,移位替换密码技术的密钥是k，k唯一地确定了明文空间到密文空间的映射，故移位替

10、换密码技术的密钥空间的元素个数为n-1。 用密钥穷搜索方法很容易破译。, 密钥字密码技术：它利用一个密钥字来构造替换作为密钥。, 仿射密码技术：是加法密码技术和乘法密码技术的结合体。,2020/9/8,19,k，b为该算法的密钥。当b=0时，仿射密码技术退化为乘法密码技术，当k=1时，仿射密码退化为移位替换密码技术。,2020/9/8,20,（2）单字符多表替换密码技术：单字符多表替换密码技术在安全性方面比单字符单表替换密码技术高。,单字符多表替换密码技术是用一系列（两个以上）替换表依次对明文的字母进行替换的加密方法。假设明文字母表为Zq，替换表序列为L= L1L2，明文字母序列为m= m1m

11、2，则相应的密文序列为c= L(m)= L1(m1)L2(m2)。,如果替换序列是非周期的无限序列，则相应的密码技术为非周期多表代替密码技术，它对每个明文都采用了不同的替换表进行加密，也称为一次一密密码技术，它是一种理论上不可破译的密码技术。,因为单字符单表替换密码技术中明文的字母与密文中的字母是一一对应的，明文中的字母统计特性在明文中没有得到改变，因此单字符单表替换密码技术很容易破译。,而在实际应用中采用的都是周期多表替换密码技术，只使用了有限的替换表，替换表被重复使用以完成对明文的加密。,例如周期为d，则替换表序列为：L= L1L2LdL1L2Ld 。,当d=1时，单字符多表替换密码技术退

12、化为单字符单表替换密码技术。,2020/9/8,21,单字符多表替换密码技术有很多，典型的有：, Vigenere（费杰尔或维吉尼亚）密码技术,定义：设m是一个正整数。设M = C = K = (Z26)m，( Z26m = Z26 Z26 Z26表示Z26的m次直积)。 对于k=(k1,k2,km)K，定义： 加密函数：Ek(x1,x2,xm) = (x1+k1,xm+km)( mod 26 ) 解密函数：Dk(y1,y2,ym) = (y1- k1,ym -km)( mod 26 ),Vigenere密码技术本质上是一种多表简单加法密码技术Vigenere密码技术循环地使用每一个替换表完成

13、明文字母到密文字母的转换。,维吉尼亚密码一次加密m个明文字母。,2020/9/8,22,- 具体的加密过程： 设密钥K= k1 k2 km，明文与密文字母表中均包含了n个字母。又设明文m= m1m2，密文为c= c1c2，则ci=mi+ki（mod n），其中m为正整数。 当密钥的长度比明文短时，密钥可以周期性地重复使用，直至完成明文中的每个字母的加密。,2020/9/8,23, Vernam（弗纳姆）密码技术,其加密方法是，将明文和密钥分别表示成二进制序列，再把它们按位进行模二加法。设明文m= m1m2，密钥k= k1k2，其中mi，kiGF(2)，i1，则密文c= c1c2，其中ci= m

14、i ki 。这里 为模二加法。, Hill（希尔）密码技术,它实际上是仿射密码技术的特例。其基本加密思想是将明文分组（如n个明文字母）通过线性变换将它们转换为n个密文字母的加密算法。解密时只需做一次逆变换即可。密钥就是变换矩阵。,2020/9/8,24,2020/9/8,25,换位密码技术本质上就是一种置换密码技术，但它置换的不是字符，而是书写的位置。换位密码技术的数学表达式可以表示成：设明文为：m= m1m2，则密文c= c1c2，ci = ，i=1，2，n。其中置换表为：,3. 换位密码技术,Hill密码技术可以较好地抗击统计分析攻击，但在面对已知明文的攻击就很容易被破译，特别是在已知密钥

15、矩阵行数的情况下。因此，Hill密码技术并不安全。,2020/9/8,26,例子：,明文：cryptography is an applied science 密钥：encry 密文：yripdn cohnii rgyaee paspsc tpalce,2020/9/8,27,为了保护信息的保密性，抗击密码分析，保密系统应当满足下述要求：, 系统即使达不到理论上是不可破的，也应当为实际上不可破的。就是说，从截获的密文或某些已知的明文密文对，要决定密钥或任意明文在计算上是不可行的。, 系统的保密性不依赖于对加密体制或算法的保密，而依赖于密钥。这是著名的Kerckhoff原则。, 加密和解密算法适

16、用于所有密钥空间中的元素。, 系统便于实现和使用。,2020/9/8,28,威胁古典密码安全的因素：,频率分析 考虑最可能的字母及单词 重复结构分析 持久性、组织性、创造性和运气 明文已知且易于识别,2020/9/8,29,频率分析攻击,由于任何自然语言都有自己的统计规律，对于古典密码来说，密文中还保留了明文的统计特征，因此可以使用统计方法（频率分析）进行攻击。 英文中的统计（频率）是有规律的： 每个单字母中E出现频率最高，其次是T、 A、O、I、N、S H、R等，V、K、J、X、Q、Z最低。 双字母频率最高的有TH、HE，它们出现的频率小于IN、ER等。 还有THE，ING等其他规律。,20

17、20/9/8,30,常见的三字母组合：THE、ING、AND、HER、ERE、ENT、THA、NTH、WAS、ETH、FOR、DTH等。,常见的双字母组合：TH、HE、IN、ER、RE、AN、ON、EN、AT；,2020/9/8,31,2020/9/8,32,频率分析攻击的一般方法：,第一步：对密文中出现的各个字母进行出现的频率统计 第二步：根据密文中出现的各个字母的频率，和英语字母标准 频率进行对比分析，做出假设，推论加密所用的公式 第三步：证实上述假设或继续作其他假设,2020/9/8,33,移位密码安全性分析,移位密码是极不安全的（mod 26），因为它可被穷举密钥搜索所分析：因为仅有26个可能的密钥，通过尝试每一个可能的密钥，直到获得一个有意义的明文串。,一般情况，一个明文在尝试26/213个密钥后将显现出来。,作为早期的密码，移位密码虽然脆弱，仅对明文进行了不透明的封装，但它可防止消息明文被人意外的获取。,2020/9/8,34,对于仿射密码，c=e(p)=( k p+b) (mod 26)，因为k要和26互质，并且还要去掉1，密钥空间只有11个，不能经得起穷举分析。,仿射密码安全性分析,2020/9/8,35