第3章　密码学探秘

众所周知，密码学原理是区块链技术的核心支柱，但很多读者在面对密码算法时，总会感觉力不从心。究其原因，密码学原理背后多是复杂的数学理论，而现有的文献和资料大都用严密的数学语言去讲述，自然会比较繁复，这给技术开发者的学习带来了很大的挑战。在本章后续内容中，笔者试图以简明的语言介绍密码学的基本原理，兼顾数学理论和工程意义，使技术开发者对这些看似高深的算法做到“知其然也知其所以然”。下面让我们共同踏上密码学的探秘之旅吧！

3.1　密码学基础知识

3.1.1　加解密的一般过程

在信息系统中，恶意窃听和攻击的威胁从未间断。加密的目的是让明文转化成密文，通过密文方式发送信息可以防止明文信息被获取。

为方便后续讨论，我们先建立一套标准的语言体系。通常情况下，可将整个过程划分为信息加密、信道和信息解密三个阶段。如图3-1所示，按照常见的提法，将信息的发送方和接收方分别称为Alice和Bob，而将信道中潜在的恶意方称为Carl。

Alice加密的过程是：

s = e (m, k1)

其中，e (x,y)是加密函数，k1是加密密钥，m和s分别是明文和密文。

Bob解密的过程是：

m = d (s, k1)

其中，d(x,y)是解密函数，k2是解密密钥。我们用不同的符号表示加密和解密密钥，是因为在许多加密算法中，这两个密钥是不相同的。

Carl总会尝试破解上述过程。他的目的是获取当前乃至之后的所有原文，手段是找到加密算法和密钥。Carl可能采用以下多种方式发起攻击。

• 唯密文攻击：Carl只获得了密文s。
• 已知明文攻击：Carl获得了某一份密文s及其对应的明文m。
• 选择明文攻击：Carl有机会接触加密设备，他可以获得任意明文m对应的密文s。
• 选择密文攻击：Carl有机会接触解密设备，他可以获得任意密文s对应的明文m。

显然，这些攻击的强度是递增的。一般考虑较多的是前两种场景。Carl执行上述攻击的前提是他知道Alice和Bob采用的是哪种加密算法。这个假设是否合理呢？密码学理论研究中有一个被广泛认同的Kerckhoffs原则。Kerckhoffs原则指出，在设计密码算法时不能够假设Carl不知道加密算法。换个角度讲，由于系统设计者无法确保Carl对加密算法并不知情（有各种因素会导致消息泄露），因此从安全性的角度考虑必须假设“敌人知道系统”。美国科学家香农在20世纪中叶也独立地论证了这一理论。密码分析是密码学的一个子学科，它研究上述各种情况下破解一套密码算法的方法及计算难度。密码算法设计和密码分析是“矛”和“盾”的关系，它们其实是相辅相成的。

3.1.2　密码学发展历程

加密技术的应用可以追溯到数千年前的军事活动。我国周朝兵书《六韬》中就有用不同长短的“符”及其组合表示信息的记录。古希腊城邦的战争中，也有使用简单密码保护军事情报的记录。在“二战”中，美军对日军的密码破译成为左右太平洋战争战局的关键点。特别是20世纪的后几十年中，密码学经历了日新月异的发展。

人们一般将密码技术的发展历程大致划分为三个阶段。

第一个阶段的密码技术主要是简单的古典密码，如移位码和仿射密码等。这类密码通常基于简单的经验设计或代数设计。人们常将这个阶段的密码算法称为“古典”密码算法或“经典”密码算法。

第二阶段开启的标志是在1949年，Claude Elwood Shannon发表了具有广泛影响力的学术论文“Communication Theory of Secrecy Systems”。Shannon（香农）生于1916年，曾获得麻省理工学院博士学位，他的主要研究成果都在麻省理工学院和贝尔实验室完成。香农启发人们基于信息和编码理论研究密码，真正意义上将密码研究带入了“密码学”的学科研究时代。

第三个阶段的标志是非对称加密技术的发源。1976年，Whitfield Diffie与Martin Hellman发表的论文“New Directions in Cryptography”给出了一种新的思路：加密和解密可以使用不同的函数及密钥，规避了使用同一密钥时密钥本身的泄密问题。后来，一些专家和学者基于这一全新思路构建了许多非对称加密算法。非对称加密技术是诸多互联网安全协议的重要技术基础，为互联网应用的迅猛发展提供了安全保障。Whitfield和Martin由于在密码学方面做出了卓越贡献而荣获2015年的ACM图灵奖。

3.1.3　密码算法的分类

常见的密码算法分类方式如表3-1所示。

根据算法和密钥的异同，可以将密码算法分为对称加密和非对称加密两类。在对称加密中，加密和解密函数在形态或原理上非常相似，而且加密和解密过程中使用的密钥k1和k2是相同的。可以将图3-1形象地看作：Alice将信息存入一个密码箱并加锁，而Bob得到同一个密码箱，并用复制的钥匙打开密码箱获得信息。

对称加密算法面临着两个挑战。第一，如何保护密钥的安全？密钥不能和信息在同一信道上进行传输，需另外开辟一条安全通道。第二，在实际应用中，如何规避通信双方之间的欺诈？例如，若Alice是采购方，Bob是供应商，Alice将加密后的订单发给Bob作为采购需求发起的标志。由于Alice和Bob都知道密钥，Bob可以伪装订单信息，或者Alice可以称某个真实订单是由Bob伪造的。非对称加密中的加密和解密使用不同的密钥（k1≠k2），可以很好地解决类似问题。在非对称加密算法中，一般将加密密钥k1称为公钥，而将解密密钥k2称为私钥（注意这并不是绝对的）。

非对称加密算法一般有两个基本要求：第一，通过公钥不能够轻易推算出私钥；第二，利用公钥不可能进行解密计算。在后续章节中，我们会进一步理解其中的奥妙。

根据对信息序列的计算处理方式，可以将密码算法分为分组密码和流密码两类。分组密码一般是将原文序列m划分为若干个分组，即每个分组是一定长度的信息块。各信息块再通过相同或不同的密钥分别进行加密，称为密文序列。在接收端，解密函数对各信息块分别进行解密，然后重构原文序列m。一般情况下，单个信息块的长度要兼顾计算复杂度和加密算法的安全性来选取。流密码对原文序列m中的单个比特进行加密操作。首先采用一定的方法产生和原文序列m等长的密钥序列k，然后利用密钥序列中相应位置的密钥逐位对原文序列信息位进行加密。流密码的安全性主要依赖于所采用的密钥序列，一般情况下基于长的伪随机序列或递归的方式来构建。

3.1.4　基础理论简析

密码学基础理论中涉及的代数、信息论等原理比较繁复，为达到深入浅出的目的，本节只对其中的精要进行概述。在不影响读者理解后续密码算法的前提下，我们并不试图涵盖所有理论细节。

1. 密码学的数学定义

首先，现代密码学的发端是将密码算法的研究表述为数学问题，并利用诸多数学原理去分析和设计。一般来说，密码学的研究课题是构建一个五元组：

{M, S, K, E, D}

其中，M是明文空间，它代表全体明文构成的集合；S和K分别是密文和密钥空间；E和D分别是加密算法和解密算法构成的集合。E中包含一系列可能的加密变化，其中任意一个加密变化都可将M中的一个元素换算为S中的一个元素；集合D中则包含一系列的解密变化，完成和集合E相反的映射。在下文中，在不特别指出时，我们将用大写字母代表空间或集合，用小写字母代表集合中的某个元素。

基于此，一个密码体制成立的条件是：对于任意m∈M，都有e∈E、d∈D、k∈K，以及s∈S，且满足：

s = e (m, k)

以及

m = d (s, k)

以上就是密码体制的数学定义。根据Kerckhoffs原则，Carl可能知道Alice和Bob所采用的密码体制，但是并不知道密钥。Alice和Bob可以事先约定一个密钥k∈K。由于密钥空间K足够大，Carl不可能轻易地破解Alice和Bob使用的是密钥空间中的哪个密钥。我们还可以看出，一个密码体制成立的必要条件是加密函数e必须是一个一对一映射函数，否则会出现一个密文s可能对应多个原文m的情况，导致Bob在解密的时候不可避免地出现歧义。此外，还要注意，一些情况下密钥k可以是一个加、解密的密钥对：

k={ke, kd}

两个密钥对应于加密和解密过程中采用的不同密钥。

2. 香农信息理论

美国科学家香农的主要研究工作完成于20世纪中叶，他是信息论和编码理论领域的奠基人，他的研究为现代密码学理论打下了坚实的基础。

香农在1949年发表了论文“Communicaiton Theory of Secrecy Systems”，率先用信息论的相关数学模型来研究加密系统。他的论述在数十年后才开始产生广泛影响。正是在香农理论的启发之下，1976年，Diffie和Hellman提出了新的思路，将密码算法带向了公钥加密方向。

香农的信息论原理的内容非常多，可作为一门专门的学科进行学习，我们下面做一下密码学方向的初探。香农信息论的研究框架是三段论。

• Step 1：将通信过程建模成一个数学模型，信源、信道和信宿都可以建模成随机过程；
• Step 2：利用概率论、信息论的数学工具研究上述过程，摸清统计特性和各种规律；
• Step 3：找到通信中各种算法的理论界限，提出设计的指导思路。

密码学中的加密、攻击和解密等也可以用上述过程来建模。香农首先建议以“信息熵”为基本度量来研究{M,S,K,E,D}等各个集合的统计特性。“熵”原本是一个热力学概念，后被香农引入了信息理论中。以密钥空间K为例，假设K包含n个元素{k1,k2,…,kn}，且任一元素ki被使用的概率为Pr(ki)，则空间K的熵可以表示为：

很容易看出，H(K)是一个用密钥空间K中各个元素出现的概率来加权求和一系列变量的结果，且这一系列变量的大小和该元素出现概率的大小成反比。这些变量可以被不甚严格地理解为“信息量”，比如1个等概率取值0或1的随机数，其任一取值的信息量恰好为1，那么由于0和1出现的概率都是50%，因此加权求和得到的信息熵为1位。那么，H(K)衡量的是什么呢？可以想象，当密钥空间K中的元素越多时，可能性就越大，则H(K)的值也越大。H(K)衡量的就是密钥空间中包含的不确定性，其值越大，说明密钥空间不确定性越大。反过来，如果密钥空间只有一个元素k1，那么Pr(k1)=1，则H(K)=0。显然，这样的密钥空间是没有实际意义的。

香农还建立了用“熵”的模型判断加密体制的方式。根据他的理论可以得出：

H(K/S) = H(K) + H(M) - H(S)

这里H(K/S)，即“条件熵”，是一个非常有价值的变量。它衡量的是Carl已知密文S后，对于密钥K还有多少不确定性。如果说H(K/S)=0，说明已知S时K就没有额外不确定性了，这说明Carl很容易从S中猜出K，加密体制设计失败。反之，H(K/S)越大，系统越安全。还有一个启发，假设明文和密文空间一样大，且明文和密文中的元素都是等概率出现、充分随机的，那么H(M)和H(S)相等，这时密钥空间越大，即H(K)越大，密码体制越安全。有了这些数学工具，人们在面对一种新的算法时就可以有的放矢地进行分析了。

以这些理论为基础，香农进一步提出了若干密码算法设计的概念，如表3-2所示。

我们在后续章节中会反复看到，现代密码学体制会贯彻这些思想，充分地将明文、密钥进行扩散和混淆。在分组密码中，我们也会看到利用多轮迭代来构造出乘积密码的结构，从而增强加密算法安全性的例子。

密码学研究的课题是对明文、密文、密钥集合以及加密和解密变换集合的研究，因此密码学理论中贯穿着集合的概念。为了更好地理解密码学算法，要进行一些必要的知识准备。我们对于集合并不陌生，如整数、实数、素数（又称质数）等都是集合。由于计算机处理的特性，在密码学算法中主要考虑整数集合Z的子集，即由一部分特殊性质的整数构成的集合。群、环和域就是由一系列的筛选规则来定义的。

我们理解这些知识的思路是，首先定义集合上最基本的数学运算，然后基于这些基本运算理解重要的群、环和域的概念。

基本的数学运算包含模加法和模乘法两种，它们和一般加法、乘法的区别是，模加和模乘的结果是将一般加法、乘法的结果再做模运算得到的余数。例如，在一个集合Z6={0,1,2,3,4,5}中做模加和模乘的计算如下：

（3+4）mod 5 = 2

以及

（2×3）mod 5 = 1

有了这些基本运算，就可以定义几个基本的集合概念。这些重要的概念如表3-3所示。

让我们从“群”的概念开始。首先要理解群的概念是基于某个集合和某个运算来说的，例如某个群G对于模和运算构成加法群。如果集合G对某种数学运算满足以下四个性质，则称集合G是一个加法群。

• 封闭性：任何G中的两个元素a和b的模和(a+b)的结果仍是G的元素。
• 结合律：(a+b)+c = a+(b+c)。
• 单位元：存在u，使得a+u=a，u+a=a；对于加法来说，有u=0。
• 逆元：存在b，使得a+b=0；b称为a的加法逆元，或者说b=a-1。

以上这些性质很容易理解。还可以验证：一个基本的整数集Zm={0,1,…,m-1}就是一个“加法群”。显然，集合Zm乘法不构成群，因为不满足逆元存在的要求。如果集合G在满足上述条件的基础上进一步满足交换律，则我们称它为“交换群”或“阿贝尔群”。

如果上述交换群G再增加一些关于乘法的性质，就可以得到“环”的概念。具体地说，如果交换群G满足对乘法的结合律、封闭性、单位元，并且满足乘法和加法的分配律，那么将集合G称为一个“环”；如果G进一步满足乘法的交换律，就构成“交换环”。

如果在上述条件的基础上，G进一步满足以下条件，则称G为一个“域”：对任何G中的元素a，如果a≠0，均能找到a的乘法逆元b=a-1，使得a×b=b×a=1。

简而言之，如果在环G中非零元素a都能找到乘法逆元，则G构成一个“域”。我们所熟知的实数、有理数等集合，对一般意义的加法和乘法来说都构成域。如果某个域所包含的元素个数有限，则称其为“有限域”。

另一个重要概念是“循环群”：如果一个群G中可以找到一个元素g，使得G中任意元素都是g的乘方，那么G是一个循环群，而g是G的一个生成元或本原元。

为什么要理解这些看上去较为复杂的集合概念呢？我们已经知道，密码学研究的课题就是对明文、密文、密钥等集合{M,S,K,E,D}进行选择。在选择这些集合时，需要利用群、环和域的一些性质，并且我们也需要理解各种加密、解密运算是如何作用于这些集合的。所以，花些时间理解这些集合的概念和相应运算的性质是有必要的。

至此我们简要了解了群、环和域的概念，也认识了乘法逆、循环群及其生成元。在后续密码学算法的介绍中，我们还会反复接触这些基本概念。