下载掌阅APP，畅读海量书库
立即打开
密码学基础理论中涉及的代数、信息论等原理比较繁复，为达到深入浅出的目的，本节只对其中的精要进行概述。在不影响读者理解后续密码算法的前提下，我们并不试图涵盖所有理论细节。
首先，现代密码学的发端是将密码算法的研究表述为数学问题，并利用诸多数学原理去分析和设计。一般来说，密码学的研究课题是构建一个五元组：
{ 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 ={ k e , k d }
两个密钥对应于加密和解密过程中采用的不同密钥。
美国科学家香农的主要研究工作完成于20世纪中叶，他是信息论和编码理论领域的奠基人，他的研究为现代密码学理论打下了坚实的基础。
香农在1949年发表了论文“Communicaiton Theory of Secrecy Systems”，率先用信息论的相关数学模型来研究加密系统。他的论述在数十年后才开始产生广泛影响。正是在香农理论的启发之下，1976年，Diffie和Hellman提出了新的思路，将密码算法带向了公钥加密方向。
香农的信息论原理的内容非常多，可作为一门专门的学科进行学习，我们下面做一下密码学方向的初探。香农信息论的研究框架是三段论。
密码学中的加密、攻击和解密等也可以用上述过程来建模。香农首先建议以“信息熵”为基本度量来研究{ M , S , K , E , D }等各个集合的统计特性。“熵”原本是一个热力学概念，后被香农引入了信息理论中。以密钥空间 K 为例，假设 K 包含 n 个元素{ k 1 , k 2 ,…, k n }，且任一元素 k i 被使用的概率为Pr( k i )，则空间 K 的熵可以表示为：
很容易看出， H ( K )是一个用密钥空间 K 中各个元素出现的概率来加权求和一系列变量的结果，且这一系列变量的大小和该元素出现概率的大小成反比。这些变量可以被不甚严格地理解为“信息量”，比如1个等概率取值0或1的随机数，其任一取值的信息量恰好为1，那么由于0和1出现的概率都是50%，因此加权求和得到的信息熵为1位。那么， H ( K )衡量的是什么呢？可以想象，当密钥空间 K 中的元素越多时，可能性就越大，则 H ( K )的值也越大。 H ( K )衡量的就是密钥空间中包含的不确定性，其值越大，说明密钥空间不确定性越大。反过来，如果密钥空间只有一个元素 k 1 ，那么Pr( k 1 )=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所示。
表3-2 密码算法设计的概念
我们在后续章节中会反复看到，现代密码学体制会贯彻这些思想，充分地将明文、密钥进行扩散和混淆。在分组密码中，我们也会看到利用多轮迭代来构造出乘积密码的结构，从而增强加密算法安全性的例子。
密码学研究的课题是对明文、密文、密钥集合以及加密和解密变换集合的研究，因此密码学理论中贯穿着集合的概念。为了更好地理解密码学算法，要进行一些必要的知识准备。我们对于集合并不陌生，如整数、实数、素数（又称质数）等都是集合。由于计算机处理的特性，在密码学算法中主要考虑整数集合 Z 的子集，即由一部分特殊性质的整数构成的集合。群、环和域就是由一系列的筛选规则来定义的。
我们理解这些知识的思路是，首先定义集合上最基本的数学运算，然后基于这些基本运算理解重要的群、环和域的概念。
基本的数学运算包含模加法和模乘法两种，它们和一般加法、乘法的区别是，模加和模乘的结果是将一般加法、乘法的结果再做模运算得到的余数。例如，在一个集合 Z 6 ={0,1,2,3,4,5}中做模加和模乘的计算如下：
（3+4）mod 5 = 2
以及
（2×3）mod 5 = 1
有了这些基本运算，就可以定义几个基本的集合概念。这些重要的概念如表3-3所示。
表3-3 几个重要的集合概念
让我们从“群”的概念开始。首先要理解群的概念是基于某个集合和某个运算来说的，例如某个群 G 对于模和运算构成加法群。如果集合 G 对某种数学运算满足以下四个性质，则称集合 G 是一个加法群。
以上这些性质很容易理解。还可以验证：一个基本的整数集 Z m ={0,1,…, m -1}就是一个“加法群”。显然，集合 Z m 乘法不构成群，因为不满足逆元存在的要求。如果集合 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 }进行选择。在选择这些集合时，需要利用群、环和域的一些性质，并且我们也需要理解各种加密、解密运算是如何作用于这些集合的。所以，花些时间理解这些集合的概念和相应运算的性质是有必要的。
至此我们简要了解了群、环和域的概念，也认识了乘法逆、循环群及其生成元。在后续密码学算法的介绍中，我们还会反复接触这些基本概念。