主题：【原创】被征服的谜――ENIGMA的故事（四）：波兰人的绝地反击（下上） -- 1001n
在研究ENIGMA的加密机制时，我们的Marian Rejewski同志注意到了一个细节。这个细节就是德军的一个规定，也就是上文提到过的对临时密钥进行重复加密的措施。
从原理上讲，德国人的这个规定，的确是有他们的道理的：限于实际应用环境，密码本上记录的密钥首先不可能是无限长的，其次它的数量也不可能是无限多的。因此，理论上无解的“一文一密”方式，在实践中是毫无价值的。他们所能做的，就是尽量减少同一密钥对不同电文的加密次数，以尽可能杜绝被破解的可能。因此，他们办法之一，就是密钥经常更换，比如，1936年前的每季一换。
而每季度的电文数量绝对不是一封两封，当有成千上万乃至更多的电文使用本季度的统一密钥加密后，这个规模的样本数量仍然可能给对手提供破解所需要的信息。为了解决这个问题，德国人在统一密钥的基础上临时设置新密钥再次加密，的确是个在理论上说的通的解决方案。
这个方案构思巧妙，也的确让一般人难以一下发现存在什么漏洞。这个一般人不仅包括你我（马后炮不算，嘿嘿），也包括著名的魔王希特勒。在看过ENIGMA的演示后，深知德国在密码上吃过大亏的希特勒兴奋地表示： “如果没有德国专家的帮助，世界上没有任何人能够解开这个谜”――这也就是说，至少在数学上，我们和很不平常的希特勒没有什么不同：大家都是一般人。
但是一般人看不出来漏洞，不代表我们的天才数学家Marian Rejewski同志也看不出来。下面尽量以通俗的方式解释一下的工作，而不去用什么群论置换之类我自己都不明白的东西来说：）
将问题高度简化，可以做一个简单的模拟。按照上文所说，现在假定德国水兵甲发送电文，在最开始的时候随便在键盘上按了三个字母，并以此对之后的电文进行加密。按照规定，三个字母是不能相邻、重复的，为了防止输入错误，需要连续输入两次。那么，例如他选择的是ATX，输入的自然就是ATXATX。而根据该季度的密钥加密后，出来一个结果，比如说是YBATAV。
为了区别起见，现在开始把每个季度换一次的密钥叫做当前密钥，输入员自己选择的密钥叫做临时密钥。
这样的电文被截获后，Marian Rejewski同志忽略后文，而把这最前六个字母单独拽出来，也就是YBATAV。可以看到，第一个字母Y和第四个字母T都是通过当前密钥，直接加密临时密钥的第一个字母而成的。区别是，Y是第一次加密的结果，T是第二次加密的结果。
这是非常宝贵的信息，因为这个时候，字母Y是使用当前密钥原汁原味加密字母A而成的，转轮都处在当前密钥所规定的初始位置上；再加密其它字母的时候，ENIGMA内部的转轮肯定要旋转了，这个初识位置也就不存在了。因此，这第一个字母的信息是十分宝贵的，它直接反映了ENIGMA的初始状态，也就是当前密钥的情况。
之后再次加密ATX的A时，由于转轮的转动（道理上讲，每加密一个字母转动一次，那么现在应该已经转动3次了），再次加密A的结果变成为了T。这也是很宝贵的信息：因为这次加密用的还是当前密钥，借此可以分析同一密钥对已知相同字母的加密变化规律；并且，一般地讲，加密这前六个字母时，由于加密过程刚刚开始，往往只有最右边的转轮会旋转，其它两个转轮还没来得及开始转动――当然这不绝对――这就大大化简了需要猜测的可能性。
这时候，Marian Rejewski同志还不可能知道这个被加密的第一个字母是A。但是，他可以把Y和T记下来。
之后，他开始研究另一份被截获的电文。它的前六个字母，比如说是这样的：SPNHAI。当然了，这里的S和H，也都是对这份电报的临时密钥的第一个字母经过当前密钥加密而成的。他也把S和H记录下来。
为了更精确地模拟这个过程，我颇花了些时间，用网上的ENIGMA模拟器做了个试验。
首先，在设置模拟器的时候，我选择了9个转轮（模拟器不支持当时用的5个转轮，呵呵）中的1、3、4号转轮，排列是341；
其次，分别把它们调整到随机设置的D、J、O位置上；
最后，连接板的字母交换设置为A与R，C与V，E与P，H与Z，J与X，L与T分别两两交换。
以上这些设置没有什么科学道理，就是随便模拟了某个情况下的结果，都是任意设的：）
为了尽快试验出每个字母的加密结果，我把全部从A到Z的26个字母都做了实验。按照临时密钥是3个字母一组的设定，我把这26个字母分了组，一律符合本身不重复、键位不邻近的原则；这样就分成了9组。而最后一组由于字母不够用了，只好临时加了个A充数。
――累死我了，以下是我的模拟结果：
分组情况是：ATX，BQU，CYF，NOW，KSH，ZMI，DVP，GEJ，LRA。
于是得到：
第一份电文输入：ATXATX――第一份电文显示：YBATAV
第二份电文输入：BQUBQU――第二份电文显示：SPNHAI
以此类推，
CYFCYF――BGYARQ
NOWNOW――DDZEMG
KSHKSH――FJVPYJ
ZMIZMI――SSRHZA
DVPDVP――NTTIGY
GEJGEJ――FZWWLL
LRALRA――KELROD
放弃前面的原始明文不看（真在解密过程中，哪有明文让你看呢，呵呵），只看被加密后显示出的第一和第四个字母，把它们的对应关系记录下来，稍加整理，我们就可以获得一个表：
Y-T，S-H，B-A，D-E，F-P，S-H，N-I，F-W，K-R。
这样就产生了一份换字表。换字表这个概念其实很简单，就是字母被更换替代所罗列的一张表。而我们面前这张换字表，就是由9组临时密钥被当前密钥加密后的第一个字母和第四个字母一一对应而来。
只是，能对应上的字母数量还不够多，还不能把所有字母覆盖全――现在只有9组的对应关系――显然，为了得到覆盖所有26个字母的换字表，我们至少需要罗列出26份密电中的第一个和第四个字母，前提是这些字母正好互不重合。
这么列表太长，于是我偷了个懒，试图直接用上面9组密文中第二个-第五个字母、第三个-第六个字母来构造完成这张表，毕竟，设计的时候，9组字母已经把全部字母都包括进去了嘛。。。而就是这个偷懒的想法，构成了我的错误的第一步。。。
这样的努力很快出现了问题，如第四份显示的DDZEMG：D第一次出现时对应E，第二次出现时则对应M。按说，这才是加密后比较正常的结果，否则如果每个字母都只对应一个字母，那也就成了单字替代了。可是如此一来，我试图构造的完整换字表就出现了问题：字母一一对应的换字表是不允许一夫多妻制这样的重合现象发生的――于是在最小改动的前提下，我惩罚了所有的陈世美们，将整张表修正为一一对应关系，得到的结果就是下面这样的：
左-右
A-C
B-A
C-D
D-M
E-O
F-X
G-R
H-E
I-F
J-Y
K-B
L-V
M-K
N-I
O-N
P-S
Q-P
R-U
S-H
T-G
U-W
V-J
W-L
X-Z
Y-T
Z-Q
现在它们一一对应，绝无重复了――看上去，这张完整覆盖所有字母的换字表的确是很逼真了。但是，逼真永远不是真，因为在随后而来的验证里就出现了问题，且让我继续讲下去：
有了这份覆盖全部字母的换字表后，我们从随便一个字母出发，按上面的一一对应关系找到它对应的字母，并不断地进行这个过程。
比如说，按上面的对应关系，左列的A对应右列的C，而查找左列的C，发现对应右列的D，而左列的D又对应右列的M……于是记录为ACDM……。将这个对应关系从始至终罗列完整，并将26个字母全部包括进去的整理结果如下：
ACDMKBA
EONIFXZQPSHE
GRUWLVJYTG
不难发现，A经过一系列对应后，最后回到了A本身，构成了一个Marian Rejewski同志所说的“字母循环圈”。当然，从这个循环圈里的任一字母出发，最后都会回到它本身，这个例子中只是把A作为了开头和结尾而已。
相应地，E和G也出现了循环圈现象。统计一下可以得知，以上对应表共有3个循环圈；每个循环圈的长度，也就是其中包含字母的数量（头尾重复的只算一个）分别为6、11、9。
而Marian Rejewski同志的光荣和伟大，以及1001n个人的失败和错误，都体现在以下这段话里：
Marian Rejewski同志通过群置换操作，严格地从数学上证明了：根据同一密钥加密后形成的字母循环圈的多少和循环圈的长度，是不随字母两两交换情况而变化的。
他成功了，我失败了……是先夸别人呢还是先检讨自己呢。。。迷茫中。。。算了，还是先检讨自己吧，因为这个错误犯的值得，令我很意外地从另一个角度撞上了ENIGMA加密机制中隐藏的弱点。。。
我的错误就是在对以上得到的字母循环圈进行字母两两交换的验证时发现的：任意选择其中两对字母进行两两交换，应该是不影响字母循环圈的数量和长度的。于是，我随意更换了D/P、M/T两对字母。这时候，对应关系就变成了
A-C
B-A
C-D
D-S
E-O
F-X
G-R
H-E
I-F
J-Y
K-B
L-V
M-G
N-I
O-N
P-M
Q-P
R-U
S-H
T-K
U-W
V-J
W-L
X-Z
Y-T
Z-Q
看起来还是满健康满逼真的啊。可是一用循环圈分析就原形毕露：还是从A出发，就变成了以下这个德行：
ACDSHEONIFXZQPMGRUWLVJYTKBA
这下彻底完蛋，从A出发，竟然一口气把所有字母都串起来了……好好的三个循环圈让我折腾的只剩了一个，长度是26――这个结果真是让人疯狂。。。
我肯定是哪步搞错了，而Marian Rejewski同志肯定是对的。究竟错在哪里了呢？
一直在想……
我想了很久，最后突然找到了答案――实际上，这是个很隐蔽的错误，但是就是这个错误，后来却大大地帮助了英国人！话说回来，如果不是这样，我又何苦把自己的错误一点点贴出来――咱扯的再远，那也是有目的的，嘿嘿。。。
出现这个错误的原因，和我两次比较随意的操作有关（倒是和从9个转轮里选3个关系不大）：
第一次是偷懒，把第一-第四字母的对应关系，强加进第二-第五和第三-第六字母的对应关系（实际上是相当于加密的转轮旋转了，而我默认为没有转，或者转得正好到位；而这肯定是错误的）；
第二次就是因为针对同一字母的重复对应（陈世美现象。。。），我随意地更改了对应关系，虽然其实只改了几个字母，但是，这张换字表已经彻底变了。特别就是这次随意的改动，是本实验完全失败的最重要原因。
事实上我的第二次改动从操作上说并没有什么不对，出现的字母组合也满足一一对应关系，并且没有重复，是符合逻辑的。也就是说，是一张符合严格定义的换字表的。
但是，最要命的地方就在这里：并不是每张符合逻辑，满足一一对应关系的换字表，都能通过ENIGMA机制获得！换言之，经过ENIGMA加密形成的换字表，只是所有可能性中的一小部分，有更多更多的换字表，通过ENIGMA机制是永远制造不出来的！
这个问题稍微深了一点，我们还是用一贯的简化方式来描述吧。
还记得ENIGMA上面那最匪夷所思的一招，也就是象镜子一样的那个反射板了么？因为它的存在，使加密解密的过程是完全一样的。例如，输入ABCD，出现KXMF。那么，解密的时候用同样的密钥之后，输入KXMF，就会出现ABCD――这样，在这个机制下，ABCD和KXMF就被称为是“对合”的。不难理解，出于这个设计，ENIGMA所有的输入和显示都是一一对合的。
根据上面的介绍可以得知，ENIGMA能做出的每张换字表都是“对合”的。道理很简单，它是通过“镜子”“对称”的――这个镜子，就是反射板；这个对称，就是说输入和显示就象镜子里的像一样，是“对称”的。之所以给这里的对称也打上引号，是因为这里所说的对称不是平常意义上的对称，而是经过某种机制歪曲映射后的“对称”。
正如输入ABCD可以获得KXMF，输入KXMF也可以获得ABCD一样，输入和显示在这里互为镜像；只不过，不是平常意义的对称，而是经过ENIGMA加密映射之后显示出来的对称。
把ENIGMA看成一面哈哈镜，也许就更容易理解这里所说的“对称”的意思了。ABCD在哈哈镜里被歪曲成KXMF；在所有特征都完全一样的另一面哈哈镜里，KXMF也会被歪曲成相应的ABCD。当然这毕竟不是镜子，只是打个比方帮助理解――哪位兄弟真拿哈哈镜的例子来质疑，咱是不认地，嘿嘿。
而这个“对称”，就是刚才所提到的对合。
如此一来，问题就出现了。
通过数学分析我们不难知道，对合的换字表，在所有可能的换字表中，只占很小的一部分，甚至是可以说是非常罕见的一种换字表。说它罕见还真不是冤枉它，因为可以算出来――老办法，不给理由前提，只照抄公式：
一般地，如果字母数为N，则
换字表的总数为
N！
对合换字表的总数为
（N-1）*（N-3）*（N-5）*（N-7）*……*5*3*1
具体怎么论证的，还是那句话，别问我，呵呵……根据以上公式我们不难算出，有着26个字母的换字表总数为26！=403291461126605635584000000种，其中对合的换字表总数为25*23*21*19*……*3*1=7905853580625种。
403291461126605635584000000种。
7905853580625种。
上下一比什么都明白了，对合的换字表只占所有的换字表总数的不到50万亿分之一！说对合的换字表罕见，还真不是开玩笑，实在是太太太太太……*5*3*1罕见了！
这就解释了两个问题：
第一，为什么我从一开始那么严格地模拟了ENIGMA的机制，只是最后随意改写了几个字母组合，验证时就惨遭失败――真正的ENIGMA加密后绝对不会形成我上面的那个循环圈结果，因为它肯定是对合的――而我随意的构造正好能对合的概率不到50万亿分之一，真要能成功反而大大见鬼了；
第二，为什么ENIGMA最后怎么改进都逃不过被破掉的命运，因为只要它还有反射板，就决定了它必然只能造出对合的换字表；换字表总数虽然庞大，但是ENIGMA的原理决定了它只能利用了其中不到50万亿分之一……
顺便说一句，1937年，日本人根据ENIGMA-K，并借鉴荷兰、瑞典、美国密码机发展出来的九七式欧文印表机（也就是紫密），就躲开了这个命门，没在里面设置反射板。也就是说在这一点上，日本人的确比德国人聪明了一些。话说回来，改进的机器当然应该比原型机强，否则还改进个什么劲――只是，在没有外人提醒的前提下，日本人能看出这个地方的玄妙，确实也有点厉害。
唉，大大增加了密钥数量而同时又露出了致命的马脚，这个反射板啊――真是成也萧何，败也萧何！
【原创】被征服的谜――ENIGMA的故事（二）：ENIGMA横空出世（上）
http://www.cchere.net/article/372331
【原创】被征服的谜――ENIGMA的故事（二）：ENIGMA横空出世（下）
http://www.cchere.net/article/372349
【原创】被征服的谜――ENIGMA的故事（三）：丘吉尔托起的灿烂星座
http://www.cchere.net/article/374308
【原创】被征服的谜――ENIGMA的故事（四）：波兰人的绝地反击（上）
http://www.cchere.net/article/375877
【原创】被征服的谜――ENIGMA的故事（四）：波兰人的绝地反击（中上）
http://www.cchere.net/article/377011
【原创】被征服的谜――ENIGMA的故事（四）：波兰人的绝地反击（中中）
http://www.cchere.net/article/378141
【原创】被征服的谜――ENIGMA的故事（四）：波兰人的绝地反击（中下）
http://www.cchere.net/article/379376
【原创】被征服的谜――ENIGMA的故事（四）（篇外）：最年轻的数学家
http://www.cchere.net/article/383181
本帖一共被 10 帖 引用 (帖内工具实现)
不过这两本书的作者显然不如1001n专业和敬业哦，写的避实就虚，可以当个故事看就是了。1001n功德无量，鲜花供奉。
献花！
麦家连摩尔斯电码都能说成福尔斯电码，
让人大倒胃口
而且他说紫密的核心就是没有密
纯粹胡扯
前面几篇勉强骗自己说看懂了，可是这篇实在是没办法了，送朵花表示一下崇拜吧。
我研究了一下1001n兄的意思，用数学的方法解释似乎是这样：
设原始的字母数组α＝[A,B,C,D...X,Y,Z]，这个enigma机加密的过程可以用一个矩阵γ来表示，最后加密出来的字母数组β=[B,X,W,F,...A,R,S]（我瞎编的）。那么，数学上的写法就是：β＝αγ。这个对合的意思呢，就是说反过来写的话，α＝βγ也能成立了。这样一来的话，γ矩阵就得是狠特殊的一类形式了。本来γ是可以随便取的，可enigma加的这个反射板一弄，能产生的γ就少了很多。这样一来，自然破解比较容易。
这样的矩阵还真是不多。