应用密码学第2讲

1应用密码学第2章古典密码学2回顾►什么是密码体制？►密码体制的分类。►密码分析的分类。32.1语言的统计特性►研究保密性和密码破译方法的实质：就是研究明文信息在密文信息中有多大程度的泄漏。►下面假设讨论的语言是某种语言的文字：设字母表为X={x0，x1，…，xm-1}为了方便起见，字母表也用0－（m-1）之间的数字来表示，此时字母表为Zm={0，1，…，m－1}42.1语言的统计特性►例如，英文字母表可以表示为X={a，b，c，…，x，y，z}或者Zm={0，1，2，…，24，25}明文是由Zm中的元素和固定的结个规则确定的。因此具有语言的统计特性。例如：字母q后总是跟着字母u。52.1语言的统计特性►语言的一阶统计特性称P={p0，p1，…，pm-1}为语言的一阶统计特性。其中，pi（0≦i≦m-1）代表字母i在该语言中出现的概率。例2.1英文字母表X={a，b，c，…，x，y，z}，由独立试验产生明文单码，Beker在1982年统计的样本总数为100362，得到单码的概率分布见表2.1。6表2.1英文字母的概率分布字母概率字母概率字母概率A0.08167J0.00153S0.06327B0.01492K0.00772T0.09056C0.02782L0.04025U0.02758D0.04253M0.02405V0.00978E0.12702N0.06749W0.02360F0.02280O0.07567X0.00150G0.02015P0.01929Y0.01974H0.06094Q0.00095Z0.00074I0.06966R0.0549772.1语言的统计特性►英文字母出现的概率大小排列：ETAOINSHRDLCUMWFGYPBVKJXQZ按字母出现的概率分类：表2.2英文字母分类表1234567极大概率字母集：E大概率字母集：TAO较大概率子母集：INSHR平均概率字母集：DL较低概率字母集：CMWFGYPBU低概率字母集：VK极低概率字母集：JXQX82.1语言的统计特性语言的一阶特性至少在以下两个方面没有反映出英文的语言特性：(1)双字母出现的概率例如QE出现的概率。按照一阶特性计算QE出现的概率为p（QE）=0.0095×0.12702≈1.21×10-4但是在英文课文中QE根本不会出现。(2)四字母SEND和SEDN在一阶统计特性下出现的概率相等，这也不符合实际。92.1语言的统计特性►双字母出现的频数表示为：N(i，j)i,j=0,1,2,(m-1)双字母出现的概率p(xi,xj)近似地可以表示为p(xi,xj)=N(i，j)/(N－1)例2.2由独立试验产生双字母表。根据Beker在1982年的统计结果我们可以计算p(SEND)=p(SE)×p(ND)≈0.7919p(SEDN)=p(SE)×p(DN)≈0.08146p(QE)=0102.1语言的统计特性同理，三字母出现的概率可以近似地表示为p(xi,xj,xk)=N(I,j,k)/(N－2)注意：在实际的通信中除了字母外还有数字，标点符号等，他们的统计特性也要考虑进去。另外数据格式，报头信息对于密码体制的安全有重要意义，，在密码分析中起着非常重要的作用。112.2单表代替密码►补充（1）变换集合X到自身的一个映射称为集合X的一个变换。对照映射的概念可以定义出满射变换，单射变换，双射变换。（2）置换有限集合X上的双射变换称为一个n次置换，通常用以下符号表示=（3）群12…n…)1()2()n(122.2单表代替密码设集合G是一个非空集合，·是它的一个代数运算，如果满足条件：（1）结合律成立，即对G中任意元素a，b，c都有(a·b)·c=a·(b·c)（2）有左单位元。即存在元素e∈G，对G中的每个元素a都有e·a=a（3）每个元素都存在逆元。即对于任意a∈G，存在a-1∈G，使a-1·a=a·a-1=e则称G对代数运算·作成一个群。若交换律成立，则称G为可交换群或Abel群。132.2单表代替密码（4）对称群假设所采用语言的字母表含有q个字母,即集合上置换的全体记为,则是上的对称群。定义2.1设是一列置换，是一列明文，其中,。变换Ek将n-明文组加密成n-密文组,即}1,......,1,0{qZq)(qZSYM)(qZSYMqZ......),......,,{21nk,......),......,,(21nxxxx)(qiZSYMqiZx),......,,(21nxxxx),......,,(21nyyyyyyyyxxxxEnnnk),......,,())(),......,(),(()(212211142.2单表代替密码称上述加密方式为代替(substitution)加密。当时,称为单表代替(monalphabeticsubstitute)加密。否则,称其为多表代替(polyalphabeticsubstitute)加密。称为代替加密密表。下面学习两种代替密码n......21i152.2.1移位代替密码以下将q个字母的字母表与Z模q中数作一一对应,利用每个字母对应的数字代替该字母。例如,将英文字母表作如下对应:abc…yz012…2425这样,可以用0表示a,用1表示b.....。移位代替密码是最简单的一种代替密码。其加密变换为：，0≤m,c＜q显然,移位代替密码的密钥空间中元素的个数为q,其中k=0是恒等变换。)(mod)(qckmmEk}0|{qkkK试着写出解密变换的公式162.2.1移位代替密码例2.3凯撒密码(CaesarCipher)是对英文字母表进行移位代替的密码,其中q=26。例如,选择密钥k=3,则有下述代替表:明:abcdefghijklmnopqrstuvwxyz密:DEFGHIJKLMNOPQRSTUVWXYZABC设明文m=helloeverybody试计算其密文。解密时,只要用密钥k=23的加密密表对密文c进行加密运算就可恢复出原明文。这种密码是将明文字母表中字母位置下标与密钥k进行模q加法运算的结果作为密文字母位置下标,相应的字母即为密文字母,因此又称其为加法代替密码。172.2乘法代替密码乘法代替密码的加密变换为：，0≤c＜q。这种密码又叫采样密码(decimationcipher)，这是因为其密文字母表是将明文字母表按下标每隔k位取出一个字母排列而成(字母表首尾相接)。显然,当gcd(k,q)=1,即k与q互素时明文字母与密文字母才是一一对应的。若q为素数,则有q-2个可用密钥。否则就只有φ(q)-1个可用密钥。这里φ(q)是欧拉函数,它表示小于q且与q互素的正整数的个数。（举例说明）)(mod)(qcmkmEk182.2乘法代替密码►例2.4英文字母表q=26,选k=9,则有乘法代替密码的明文密文字母对应表:012345678910111213141516171819202122232425明:abcdefghijklmnopqrstuvwxyz密:AJSBKTCLUDMVENWFOXGPYHQZIR若明文m=multiplicativecipher密文c=？192.2.3仿射代替密码将移位代替密码和乘法代替密码结合起来就构成仿射代替密码。其加密变换为其中以表示仿射代替密码的密钥。当k0=0时,就得到乘法代替密码,当k1=1时就得到移位代替密码。q=26时,可用的密钥数为26×12-1=311个。解密变换为)(mod)(01qckmkmEkqZkk10,1),gcd(1qk],[01kk)(mod)()(110qkkccDk202.2.3仿射代替密码例2.5的仿射代替密码的代替表为:c=m×7+3，m=cipher求c=?试计算解密变换的代替表.212.2.4密钥短语密码可以通过下述方法对例2.2.1的加法代替密码进行改造,得到一种密钥可灵活变化的密码。选一个英文短语,称其为密钥字(keyword)或密钥短语(keyphrase)，如HAPPYNEWYEAR,按顺序去掉重复字母得HAPYNEWR。将它依次写在明文字母表之下,而后再将明文字母表中未在短语中出现过的字母依次写在此短语之后,就可构造出一个代替表,如下所示:明:abcdefghijklmnopqrstuvwxyz密:HAPYNEWRBCDFGIJKLMOQSTUVXZ22小结►语言的表示方法及统计特性►映射、置换、群、对称群►移位代替、乘法代替、仿射代替、密钥短语作业：2.2、2.3、2.4