1701018530
1701018531
（8）字母信号再从左边转轮、中间转轮、右边转轮和插口板依次传回，每经过一处都要作一次字母替换；
1701018532
1701018533
（9）最后，信号传到字母板上，使相应字母下面的小灯泡闪亮，这就是加密后的字母。
1701018534
1701018535
由于反射轮的作用，使得“隐谜”的解密变得很简单，其过程与加密相同。在设定好了与加密时一样的转轮初始值和插口接线后，在键盘上打入密文，则经过以上步骤后，在字母板上就显出了明文。
1701018536
1701018537
从以上的加密过程可以看到：从明文到密文，一个字母要经过至少7次至多9次的替换，而且对于转轮的不同状态、插口板的不同连接以及套接圆环上不同的字母排列顺序，其替换都是不同的。所以“隐谜”的加密方法比以往任何的加密方法复杂得多。谢比乌斯因而在向德国海军推销自己的产品时，很自信地说，即使敌人拿到了一台“隐谜”机，也破解不了密码；即使他们掌握了“隐谜”机的加密原理并获得了一部分密码，也发现不了密钥（即“隐谜”机的初始设定）。
1701018538
1701018539
“隐谜”机的市场销售并不好。直到后来，德国人意外地从丘吉尔的回忆录中得知，在第一次世界大战中，自己的密码系统早被英国人破译，因此遭受了惨重损失。德军于是开始着手改进自己的密码系统。这时，他们看中了“隐谜”这一革命性的密码装置。1926年，德国海军开始采购“隐谜”机，同时要求对它进行彻底地改装，使得它比商用的“隐谜”机更复杂更安全；2年后，德国陆军也开始使用。1933年，纳粹上台。不久，希特勒撕毁《凡尔赛条约》，开始肆无忌惮地扩充军备，“隐谜”机则成为德军最重要的秘密通信工具。
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