密码学基础课件：第四讲 古典密码学

1、第四讲 古典密码学-3置换密码及其密码分析密码学中的轮子对称密码设计的基本原则扩散混淆现代密码学设计的基本原则古典密码（Classical Cipher） 代换密码(Substitution Cipher)是明文中的每一个字符被替换成密文中的另一个字符。接收者对密文做反向替换就可以恢复出明文。置换密码(Permutation Cipher)又称换位密码（Transposition Cipher)，加密过程中明文的字母保持相同，但顺序被打乱了。置换密码 置换密码(Permutation Cipher)。置换密码又称为换位密码，通过改变明文消息各元素的相对位置，但明文消息元素本身的取值或内容形式不

2、变。它是对明文L长字母组中的字母位置进行重新排列，而每个字母本身并不改变。 明文：m=m1 m2,mL。， 加密变换：c=(c1,c2,cL)=E(m)=m(1) m(2) m(L)。 解密变换： 置换密码换序构词的声明意大利天文学家伽利略用他的望远镜发现了土星这颗行星似乎由三颗星组成，用拉丁语表示为：altissimum planetam tergeminum observavi调换字母顺序之后，伽利略“公开”了他的发现：SMAISMRMIL MEPOETAL EUMIBUNENU GTTAUIRAS换序构词的声明惠更斯后来发现土星不是三颗星，他发现“它的周围环绕着一个扁平的环，两者没有接触

3、，环向黄道倾斜”这个发现使用了简单的依照字母表顺序重新排列的方式“公开了”。三年后才明确了这一发现。致桑道夫伯爵的信一个小混混偷走了编码框。使用密钥字的置换方法首先把明文写成方框，例如写成7*15的矩阵，明文不足则填充使用密钥字的置换方法选择大于列数的提示词，例如 “在绿色的草地上”选择与列数相同的句子，根据字母表顺序对句子中的字母编号，重复字母按照出现顺序依次编号 使用密钥字的置换方法按照编号大小调换列的顺序原文置换后按列写出得到密文使用密钥字的置换方法再复杂一些，可以再为行选择提示词，类似调换行上述置换方法的分析攻击者可以通过密文数量推测方框的行和列（因式分解）之后攻击者可以根据自然语言中

4、双字符的统计特性推断列与列之间的先后关系，例如英语中“CH”和“TH”等组合，尝试破译。用英语说这件事情Because the cipher operates on blocks of size e, the plaintext and the ciphertext have to have a length which is some multiple of L. This causes two weaknesses in the system: first, the plaintext may have to be padded (if the padding is identifiabl

5、e then part of the key is revealed) and second, information relating to the length of the key is revealed by the length of the ciphertext. To see this, note that if the ciphertext is of length i then L must be one of the divisors of i. With the different possible key sizes different possible permuta

6、tions are tried to find the permutation which results in the highest number of frequent bigrams and trigrams as found in the underlying language of the plaintext. 置换方法的可识别性Because the cipher doesnt change any of the characters, the ciphertext will have exactly the same letter frequencies as the unde

7、rlying plaintext. This means that the cipher can in many cases be identified as a transposition by the close similarity of its letter statistics with the letter frequencies of the underlying language 给定一个集合1，2， . . .，n的置换，写出置换矩阵为 这时，置换矩阵是每一行和每一列都刚好有一个“1”，而其余元素为“0”的稀疏矩阵。如加解密置换=(3 5 1 6 4 2)， =（3 6 1

8、5 2 4），对应的置换矩阵（按照右乘）为：；表示仅第i行中第(i)个元素为1，其余为零。置换密码的数学分析 加密变换： 解密变换： = 所以，置换密码实质上是输入分组的一个线性变换。 置换密码的数学分析置换密码在实质上是Hill密码的特例密码学中的轮子下面是把a,b,c,d映射为C,A,D,B的轮子密码学中的轮子上述轮子可以转动（轮子内部连接方式与上图相同）轮子的分析当4字母换为26个字母之后，每加密一个字母轮子旋转1/26周，因此相当于我们学习过的维吉尼亚密码或者改进的维吉尼亚密码一种多表代换的方法两个轮子W1轮旋转4次，W2轮旋转1次。类似钟表。此时可以表示16种4位字符的排列。赫贝恩5

9、个轮子的密码机用同一台机器加密解密可以看到按c输出B。按b输出C。最左侧的轮子叫做互助轮舍尔比乌斯的哑谜希特勒的哑谜哑谜的弱点古典密码小结对称密码体制主要分为分组密码和流密码对称密码的两个基本运算代换和置换(Substitution & permutation)对称密码的两个基本设计原则:扩散（Diffusion):明文的统计结构被扩散消失到密文的长程统计特性 ,使得明文和密文之间的统计关系尽量复杂。 混淆(confusion)：使得密文的统计特性与密钥的取值之间的关系尽量复杂 扩散扩散是使得明文的统计特性分散在密文中混淆混淆是使得密文的统计特性与每一个密钥比特相关经典密码算法特点要求的计算强

10、度小DES之前以字母表为主要加密对象代换和置换技术数据安全基于算法的保密密码分析方法基于明文的可读性以及字母和字母组合的频率特性现代密码学的基本原则Principle 1 ： the first step in solving any cryptographic problem is the formulation of a rigorous and precise denition of security. Principle 2： when the security of a cryptographic construction relies on an unproven assumption, this assumption must be precisely stated. Furthermore, the assumption should be as minimal as possible.Principle 3 ：cryptographic constructions should be accompanied with a rigorous proof o