1701018540
1701018541
3.波兰数学家首作贡献
1701018542
1701018543
第一次世界大战后的波兰，处于一种尴尬的境地。她东邻苏联，西接德国；两个强大的邻国一直在虎视眈眈，觊觎着她的领土。当时的波兰就像一只身处险境的野兔，要时刻竖起警惕的长耳，留心着不怀好意邻国的一举一动。隶属于波军总参谋部情报机构的密码局，就是波兰的长耳，它一直在监听国外的无线电通信。虽然波兰的国力远不如她的邻国，却拥有欧洲顶尖的密码技术。他们对德国人的密码系统一直了如指掌。然而，到了1928年，波军密码局发现德军开始使用一种全新的密码，这种新密码根本无法破解，这使他们感到日益不安。
1701018544
1701018545
不久，他们做出了一个很有远见的决定：培养数学专业的学生来帮助破译德国人的密码。当时的这种做法实属一项创新举动，因为那时人们都认为破译密码不需要多少数学知识。许多国家都请语言分析专家、纵横字谜高手和国际象棋冠军来破译密码，很少找专业的数学家帮忙。后来的事实证明，只有采用数学方法，才能对付“隐谜”这样的密码。
1701018546
1701018547
1929年1月，波兰波兹南大学数学系的一群20多岁的大学生和部分研究生被要求宣誓保密，然后开始学习一门密码学课程。学生们每周上两个晚上的课，几个星期后就开始破解各种密码，那些无法完成破解功课的学生则被淘汰。随着课程的深入，破解的密码越来越难，过关的学生也越来越少。最后只剩下3名最优秀者，他们是雷耶夫斯基（Marian Rejewski，1905—1980）、齐加尔斯基（Henryk Zygalski，1907—1978）和鲁日茨基（Jerzy Rozycki，1909—1942）（图9.3.4）。正是这三位年轻的波兰数学家，后来破译了曾经被认为是不可能被破译的“隐谜”密码。其中雷耶夫斯基居功至伟。
1701018548
1701018549
1701018550
1701018551
1701018552
▲ 图9.3.4 雷耶夫斯基、齐加尔斯基和鲁日茨基
1701018553
1701018554
1932年夏，雷耶夫斯基、齐加尔斯基和鲁日茨基一起正式加入了密码局。同年10月，密码局的领导就把那个谁也拿它没办法的德军新密码交给雷耶夫斯基破译。令他们喜出望外的是，这位年轻人在数周之内就取得了进展。
1701018555
1701018556
由于常规的破译方法对于“隐谜”密码毫无作用，雷耶夫斯基决定另辟蹊径，从分析密码机的工作原理着手。他发现从数学的角度来看，密码机的作用就是对26个字母进行置换，而所有可能的置换通过合成关系形成了一个置换群[1]。
1701018557
1701018558
雷耶夫斯基于是建立了“隐谜”的置换群方程，并断定只要解出这些方程，就能够破解它的密码。但是在一般情况下置换群的结构很复杂，所以这些方程几乎无法解出。幸运的是，他发现了“隐谜”两个致命的弱点，使得局面完全改观。
1701018559
1701018560
其中一个弱点来自于密码机的结构。如上小节所述，密码机上有个反射轮，由于该轮的作用使得加密和解密的过程完全一样，即如果键入字母a得到x，则键入x就得到a。如此操作当然很方便，但对于密码的安全来说，这种方便是一场灾难。雷耶夫斯基发现，由于“隐谜”的这一功能，使得它的置换群结构变得简单：所有的置换都是字母的两两对换（transposition）。这就大大降低了求解置换群方程的难度。
1701018561
1701018562
“隐谜”的第二个弱点来自于它的操作规程。如前所述，每份“隐谜”电文的开头都有一组6字母的密钥字符串，它是通过把转轮初始位置的3字母密钥重复加密得到的。重复加密的目的是为了确保接收方能够获得解密电文所需的密钥，但它也提供了雷耶夫斯基求解置换群方程的钥匙：比如说，在某天“隐谜”的某一份密文中，其起首的密钥字符串为
1701018563
1701018564
dmpvbm,
1701018565
1701018566
则可以假设加密前相应的明文字母是xyzxyz，这xyz三个字母就是该电文的密钥，也就是加密电文时3个转轮的初始位置参数，它们对于破译者来说是未知的。用置换的语言来描述：如果假设密钥字符串上第1个位置上的置换为T1，第2个位置为T2，…，第6个位置为T6，则有
1701018567
1701018568
T1(x)=d,T2(y)=m,T3(z)=p,T4(x)=v,T5(y)=b,T6(z)=m.(1)
1701018569
1701018570
其中T1，…，T6当然是未知的。但是根据以上分析，知道T1，…，T6都是两两对换的置换。所以有T1（d）=x，T2（m）=y，T3（p）=z。于是从（1）式可以得到
1701018571
1701018572
T4(T1(d))=v,T5(T2(m))=b,T6(T3(p))=m.(2)
1701018573
1701018574
这样，如果令置换A为T1和T4的合成，B为T2和T5的合成，C为T3和T6的合成，则置换A，B，C是部分可知的。雷耶夫斯基观察到，只要一天能够截获80份“隐谜”密文，则26个字母都会在密钥字符串的1到6的每个位置上出现。这样就可以完全决定置换A，B，C！雷耶夫斯基把这三个置换称为这一天“隐谜”密码的“特征集”，因为它在一天里不变。
1701018575
1701018576
下一步是要通过特征集求出T1，…，T6。注意到T1，…，T6都是两两对换，所以特征集中的置换都是由两个两两对换合成的，雷耶夫斯基证明了这样一条关于两两对换合成的置换群定理。
1701018577
1701018578
定理 在由两个两两对换合成的置换中，所包含的长度相同并且不相交的圈的个数总是为偶数；反过来，如果一个置换中出现的长度相同并且不相交的圈的个数总是偶数，那么，它一定可以分解为两个两两对换的合成。（说明：如果在一个置换中，把两两不同的元素a1换成a2，a2换成a3，…，an换成a1，则称该置换包含一个长度为n的圈，记为（a1 a2…an）。例如，“两两对换”其实就是长度为2的圈。）
1701018579
1701018580
这条定理被人称为是“打赢第二次世界大战的数学定理”！它给出了求解T1，…，T6的方法：只要找出特征集置换的所有对换合成就可以了。
1701018581
1701018582
再下一步是要确定转轮上的接线方式。从理论上讲，只要通过比较多天的特征集并利用置换群方程（2），就能够做到这一点。当然，需要很复杂的计算。然而，雷耶夫斯基的面前突然出现了一条捷径。
1701018583
1701018584
1932年12月，法国密码局局长贝特朗（Gustave Bertrand）造访波兰密码局。他随身带来一包东西，里面是德军关于“隐谜”密码机的操作手册和1932年9月和10月的两个月里的每天“隐谜”的初始条件值，即转轮的排列与起始位置以及插口板上的接线方式！原来这些材料是德国密码局中负责掌管“隐谜”资料的军官施密特（Hans Thilo Schmidt）为了赚钱而出卖给法国人的。但是法国人拿到这些东西却不知道如何利用。因为法国和波兰有情报合作协议，所以就复制了一份送给波兰密码局。
1701018585
1701018586
雷耶夫斯基拿到了这些宝贵的材料后，立即利用其中详细的数据算出了每个转轮上的接线方式。至此，德军使用的“隐谜”密码机的结构已经完全清楚了。为了进一步破译的需要，波兰密码局立即仿制了数台“隐谜”机。这是在1932年年底。就在这个时候，雷耶夫斯基的两个同学，齐加尔斯基和鲁日茨基，也加入了破译“隐谜”的队伍。
1701018587
1701018588
这三位年轻的波兰数学家先后设计了回转机（Cyclometer）、穿孔纸和“炸弹”（Bomba）机等设备。其中回转机相当于把两台“隐谜”机对接，而“炸弹”机（据说这一名字是鲁日茨基借用当时的一种冰淇淋名而得来的）相当于把6台“隐谜”机连接在一起。有了这些设备，就能针对德军“隐谜”机不同的使用情况，获取其每天的初始设置参数。至此，“隐谜”遂告破解。以后几年，波兰密码局每天都可破译大量的德军电报。
1701018589