第2章 密码学基础

2.1 密码学的基本概念和术语

自从人类文化诞生以来，就产生了保护敏感信息的愿望。而信息的价值来源于信息可以被交流和使用。我们需要在公开的地方存储信息，使用非隐秘介质交换信息，通过不安全的信道传输信息，就需要某种手段保护信息在存储、交换和传输中的安全，而密码技术正是基于保护敏感信息的需要而产生和发展起来的。密码在今天与我们的生活息息相关，每个人的脑子里大概都记着一堆密码，无论是在ATM机上取钱、拨号上网、登录电子邮箱都要输入密码。密码真的能保证我们的钱财与隐私的安全吗？它又是怎样使我们的信息得到保密和安全的？本章将初步回答这些问题，引导读者步入信息安全的大门。

首先来了解一些有关密码学的基础知识和概念。

2.1.1 消息和加密

消息被称为明文。用某种方法伪装消息以隐藏它的内容的过程称为加密，被加密的消息称为密文，而把密文转变为明文的过程称为解密。图2.1表示了这个过程。密码算法是用于加密和解密的数学函数。

密码学（Cryptology）是研究信息系统安全保密的科学。传统密码学包括密码编码和密码分析两方面的内容。密码编码学（Cryptography）主要研究对信息进行编码，实现对信息的隐蔽。密码分析学（Cryptanalytic）主要研究加密消息的破译或消息的伪造。密码编码技术和密码分析技术是相互依存、相互促进、密不可分的两个方面。随着密码学的发展，这一学科包含了更广泛的内涵，除了编码与破译，而且还包括密码协议、散列函数、安全管理等内容。密码学的进一步发展，又涌现了大量的新概念和新技术，如零知识证明、盲签名、量子密码、混沌密码等。

● 对明文进行加密操作的人员称为加密员或密码员（Cryptographer）。

● 密码算法（Cryptography algorithm）是用于加密和解密的数学函数。

● 密码员对明文进行加密操作时所采用的一组规则称为加密算法（Encryption algorithm）。

● 所传送消息的预定对象称为接收者（Receiver）。

● 接收者对密文解密所采用的一组规则称为解密算法（Decryption algorithm）。

● 加密和解密的操作通常都是在一组密钥的控制下进行的，分别称为加密密钥（Encryption key）和解密密钥（Decryption key）。

下面通过一个例子来解释以上概念。

2.1.2 恺撒密表

公元前54年，古罗马杰出的军事家、政治家和作家，共和国末期的独裁者恺撒（Caesar）使用一个简单的代替密码来保护军队和政府的通信，在密码学上称为“恺撒密表”。古罗马文字就是我们英语中所熟知的26个拉丁字母，“恺撒密表”把明文中每一个字母用它在字母表中位置后面的第三个字母代替，如表2.1所示。

例如，有一个拉丁文句子：

omnia gallia est divisa in partes tres

（高卢全境分为三个部分）

用恺撒密表加密后就成为密文RPQLD JDOOLD HVW GLYLVD LQ SDUWHVWUHV。如果不知道其中奥秘，简直不知所云。收信者收到这段密文后要进行解密，解密也用的是恺撒密表，就是把恺撒密表第二行中的每一个字母用它头顶上第一行的相应字母代替。虽然加解密都在用恺撒密表，但加解密时所用的变换是两个互逆的变换。如果用数字0，1，2，…，25分别表示字母a，b，c，…，z，加密相当于模26加3，解密相当于模26减3。除了这种简单代替外，恺撒还把明文的拉丁字母代替为对应的希腊字母。

从以上例子看到，密码的变换规则显然是至关重要的，一旦变换规则被敌方掌握，则无秘密可言，因此变换规则必须严格保密。要提高密码的安全性，不能让敌方轻易破译，就要把变换规则设计得尽量复杂，但变换规则复杂到一定程度就变得难以记忆，需要用文字记录下来，而一有文字记录，其安全性就大打折扣。首先，加密双方需要有变换规则的复本，而复本越多，安全性就越差，文字记录与被保管者的分离，也增加了其被窃取的可能性。如果在把变换规则设计得尽可能复杂的同时，设计出一个或一组“关键词”，根据这个（组）关键词可以推导出变换规则，这个关键词就称为密钥。恺撒密表的密钥就是3，加密规则是“后移3”，而解密规则是“前移3”。

2.1.3 密码体制

图2.2给出了保密通信的模型，密码学的目的就是A和B两个人在不安全的信道上进行通信，而攻击者（破译者）O不能理解他们通信的内容。

通常一个完整密码体制要包括如下5个要素M、C、K、E、D：

● M是可能明文的有限集，称为明文空间。

● C是可能密文的有限集，称为密文空间。

● K是一切可能密钥构成的有限集，称为密钥空间。

● 对于密钥空间的任一密钥k∈K，有一个加密算法ek∈E和相应的解密算法dk∈D，使得 e: →k M C和d: →k C M 分别为加密解密函数，满足dk（ek（x））= x，这里x∈M。

一个密码体制要是实际可用的，必须满足如下特性：

（1）每一个加密函数ek和每一个解密函数dk都能有效地计算。

（2）破译者取得密文后，将不能在有效的时间内破解出密钥k或明文x。

（3）一个密码系统是安全的必要条件是穷举密钥搜索将是不可行的，即密钥空间非常大。

密码学中的术语“系统或体制”（System）、“方案”（Scheme）和“算法”（Algorithm）本质上是一回事情，本书按作者的习惯交替使用这些术语。

2.1.4 密码算法的分类

密码的发展经历了古典密码、对称密钥密码、公开密钥密码的发展阶段。古典密码是基于字符替换的密码，现在已很少使用了，但是它代表了密码的起源。现在仍在使用的则是对位进行变换的密码算法。密码算法可以按照不同的标准分类如下。

（1）按照保密的内容分为，受限制的（Restricted）算法和基于密钥（Key-based）的算法。

受限制的算法指的是算法的保密性基于保持变换规则的秘密。虽然这种密码也有密钥，但算法的安全基于对整个变换规则的保密。古典密码就是这类密码。1883年Kerchoff第一次明确提出了密码编码的原则：加密算法应建立在变换规则的公开不影响明文和密钥的安全的基础上。这一原则已得到普遍承认，成为判定密码强度的衡量标准，实际上也成为古典密码和现代密码的分界线。基于密钥的算法指的就是算法的保密性基于对密钥的保密的密码算法。现代密码都属于这类密码。为什么基于密钥的算法比受限制的算法更安全和实用，这里可以给出如下几个理由：

（a）攻击者总会设法找到算法：在密码学的历史上，攻击者总是能在没有任何帮助的情况下推导出你的算法。在战争年代，他们可以偷盗密码机，或是通过敲诈、勒索等手段使一些人泄密，甚至可以在没有密码机的情况下，确定它是如何工作的。在现代，如果密码系统是用软件实现的，密码分析者可以使用汇编语言调试器跟踪目标代码得到它，如果密码系统是基于硬件的，工程师就可以打开它，了解它的内部结构。有时，使一个算法保密的时间足够长是可能的，但最终攻击者仍可以找到它。

（b）更换密钥比更换密码算法更容易：如果一个算法的安全性基于算法的保密，算法泄露就意味着不得不使用新算法，而设计一个新算法的代价远比更换密钥要大得多。

（c）公开的算法更安全：当算法公开后，全世界的密码分析者和计算机工程师就有了检验它的弱点的机会，如果算法是保密的，就没有足够多的分析者来发现它可能存在的弱点，这不意味着它没有弱点，而是仅仅意味着你不知道算法的弱点。

（d）商业应用的需要：密码算法公开才能进行标准化，得到更广泛的应用，从而带来经济效益。如果希望算法保密，就只能让有限的信任的人才可以使用它，结果就是无钱可赚。

（2）基于密钥的算法，按照密钥的特点分为对称密码算法和非对称密码算法。

对称密码算法（Symmetric cipher）的加密密钥和解密密钥相同，或实质上等同，即从一个易于推出另一个，对称密码算法又称为秘密密钥算法或单密钥算法。

非对称密钥密码算法（Asymmetric cipher）的加密密钥和解密密钥不相同，从一个很难推出另一个，非对称密钥算法又称为公钥密码算法（Public key cipher）、双钥密码算法。

公钥密码算法用一个密钥进行加密，而用另一个进行解密。其中的加密密钥可以公开，又称为公开密钥（Public key），简称公钥。解密密钥必须保密，又称为私人密钥（Private key）或私有密钥，简称私钥。

（3）按照明文的处理方法，密码算法又可分为序列密码和分组密码两大类。

序列密码每次加密一位或一字节的明文，也可以称为流密码。序列密码是手工和机械密码时代的主流。它的主要原理是：通过有限状态机产生性能优良的伪随机序列，使用该序列逐比特加密信息流，得到密文序列，算法的安全强度完全决定于它所产生的伪随机序列的好坏。产生好的序列密码的主要途径之一是利用移位寄存器产生伪随机序列。目前要求寄存器的阶数大于100 阶，才能保证必要的安全。由于序列密码具有实现简单、速度快、错误扩展小等优势，在专用和机密机构中仍保持着优势。分组密码将明文分成固定长度的组，用同一密钥和算法对每一分组加密，输出也是固定长度的密文。

对称密钥密码又可分为分组密码和流密码，多数网络加密应用的就是对称分组密码，如DES，IDEA，RC6，Rijndael等。对称流密码一次对一位或一字节加密，一次一密（One-time pad）以及古典密码中的Vigenére，Vernam密码可以看做流密码。

公开密钥密码大部分是分组密码，只有概率密码体制属于流密码。公开密钥密码可用于数字签名和身份鉴别，如RSA、ECC和ElGamal算法，每次对一块数据加密，加密解密速度比对称密码慢。

2.1.5 密码分析

假设破译者O是在已知密码体制的前提下来破译正在使用的密钥。这个假设称为Kerckhoff原则。密码分析必须假设在破译时已经具备了一些已知条件，根据攻击者掌握的信息的多少，最常见的破解类型如下：

唯密文攻击：破译者O仅掌握了一些密文，具有密文串y。

已知明文攻击：破译者O具有明文串x和相应的密文y。

选择明文攻击：破译者O可获得对加密机的暂时访问，因此他能选择明文串x并构造出相应的密文串y。

选择密文攻击：破译者O可暂时接近密码机，可选择密文串y，并构造出相应的明文串x。

选择密文攻击主要用于公钥密码体制，有时选择明文攻击和选择密文攻击一起称为选择文本攻击。

上述4 种攻击的强度按序递增，唯密文攻击显然是比较困难的，但对于密码的编制者来说，设计一个密码能抵御唯密文攻击应该是最低的要求了。如果设计的密码系统能抵抗选择明文攻击，那么它肯定能抵抗唯密文攻击和已知明文攻击。

2.1.6 密码算法的安全性

密码算法的安全性有两种理解：无条件安全（Unconditionally secure）和计算上的安全（Computationally secure）。无条件安全指的是无论破译者有多少密文，他也无法解出对应的明文，即使他解出了，也无法验证结果的正确性。有一种理想的加密方案，叫做一次一密密码（One-time pad）。它是由Major Joseph Mauborgne和AT&T公司的Gilbert Vernam在1917年发明的。一次一密密码本是一个大的不重复的真随机密钥字母集，每个密钥仅对一个消息使用一次，该体制的主要问题是密码本的安全分配和存储问题。除了一次一密之外，所有的加密算法都不是无条件安全的。使用者应尽量挑选满足下列要求的算法：

● 破译的代价超出信息本身的价值。

● 破译的时间超出了信息的有效期。

满足上述两条标准的加密体制是计算上安全的。

可以从以下三方面来衡量攻击方法的复杂性：

● 数据复杂性（Data complexity）：用做攻击输入所需要的数据量。

● 处理复杂性（Processing complexity）：完成攻击所需要的时间。

● 存储需求（Storage requirement）：进行攻击所需要的存储量。

密码分析者攻击密码的两个基本方法是穷举法和分析法。

穷举法（Exhaustive attack method），又称为强力法（Brute-force method），完全试凑法（Complete trial-and-error method）。可以采用两种做法，一种是对截获的密文依次用各种可能的密钥破译，一种是对所有可能的明文加密直到与截获的密文一致为止。分析法又分为统计分析法（系统分析法）和确定性分析法，统计分析法通过分析明文和密文的统计规律来破译密码，确定性分析法指针对加密算法的数学依据，通过数学求解的方法来破译密码。