信息安全-古典密码学简介

目录

C. D. Shannon: 

一、置换密码

二、单表代替密码

① 加法密码

② 乘法密码

③密钥词组代替密码

三、多表代替密码

代数密码

四、古典密码的穷举分析

1、单表代替密码分析

五、古典密码的统计分析

1、密钥词组单表代替密码的统计分析        

2、英语的统计规律        

C. D. Shannon: 

采用混淆、扩散和乘积的方法来设计密码； 

混淆：使密文和明文、密钥之间的关系复杂化

扩散：将每一位明文和密钥的影响扩大到尽可能多的密文位中。

乘积和迭代：多种加密方法混合使用对一个加密函数多次迭代

古典密码编码方法：置换，代替，加法

古典密码学举例：

一、置换密码

把明文中的字母重新排列，字母本身不变，但其位置改变了，这样编成的密码称为置换密码。最简单的置换密码是把明文中的字母顺序倒过来，然后截成固定长度的字母组作为密文。

明文：明晨5点发动反攻。MING CHEN WU DIAN FA DONG FAN GONG

密文：GNOGN AFGNO DAFNA IDUWN EHCGN IM

理论上：①、置换密码的加密钥是置换矩阵 p，解密钥是置换矩阵 p-1 。②、置换密码经不起已知明文攻击。           

           

二、单表代替密码

① 加法密码

A和B是有 n个字母的字母表。定义一个由A到B的映射：f: A→B。f(ai )= bi=aj；j=i+k mod n；加法密码是用明文字母在字母表中后面第 k个字母来代替。K=3 时是著名的凯撒密码。

② 乘法密码

A和B是有n个字母的字母表。定义一个由A到B的映射：f: A→B。f(ai )= bi= aj      j=ik mod n。其中，(n,k)=1。注意：只有(n,k)=1，才能正确解密。

③密钥词组代替密码

随机选一个词语，去掉其中的重复字母，写到矩阵的第一行，从明文字母表中去掉这第一行的字母，其余字母顺序写入矩阵。然后按列取出字母构成密文字母表。

举例：密钥： HONG YE 

 矩阵：    HONGYE   选出顺序：按列

                ABCDFI

                JKLMPQ   改变密钥、矩阵大小

                RSTUVW  和取出序列，得到不同的

                XZ        密文字母表。

密文字母表 :  B={ HAJRXOBKSZNCLTGDMUYFPVEIQW }

三、多表代替密码

单表代替密码的安全性不高，一个原因是一个明文字母只由一个密文字母代替。

构造多个密文字母表，在密钥的控制下用相应密文字母表中的一个字母来代替明文字母表中的一个字母。一个明文字母有多种代替。Vigenere密码：著名的多表代替密码

代数密码

① Vernam密码

     明文、密文、密钥都表示为二进制位：

      M=m1,m2,… ,mn K =k1,k2,… ,kn C =c1,c2,… ,cn

② 加密 ： c1= mi⊕ ki  ,i=1,2,… ,n   

     解密 ： m1= ci⊕ ki  ,i=1,2,… ,n

③ 因为加解密算法是模2加，所以称为代数密码。

④ 对合运算：f=f-1，模 2加运算是对合运算。

      密码算法是对和运算，则加密算法＝解密算法，工程实现工作量减半。

⑤ Vernam密码经不起已知明文攻击。

⑥ 如果密钥序列有重复，则Vernam密码是不安全的。

⑦一种极端情况：一次一密

               • 密钥是随机序列。

               • 密钥至少和明文一样长。

               • 一个密钥只用一次。

⑧一次一密是绝对不可破译的，但它是不实用的。

⑨ 一次一密给密码设计指出一个方向，人们用序列密码逼近一次一密。

四、古典密码的穷举分析

首先了解下什么是安全？

如果把一封信锁在保险柜中，把保险柜藏起来，然后告诉你去看这封信，这并不是安全，而是隐藏；

相反，如果把一封信锁在保险柜中，然后把保险柜及其设计规范和许多同样的保险柜给你，以便你和世界上最好的开保险柜的专家能够研究锁的装置，而你还是无法打开保险柜去读这封信，这才是安全。

柯克霍夫原则（Kerckhoffs‘s principle）密码系统的加密算法和解密算法应该是公开的，密码系统的安全性要取决于密钥的安全性。密码分析学是基于己知密码算法但不知道密钥的情况下，试图从密文中破译出明文的科学。

1、单表代替密码分析

① 加法密码

因为f(ai )= bi=aj  j=i+k mod n

所以k=1,2，... ,n-1,共n-1种可能，密钥空间太小。以英文为例，只有25种密钥。经不起穷举攻击。

② 乘法密码

因为f(ai )= bi=aj   j=ik mod n，且（k,n）=1。所以k共有（n）种可能，密钥空间更小。

对于英文字母表，n=26，k=1,3,5,7,9,11,15,17,19,21,23,25 取掉1，共11种，比加法密码更弱。经不起穷举攻击。

③ 密钥词语代替密码

因为密钥词语的选取是随机的，所以密文字母表完全可能穷尽明文字母表的全排列。 以英文字母表为例，n=26，所以共有26！种可能的密文字母表。26！≈4×10^26用计算机也不可能穷举攻击。

注意：穷举不是攻击密钥词语代替密码的唯一方法。

五、古典密码的统计分析

统计攻击（频率攻击）

假设：根据分析假设某些结论。

推断：在假设的前提下，推断出一些结论。

验证发展：填上破译出的字母，根据词义、词规则不断发展

当攻者能窃听到密文时，否有其它更有效攻击方法？

1、密钥词组单表代替密码的统计分析        

任何自然语言都有自己的统计规律。如果密文中保留了明文的统计特征，就可用统计方法攻击密码。由于单表代替密码只使用一个密文字母表，一个明文字母固定的用一个密文字母来代替，所以密文的统计规律与明文相同。因此，单表代替密码可用统计分析攻破。

2、英语的统计规律        

每个单字母出现的频率稳定。

  最高频率字母      E

  次高频率字母      T A O I N S H R

  中高频率字母      D L

  低频率字母        C U M W F G Y P B

  最低频率字母     V K J X Q Z

频率最高的双字母组：

  TH HE IN ER AN RE ED ON

  ES ST EN AT TO NT HA ND

  OU EA NG AS OR TI IS ET

  IT AR TE SE HI OF

频率最高的三字母组：

   THE ING AND HER ERE ENT THA WAS

  ETH FOR DHT HAT SHE ION HIS ERS

  VER

其中THE的频率是ING的3倍！

英文单词以E，S，D，T为结尾的超过一半。英文单词以T，A，S，W为起始字母的约占一半。还有其它统计规律！教科书上有一个完整的统计分析例子。经得起统计分析是对近代密码的基本要求！