密码学简史：“矛”与“盾”的千年战争

莫提

2019年10月26日，《中华人民共和国密码法》发布，自2020年1月1日起施行，这标志着我国在密码的应用和管理等方面有了专门性的法律保障。从常见的数字与字母密码、指纹密码，再到声纹密码、面部识别……密码无处不在，时刻守卫着我们每个人的安全。关于密码学背后的知识，同学们是否了解呢？让我们从遥远的古代开始讲起……

古典密码学

人类使用密码的历史几乎与使用文字的时间一样长，公元前 400 年，斯巴达人发明了“塞塔式密码”，即把长条纸螺旋形地斜绕在一根多棱棒上，将文字沿棒的水平方向从左到右书写，写一个字旋转一下，写完一行再另起一行从左到右写，直到写完。解下来后，纸条上的文字消息杂乱无章、无法理解，但将它绕在另一个同等尺寸的棒子上后，就能看到原始的消息，这是最早的密码技术。

我国古代也早有以藏头诗、藏尾诗、漏格诗及绘画等形式，将要表达的真正意思或“密语”隐藏在诗文或画卷中特定位置的记载。一般人只注意诗或画的表面意境，而不会去注意或很难发现隐藏其中的“话外之音”。如《水浒传》中写道，为了拉卢俊义入伙，“智多星”吴用和宋江便想出一个“吴用智赚玉麒麟”的主意来，利用卢俊义正为躲避“血光之灾”的惶恐心理，口占四句卦歌：“芦花丛中一扁舟，俊杰俄从此地游。义士若能知此理，反躬难逃可无忧。”这首卦歌中暗藏“卢俊义反”四字。结果，这首诗成了官府治罪的证据，终于把卢俊义逼上了梁山。

这一时期的密码学更像是一门艺术，其核心手段是代换和置换。代换是指明文（没有加密的文字）中的每一个字符被替换成密文中的另一个字符，接收者对密文做反向替换便可恢复出明文;置换是密文和明文字母保持相同，但顺序被打乱。

代换密码的著名例子有古罗马的恺撒密码（公元前1世纪）和法国的维吉尼亚密码（16世纪）。恺撒密码是对字母表中每个字母用它之后的第k个字母来代换，如将“comeatnine”加密为“htrjfysnsj”（k=5）。但这种加密方式无法掩盖各字母的频率特征，易被破解。

相比之下维吉尼亚密码提升了安全性，它的密钥通常是一个单词，如“hear”。对于上述明文“comeatnine”，加密时将第1个字母后移8位（密钥“hear”的第一个字母h处于字母表第8位），第2个字母后移5位（密钥的第二个字母e处于字母表第5位），以此类推，得到的加密后的结果是“ktnwiyoavj”。

近代密码学

德国工程师亚瑟·谢尔比乌斯于1919年设计出了历史上最著名的密码机——德国的恩尼格玛机（德语：Enigma，又译哑谜机，或“谜”式密码机），在第二次世界大战期间，恩尼格玛机曾作为德国陆、海、空三军最高级密码机，并使得英军从1942年2月到12月都没能解读出德国潜艇发出的信号。这类密码机的使用大大提高了密码加密速度，但由于密钥量有限，到二战中后期时，引出了一场关于加密与破译的对抗。首先是波兰人利用德军电报中前几个字母的重复出现，破解了早期的恩尼格玛机，而后又将破译的方法告诉了法国人和英国人。英国人在计算机理论之父——图灵的带领下，通过寻找德国人在密钥选择上的失误，夺取德軍的部分密码本获得密钥，以及进行选择明文攻击等手段，破解出相当多非常重要的德军情报。

密码学正式成为一门新的学科，是受计算机科学蓬勃发展刺激和推动的结果。快速电子计算机和现代数学方法一方面为加密技术提供了新的概念和工具，另一方面也给破译者提供了有力武器。计算机和电子学时代的到来给密码设计者带来了前所未有的自由，他们可以轻易地避免原先用铅笔和纸进行手工设计时易犯的错误，也不用再面对用电子机械方式实现的密码机的高额费用。

现代密码学

1976年，美国密码学家提出“公钥密码”概念。此类密码中加密和解密使用不同的密钥，其中，用于加密的叫作公钥，用于解密的为私钥。1977年，美国麻省理工学院提出第一个公钥加密算法——RSA算法之后，ElGamal、椭圆曲线、双线性对等公钥密码算法相继被提出，密码学进入了一个新的发展时期。一般来说，公钥密码的安全性由相应数学问题在计算机上的难解性来保证，以广为使用的RSA算法为例，它的安全性建立在大整数质因子分解在计算机上的困难性。

在数学中，把一个合数变成质数乘积的过程被称为质因子分解。对于一台计算机来说，把两个很大的质数相乘，即使每一个质数长达100位，计算出结果也并不难。然而，把一个很大的数分解成质数的乘积则是出了名的困难。例如，对于整数22，我们易于发现它可以分解为2和11两个质数相乘，但对于一个几百上千位的整数，即使采用相应算法，对于计算机来说，也要很长时间才能完成分解。

世界上没有攻不破的盾，也没有不可抵挡的矛。随着计算能力的不断增强和质因子分解算法的不断改进，特别是量子计算机的发展，公钥密码的安全性也渐渐受到威胁，量子密码等前沿密码技术逐步成为研究热点。量子密码是一种新的重要加密方法，它利用了量子力学中的两个关键点，一个是量子的不可复制性（无法复制密钥），另一个是量子的不可观测性（对通信进行窃听会导致量子状态突变），借助量子密钥分配协议可实现数据传输的可证性安全。中国科学技术大学教授、中国科学院院士潘建伟在量子领域研究和实用化方面做出了突出的贡献。近年来，他率领团队发射全球首颗量子科学实验卫星“墨子号”，开通全球首条千公里级量子保密通信干线——“京沪干线”，成功实现洲际量子保密通信等一系列研究，使中国在量子保密通信方面研究处于国际领先水平。

密码学的前景

公钥密码思想的提出，标志着现代密码学的诞生，在国际密码学发展史上是具有里程碑意义的大事件。如今，国际上已提出了许多种公钥密码体制，如基于分解大整数的困难性的密码体制——RSA 密码及其变种ElGamal 密码等，这些都得到了广泛的应用，并且为当今信息化时代提供了各种各样的安全性服务。

这些公钥密码体制的安全性均依赖于数学难题（大整数分解难题和离散对数求解难题）的困难性，然而这些问题在量子计算情形下经过算法处理均可变为易解问题，因而我们可以预言：量子计算机出现之日，便是现今密码寿终正寝之日。因此，量子密码加密技术以及抗量子计算机的新算法是未来密码学的研究方向。

密码学最基本的学科是数学，包括离散数学、线性代数、概率论等数学分支学科。想要研究密码学，不仅要拥有严密的逻辑思维，能够掌握复杂抽象的推导方法，而且要有足够的耐心和较强的意志力，在擅长学习数学的同时，能做到对数学这门学科抱有持久的兴趣。另外，计算机科学与技术专业中的逻辑学、图形学、信息论等也是必须掌握的知识，很多密码相关算法的设计涉及复杂的计算过程，需要通过计算机编程来解决，因此计算机与编程技术也很重要。此外，如果想要研究量子计算机、量子密码，物理学、光学工程、核物理等专业相关的知识也必不可少。

关于密码学的起源与发展，还有许多有趣的故事，若同学们对于密码学的专业书籍感觉阅读有困难的话，大家也可以看一些密码学相关的文学与影视作品，例如著名的阿瑟·柯南道尔的作品《福尔摩斯探案集》，丹·布朗的作品《达·芬奇密码》《数字城堡》等，相信同学们一定会乐在其中。