第2章 古典密码
主要内容
古典密码中的基本加密运算 几种典型的古典密码体制 古典密码的统计分析
2.1 古典密码中的基本加密运算
单表密码体制 多表密码体制
对于一个密码体制, 明 文字母对不同位置的同一明文字 母在密文中对应的密文字 母不同.
ci = mi⊕ki , i ≥1。
在用Vernam密码对明文加密时，如果对不同的明文使 用不同的密钥，则这时Vernam密码为“一次一密”（onetime pad）密码，在理论上是不可破译的。如果存在不 同的明文使用相同的密钥，则这时Vernam密码就比较 容易被破译。
5. Hill体制
Hill体制的基本思想是将n个明文字母通过线性 变换转换为n个密文字母。解密时只需做一次逆 变换即可。密钥就是变换矩阵。
例2.6（P22）
第2章总结
单表古典密码中的基本加密运算：加法、乘法、仿射、置 换 多表古典密码中的基本加密运算：简单加法、简单乘法、 简单仿射、简单置换、换位、广义置换、广义仿射 几种典型的古典密码体制：Caesar、标准字头、Playfair、 Vigenere、Beaufort、Vernam（one-time pad）、Hill 古典密码的统计分析：单表、多表（Kasiski测试法、重 合指数法）
确定密钥字：交互重合指数
定义2.1（x的重合指数）：x中的两个随机元素相 同的概率，记为Ic(x)。
Ic(x) ≈ 0.065
定义2.2（x和y的交互重合指数）：x中的一个随机 元素与y中的一个随机元素相同的概率，记为 MIc(x, y) 。
yi与yj的相对位移：(ki − kj) mod 26
3. Beaufort体制
设明文m = m1m2…mn，k = k1k2…kn，则密文
c = Ek(m) = c1c2…cn， 其中ci = (ki + 25 - mi) mod 26, i = 1, 2, …, n。
同Vigenere体制一样，当密钥的长度比明文短时，密钥 可以周期性地重复使用，直至完成明文中每个字母的 加密。 表2.5称为Beaufort方阵（书P13）。当用密钥字母ki对明 文字母mi进行加密时， Beaufort方阵中的第ki行第mi列 的字母就是相应的密文字母。
2.1.1 单表古典密码中的基本加密运算
4. 置换密码 2. 仿射密码 3. 乘法密码 1. 加法密码
设 为 ，对任意 上全体置换 设 ，对任意 ，密文 对任意 密文 的集合. 对任意 密文 显然 , 仿射密码是置换密码的特例 解密变换为 其中， q 是正整数， 解密变换为 其中，
显然, 加法密码和乘法密码都是仿 射密码的特例.
例2.5（P16）
表2.6 26个英文字母的出现频率
2.3.2 多表古典密码的统计分析
在多表古典密码的分析中，首先要确定密钥字的长度, 也就是要首先确定所使用的加密表的个数，然后再分析确 定具体的密钥。 确定密钥字长的常用方法有： Kasiski 测试法 (Kasiski test)
重合指数法 (index of coincidence)
问题：
置换和换位的定义、区别？
作业：
习题2.1、2.2、2.3、2.4、2.6
抽象代数
群：由一个非空集合和一个二元运算组成，并满 足封闭性、结合性、单位元、逆元的代数系统。
乘法群
环：一个集合，可以在其上进行加法和乘法运算 而封闭。
交换环：对于乘法运算可交换
域：非零元都有乘法逆的交换环。
2. 2 几种典型的古典密码体制
几种典型的单表 古典密码体制
几种典型的多表 古典密码体制
2. 2.1 几种典型的单表古典密码体制
Caesar 体制
标准字头密码体制
2.2.2 几种典型的多表古典密码体制
明文 Playfair 体制 其他多表古典密码体制有 密钥是一个 5×5 的构造矩阵 分组 Vigenere 体制 Beaufort 体制 加密时, 先在明文字母串插入特定字母 , 譬 如字母q, 使得长度为偶数 , 然后两两分组, Vernam 体制 每组中的两个字母不同。 Hill 体制
首先确定密钥字的长度，即加密表的个数。
Kasiski测试法：寻找密文中长度至少为3的相同 的密文片段对，计算每对密文片段中的两个密 文片段之间的距离。这样，我们就得到了一些 距离值d1, d2, d3, …di．我们可以猜测密钥字的 长度m可能是d1, d2, d3, …di的最大公因子。 重合指数法：利用重合指数法可以进一步确定 密钥字的长度是否为m。
P 中同行,
密文
P 中同列,
非同行同列,
为紧靠各自右端的字母 为紧靠各自下方的字母 为确定矩阵的对角字母
2. Vigenere体制
设明文m = m1m2…mn，k = k1k2…kn，则密文
c = Ek(m) = c1c2…cn， 其中ci = (mi + ki) mod 26, i = 1, 2, …, n。 当密钥的长度比明文短时，密钥可以周期性地 重复使用，直至完成明文中每个字母的加密。
字母 a b c d e f g h i j k l m 百分比 8.2 1.5 2.8 4.2 12.7 2.2 2.0 6.1 7.0 0.1 0.8 4.0 2.4 字母 n o p q r s t u v w x y z 百分比 6.8 7.5 1.9 0.1 6.0 6.3 9.0 2.8 1.0 2.4 2.0 0.1 0.1
表2.4称为Vigenere方阵（书P12）。当用密钥字 母ki对明文字母mi进行加密时，Vigenere方阵中 的第ki行第mi列的字母就是相应的密文字母。
例2.2
设明文为 This cryptosystem is not secure， 密钥为cipher， 则密文为：
VPXZGI AXIVWP UBTTMJ PWIZIT WZT。
例2.3
设明文为 This cryptosystem is also not secure， 密钥为cipher， 则密文为：
IAGOBZ DSVSLS JOKUVY BWWSQC IPKEJZ X。
4. Vernam体制
Vernam密码在加密前首先将明文编码为(0, 1)字符串。
设明文m = m1m2…mn，k = k1k2…kn，其中mi , ki∈GF(2) ， 则密文c = c1c2…cn ，其中
因此，明文Hill的密文为XIYJ.
2. 3 古典密码的统计分析
单表古典密码的 统计分析
多表古典密码的 统计分析
2.3.1 单表古典密码的统计分析
单表古典密码体制的密文字母表实际上是明文字母表 的一个排列。 因此, 明文字母的统计特性在密文中能够反 映出来。当截获的密文足够多时, 可以通过统计密文字母 的出现频率来确定明文字母和密文字母之间的对应关系。
2.1.2 多表古典密码中的基本加密运算
3. 4. 6. 1. 7. 简单仿射密码 简单置换密码 广义置换密码 广义仿射密码 5. 2. 简单乘法密码 换位密码 简单加法密码 设 设 设 对任意
对任意 密文 对任意
密文 密文 其中的加法都是模 q 加法 . 显然 , 简单 其中的乘法都是模 q 乘法 . 显然 , 简单乘法 加法密码的密钥量为 密码的密钥量为 其中的加法和乘法都是模q 加法和乘法. 显然, 简单仿射密码的密钥量为
设明文m = (m1, m2, …, mn) ∈Z26n，密文c= (c1, c2, …, cn) ∈ Z26n ，密钥为Z26上的的n×n阶可逆 方阵K = (kij) n×n ，则 c = mK mod 26, m = cK-1 mod 26。
例2.4 设n＝2，密钥为 11 8 7 18 －1 K＝ ，容易计算 K ＝ 3 7 23 11 设明文为Hill, 则相应的明文向量为（7，8）和（ 11,11）。于是，相应的密文向量 分别为 11 （7，8） 3 11 （ 11,11） 3 8 77 24， 56 56 ）＝（23，8）， ＝（ 7 8 121 33， 88 77 ）＝（24， 9 ）， ＝（ 7
有限域（伽罗瓦域）：GF(2)