【计算机博物志】战争密码（中集）蝴蝶的翅膀

波兰人尝试用上级提到的语言学密码破解方案，搞不定了（由于不是暴力替换

）

整/数学家！破译！

多标替换消除统计学特征

恩格马做到了一字一换表，所以很难整

一天一换秘钥，有风险

这时候秘钥容易透露到别的国家

使用随机秘钥，然后先用统一秘钥加密随机秘钥，把随机秘钥再使用。

也就是

如果en函数是恩格马函数的话

en2(pwd, text) = en(unique_pwd, pwd) + en(unique_pwd, pwd) + 注意这里和en(unique_pwd, pwd) * 2的区别en(pwd, text)

但是因为前六个字母有了重复

这个妙了：把一个恩格马机分成6个转子不动的恩格马机

后用xyz表示这三个

我们有了一个函数（就是en函数啊）

标注为abcdef（我会标注为a1,a2,a3,a4,a5,a6）

恩格马机有一个问题（看过我上期笔记的童鞋都知道）

对于所有的n，满足对于所有的x，满足an(an(x)) = x

所以F = a1(X)则 a1(F) = X，所以G = a4(a1(F))

L = a5(a2(J)) V = a6(a3(B))，这里就是真妙

然后我们知道了

a41、a52、a63函数的（从N份密文得出）的对应关系

有了一个对应表：

like this:

现代数学的开端——群论！

简单介绍一下：

一个群（group）是指一些操作的集合（要求这些操作可以叠加）

比如整数加法群

操作有（前面省略把一个数）

……减3(-3)，减2(-2)，减1(-1)，什么也不干(0)，加1(+1)，加2(+2)，加3(+3)……

这个操作叠加起来就是加法，而0被称为identity（对于任意的x，x 操作 identity = x）其中操作满足交换律、结合律、……

算了扯得有点远了qaq

这里可以把a41、a52、a63试做一个图论的图：

这样就有了up猪所说的循环圈（图论中叫做环）

这就变成了一个图like this:

（真的很肝！）

把一个循环的字母放进一个括号：

(VYLP) (FGDW) (ARSETZJHX)(OCNMKUIBQ)

a52和a63关系也能整出循环圈（肝不动了eve）

然后把每个循环圈的长度的数列 称为 特征集合（指纹） of ZBY

AAA、AAB、……、ZZZ分别有不同的指纹

使用80+份的密文得到特征集合，对应出秘钥

但是有接线板啊

这里发现字母交换不会改变特征集合

（接线板在做单表替换，所以只要破解不带接线板的就可以破解带接线板的）

但是特征集合的逆推过程需要26^3种，如果没有一个快速求的公式，就很难搞了

还记得a(1-6)吗？

我们

雷耶夫斯基定理：对于一个恩格吗回路a，特征集合中必然存在一个|a|/2的数（|a|是a的长度）

a1(A) = N

a4(N) = J

a1(J) = G

a4(G) = Q

a1(Q) = S

a4(S) = E

a1(E) = H

a4(H) = A

你想想，AD组合是不是 A->G->S->H->A?因为a1(a4(x))是这样跳过两步嘛

于是还有了N->G->S->H->N

为什么？因为跳过了两步，偶数位置上就空出来了，而且易得

对于所有的a1-a4（和a14不一样）循环圈中的成员，由它开始一定做a14运算迭代几次后回到该成员。

这里不就说 A->G->S->H->A和N->G->S->H->N都是回路了吗？这样定理得证。

很快得到特征集合

“循环测定仪”

两套恩格吗机转子（称为m和n）

AAA的位置：把初始位置调到AAA-1+1(这里定义字符串加法：就是A+1=B,B+1=C,……，Z+1=进位)

把第二个转子调到AAA-1+4

就像如此

这些被电路穿过的灯泡被点亮，就完成了一个回路

有了两个8/2=4的循环圈然后把没亮的字符开关拨上去，这次18/2了

然后左2(AAA-1+2)右5(AAA-1+5)

测定出a52循环圈数据

还有a63的

然后测量下一个秘钥

这样得到恩格吗特征集合表

整了5个转轮

研究bomba机器

失败了：不再输入两次

于是这里我不谈历史，友情图灵出现