一文概览密码学发展史、基本原理与常见算法

是不是只有那些数学头脑很好的人，才能理解那些在信息安全中常常用到的技术（密码学）？如果你要成为密码学家，那可能是的，毕竟密码学家的工作就是构造极难破解的加密算法。但是加密方法在当今世界的用途已经非常普遍了，从保护用户的信用卡信息、保护远程用户的网络连接，到保护智力产权、防止盗版，密码学无处不在。

我这篇文章的目的，就是把令人望而生畏的密码学转述成大白话，让大家都能理解这些方法是如何用来加密数据的。

密码学就是数学和物理学的组合；它是信息安全技术的核心，保护我们的数据安全和隐私

密码学（Cryptology）的历史

「cryptology」 和 「cryptography」 两个词在现代的文献中常常是无差别混用的，这就把对它们实际意义的混淆延伸到了语义学中。实际上，这几个不同的词语最好这样解释：

Cryptology（密码学） —— 对保密技术的艺术性 以及 / 或者 密码系统科学性的研究

Cryptography（密码设计学）—— 设计密码系统来保密的实用方法

Cryptoanalysis（密码学分析）—— 致力于发现无需得知密钥或算法就能从密文中反推出明文的漏洞

译者注：正如作者所说，在现代的文献中，「cryptology」 和 「cryptography」 基本上是没有差别的了，都是 「密码学」 的意思，而且，密码学虽然脱胎于加密方法研究，但现代的密码学早已不止于研究加解密，而是延伸到了研究如何保障通信中的 「机密性」、「身份同一性」 等属性上。因此，可以说，作者这里的定义即使不算过时，也至少是窄化了密码学。不过，出于理解作者原意的需要，对下文中的相应词语，我们仍沿用此处的翻译。

本文的绝大部分篇幅是在解释 「Cryptography （密码设计学）」，也就是今时今日的密码学实践，也希望读者能意识到这几个词的含义和区别。

就其本身而言，密码学作为一种科学的研究已经存在了很多年，已知最早的一个密码设计学的例子是在一段刻于公元前 1900 年的铭文，是在埃及贵族 Khnumhotep 二世墓地的主墓室里发现的。那个雕刻者到处使用一些奇怪的符号来代替更常见的符号。不过目的似乎并不是隐藏信息，只是为了改变其形式，让它看起来更高贵一些。

在罗马帝国的鼎盛时期（公元前 100 年），Julius Caesar （凯撒大帝）也因使用加密技术向前线将军传送消息而闻名。这种字符替换型加密方法（cipher）被称为 「凯撒密码」，可能是文献中最常提到的人类曾用过的加密方法。（所谓 「cipher」，就是用来加密或者解密的算法）。所谓 「字符替换型加密方法」，就是把明文（我们想要加密的消息）中的每个字母都换成另一个字母，形成密文（即被编码过的消息）。凯撒所用的方法是把每个字母位移三位，比如，「A」 会被换成 「D」，「B」 会被换成 「E」，以此类推（都是换成该字母后面第三个字母）。相应地，最后的几个字母会被换成开头的字母，比如 「X」 会被换成 「A」。

在第二次世界大战期间，美国海军从纳瓦霍人（Navajo）中招募并训练了许多熟练使用纳瓦霍语的人。从编码消息的角度来看，这是个绝妙的办法，因为很少有纳瓦霍人以外的人学过怎么说这种语言，而且当时还没有用纳瓦霍语出版的书。但是除了词语之外，纳瓦霍人的口语并不是十分复杂（按密码设计学的标准来看），一个母语为纳瓦霍语的人再加上一个训练有素的密码学家，合作起来完全可以破解这套密码。日本人曾经有过一次机会，就是在 1942 年 「巴丹死亡行军（Bataan Death March）」 期间他们在菲律宾抓住了 Joe Kieyoomia。Joe 是美国海军的一位纳瓦霍中士，但他并不是密语播报员，只负责翻译无线电消息。只不过，因为他没有参与过密语训练，这些词语是什么意思他一点也不懂。当他说自己不能解读这些消息时，日本人就开始严刑拷打他。因此，日本陆军和海军从来没有破译过这些密语。

再到 1970 年代，IBM 发现他们的客户需要某种形式的加密手段，所以他们成立了一个密码学小组，由 Horst-Feistel 领头。他们设计出了一种加密算法叫 「Lucifer」。1973 年，美国国家标准局（现在叫做国家技术与标准局，NIST）放出话来，希望大家能提议一种够格成为国家标准的数据加密方法。他们显然已经意识到，自己买了很多并没有什么密码学基础的商业产品。Lucifer 最终被接受了，因此叫做 「DES （数据加密标准）」。1997 年以后，DES 被穷举式搜索攻击攻破。DES 的主要问题在于加密密钥的位数太小。随着计算机运算力的增加，通过暴力穷举所有可能的密钥组合来破解密文慢慢变成了一种可行的办法。

在 80 年代，大家几乎只有一个选择，就是 DES。今天的情形已经大不相同了，有一大堆更健壮、更快，设计也更好的算法可供选择。问题已经变成了你如何厘清这些选择。

1997 年，NIST 再次征求新的加密算法提案，最终收到了 50 份提案。2020 年，NIST 接受了 「Rijndael」 算法，并命名为 「AES」，高级加密标准。

基本原理

所谓加密，就是一个改变数据，使之变得不可辨识、无授权者无法使用的过程；同时，它还要保证解密过程能成功把改变后的数据恢复成原始形式。安全技术一般都把加密的数学方法和用于加密的参数（叫做 「key （密钥）」）区别开来。被选定的密钥（通常是一段随机的字符串）也是加密过程的输入，对加密过程来说也是必不可少的。同一把密钥往往也是解密过程的必要输入。

这个保护过程的原理是，只要密钥（有时候也叫 「口令」，password）没有暴露、只被得到授权的人所知，那么原始数据就不会暴露给其他人。只有知道密钥的人才能解密密文。这个思路，我们叫 「私钥」 密码设计学（译者注：称作 「对称密码学」 可能更恰当一些，因为加解密过程是对称的，都使用同一把密钥），也是最广为人知的加密形式。

那么，加密之所以必要的基本理由如下：

机密性（confidentiality）—— 在传输数据的时候，不希望窃听者能够知道被广播的消息的内容。在保管数据的时候不希望未经授权的人（比如黑客）能够访问，也是同理。

身份认证（Authentication）—— 相当于签名。收信者希望能确证该信息是特定的某个人发出的，其他人不能冒充（甚至初始发信方后面想抵赖也不可能）。

完整性（Integrity）—— 这意味着收信者能够证实自己得到的数据是完完整整、没有经第三方改动过的。

不可抵赖性（Non-repudiation）—— 防止发信方抵赖自己创建过、发送过某条消息。

译者注：作者在这里提到的才算是现代密码学研究的范围。比如身份认证和不可抵赖性，都是很重要的属性，但是在实用中几乎与加解密过程无关，但对数字签名的研究毫无疑问是密码学的内容。加解密的安全性跟机密性有关，只是现代密码学的一部分。

Cipher

密码设计学是（通过加密）隐藏敏感数据的艺术和科学。它包括加密过程（就是在原始的 「原文」 上使用加密算法）和解密过程（就是在密文上使用算法，使之恢复到可读的形式）。

要解释什么是 Cipher，最好还是给你看几个简单的例子：

波利比乌斯密码

波利比乌斯密码（Polibius Cipher）也是一种字符替换型密码。在我这个示例中，我用的是一个 6×6 的二维矩阵，可以把所有的大写字母和数字 0 到 9 都包括进去。然后我们可以得出下表：

有了这个矩阵，我们就可以开始代换了。比如，字母 「A」 可以表示成 「1 × 1」，或者 「X = 1，Y = 1」，甚至再简化成 11。再举例，字幕 「N」 可以表示成 「2 × 3」，或者 「X = 2，Y = 3」，简化后就是 23。

来试试加密一条简单的信息：

消息（原文）：ENCRYPT ME 2 DAY

加密后的数据（密文）：51–23–31–63–15–43–24 13–51 55 41–11–15

纳入生僻字符后，这张表可以变得很大很复杂。而且，定期地随机改变字符的位置也会让暴力破解无从下手。这很像我们今天在高级计算型加密方法所用的多态性（polymorphism）。

凯撒密码

历史最悠久的加密算法之一就是以其创造者凯撒而闻名的凯撒密码（Caeser Cipher）。他用这套方法来保证跟罗马将军们的安全通信，这样罗马帝国的敌人们就算拿到信也没有办法读懂。凯撒密码是加密的一种初级形式，很容易被破解，所以今天已经基本不会用在任何安全用途中了。

从原理上来说，凯撒密码就是重排字母表，不同的位移值也会使得编码后的数据完全不同。位移值，顾名思义，就是通过让字母左移或者右移一定位数来生成密文的数值。（译者注：所以，在这里，大家可以把凯撒密码理解成一种根据字母表顺序的位移来加密的算法（cipher），而位移值就是那个 Key，密钥。）

这里我们用右移 3 位的做法来看一个实际的例子：

英文原文：ENCRYPT ME

密文：HQFUBSW PH （解密时候要相应左移 3 位才能解密）

上面这条消息可以通过尝试所有可能的位移值来暴力破解：不断尝试新的位移值，直到解出来的原文看起来像样子。更加复杂的密码比如 Vigenere 密码和 Gronsfeld 密码也是用同样的原理设计出来的。但是解密起来就很麻烦，因此每个字母都代表一个位移值。

维吉尼亚密码表

在理解密码设计学之前，我们先要了解加密算法的工作原理，因为它们是所有加密过程的基础。速记是一种记录隐藏信息的方法，实际上可以归为古典密码设计学一类，因为现代密码设计学已经成了 「计算机安全」 的代名词。

多态性

多态性是密码设计学中较为高级的部分，在计算机加密技术中最为常见。多态性指的是，一种加密方法在每次使用时都会产生不同的结果，而且在每次使用过后都会发生改变。多态性常见于计算机加密算法。也就是说，如果我们将相同的数据加密两次，每次都会得到一个不同的加密结果。

我们用汽车钥匙来打个比方。现在，我们只需要在一个小巧的电子遥控设备上轻轻一按，就可以解锁汽车了。当你解锁车门时，你或许从来没思考过其中的原理 —— 你按下按钮的那一刻，会有一段特定的数据发送到你的车上，一旦匹配成功，车门就解锁了。要实现这点，最简单的方法是为每个遥控设备设定不同的频率。但是，这样管理起来会很麻烦。因此，所有遥控设备都采用了同样的波长，但是使用不同的算法（滚动码）来生成发送给汽车的数据。这些就是多态性算法。

由于这些算法每次使用过后都会发生改变，很难对其进行逆向工程。即使有黑客破解了算法（首先，破解多态性算法本身难度就很大），他还得找到与该算法匹配的汽车 / 钥匙（这又是一项复杂的任务）。

常用算法

现如今，常用的加密算法不外乎私钥加密方法和公钥加密方法。私钥加密方法可以用来保护关键 / 敏感数据。密钥密文只需一把钥匙（由通信双方共享）破解，因此被称为对称性密码设计学。

1949 年，贝尔实验室的 Claude Shannon 公布了私钥加密方法的基本理论。数十年来的演化已经孕育出了很多高质量的私钥加密算法。然而，直到 1975 年，一个名为 DES 的强大私钥加密方法才得到了广泛使用。

公钥 / 非对称性密码设计学诞生于 20 世纪 70 年代中期。公钥加密方法需要用到一对密钥，分别是对外公开的公钥和相对应的由个人持有的私钥。例如，接收方可以创建一对密钥，并将公钥分享给任何想要向 ta 发送密文的人。发送方可以使用公钥加密发送给接收方的信件，接收方可以用私钥来解密。

加密算法的强大程度取决于三个主要因素：

基础设施—— 如果相关密码设计主要由软件实现，那么底层基础将是最薄弱的环节。如果你总是会加密某些信息，那么对黑客来说，最好的做法是黑进你的电脑，在信息被加密前将其偷到手。相比破解密钥来说，入侵系统或者使用病毒感染系统要容易得多。很多情况下，破解密钥最简单的方法是窃听用户，并在密钥被传入加密程序时进行拦截。

密钥长度—— 在密码设计学中，密钥长度很重要。如果攻击者无法安装按键监视器（keystroke monitor），那么破解密文的最佳方法就是通过不断的试错来暴力破解。实用的加密算法必须将密钥长度设定得足够长，来杜绝暴力破解的可能性。但是，随着电脑运算速度一年比一年快，密钥长度的安全阈值也需要一直提高。专家们承认，小于等于 64 位的密钥，包括 DES 密钥在内，都很容易被暴力破解。在 1999 年，电子前线基金会（Electronic Frontier Foundation）资助开发了一种叫做 「Deep Crack」 的设备，可以在三天以内破解一个 DES 加密密钥。所以现在加密算法的密钥长度一般都在 100 位以上，少数算法支持 256 位的密钥。

算法质量—— 算法质量本身是很难评价的，基于一个现有算法去构造一个看似可行的算法是很容易的，但只有经验老道的专家仔细检查才能发现其中的微妙漏洞。算法中的漏洞会产生 「捷径」，让攻击者可以在暴力搜索攻击时候跳过大批密钥。举个例子，流行的压缩程序 PKZIP 以前继承了一个定制的的加密功能，使用 64 位的密钥。理论上来说，应该要 264 尝试才能试完所有的密钥。但实际上，有捷径可走，所以攻击 PKZIP 加密算法只需 227 次尝试就能破解密文。发现这样漏洞的唯一办法就是尝试破解算法，一般来说就是使用对付其它算法的技巧。只有在经过这样的分析和攻击之后，算法的质量才会展现出来，所以，还没有找出这样的漏洞，并不代表这个算法永远不被发现有漏洞。

算法的类型

DES—— DES 已经经受住了时间的考验，多来年出版的研究都证明了其质量。经过四分之一世纪的研究之后，研究员也只能找出一些猜测式的攻击方法，而且实用性还不如暴力破解。DES 算法的唯一真实弱点就是它过短的密钥长度（56 位）。

三重 DES—— 使用 112 位或者 168 位的密钥连续三次使用 DES 算法。最终这个算法会比其它有类似强度的算法慢得多，而且，因为计算机还是强大到了能破解这个算法，这一方法已经过时了。

AES—— 高级加密标准（AES）支持三种密钥大小，128 位的、192 位的和 256 位的，而数据则按 128 位为一个组。现在 AES 被当成标准，全世界都在使用。

Rijndael 密码表

DES 是明确设计为内置在硬件中的，从没考虑过怎么让它在软件层面实现。后来，NIST 评估了执行效率和存储需求，保证 AES 能在 C 语言和 Java 语言中工作，既能在工作站中运行，也能在资源更有限的环境比如嵌入式 ARM 处理器和智能卡中运行。

虽然荷兰研究院 Vincent Rijman 和 Joan Daemen 发明的 Rijndael 算法赢得了 NIST 精算，但所有进入 AES 决赛的算法相对比 DES 和 DES 的替代品都显现出了巨大的进步。所有这些算法都是分组加密（block cipher）算法并且支持 128 位乃至更大的密钥；没有一种算法有严重的漏洞；最终选择其实是密码设计强度和性能的权衡。

AES 基于一种叫做 「置换-排列」 的设计原理，在计算中既有置换，又有排列，无论在软件层还是硬件层，计算起来都很快。不像其前辈 DES，AES 不使用费斯托密码（Feistel）原理，AES 是 Rijndael 密码的一种变种，使用固定的 128 位大小作为输入，而且支持 128 位、192 位 和 256 位的临界维数（critical dimension）。相反，Rijndael 设计规范仅指定了输入组和密钥的大小都是 32 的倍数，最小是 128 位，最大是 256 位。

AES 在一个 4×4 的字节矩阵上操作，这些举证叫做 「状态」。但是 Rijndael 算法的某些版本的输入组更大，因此矩阵更大。大部分 AES 计算都是在一个特定的有限域内完成的。

AES 算法所用的密钥大小会相应决定转换操作的重复轮数。对应关系如下：

128 位密钥对应 10 轮重复

192 位密钥对应 12 轮重复

256 位密钥对应 14 轮重复

每一轮都包含几个处理步骤，而每个步骤都包含 4 个相似但不同的阶段，其中包括取决于加密密钥本身的一个阶段。在解密的时候，需要用同一把密钥来反向重复操作、将密文恢复成原文。

量子密码学

上面这个图示说明了量子密钥分发方案（BB84 协议），它实现了一种包含量子力学的密码学协议，能够保证安全通信。它让通信双方可以生成一个共享的随机密钥（是个对称密钥），这个密钥只有他们双方才知道，因此可以用于加解密消息。量子力学是一组描述组成宇宙的光子、电子和其它粒子运动规律的科学定律。

业界一直在尽最大努力寻找能够抵抗黑客攻击的最高安全手段，而新一代的密码设计学已经从数学转向物理学。量子力学科学家已经进入密码学的世界了，这些科学家希望利用量子力学的原理来发送无法被黑的消息。这就是 「量子密码学」 的大概，它是在过去这几十年里才成长起来的。

量子密码学将自己的根扎在量子物理学中。组成我们这个宇宙的基本粒子具有内在的不确定性，可能同时存在于此处或彼处，也可以有不止一种状态。只有在撞上一个物体或者被测量时，它们才会显现出运动现象。

密码设计学是信息安全的一个迷人领域，也是最复杂的学科之一。不过，我们从简单的凯撒密码和波利比乌斯密码介绍到多轮加密的 DES 和 AES 算法，相信读者会觉得理解起密码算法的概念来不那么复杂了。

对于密码学这门科学，我们已经了解其历史、从最简单到最复杂的加密算法的基本概念