向密码挑战的故事
向密码挑战的故事
前言
向密码挑战是西蒙.辛格《密码故事》书后列出的10个密文，需要用到书中介绍过的密码学技术逐一破解。2000年10月一个瑞典团队破解了所有密文，这里就是西蒙关于这个故事的文章，其后是破解团队解密的经历。即使没有读过西蒙的书，看一看对10个密文破解的过程也能一窥密码学的历程。
内容和格式与作者网站并不一致，这里将链接的信息集中在一起便于阅读，但也保留了原始链接。
向密码挑战的故事
向密码挑战是《密码故事》书后的10个加密信息。解读所有10个密文除了挑战智力的乐趣之外，我还提供一万美元的奖金给第一个解密成功的人。
在世界各地众多爱好者和专业解密者孜孜不倦的努力下，2000年10月7日，书出版一年零一个月后，挑战被正式攻克。这里要讲述的就是向密码挑战背后的故事，包含了解决这个挑战的瑞典团队非常值得一读的报告，还有可以认为是第二名的Jim和John的文章。
这个榜单显示了谁最先破解了哪部分信息:
Stage 1, Solved by Carolyn Hawkes from Edinburgh on 1 September 1999
Stage 2, Solved by Alec McEachran from Staffordshire on 2 September 1999
Stage 3, Solved by Roger Gunn from Ealing Common on 7 September 1999
Stage 4, Solved simultaneously by Souraya Dyer from London and Roger Gunn from Ealing Common on 8 September 1999
Stage 5, Solved by Andrew Plater from Cambridge, England on 7 December 1999
Stage 6, Solved by Andrew Plater from Cambridge, England on 15 December 1999
Stage 7, Solved by Andrew Plater from Cambridge, England on 14 January 2000
Stage 8, Solved by Andrew Plater from Cambridge, England on 14 January 2000
Stage 9, Solved by J. Gillogly & J. Palagyi from America on 20 September 2000
Stage 10, Solved by the winners! Fredrik Almgren et al, from Sweden on 7 October 2000
一些关于这个挑战的照片:
Stealth Swedes
这里是密文，虽然答案已经揭晓，你仍然可以试着自己破解一部分。
Stage 3 和 Stage 4 困难一些 – 3可能比4要难，所以你要是被3卡住了可以先跳过它。
Stage 5 出了名的困难。
Stage 6, Stage 7 和 Stage 8 很难，但是由爱好者解决了它们。
Stage 9 需要用到计算机。
Stage 10 需要大量的计算和智慧。
如果你想了解密码挑战的更多背景可以继续往下读，也可以看看这几篇文章，Telegraph和Hindu，这里是他们是如何破解以及这个竞赛之前的一些归档材料。
cheque
注意以下情节包含剧透！
当我开始写《密码故事》这本书的时候，很自然的觉得一本关于密码和解密历史的书中应该包含一些加密的信息来让读者活动一下头脑。
我决定用10种不同的方式加密10条信息，它们的难度逐渐递增。我希望所有的读者至少都能破解前几条密文并能体验到破译的乐趣。我也希望一些为之着迷的读者在尝试6，7，8阶段时学习到相关的更为复杂的技巧。当然，我期望少数专业读者和密码学爱好者能够完成全部的挑战。
向密码挑战的主要目的是用谜题激发人们对破译的兴趣。看起来这个目的已经达到了，有成千上万的人投入其中。我相信这些人有着旺盛的好奇心并乐在其中。一万美元的奖金仅仅是增加了一点刺激。
我在写书的同时构思这个挑战，所以总的算来用了两年的时间准备。挑战的编制非常秘密，我很小心的防止相关材料的泄露。每当我完成一个阶段的记录、加密、校验和确认的过程，我会烧掉所有相关的材料。我会定期到小花园里，将材料蘸上蜡油然后点燃。
编制谜题的每个阶段也是吸收的过程。在恩格玛阶段我用到了计算机模拟器。为了确认正确性我设计了一个有六条纸带的纸质恩格玛机器，滑动纸带就可以模拟机器的转子动作。
向密码挑战有如下的原则：
-
10个阶段难度依次递增，每个人都能参与其中的几个阶段
-
加密技术按年代顺序
- 经典替换
- 凯撒密码
- 同音替换
- 维吉尼亚（维热纳尔）密码
- 书卷密码
- 普来费尔密码
- ADFGVX密码
- 恩格玛密码
- DES
- RSA
-
密文使用了多种语言（共6种）。例如在第二阶段是用凯撒密码加密了一条拉丁语信息，在第四阶段用维热纳尔密码加密了法语信息。这增加了破译的难度，不过也使其更有趣，对世界各地的人来说也更加公平。这是个世界范围内的竞赛。
-
前面的几个阶段适合所有人，后面则需要更深入的技能。我猜获胜者可能是由破译古代密码和熟悉DES/RSA的密码学专家组成的团队。而且我认为年度奖金会被业余爱好者获得，最终的胜利是由专家团队赢取。这种事情多多少少总在发生。
-
第十阶段设计为当前最难的公开密码挑战。我希望它的破译能够衡量当前解密的水平并借此促进算法的发展。
向密码挑战的第九和第十阶段是我信赖的密码专家保罗莱兰帮助设计的。他在微软工作，是世界上唯一一个知道这两个密码答案的人。1993到1994年，保罗带领全球600人合作破解一个RSA-129的挑战，这可能是当时计算量最大的一件事情了。总之他是一个合适的人选来帮我构建难以破解的第十个密文。
向密码挑战开始于1999年9月，《密码故事》于美国和英国出版的时候。随后译有芬兰语、法语、德语、丹麦语、挪威语、西班牙语和瑞典语版本。
很快许多网络讨论组就成立了，有2500多成员的e-Group是其中最大的一个，他们通过邮件提供支持，交换建议并相互鼓励。我潜伏在这个小组里，常常惊讶于其中的进展和突破。最有意思的是看著名的关于第五阶段的各种猜想。
另一个方面反映了向密码挑战的广泛兴趣是在牛津举办的密码研讨班，来自英国、美国、瑞典、瑞士和挪威的人聚在一起。无论我在英国或海外做讲座，我总能碰到各种经历各个年纪挑战密文的人，有新手，有学生，有数学家和密码专家，甚至还有菲尔兹奖得主。
向密码挑战的进度和简要描述列在上面的榜单里，这里就不再赘述。不过我要说一开始我觉得我设计的太简单了，因为头四个阶段很快就被破解了。还好第五阶段挡住了这波浪潮，但是没多久我就看到Andrew Plater已经推进到第八阶段了。
下一个突破来自Jim Gillogly, John Palagyi和EFF组成的团队，他们解决了阶段1-9的谜题。Jim和John写下了他们探索的过程。
我曾经说过在2001年10月1日给领先的人1000美元奖金，吉姆，约翰和EFF当之无愧的得到这个奖励。
仅仅一周之后，出版社收到了来自一个来自瑞典研究团队的传真声称它们已经完成了全部的挑战。两天后（10月7日）正式的邮件也到了。我给他们的代言人Fredrik打电话，不过他表现的非常谨慎。这些瑞典人怎么能确定跟他们通话的真是西蒙辛格还是某些想窃取他们答案的骗子？我是这个世界上除了他们之外唯一知道明文的人，这个事实最终让我们相互信任。
挑战结束了。
这个瑞典团队的成员是：弗雷德里克（Fredrik Almgren），贡纳（Gunnar Andersson），托比约（Torbjorn Granlund），拉斯（Lars Ivansson）和斯塔凡（Staffan Ulfberg）。
他们在《密码故事》出版不久后就开始研究，此时弗雷德里克还在伦敦参加一个庆祝活动。
不象其他的参与者，他们从不公开讨论自己的工作直至完成全部的十个阶段，这种秘密的方式看起来很有效。他们写下破解的过程，一份40页的文档：
| HTML | PS | DVI |
|---|
这个报告不仅总结了他们自己的破译方法，还涉及到密文、秘钥、明文和策略等方面。
对密码学专家来说他们成就中最引人注目的地方是没有用超级计算机就破译了第十阶段。瑞典团队写了一个能在“普通”计算机上运行的数域筛法算法，演示了不用超级计算机就能处理大数因子分解。
向密码挑战的主要目标是激起人们对密码学和破译的兴趣，有数千人参与了挑战已经很令人满意。
第二个目标看看当今加密的强度。阶段十代表了某种程度上网络安全所用到的加密方式。不过它被破解并不是说我们从此就要忧心于网络安全问题。才华横溢的瑞典研究员组成的团队用相当强劲的计算设备花费了数周时间才最终解密了阶段十。这对那些想窃取你的信用卡信息的窃贼们来说一点都不实用，因为他们要付出数万元才能获得一个限额可能只有1000元的信用卡信息。再说，用一个比阶段十强出几个数量级的秘钥也很容易，这是一个从实效角度讲无法破解的加密系统。
更重要的地方或许在于RSA也用作数字签名，阶段十所用的512位秘钥是使用最广泛的。签名需要在几十年的时间中保证其真实性，所以我们需要在将来计算机能力极大提升后仍然确信签名的可靠性。如果解密者破解了你的RSA秘钥他就能伪造你的签名。使用1024位的秘钥可以建立很高的安全性，但是自然的惰性让很多人还是继续使用512位的秘钥。这个事例说明随着解密者能力的提高，监督和更新加密标准的重要性。
第三个带着点乐观倾向的目的是希望这个挑战可以产生一些新的破译技术。瑞典团队实际上重写了数域筛法的算法让它能跑在相对较弱的计算机上，演示了不是一定要用超级计算机来分解大数。
在这一点上，向密码挑战确实是结束了。
当我在准备这个挑战的时候，我有时在想它是否值得这么做。会有人对这个挑战感兴趣吗？最终读者们的反应相当好，我惊讶于你们的热情、专注、毅力、独创性、幽默感和智慧。
当然，祝贺获胜者。这包括约翰和EFF，他们当之无愧的努力获得了1000元奖金。特别要提到吉姆，在过去一年里他以极大的耐心给新的破译者和可能的竞争对手提供了无数的建议和支持。
我们不能低估优胜者的成就。用一种创新的方式解决阶段十对密码学社区有重大意义。不仅仅是弗雷德里克，贡纳，托比约，拉斯和斯塔凡展现了破解现代计算机密码的天份，他们也解密了大量的古典密码，从单字母替换到恩格玛密码。完成这一切需要大量的技能。
最后，感谢每个参与向密码挑战的人，是你们让它如此成功。遇见来自世界各地的挑战者（从悉尼到密尔沃基）是一件愉快的事情，我希望能碰到更多的人。如果现在遇到你，我至少可以不用保密了。作为一个话唠过去两年实在很难熬。
更多关于破译向密码挑战的新闻：
The Daily Telegraph, Thursday 12 October, 2000
Ny Teknik, October 2000
Svenska kodknackare vann Simon Singhs chiffertavling (瑞典语)
Plus Net Magazine
