恩格玛机研究
恩格玛机是一战之后德国发明的一种密码机, 在二战中广泛使用.
很早之前就对恩格玛机有很大的兴趣, 昨天, 看到了一个系统性讲解恩格玛机加密以及破译工作的视频, 这里简单解释/记录一下.
B站视频: 上: 恩格玛机加密原理 中: 波兰数学家的破译工作 下: 英国数学家的破译工作
凯撒密码
凯撒密码是一种很简单的加密方式, 通过设定的key
对明文进行偏移, 从而得到密文.
凯撒密码的实现已经成为了目前计算机专业初学者练手的题目
def caesar_encrypt(msg: str, key: int) -> str:
code = ""
for _ in msg:
if _ == ' ':
code += ' '
else:
code += chr((ord(_) - ord('A') + key) % 26 + ord('A'))
return code
def caesar_decrypt(code: str, key: int) -> str:
msg = ""
for _ in code:
if _ == ' ':
msg += ' '
else:
msg += chr((ord(_) - ord('A') - key) % 26 + ord('A'))
return msg
但是凯撒密码的破译也很简单, 由于key
只能取0 - 26
, 因此只要穷举这26种情况, 观察哪种情况看起来是"人话"即可.
def caesar_decode(code: str):
for key in range(26):
msg = ""
for _ in code:
if _ == ' ':
msg += ' '
else:
msg += chr((ord(_) - ord('A') - key) % 26 + ord('A'))
print(f"{key} : {msg}")
当明文为HELLO WORLD
, key = 3
时, 密码为KHOOR ZRUOG
, 则caesar_decode("KHOOR ZRUOG")
结果为:
0 : KHOOR ZRUOG
1 : JGNNQ YQTNF
2 : IFMMP XPSME
3 : HELLO WORLD
4 : GDKKN VNQKC
5 : FCJJM UMPJB
6 : EBIIL TLOIA
7 : DAHHK SKNHZ
8 : CZGGJ RJMGY
9 : BYFFI QILFX
10 : AXEEH PHKEW
11 : ZWDDG OGJDV
12 : YVCCF NFICU
13 : XUBBE MEHBT
14 : WTAAD LDGAS
15 : VSZZC KCFZR
16 : URYYB JBEYQ
17 : TQXXA IADXP
18 : SPWWZ HZCWO
19 : ROVVY GYBVN
20 : QNUUX FXAUM
21 : PMTTW EWZTL
22 : OLSSV DVYSK
23 : NKRRU CUXRJ
24 : MJQQT BTWQI
25 : LIPPS ASVPH
观察可知3
时, 输出结果为合法单词, 这样暴力破解即可轻松破解凯撒密码.
之后便有了新的密码对应方案, 使用随机对应关系进行编码
import random
code_book = [chr(_) for _ in range(ord('A'), ord('Z') + 1)]
print(code_book)
random.shuffle(code_book)
print(code_book)
这样我们得到一个随机的密码本
code_book = ['J', 'U', 'Y', 'E', 'V', 'B', 'A', 'W', 'R', 'T', 'C', 'S', 'Z', 'D', 'I', 'G', 'K', 'Q', 'P', 'M', 'O', 'X', 'N', 'L', 'H', 'F']
此时编写加密/解密程序为:
def random_encrypt(msg: str, code_book: List[str]) -> str:
code = ""
for _ in msg:
if _ == ' ':
code += ' '
else:
code += code_book[letter.index(_)]
return code
def random_decrypt(code: str, code_book: List[str]) -> str:
msg = ""
for _ in code:
if _ == ' ':
msg += ' '
else:
msg += letter[code_book.index(_)]
return msg
测试如下:
print(random_encrypt("HELLO WORLD", code_book))
print(random_decrypt("WVSSI NIQSE", code_book))
WVSSI NIQSE
HELLO WORLD
该方法暴力破解难度大大增加, 如果穷举所以可能, 情况数为26的全排列, 是一个非常大的数.
但是, 单独一句话无法得出结论, 若得到大篇幅信息, 可以得到统计规律.
字母使用频率是不均匀的, 大概顺序为ETAON RISHD LFCMU GYPWB VKJXQ Z
.
根据字母分布信息, 我们即可推测出密码本, 但是这需要大量信息来统计. 不过对于截取敌军电报, 以及部分错误但大体正确的明文, 语言学家人工解密完全可行.
使用一个密码本, 字母存在统计规律. 但是, 如果我们使用两张密码本交替使用, 字母的统计规律将大大缩小.
如果是更多的密码本, 字母频率将区域平衡, 最优解便是每打一个字, 便换一个密码本.
但是, 这样做及其复杂, 且人工极易出错, 因此, 恩格玛机诞生了.
恩格玛机使用
恩格玛机拥有键盘, 显示器(对应26个字母的灯泡), 接线板, 转子组, 电池等结构.
加密时, 拨动转子组到初始位置(密码本), 按下按键, 记录显示器显示的字母. 此时转子组自动转动, 等待下次输入.
解码时, 拨动转子组到初始位置(密码本), 按下按键, 记录显示器显示的字母. 此时转子组自动转动, 等待下次输入.
也就是, 初始状态相同时, 加密和解码步骤完全相同, 输入明文得到密码, 输入密码得到明文. 这被称作可逆性.
同时恩格玛机可以做到按下A
时, 绝不输出A
, 这被称作排己性.
机械原理
加密时, 恩格玛机内部原理如下:
首先将转子组拨动到某位置, 然后按下键盘对应按键, 信号经接线板初次交换之后, 进入转子组进行第二次交换, 转子组交换十分复杂.
信号从转子组返回后, 再次进入接线板进行第三次交换, 之后输出在显示器上, 对应灯泡亮起, 加密结束.
同时, 转子组转动一下, 进行换表.
接线板原理不难解释, 实际上就是将对应开关和灯泡连接起来. 例如, 使用接线连接A
, B
对应的孔, 此时按下A
, 进入转子组进行计算的是B
, 反之亦然, 从转子组返回的信号输出时也会同样的交换.
也就是说, 接线板实际上就是一次随机换表
, 若只有接线板, 语言学家仍可轻松破译, 下面介绍恩格玛机核心部分, 转子组
.
转子组
转子组由三个转子和一个反射板组成, 每个转子两面各有26个触点, 代表A - Z
, 之间通过乱序的导线连接, 代表随机的对应关系. 三个转子内部连线互不相同, 同一批次的恩格玛机三个转子连线分别相同且无法更改.
使用时, 信号从右侧进入第一个转子, 进行交换X1 = R1(C)
, 然后从第一个转子某处X1
输出进入第二个转子, 进行交换X2 = R2(X1)
, 接下来再进入第三个转子, 进行交换X3 = R3(X2)
, 最终从X3
输出到达反射板.
此时信号进入左侧的反射板, 这是恩格玛机两个性质的由来.
反射板有26个触点, 代表A - Z
, 内部通过乱序的导线连接随意两个触点, 假设内部M
, N
触点相连, 则输入M
, 输出N
, 反之亦然.
这就做到了可逆性. 同理, 输入M
, 绝对不可能输出M
, 这就做到了排己性 (经过三个转子后会不会再次变回M
, 稍后解释)
信号进入反射板后, 进行交换X4 = R(X3)
, 之后回到第三个转子, 第二个转子, 第一个转子, 进行交换X5 = R3(X4), X6 = R2(X5), X = R1(X5)
, 输出.
上述过程中, 一共经过两次R1
, R2
, R3
交换和一次R
交换, 完整过程为:
R1
, R2
, R3
都是一一对应关系, 上述过程中, X3
X4
, 而(X2, X3)
和(X4, X5)
通过R3
对应. 那么X3
X4
, 则X2
X5
, 同理X1
X6
, C
X
, 即排己性.
同理上述所有关系都是一一对应关系, 则上述关系可逆, C => X
等价于X => C
, 这样从数学角度论证了转子组的原理和性质.