大话密码学史：过去、现在和未来

在上篇文章《大话密码学史：从姜太公折断鱼竿说起》中，我们讲述了姜子牙发明的军用“阴符”、古希腊的斯巴达人发明了“塞塔（scytale）”密码、《左传·宣公十二年》记载的“隐语”法等远古密码，以及公元前400年以后人们又相继发明了更复杂且具有启蒙意义的密码，即古典密码。

本文将接着讲解密码学史，涉及第一次和第二次世界大战期间以及二战结束以来在密码学领域取得的进展。1914年6月28日，奥匈帝国皇储斐迪南大公夫妇在萨拉热窝视察时，被塞尔维亚青年普林西普枪杀。一个月后，奥匈帝国在德国的支持下，以萨拉热窝事件为借口，向塞尔维亚宣战。第一次世界大战正式爆发。在第一次世界大战前期，英军陆军主要使用是英国物理学家Wheatstone在1854年发明的Playfair密码。Playfair密码的核心是通过使用一个关键词方格来对字符对进行加密，此前曾被广泛用于克里米亚和布尔战争。但在1915年，Playfair密码就被同盟国破解了。

1918年，美国数学家Gillbert Vernam发明出一次性便笺密码，它是一种理论上绝对无法破译的加密系统，被誉为密码编码学的圣杯。但由于产生和分发大量随机密钥的过程十分困难，因此这种密码的实际应用受到了很大限制。从另一方面来说，其安全性也更加无法保证。同年，美国工程师E.H.Hebern发明了第一台转轮机，它是基于一台用有线连接改造的早期打字机来产生单字母表替代的，其输出为原始的亮灯式指示。与此同时，欧洲的工程师们也独立地提出了转轮机的概念。

1919年，德国工程师Arthur Scherbius设计出了历史上最著名的密码机：Enigma机。此后，瑞典工程师Hagelin也发明了另一类转轮密码机，即Hagelin机。二者都曾被用于第二次世界大战，其中Enigma机装备于德军；Hagelin机C-36型号装备于法军；Hagelin机C-48型号装备于美军；而根据Enigma机改进而成TYPEX机则装备于英军。1939年，日军又引入了以电话交换步进机取代转轮机的PURPLE密码机。

转轮密码机的使用虽然极大提升了明文加密速度，但由于密钥量有限，到了二战中后期时，这场加密与破译的对抗愈加激烈。

最先破解早期Enigma密码机的是波兰人，其利用德军电报中前几个字母的重复出现，摸索出了破译方案，并将其告知英军和法军。英军在计算机理论之父Turing的带领下，通过寻找德军在密钥选择上的失误以及借助战争中成功夺取的德军密码本破解出重要的德军情报。与此同时，1942年，美国教授Atanasoff 和 Berry发明了世界上第一台采用真空管的计算机ABC（请注意，并不是1946年发明的通用计算机ENIAC）。借助于快速电子计算机和现代数学方法，美军成功破解出日军的PURPLE码，并在中途岛途中截击山本五十六。可以说，密码学的发展直接改变了二战后期的格局，缩短了战争结束的时间。

值得一提的是，在第二次世界大战中，美军还特别征摹了一批印第安纳瓦霍通信兵，并使用印第安纳瓦霍土著语言作为密码。在二战的日美太平洋战场上，美国海军让北墨西哥和亚历桑那印第安纳瓦霍族人使用纳瓦霍语进行情报传递。由于纳瓦霍语的语法、音调及词汇都极为独特，且知之者甚少。因此，纳瓦霍语密码也成为了近代史上从未被破译的密码。

Egnima的破译让密码学家们深刻地意识到，真正保证密码安全的往往不是算法，而是随时可以改变的密钥。随着计算机技术和电子通信技术的发展，密码的使用迅速扩张到各个领域，也进一步促进了现代密码学体系的发展和完善。

二战结束以后，密码学在相当长的一段时间内都像军火一样被各国政府严密看管。美国国家安全局（NSA）雇佣了一大批密码学家在五角大楼内研究最前沿的密码学，严令禁止技术出口及民用。

至20世纪60年代末，企业对于商用密码的需求愈发强烈。1972年，IBM研制出了对称密码体制加密算法。3年以后，美国国家标准局将其颁布为国家标准，即数据加密标准（DES）。这是密码学历史上一个颇具里程碑意义的事件。DES的公布，也促使了大量封禁已久的密码学著作流入民间，其中包括有信息论创始人 Claude Shannon在1949年发表的密码学奠基理论《保密系统的通信理论》。

1976年，W.Diffie和M.Hellman发表了《密码学的新方向》一文，文中首次提出了适应网络保密通信需求的公钥密码思想，掀起了公钥密码学的序幕。次年，美国的Ronald Rivest、Adi Shamir和Len Adleman提出了第一个建立在大数因子分解基础上的公钥密码算法，即著名的RSA算法。

为了寻找破解RSA的方法，1985年，英国牛津大学物理学家David Deutsch提出了量子计算机的初步设想。量子计算机一旦问世，即可在30秒钟内完成传统计算机要花上百亿年才能完成的大数因子分解，从而破译RSA。同年,美国科学家 Bennet 根据关于量子密码学的协议，在实验室首次实现了量子密码加密信息的通信。尽管通信距离只有30厘米，但已经足以证明量子加密的可用性。

同样是这一年，Victor Miller和Neal Koblitz分别提出了如今家喻户晓的椭圆曲线密码学（ECC）。尽管在当时而言，ECC更接近于数学理想的范畴，不具备实用性，但ECC在安全性上的优势以及实现效率使其一直成为密码学家们乐此不疲的研究课题——相比起其它公钥密码算法，ECC的抗攻击性具有绝对的优势。例如，使用ECC加密的256位密钥所提供的安全性，与使用RSA或DSA加密的3072位密钥相当。这意味着ECC算法所要求的带宽更低、存储空间更小。这些优点在某些对于带宽、处理器能力或存储空间有限制的应用（比如移动设备）中显得尤为重要。

步入90年代初，麻省理工学院教授Ronald Rivest提出了MD4信息摘要算法，它是一种用来测试信息完整性的哈希函数。MD4的实现，旋即开启了哈希函数的大门，包括后来Ronald Rivest重新提出的安全性更优的MD5，由NSA和NIST提出的SHA函数家族以及Hans Dobbertin,Antoon Bosselaers 和 Bart Prenee提出的RIPEMD。在这一时期，密码学家来学嘉和JamesMasseey还提出了在软硬件实现上比DES更优的国际数据加密算法，即IDEA。

随着计算机能力的不断提高，不少密码体系比如主流的DES正逐步面临淘汰。1998年，电子边境基金会（EFF）利用耗资25万美元打造的专用计算机，仅用56个小时就成功破解了DES密钥。随后在1999年，EFF仅用了22小时15分就完成了破解工作。此后，美国国家安全局宣布弃用DES，转而启用由比利时密码学家Joan Daemen和Vincent Rijmen所提出的Rijndael加密算法，即高级加密标准AES。

进入千禧年以后，MD4、MD5、RIPEMD（RIPEMD-160仍然安全）、SHA1以及RSA-768的强抗碰撞性相继被攻破，RSA-1024业已在2012年前后被停用。随着区块链技术的兴起，ECC俨然成为密码学殿堂最亮眼的新星，但依旧难逃量子计算技术的威胁。

在 Bennet 实现量子加密通信的第33个年头，量子密码学已经走上了与量子计算技术赛跑的赛道。尽管目前国内外已经出现有量子加密技术落地的应用案例（比如阿里云在2017年公布的网商银行信贷业务数据在专有云上完成量子加密通讯的案例），但量子加密技术的大规模落地仍有待时日。

与此同时，量子计算机的研发也步入了“而立”之年，至于何时能面世，又或者是否已经存在于世界的某个角落，依然是个未知数。

（作者：喏呗尔）