恩格玛机研究

恩格玛机是一战之后德国发明的一种密码机, 在二战中广泛使用.

很早之前就对恩格玛机有很大的兴趣, 昨天, 看到了一个系统性讲解恩格玛机加密以及破译工作的视频, 这里简单解释/记录一下.

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交换, 完整过程为:

$$C\stackrel{R1}{\Rightarrow }X1\stackrel{R2}{\Rightarrow }X2\stackrel{R3}{\Rightarrow }X3\stackrel{R}{\Rightarrow }X4\stackrel{R3}{\Rightarrow }X5\stackrel{R2}{\Rightarrow }X6\stackrel{R7}{\Rightarrow }X$$

R1, R2, R3都是一一对应关系, 上述过程中, X3$\ne$X4, 而(X2, X3)和(X4, X5)通过R3对应. 那么X3$\ne$X4, 则X2$\ne$X5, 同理X1$\ne$X6, C$\ne$X, 即排己性.

同理上述所有关系都是一一对应关系, 则上述关系可逆, C => X等价于X => C, 这样从数学角度论证了转子组的原理和性质.