古代

通过隐藏而实现保密的隐藏术

仅仅将密文隐藏起来的隐藏术（steganography），也是保密的一种形式，例如：

• 希波战争中，狄马拉托斯Demaratus通过将刻字模板涂上蜡掩盖的方式，警告故土关于薛西斯一世Xerxes的阴谋（尽管很多历史学家认为这是编造的）；
• 中国古代将写有文字的丝绸藏于蜡中，随后让信使吞下。

显然，单纯的隐藏术一旦被发现就无法挽回。因此，人们开始研究加密术，以便第三方即使看到密文，也无法理解其中的含义。

加密术：换位和替换

加密术（cryptography）可以被粗略的分类为transposition（换位） 和 substitution（替换）两类。

• 世界上首个军用加密装置（斯巴达的scytale）使用了换位的技巧，需要通过将写有密文的皮带缠在特定直径的scytale上来解读；

• 首个有记载的军用替换式密码是著名的凯撒密码：最基础的形式是根据字母表平移（例如将D变为A，E变为B，等等）。

无论换位还是替换，都可以理解为：通过某种算法（algorithm），将密钥（key）应用于明文（plaintext）而生成密文（ciphertext）。在不知道密钥的前提下，即使知道算法，也难于完成解密。这一原则在19世纪被科克霍夫原则（Kerckhoffs’s Principle）固化，其核心在于：即使除了密钥外的所有信息均被公开，密文仍是安全的。与之相反的是隐密式安全（Security through obscurity）：通过隐藏某个系统或部件实现的安全。美国国家标准技术研究所NIST表示，“系统的安全性不能只靠实现方式的保密或是元件的保密来达成。”

对抗加密术：密码分析学和频率分析

• 为了对抗加密术，不使用密钥读取明文，在阿巴斯王朝时期，阿拉伯人在数学、统计学和语言学的基础上发明了密码分析学（cryptanalysis）。
• 9世纪，阿拉伯科学家al-Kindi（肯迪）发明了频率分析（frequency analysis）：根据不同字母的出现频率，破译逐个字母互换的单表加密密码（monoalphabetic substitution）。
  • 频率分析并非通用，尤其是对于专门为了对抗频率分析写出的文章。1969年，法国作家写的《La Disparition》（A Void）完全没有使用字母e（频率最高的字母）。
  • 频率分析不止看单个字母的频率，也会看不同字母组合（包括the、and等单词）的频率等。
• 欧洲中世纪研究密码分析学的主要是僧侣（试图寻找圣经的隐含意义），但到15世纪，随着文艺复兴和政治变幻，欧洲密码分析学开始兴盛。
  • 关于圣经，历史上不断有人提出所谓的圣经密码（Bible Code）。然而，考虑到圣经的体量，如果仔细找，就可以找到几乎任何想要的信息，但这纯属巧合。澳大利亚国立大学的Brendan McKay曾经在著名小说Moby-Dick（《白鲸》）中“找到”关于甘地、肯尼迪等被暗杀的信息。

对抗频率分析：多表加密和维吉尼亚密码

• 引入空字符（例如：将26个字母换为1-99之间的数字，而剩下的73个则为空字符）；
• 替换密码词而不是单个字母（例如：使用D代表assassinate）；有时，加密者会结合替换字母和密码词，又称为命名法密码（nomenclators）；
• 16世纪，苏格兰的玛丽一世（Mary, Queen of Scots）密谋反叛英国伊丽莎白一世一案中，密码分析学帮助破译了定罪的核心证据：玛丽一世同意暗杀计划的回信。

• 多表加密 polyalphabetic：单表加密是1对1的对应关系，如果增加更多的对应关系，就成为多表加密。将其做到极致就是类似维吉尼亚密码（the Vigenere cipher）的解决方式，加密者反复书写某个密码词，并根据密码词的每个字母对应的数字，选择当前明文需要使用哪一行进行加密。通过多表加密，同一个明文字母可能被加密为不同的密文，大幅降低了被频率分析破解的可能。

维吉尼亚密码的终结：找到重复的密文

• 19世纪英国发明家Charles Babbage发现，维吉尼亚密码中，由于密码词长度的局限性，随着密文长度增加，仍然会出现重复，尤其是the等常见单词的密文重复最终会带来可被用于破译的弱点。
• Babbage的破解步骤如下：
  1. 找到密文中重复出现的字母序列；这一重复出现的序列很可能是由于密码词重复导致的；
  2. 根据重复序列之间的间隔（例如：20个字母），可以假定密码词的长度是这一间隔的因数（2、4、5、10、20）；
  3. 重复1、2步，寻找其他的重复序列，从而确定唯一的密码词长度（例如：5个字母）；
  4. 找到密码词每一个字母（L1 - L5）对应的所有密文字母，依次参照单表加密的方式进行频率分析。
• Babbage并未发表这一破译方法（不排除是英国政府有意命其保密）。但在19世纪中期，一名退役普鲁士军官Kasiski也独立研究并发表了破译方式。

近代

• 19世纪末，马可尼的无线电系统吸引军方注意。无线电大幅提升了通讯便利性，同时也使得加密变得不可或缺。一战中，德国试图拉拢墨西哥的Zimmermann电报被破译，美国因此参战，对战局造成了重要影响，进一步促进了加密技术的研究。
  • Zimmermann电报是1917年1月德国外相向德国驻墨西哥大使发出的电报，建议墨西哥与德国结成对美同盟。其内容如下：“我们计划于2月1日开始实施无限制潜艇战。与此同时，我们将竭力使美国保持中立。如计划失败，我们建议在下列基础上同墨西哥结盟：协同作战；共同缔结和平。我们将会向贵国提供大量资金援助：墨西哥也会重新收复在新墨西哥州、得克萨斯州，和亚利桑那州失去的国土。建议书的细节将由你们草拟。请务必于得知将会与美国开战时（把此计划）以最高机密告知贵国总统，并鼓励他邀请日本立刻参与此计划；同时为我们与日本的谈判进行斡旋。请转告贵总统，我们强大的潜水艇队的参与将可能逼使英国在几个月内求和。 ”

德国在二战中使用的密码机：恩尼格玛密码机（Enigma）

1918年，德国发明家Scherbius发明了Enigma机器，将在二战中发挥重要作用。

Enigma本质上仍然是替换类的密码，但其创举在于：

• 打字时，Enigma机器中的转子（scrambler）会随着按键自动转动。通过增加转子的数量，大幅延长了明文字母被加密为同一个密文的间隔（类似于使用一个极长的密码词的效果）；再加上接线板（plugboard，用于选择性互换部分字母）等装置，暴力破解变得极为困难；
• 通过使用反射器（reflector），确保加密和解密的流程一致（输入明文生成密文，输入密文生成明文），大幅提升了使用容易程度。

Enigma机器的安全性依赖于其结构和密码本的保密，其原理本身并非无懈可击。这为后续的破译工作提供了切入口。

波兰的破译工作：机械化解密工具Bomba

一战后，独立建国的波兰在密码学家Rejewski的领导下，首先通过法国的间谍网络获得了Enigma机器的结构以及使用手册。突破点仍然在于寻找重复：德国人在消息开头会根据密码本规定的当日密钥重复发送两次消息特定密钥，然后用消息特定密钥加密这条信息。重复发送的消息特定秘钥对应的密文被用来破译当日密钥，进而破解当日其他的所有密文。Rejewski发明了bomba，一种用来自动尝试转子组合的机器。Enigma是机械化的加密工具，而bomba是顺理成章的回应：一种机械化的解密工具。

二战开始前，德国增加了转子的可选数量和接线板的飞线数量，使得破解所需的资源大大增加，波兰无法继续承担。波兰将Enigma机器和相关知识转交予英国和法国。

英国的破译工作：“crib”，Bletchley Park和艾伦·图灵

英国从波兰手中获得了Enigma的信息后，随即增加了密码学人员，并将他们安置在著名的Bletchley Park。其中最著名的便是艾伦·图灵（Alan Turing）。 图灵利用的第一个重要突破点是：德军发送的明文有很强的结构性，例如：早晨6点后不久会发出天气预报，包括wetter这个单词，甚至其位置都能大致猜出。这种被猜出的、可以和密文相对应而能帮助破译的明文/密文片段组合被称为crib。利用crib，图灵设计了名为bombe的机器，用来尝试Enigma的转子设置，从而破译消息特定密钥并进一步破译当日密钥。第二个重要的突破点是，Enigma机器无法将一个字母加密为其本身。这一缺陷使得破译员可以迅速尝试并排除错误选项，从而找到crib对应的正确位置，并进而完成破译。

Enigma的破译对战争带来了重大帮助。Bletchley Park的贡献直到1974年才被公之于众，而图灵由于其同性恋身份被英国政府迫害，其安全许可被剥夺，被迫接受所谓荷尔蒙治疗并带来诸多后遗症，包括严重的抑郁。1954年，图灵吃下了有氰化物的苹果后离世。

语言的破译

无人能懂的明文：纳瓦霍语

• 纳瓦霍语（Navajo）是基于声音的土著语言，二战中被美军用于进行通讯。由于纳瓦霍语不需要传统的加密、解密过程，因此效率远超其他的加密方式；
  • 纳瓦霍语属于Na-Dene语系，与亚洲和欧洲的任何语言都没有关联，客观上大幅增加了破译难度（尽管目前有部分学者认为其与西伯利亚叶尼塞河流域的叶尼塞语系有关，但即使属实，恐怕也不会影响这一结论）；
  • 破译了日本Purple密码的美国海军破译机构在尝试了三个星期后仍未破译纳瓦霍语，这为军方提供了重要信心；
• 纳瓦霍语是历史上极少的从未被破解的密码之一：日本二战时的情报负责人有末精三中将（Seizo Arisue）表示，日军在破解纳瓦霍语的过程中并未有任何进展。

古埃及象形文字

• 破解古文字的难度往往要高于破解类似于纳瓦霍语这样的密码语言，因为：
  1. 被发现的古文字（“密文”）经常只有一些石板，量远少于纳瓦霍语，并且
  2. 考古学家一般并不清楚古文字的任何背景线索。
• 与其他的例子相比，古文字的使用者并没有刻意隐藏其含义，然而破解古文字的基本原则和破解其他密码是一致的。
• 古埃及象形文字（hieroglyph，又称为圣书体）从公元前3千年就开始被用于神庙等处，日常使用的更多是僧侣体（hieratic，可以理解为一种简写），并在公元前600年左右被进一步简化为世俗体（demotic）。它们本质上是同一种语言。
  • 然而，在公元4世纪末，受基督教传播和相应禁令的影响，古埃及象形文字在一代内就迅速消亡了，而被替代为了科普特语（coptic），一种更接近希腊文的语言。
  • 公元11世纪，科普特语又被阿拉伯语替代，最终使得无人再能理解古埃及象形文字。

罗塞塔石碑

在罗塞塔石碑被发现之前，古埃及象形文字的破译基本没有进展，其中一个重要障碍是：学界错误地认为古埃及象形文字是表意文字，而事实上它是一种表音文字。1799年，拿破仑治下的法军在罗塞塔镇发现了这块记有象形文字，世俗体和希腊文的石碑。由于希腊文可被翻译，这大幅加快了破译的进程。然而：

• 石碑的损坏导致大量文本缺失；并且
• 仅凭符号无法知道表音文字的声音，对破译造成了困难。

古埃及象形文字的破译突破口主要有：

• 成功被猜测的明文/密文对（cribs）：Thomas Young发现部分象形文字被圆框框住（被称为cartouche），并正确的猜测其代表重要性，可能是法老等人物的名字，首先被猜出的是法老托勒密（Ptolemy）；据此，Young破译出了部分文字的读音；
• 破译者得到了更多带翻译的文本，例如带有希腊文和古埃及象形文字的Philae obelisk，并且其中包括Ptolemy和Cleopatra的cartouche。语言学家Jean-Francois Champollion据此推测出了其它cartouche里字母的发音。
• “桥梁语言”科普特语的破译：Champollion发现了科普特语和象形文字的关系，并且由于科普特语在科普特基督教会的文献中得以部分保留，Champollion能够学会科普特语，从而进一步修复了象形文字和现代文字之间的桥梁。

现代

二战期间，希特勒和将军之间的通讯使用的是另一种更为复杂的密码：洛伦茨密码（the German Lorenz cipher）。为破解它发明的Colossus决定了现代密码学的发展方向。Colossus可以被认为是第一台可编程的、电子的、数字的计算机，也是现代电子计算机的前身。

洛伦茨密码破解的突破口在于：人为错误和懒惰导致一条4,000余字的消息被以同样的密钥重发，并且重发的消息存在简写导致两条密文不完全一致，为密码分析提供了切入口。

先有鸡还是先有蛋：密钥交换问题

• 计算机的价格下降，使得企业也可以使用加密工具，但随之而来的问题是：如何安全地交换解密所需要的密钥。在军队中，这一问题可以通过物理传递实现。但对企业而言，每次进行物理传递可能并不现实。如何在加密开始前安全地交换密钥（密钥交换问题）是一个经典的先有鸡还是先有蛋的问题，它的解决被认为是自单表密码发明以来密码学最大的突破。
• 一个直观的例子说明，这个问题至少从理论上是能解决的：如果A和B希望通过邮件交换密钥，可以用以下的步骤：
  1. A将密钥放进箱子用锁锁上，寄给B；
  2. B用自己的锁再次锁上箱子，寄还给A；
  3. A取下自己的锁，寄还给B；
  4. B打开自己的锁，打开箱子取得密钥。
• 然而，对于数字密钥而言，绝大多数的加密算法无法打乱顺序进行解密。换言之：第3步A无法单独“取下”自己的“锁”，因为此时A必须首先解除B的“锁”。
• Diffie-Hellman-Merkle：发明了一种新的加密方式：非对称加密（加密和解密的密钥并不相同）。B可以披露一个公钥，同时保留对应的私钥用于解密。A生成需要传输的密钥后，用B的公钥加密并传输给B，只有B的私钥才能将其解密。
  • 非对称加密关键在于找到一个单向函数：一个方向容易，另一个方向困难。但找到一个合适的函数并不容易。
  • RSA（Ron Rivest, Adi Shamir, Leonard Adleman）：现代密码学最具影响力的密码，利用了两个大素数p和q的积N难以被分解质因数的特性；N是公钥，而p和q则是私钥。由于RSA不受密钥交换问题的影响，只要p和q的长度足够，目前破解几乎是不可能的。
  • 英国情报机构GCHQ在此之前已经单独发现了RSA算法，但显然并未公布，有关研究直到1997年才被解密。
• PGP and Zimmermann: RSA需要耗费相对较多的系统资源，对（当时的）普通人而言难于应用。美国密码学家Phil Zimmermann试图通过PGP改变这一点，使普通人享有和政府、军队同样的隐私权利。
  • PGP的主要突破点之一是：将非对称加密和传统的对称加密结合起来。前者解决密钥交换问题，但耗费更多资源，后者资源较少且同样安全，但需要交换密钥。这使得PGP可以兼顾安全性能和效率。

未来

• 数字时代的加密技术给企业和个人带来方便，但也给政府和执法者带来了挑战。
  • 其中一个解决方案是密钥托管（key escrow），例如1994年的美国托管加密标准American Escrowed Encryption Standard，将私钥托管至2个联邦机构，以便在必要时进行破译。但这根本上没有解决企业和个人对政府不当行为的担忧。
  • 政策可以随时调整，其决定因素在于彼时公众更担忧的是什么：利用加密技术的犯罪者，还是政府的不当行为。
  • Zimmermann由于PGP被调查，但检方最终在1996年放弃了控告。
• 以目前的技术和算力，现代加密算法可以被认为是无法破译的。然而历史告诉我们，维吉尼亚密码、Enigma等一度被认为无法破译的密码，最后都被攻破了。GCHQ最先发现RSA算法而秘而不宣，也再次说明公众无法知悉政府目前在密码学方面已经取得了何种突破。

量子密码学 quantum cryptography

• A可以使用基本粒子向B传输信息，如果中途被截取，基于量子物理，信息内容会发生改变，窃听将会失败，并且A、B也会发现存在窃听行为。
  • B同样会受到量子物理法则的约束，因此在收到信息后，需要向A确认其收到的内容，以便A将其与自己原始发出的文本相对照，确认发送成功。
  • 1988年，Charles Bennett成功完成了概念验证。但远距传输在实践中仍然存在难点。
• RSA未被破解前，量子密码并不能带来更多好处，但如果RSA被破解，量子密码就会成为必需品。
• 实现可靠的远距传输后，量子密码将是真正意义上无法被破解的密码。唯一的问题是：政府是否会允许公众使用这一技术。

来源

本文是Simon Singh《The Code Book: The Science of Secrecy from Ancient Egypt to Quantum Cryptography》的读书笔记，补充的内容和部分图片主要来自于维基百科相关条目，玛丽墓、罗塞塔石碑及Thomas Young信件副本照片为自行拍摄。