密码学 Chap.3 古典密码学
1. 古典密码概述
In cryptography, a classical cipher is a type of cipher that was used historically but for the most part, has fallen into disuse.
-From Wikipedia
古典密码 , 指的是在计算机出现之前, 人类使用各种方法进行加密和解密的技术. 但时至如今, 由于计算机的出现, 大部分古典密码算法已经不再使用.
1.1 古典密码的分类
古典密码按照加密方式的不同, 主要分以下几类:
- 代换密码 : 即基于字符的密码, 其将明文中的每一个字符替换成密文中的另一个字符.
- 单字母代换密码
- 单表代换密码
- 多表代换密码
- 多字母代换密码
- 单字母代换密码
- 置换密码 : 又被称为 换位密码 , 明文中的字母保持相同, 但顺序被打乱了.
- 轮转机
1.2 单字母代换密码
单字母代换密码 , 又称 简单代换密码 , 是一种最简单的代换密码, 其将明文中的每一个字符替换成密文中的另一个字符.
- 单表代换密码
- 移位密码 (Shift Cipher)
- 乘数密码 (Multiplicative Cipher)
- 仿射密码 (Affine Cipher)
- 多项式密码 (Polynomial Cipher)
- 多表代换密码
- 维吉尼亚密码 (Vigenere Cipher)
- 博福特密码 (Beaufort Cipher)
- 滚动密钥密码 (Running-Key Cipher)
1.3 多字母代换密码
多字母代换密码 , 又称 矩阵变换密码 , 特点表现为能够通过矩阵变换方便的描述和实现.
- 希尔密码 (Hill Cipher)
- Playfair密码 (Playfair Cipher)
2. 单字母代换密码
2.1 单表代换密码
2.1.1 移位密码 (Shift Cipher)
移位密码 是一种最简单的单表替换密码, 其具体规则为: 将明文中的每一个字符替换成其后面第 $ k $ 个字符, 其中 $ k $ 被称为为密钥(Key).
$$ e_k(x) = (x + k) mod \space 26 $$
$$ d_k(y) = (y - k) mod \space 26 $$
之所以以e / d 开头, 是因为加密 / 解密的英文: encrypt / decrypt . 这种写法我们会经常用到, 读者请注意.
由于上述加密机制最初被 儒勒 · 凯撒 所用(当时 $ k = 3 $ ) , 因此当 k = 3 时, 移位密码又被称为 凯撒密码 (Caesar Cipher).
这种加密机制显然不够安全, 在当前的计算机背景下, 破译者只需要进行密钥穷举, 就能很轻松地得到原来的明文.
一个密码体制安全 的 必要条件 是能够抵抗穷尽密钥的攻击, 最普遍的做法是密钥空间足够大. 显然, 移位密码完全不符合这个条件.
2.1.2 仿射密码 (Affine Cipher)
仿射密码 是一种比移位密码更复杂的单表替换密码, 其将移位密码中的明文字符值前方加了一个系数.
$$ e(x) = (ax + b) mod \space 26 $$
需要注明, 当 $ b = 0 $ 时, 就是我们所说的乘积密码(Multiplicative Cipher).
显然, 这种机制的解密并没那么简单了, 我们需要保证对于任意 $ y $ , 同余方程 $ ax + b \equiv y (mod \space 26) $ 有唯一解 $ x $ .
对于同于方程有了解的读者应当了解, 这需要 $ a $ 和 $ 26 $ 互素, 即 $ gcd(a, 26) = 1 $ .
如您还并不了解同余方程, 请见: 密码学Chap.2 数论基础 以及 信安数学基础-期末复习章 . 这两章中有更加详细的解释.
我们讨论一下仿射密码的密钥空间:
与26互素的数: {1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25} , 共12个.
因此仿射密码的总密钥空间: $ 12 \times 26 = 312 $ . 这对于现代计算机而言仍然不够安全.
2.1.3 仿射密码的推广形式
如果我们更加深入一点, 将仿射密码的机制进行推广, 并不局限于26个字母的话 , 我们可以得到更大的密钥空间.
$$ e(x) = (ax + b) mod \space m $$
显然, 这要求 $ gcd(a, m) = 1 $ , 总密钥空间为 $ \phi(m) \times m $ ( $ \phi $ 为欧拉函数).
2.1.4 频率分析: 对抗单表代换的利器
频率分析是古典密码学中最为经典的一种分析方式, 由于英文中的大部分字母出现频率是存在显著差别的, 因此我们可以通过分析密文中的字母频率, 来推测出明文.
举个例子: 在英文中, 字母 E 出现的频率最高 , 因此我们可以推测密文中出现频率最高的字母是明文中的 E , 此外, 双字符的统计频率也具有很高的参考价值, 比如常见的双字母组: {th / he / in / er / on / an / …}
2.2 多表代换密码
多表代换密码 是对抗频率分析的有效手段. 其基本思想是: 将明文中的每一个字符替换成密文中的另一个字符, 但密钥是变化的 .
2.2.1 维吉尼亚密码 (Vigenere Cipher)
维吉尼亚密码 是一种多表代换密码, 其密钥是一个字符串 (通常是一个单词), 明文中的每一个字符通过密钥中的字符进行加密, 密钥中的字符循环使用.
定义: $ K(Key) = (k_1, k_2, k_3, … , k_n) $
$$ e_K(x_1, x_2, x_3, … , x_m) = (x_1 + k_1, x_2 + k_2, x_3 + k_3, … , x_m + k_m) mod \space 26 $$
$$ d_K(y_1, y_2, y_3, … , y_m) = (y_1 - k_1, y_2 - k_2, y_3 - k_3, … , y_m - k_m) mod \space 26 $$
我们对维吉尼亚的密钥空间进行一个简要的分析:
由于其密钥是一个长度为 m 的字符串, 因此其密钥空间为 $ 26^m $ .
显然, m 越长, 密钥空间越大, 因此维吉尼亚密码的安全性就越好.
最理想的情况是, 密钥长度等同于明文长度. 此时被称为 滚动密钥密码
2.2.2 随机序列密钥算法(Vernam Cipher)
随机序列密钥算法的思路与维吉尼亚密码类似, 但其密钥长度与明文长度相同, 且采用二进制数据进行加密:
$$ E: C_i = P_i \bigoplus K_i $$
$$ D: P_i = C_i \bigoplus K_i $$
符号 $ \bigoplus $ 表示 异或运算 .
C 通常表示 密文(Ciphertext) , P 通常表示 明文(Plaintext) .
3. 多字母代换密码
3.1 PlayFair密码算法(Playfair Cipher)
PlayFair密码算法是一种多表代换密码, 其将明文中的双字母组根据一个由密钥生成的 $ 5 \times 5 $ 矩阵进行加密 , 其加密方式如下:
- 生成密钥矩阵 :
预先写一个 $ 5 \times 5 $ 的矩阵, 然后自左上至右下填充字母, 先将密钥字(Key)中的字母填入, 然后将剩余的字母按字母表顺序填入, 如果出现重复字母, 则跳过 , 同时, 字母 J 和 I 填入同一格内 .
举个例子: 密钥为Cipher, 则密钥矩阵为:
C I P H E
R A B D F
G K L M N
O Q S T U
V W X Y Z- 加密 :
先将明文中按照两个为一组的双字母组进行分组, 如果前后出现字母组的两个字母相同, 则在两个字母之间填充分隔符 (如x).
举个例子: Plaintext: Balloon -> ba lx lo on
然后, 对于每一个双字母组, 在密钥矩阵中找到两个字母的位置 , 然后根据以下规则进行加密:
- 如果两个字母在同一行, 则将两个字母分别向右移动一位, 如果到达行末, 则移动到行首.
- 如果两个字母在同一列, 则将两个字母分别向下移动一位, 如果到达列末, 则移动到列首.
- 如果两个字母不在同行 / 同列, 则取两个字母对应的矩形的另一个对角线上的两个字母.
以上面的密钥矩阵与明文为例:
C I P H E
R A B D F
G K L M N
O Q S T U
V W X Y Z
ba lx lo on
ba -> db
lx -> sp
lo -> gs
on -> ug3.2 希尔密码(Hill Cipher)
希尔密码 将明文中的字符按照规定的长度分为若干字符组, 然后对每一个字符组进行加密.
设一个长度为2的字符组, $ (p_1, p_2) $ , 则密钥必然为一个 $ 2 \times 2 $ 的矩阵 $ K $ , 加密方式如下:
$$ E: (c_1, c_2) = (p_1, p_2) \times K $$
相应的, 解密方式:
$$ D: (p_1, p_2) = (c_1, c_2) \times K^{-1} $$
其中, $ K^{-1} $ 为矩阵 $ K $ 的逆矩阵.
对于希尔密码而言, 其矩阵的逆矩阵必须存在, 并且矩阵的行列式必须与26互质 (否则矩阵中的分数无法通过取模运算化为整数), 否则希尔密码无法进行解密.
4. 置换密码
置换密码 的特点是: 明文中的字符在加密后保持不变, 只是位置发生了变化.
即定义有限集 $ X $ 上的置换( 双射函数 ): $ \pi:X \to X $
$$ e_{\pi}(x_1, x_2, …, x_m) = (x_{\pi(1)}, x_{\pi(2)}, …, x_{\pi(m)}) $$
$$ d_{\pi}(y_1, y_2, …, y_m) = (y_{\pi^{-1}(1)}, y_{\pi^{-1}(2)}, …, y_{\pi^{-1}(m)}) $$
上式中, $ \pi^{-1} $ 表示 $ \pi $ 的逆置换.
4.1 栅栏密码(Rail Fence Cipher)
In the rail fence cipher, the plaintext is written downwards diagonally on successive “rails” of an imaginary fence, then moving up when the bottom rail is reached, down again when the top rail is reached, and so on until the whole plaintext is written out.
From Wikipedia
栅栏密码是一种简单的置换密码, 将明文按照特定的规则(像一个栅栏)排列, 然后按照自上至下 / 自左向右的顺序读取.
举个例子: Plaintext: WE ARE DISCOVERED. RUN AT ONCE!
按照3个栅栏排列:
W . . . E . . . C . . . R . . . U . . . O . . .
. E . R . D . S . O . E . E . R . N . T . N . E
. . A . . . I . . . V . . . D . . . A . . . C . 形成密文: WECRUO ERDSOEERNTNE AIVDAC
另一种方式是直接将明文进行划分, 横着写, 竖着读:
Plaintext: We are discovered. run at once.
共24个字母, 写成四行:
W E A R E D
I S C O V E
R E D R U N
A T O N C E形成密文: WIRAESETACDORORNEVUCDENE
解密时通过总字母数猜测栅栏数(就是写了几行), 竖着写再横着读就行.
至此, 博主课内需要涉及到的古典密码学算法就可以结尾了.
这篇博文就到这里~
