经典密码（课堂PPT）

1、.1经典密码代替密码讲师：张远课程：通信网的安全与保密.2课程信息课程：选修课地点：时间：36学时电话：邮件：教材参考资料密码学简明教程计算机密码学.3课程简介简介本课程将介绍现代密码学相关的算法及应用，旨在让学生掌握现代密码的设计、分析原理及应用。本课程面向通信工程专业的学生开设，需要具备通信原理、信息论、计算机基础等预备知识。.4章节绪论经典密码经典密码分组密码序列密码公开秘钥密码单项散列函数数字签名密码协议密码应用.5开始上课。.6经典密码经典密码经典密码（古典密码）通常将字符通过易位或者代替的方式实现加密，这一类加密算法大都比较简单，分析也相对容易，研究这些密码的原理，对于理解和分析现

2、代密码具有一定的指导意义。易位密码代替密码.7代替密码代替密码代替密码就是将明文中的字符替换成字母表中另外一个字符，从而隐藏原有明文含义的加密方法。单表代替密码多变代替密码.8代替密码单表代替密码单表代替密码编号编号0123456789101112明文明文abcdefghijklm密文密文DEFGHIJKLMNOP编号编号13141516171819202122232425明文明文nopqrstuvwxyz密文密文QRSTUVWXYZABC明文：明文：n o r t h w e s tn o r t h w e s t密文：密文：Q Q R R U U W W K K Z Z H H V V

3、W W.9代替密码单表代替密码单表代替密码编号编号0123456789101112明文明文abcdefghijklm密文密文DEFGHIJKLMNOP编号编号13141516171819202122232425明文明文nopqrstuvwxyz密文密文QRSTUVWXYZABCc c= =m m+3+30=0=m m2326m m2222c c=(=(m m+3)mod+3)mod 2626.10代替密码单表代替密码单表代替密码编号编号0123456789101112明文明文abcdefghijklm密文密文DEFGHIJKLMNOP编号编号13141516171819202122232425

4、明文明文nopqrstuvwxyz密文密文QRSTUVWXYZABCc c=(=(m m+3)mod+3)mod 2626.11代替密码单表代替密码单表代替密码c c=(=(m m+3)mod+3)mod 2626名词解释：秘钥是用于控制加密解密变换的参数。名词解释：秘钥是用于控制加密解密变换的参数。c c=(=(m m+k)mod+k)mod q q加法密码加法密码.12代替密码单表代替密码单表代替密码加法密码加法密码加法密码如何解密呢？加法密码如何解密呢？c c= =m m+3+30=0=m m2326m m2222m m= =c c-3-32626c c22m m= =c c-3+26-

5、3+260=0=c c33m m=(=(c c-3)mod-3)mod 2626m m=(=(c-c-k)modk)mod q q.13代替密码单表代替密码单表代替密码加法密码加法密码加法密码安全性如何呢？加法密码安全性如何呢？名词解释：秘钥量是秘钥空间中不同秘钥的个数。名词解释：秘钥量是秘钥空间中不同秘钥的个数。加法密码的秘钥量是多少呢？加法密码的秘钥量是多少呢？q q由于秘钥量很小，因此加法密码很容易被分析出来。由于秘钥量很小，因此加法密码很容易被分析出来。.14代替密码单表代替密码单表代替密码加法密码加法密码mabcdefghijkl m n opqrstuv w xyzk0A B C

6、D E F G HIJ K L M N O P Q R S T U V W X Y Z1B C D E F G HIJ K L M N O P Q R S T U V W X Y Z A2C D E F G HIJ K L M N O P Q R S T U V W X Y Z A B3D E F G HIJ K L M N O P Q R S T U V W X Y Z A B C4E F G HIJ K L M N O P Q R S T U V W X Y Z A B C D5F G HIJ K L M N O P Q R S T U V W X Y Z A B C D E6G HIJ

7、K L M N O P Q R S T U V W X Y Z A B C D E F7HIJ K L M N O P Q R S T U V W X Y Z A B C D E F G8IJ K L M N O P Q R S T U V W X Y Z A B C D E F G H9J K L M N O P Q R S T U V W X Y Z A B C D E F G HI10 K L M N O P Q R S T U V W X Y Z A B C D E F G HIJ11 L M N O P Q R S T U V W X Y Z A B C D E F G HIJ K1

8、2 M N O P Q R S T U V W X Y Z A B C D E F G HIJ K L13 N O P Q R S T U V W X Y Z A B C D E F G HIJ K L M14 O P Q R S T U V W X Y Z A B C D E F G HIJ K L M N15 P Q R S T U V W X Y Z A B C D E F G HIJ K L M N O16 Q R S T U V W X Y Z A B C D E F G HIJ K L M N O P17 R S T U V W X Y Z A B C D E F G HIJ K

9、L M N O P Q18 S T U V W X Y Z A B C D E F G HIJ K L M N O P Q R19 T U V W X Y Z A B C D E F G HIJ K L M N O P Q R S20 U V W X Y Z A B C D E F G HIJ K L M N O P Q R S T21 V W X Y Z A B C D E F G HIJ K L M N O P Q R S T U22 W X Y Z A B C D E F G HIJ K L M N O P Q R S T U V23 X Y Z A B C D E F G HIJ K

10、L M N O P Q R S T U V W24 Y Z A B C D E F G HIJ K L M N O P Q R S T U V W X25 Z A B C D E F G HIJ K L M N O P Q R S T U V W X Y已知密文：已知密文：XYBDRGOCDXYBDRGOCD采用穷举法分析采用穷举法分析 X Y B D R G O C D0 x y b d r g o c d1w x a c q f n b c2v w z b p e m a b3u v y a o d l z a4t u x z n c k y z5s t w y m b j x y6r s

11、 v x l a i w x7q r u w k z h v w8p q t v j y g u v9o p s u i x f t u10 n o r t h w e s t11 mn q s g v d r s12 l mp r f u c q r13 k l o q e t b p q14 j k n p d s a o p15 i j m o c r z n o16 h i l n b q y mn17 g h k m a p x l m18 f g j l z o w k l19 e f i k y n v j k20 d e h j x m u i j21 c d g i w l

12、t h i22 b c f h v k s g h23 a b e g u j r f g24 z a d f t i q e f25 y z c e s h p d e解密得到：解密得到：northwestnorthwest.15代替密码单表代替密码单表代替密码乘法密码乘法密码根据加法密码的设计思路，采用乘法原理可以得到以下算法根据加法密码的设计思路，采用乘法原理可以得到以下算法c c=(=(m m* *k)modk)mod q q编号编号0123456789101112明文明文abcdefghijklm密文密文ADGJMPSVYBEHK编号编号13141516171819202122232

13、425明文明文nopqrstuvwxyz密文密文NQTWZCFILORUX当当 k=3 k=3 时，可以得到如下的代替表时，可以得到如下的代替表.16代替密码单表代替密码单表代替密码乘法密码乘法密码gcd(k,q)=1gcd(k,q)=1为了保证算法的可逆性，为了保证算法的可逆性，k k的取值需要满足以下要求的取值需要满足以下要求根据欧拉函数，计算出根据欧拉函数，计算出q=26q=26时，时，(q)=(13-1)(q)=(13-1)* *(2-1)=12(2-1)=12乘法密码的秘钥量为乘法密码的秘钥量为(q) (q) 在保证可逆性的前提下，采用乘法密码可以构造出在保证可逆性的前提下，采用乘法

14、密码可以构造出1212个不个不同的代替表。根据秘钥量的定义，可以得到：同的代替表。根据秘钥量的定义，可以得到：.17代替密码单表代替密码单表代替密码乘法密码乘法密码乘法密码如何解密？乘法密码如何解密？c c=(=(m m* *k)modk)mod q q初等数论中，素域初等数论中，素域GF(q)GF(q)定义了乘法运算以及乘法逆，对于定义了乘法运算以及乘法逆，对于所有非所有非0 0元素，元素，都可以找到逆元都可以找到逆元-1-1，计算方法通常采，计算方法通常采用用扩展欧几里得算法扩展欧几里得算法实现（后续章节介绍）。根据逆元的实现（后续章节介绍）。根据逆元的定义和计算方法，乘法密码的解密变换可

15、以定义为：定义和计算方法，乘法密码的解密变换可以定义为：m m=(C=(C* *k k-1-1)mod)mod q q.18代替密码单表代替密码单表代替密码乘法密码乘法密码加法密码加法密码c c=(=(m m+k)mod+k)mod q qm m=(=(c-c-k)modk)mod q q加法密码的秘钥量：加法密码的秘钥量：q qc c=(=(m m* *k)modk)mod q qm m=(=(c c* *k k-1-1)mod)mod q q乘法密码的秘钥量：乘法密码的秘钥量：( (q q) ).19代替密码单表代替密码单表代替密码乘法密码乘法密码加法密码加法密码+c c=(=(m m+k

16、)mod+k)mod q qc c=(=(m m* *k)modk)mod q qc c=(k=(k1 1m m+k+k2 2)mod)mod q q仿射密码仿射密码.20代替密码单表代替密码单表代替密码c c=(k=(k1 1m m+k+k2 2)mod)mod q q仿射密码仿射密码仿射密码的解密变换仿射密码的解密变换m m=k=k1 1-1-1( (c c- -k k2 2)mod)mod q q仿射密码的秘钥量：仿射密码的秘钥量：( (q q) ) * * q q.21代替密码单表代替密码单表代替密码以上三种单表代替密码从秘钥的数量来看，以上三种单表代替密码从秘钥的数量来看，安全性都非

17、常低，换言之，所设计的代替表的数安全性都非常低，换言之，所设计的代替表的数量非常有限，如何能够增加秘钥数量，增加代替量非常有限，如何能够增加秘钥数量，增加代替表的数量呢？表的数量呢？编号编号0123456789101112明文明文abcdefghijklm密文密文编号编号13141516171819202122232425明文明文nopqrstuvwxyz密文密文编号编号0123456789101112明文明文abcdefghijklm密文密文FDVHWTUBALRSA编号编号13141516171819202122232425明文明文nopqrstuvwxyz密文密文ZXQPEMNIJKGO

18、C根据排列组合的原理，秘钥数量将达到根据排列组合的原理，秘钥数量将达到26！置换密码置换密码.22代替密码单表代替密码单表代替密码虽然置换密码可以构造大量的代替表，对于虽然置换密码可以构造大量的代替表，对于密码分析者来说，密码破译的难度有所增加。密码分析者来说，密码破译的难度有所增加。但是从单表代替密码的固有属性分析，我们但是从单表代替密码的固有属性分析，我们会发现，密文中字母出现的统计特性与明文是相会发现，密文中字母出现的统计特性与明文是相同的，因此，统计分析将对单表代替密码非常奏同的，因此，统计分析将对单表代替密码非常奏效。效。.23代替密码单表代替密码单表代替密码下表是统计了近下表是统计了近2000020000个常用的英文词汇后得出的结果个常用的英文词汇后得出的结果统计分析法统计分析法字母出现次数出现频率字母出现次数出现频率e1678211.42%d45963.13%a125748.56%h40582.76%i116747.94%g33802.30%r110427.51%b31212.12%t109597.46%y29382.00%o104667.12%f21571.47%n94136.41%v15741.07%s81545.55%w13880.94%l81145.52%k12350.84%c69684.74%x5070.35%u53733.66%z3