1.2 现代密码学

现代密码学的任务不再仅限于传统密码学的“保密通信”，而是含义更广的“信息安全”，包括“保密通信”“数据加密”“数字签名”等重要功能，并且其应用也远远突破了军事的范围，开始全面进入经济、商务、科学、教育等各个领域。现代密码学方法可分为如下5个类别。

·对称加密：同一个密钥可以同时用作信息的加密和解密，这种加密方法称为对称加密。

·非对称加密：需要两个密钥来进行加密和解密，这两个密钥是公开密钥（Public Key，简称公钥）和私有密钥（Private Key，简称私钥）。

·密码学哈希：哈希（Hash）函数将可变长度的数据块作为输入，产生固定长度的哈希值，在安全应用中使用的哈希函数被称为密码学哈希。

·消息认证码：经过特定算法后产生的一小段信息，检查某段消息的完整性，以及做身份验证。它可以用来检查在消息传递过程中，其内容是否被更改过，不管更改的原因是来自意外或是蓄意攻击。同时可以作为消息来源的身份验证。

·数字签名：只有信息的发送者才能产生的别人无法伪造的一段数字串，这段数字串同时也是对信息的发送者发送信息真实性的一个有效证明。

1.2.1 现代密码学的特点

现代密码学研究信息从发端到收端的安全传输和安全存储，是研究“知己知彼”的一门科学。其核心是密码编码学和密码分析学。1949年，香农发表了一篇名为《保密系统的通信理论》的论文，把已有数千年历史的密码学推向了基于信息论的科学轨道。该文提出了 混淆 （Confusion）和 扩散 （Diffusion）两大设计原则，为对称密码学建立了理论基础。而密码学真正意义上开始进入发展期还是20世纪70年代中期。1976年，美国密码学家迪菲和赫尔曼发表了一篇名为“密码学新方向”的论文，开启了公钥密码体制（非对称密码体制）的新篇章。

同时，计算机科学的蓬勃发展也极大地刺激和推动了密码学的变革。善于快速计算的电子计算机为加密技术提供了新的工具。计算机和电子学时代的到来给密码设计者带来了前所未有的自由。

当代密码学具有如下基本属性。

●信息的机密性：保证信息不被泄露给非授权者等实体。采用密码技术中的加密保护技术可以方便地实现信息的机密性。

●信息的真实性：保证信息来源可靠、没有被伪造和篡改。密码中的安全认证技术可以保证信息的真实性。

●数据的完整性：数据没有受到非授权者的篡改或破坏。密码杂凑算法可以方便地实现数据的完整性。

●行为的不可否认性（抗抵赖性）：一个已经发生的操作行为无法否认。基于公钥密码算法的数字签名技术可以有效解决行为的不可否认性问题。

依据加密和解密所使用的密钥是否相同可将密码分为对称密码体制与非对称密码体制。

1.2.2 对称加密

对称密码体制（单钥体制）是指加密和解密使用相同密钥的密码算法，如图1-3所示。

采用对称密码体制的系统的保密性主要取决于密钥的保密性，与算法的保密性无关， 即算法无须保密，需要保密的仅有密钥。

对称密码体制对明文消息的加密有两种方式：一种是将明文消息分组（每组中含有多个字符），逐组对其进行加密，这种密码体制称为 分组密码 （Block Cipher）；另一种是由明文消息按字符逐位加密，这种密码体制称为 序列密码或流密码 （Stream Cipher）。

1.分组密码

利用分组密码对明文加密时，首先需要对明文进行分组，每组的长度都相同，然后对每组明文分别加密得到密文。设 n 是一个分组密码的分组长度， k 是密钥， x = x ₀ x ₁ … x _{n -1} 为明文， y = y ₀ y ₁ … y _{m -1} 为相应的密文，则：

y =Enc _k （ x ）

x =Dec _k （ y ）

其中，Enc _k 和Dec _k 分别表示在密钥 k 控制下的加密变换和解密变换。分组密码模型如图1-4所示。

分组密码有两种常见的结构，分别为 Feistel网络 （Feistel Net）和 SP网络 （Substitution Permutation Net）。DES和SM4是Feistel网络的典型例子，AES是SP网络的典型例子。

Feistel网络包含对称结构和非对称结构两类，以它的发明者Horst Feistel命名。在Feistel网络中，加密的各个步骤称为轮（Round），整个加密的过程即进行若干轮次的循环。以对称结构的Feistel网络为例，其一轮的计算步骤如图1-5所示。

Feistel网络第 i 轮的计算步骤如下。

1）将输入的待加密的明文 x 分为左（ L _{i -1} ）和右（ R _{i -1} ）两部分。

2）将输入的右部分 R _{i -1} 直接传送至输出的左部分 L _i 。

3）将输入的右部分 R _{i -1} 与使用密钥 k 生成的子密钥 k _i 一起输入加密的轮函数（Round Function，RFun），也称圈函数。

4）将输入的左部分 L _{i -1} 与加密函数RFun的输出进行异或运算，再传送至输出的右部分 R _i 。

Feistel网络的优点在于加密过程与解密过程相似，甚至可以使用同一个算法实现加密和解密。

SP网络的加密思想为：设待加密的明文为 x ，令 X ₀ = x ，且 r 为加密变换的迭代次数。对于1≤ i ≤ r ，在子密钥 k _i 的控制下，对 X _{i -1} 做替换 S ，再对替换结果做可逆的线性变换 P ，得到 X _i ，如图1-6所示。

在SP网络中，替换 S 通常被称为混淆层，主要起混淆的作用；置换或可逆的线性变换 P 通常被称为扩散层，主要起扩散的作用。

SP网络加密和解密过程一般不相似，即不能用同一个算法来实现加密和解密。

上述两种网络描述如何根据密钥对一段固定长度（分组长度）的数据进行加密，对于较长的数据，需要重复应用某种分组加密的操作来安全地加密数据，称为分组密码工作模式。常见的分组密码工作模式有 电子密码本 （Electronic Code Book，ECB）、 密码分组链接 （Cipher Block Chaining，CBC）、 密码反馈 （Cipher Feedback，CFB）、 输出反馈 （Output Feedback，OFB）和 计数器 （Counter Mode，CTR）5种模式。

ECB模式是最简单的工作模式。该模式一次对一个固定长度的明文进行分组加密，且每次加密所使用的密钥均相同。ECB模式的加密操作如图1-7所示。

CBC模式解决了ECB模式的安全缺陷，可以让重复的明文分组产生不同的密文分组。CBC模式一次对一个明文分组进行加密，每次加密使用同一密钥，加密算法的输入为当前明文分组和前一次密文分组的异或，因此CBC模式能隐蔽明文的数据模式，在某种程度上能防止数据篡改，如重放、嵌入和删除等。但是CBC模式会出现传播错误，对同步差错敏感。CBC模式的加密操作如图1-8所示。

CFB模式和CBC模式比较相似，明文单元被链接在一起，使得密文是前面所有明文的函数。CFB模式中加密的输入是64bit移位寄存器，其初值为某个初始向量 IV ，解密为将收到的密文单元与加密函数的输出进行异或操作。CFB模式适于用户数据格式的需要，能隐蔽明文数据图样，也能检测出对手对于密文的篡改，但对信道错误较敏感，且会造成错误传播。此外，CFB模式需要一个初始向量，并且需要和密钥同时进行更换。CFB模式的加密操作如图1-9所示。

OFB模式和CFB模式比较相似，将分组密码算法作为一个密钥流产生器，其输出的 k bit密钥直接反馈至分组密码的输入端，同时这 k bit密钥和输入的 k bit明文段进行对应位模2相加。OFB模式克服了CBC和CFB的错误传播所带来的问题，然而 OFB模式对于密文被篡改难以进行检测，不具有自同步能力，要求系统要保持严格的同步。 OFB模式的加密操作如图1-10所示。

CTR模式被广泛用于ATM网络安全和IPSec应用中。CTR模式的加密操作如图1-11所示。

2.序列密码

序列密码也称为流密码（Stream Cipher），是对称密码算法的一种，也是密码学的一个重要分支，具有实现简单、便于硬件实施、加解密处理速度快、没有或只有有限的错误传播等特点，因此获得了广泛应用。

理论上“一次一密”密码是不可破译的。 使用尽可能长的密钥可以使序列密码的安全性提高，但是密钥长度越长，存储、分配就越困难。于是人们便想出 采用一个短的种子密钥来控制某种算法获得长的密钥序列的办法 ，这个种子密钥的长度较短，存储、分配都比较容易。序列密码的原理如图1-12所示。

密钥流由密钥流生成器 f 产生，即 z _i = f （ k ， σ _i ），其中 σ _i 是加密器中的记忆元件（寄存器）。在时刻 i 的状态， k 为种子密钥， f 是由密钥 k 和 σ _i 产生的函数。序列密码的滚动密钥 z ₀ = f （ k ， σ ₀ ）由函数 f 、密钥 k 和指定的初态 σ ₀ 完全确定。输入加密器的明文影响加密器中内部记忆元件的存储状态，因此 σ _i （ i >0）可能依赖于 k ， σ ₀ ， x ₀ ， x ₁ ，…， x _{i -1} 等参数的变化而变化。因此序列密码是有记忆性的。

序列密码通常被划分为 同步序列密码 和 自同步序列密码 两大类。

同步序列密码的密钥序列的产生独立于明文消息和密文消息。此时， z _i = f （ k ， σ _i ）与明文字符无关，密文字符 c _i =Enc _{z i} （ p _i ）也不依赖此前的明文字符。因此，可将同步序列密码的加密器分成密钥流生成器和加密变换器两个部分，如图1-13所示。

自同步序列密码的密钥序列的产生是密钥及固定大小的以往密文位的函数，也称非同步序列密码，其加解密流程如图1-14所示。自同步序列密码的加密过程可以用下列公式来描述：

σ _i =（ c _i-t ， c _{i-t +1} ，…， c _{i -1} ）

z _i = g （ σ _i ， k ）

c _i = h （ z _i ， m _i ）

其中， σ _i =（ c _i-t ， c _{i-t +1} ，…， c _{i -1} ）是初始状态； k 是密钥； g 是产生密钥序列 z _i 的函数； h 是将密钥序列 z _i 和明文 m _i 组合产生密文 c _i 的输出函数。

1.2.3 公钥密码：密码学历史上最伟大的发明

随着计算机和网络通信技术的迅速发展，保密通信的需求也越来越广泛，对称密码体制的局限性也日益凸显，主要表现在密钥分配的问题上，即发送方如何安全、高效地将密钥传送至接收方。此外，采用对称密码体制，在有多个用户的网络中，任何两个用户之间都需要有共享的密钥，当网络中的用户量很大时，密钥的产生、保存、传递、使用和销毁等各个方面都变得十分复杂，存在安全隐患。

1976年，Diffie和Hellman提出了公钥密码的思想，基于此思想建立的密码体制，被称为公钥密码体制，也称非对称密码体制。 公钥密码算法中的加密算法也被称为非对称加密，因为加密和解密使用不同的钥匙，其中一个公开的，称为公开密钥（Public-Key），简称公钥，用于加密；另一个是用户私有的，称为私钥（Private-Key），用于解密， 如图1-15所示。

公钥密码体制加密过程包括如下4步。

1）接收者产生一对钥匙 pk 、 sk ，其中 pk 是公钥， sk 是私钥。

2）接收者将加密的公钥 pk 予以公开，解密的私钥 sk 自己保存。

3）发送者使用接收者公钥加密密文 m ，表示为 c =Enc _pk （ m ），其中 c 是密文，Enc是加密算法。

4）接收者接收到密文 c 后，用自己的 sk 解密，表示为 m =Dec _sk （ c ），其中Dec是解密算法。

因为只有接收方知道自身的私钥 sk ，因此其他人都无法对 c 解密。公钥密码加密和解密结构图如图1-16所示。

RSA算法是经典的非对称加密算法，由麻省理工学院三位年青学者Rivest、Shamir和Adleman在1978年用数论构造，后来被广泛称之为RSA体制，其安全性基于数论中大整数因式分解的困难性。

1.2.4 密码学哈希

哈希函数（Hash Function）是密码学中用途最多的密码算法之一，在消息摘要、网络协议等诸多领域得以应用。哈希函数 H 将任意长度的数据块 M 作为输入，生成固定长度的哈希值 h = H （ M ）作为输出。在密码学中，一个性质优良的哈希函数应当具有以下特点： 对于不同的输入，哈希函数应当使输出结果均匀分布于哈希值域，并且让哈希结果看起来随机。 对于输入的极小改动都会引发哈希值的极大改变。

在实际应用中，密码学哈希函数有以下安全性需求：抗原像攻击，给定任意的哈希值 h ，找到对应的哈希函数，输入 M 是计算上不可行的；抗第二原像攻击，给定输入 M ₁ ，找到 M ₂ ≠ M ₁ 且 H （ M ₁ ）= H （ M ₂ ）是计算上不可行的；抗碰撞攻击，找到任意的 M ₁ 和 M ₂ ，使得 H （ M ₁ ）= H （ M ₂ ）；伪随机性，哈希函数的输出能满足伪随机判定。如果一个哈希算法满足抗原像攻击和抗第二原像攻击，就称为弱哈希函数，在此基础上如果满足抗碰撞攻击，则称为强哈希函数。

1.密码学哈希的应用

哈希函数可以用来验证消息或是文件的完整性。通过比对传输前后消息的哈希值是否一致可以快速地判断消息或是文件是否有被篡改或是数据丢失。当哈希函数用于消息认证时，消息的哈希值通常被称为消息摘要。同样，这一概念可以拓展到对任意数据的认证，例如，对存储中的文件进行快速分块检查，确保文件没有被篡改，或是对于网络下载数据进行完整性检验，确保文件通过网络传输后的完整性。由于消息摘要的长度远远小于消息本身，因此通过比对消息摘要可以更快地实现消息或文件的完整性验证。

此外，由于密码学哈希具有抗原像攻击和抗第二原像攻击的良好性质，通常还被用于产生单向口令文件。在操作系统中，为了防止恶意攻击者获得口令文件后获取用户口令，需要将用户口令的哈希值作为口令文件进行存储。每次用户输入口令时，操作系统首先生成输入口令的哈希值，再将该哈希值与口令文件中的哈希值进行比对。这样一来，攻击者即使掌握了口令文件，由于密码学哈希具有抗原像攻击的性质，攻击者无法复现出用户口令，使得用户口令的安全性得到了保障。大多数系统目前都采用了这样的口令保护机制。

除此之外，密码学哈希还可用于伪随机数发生器和构建伪随机函数，在此基础上构造的伪随机函数可以用来生成对称密码中的密钥。

2.常见的密码学哈希

MD5是Ronald Linn Rivest在1991年设计的，用来取代以前的MD4算法，输出128比特的哈希值。随着近年来密码学研究的不断深入以及计算机硬件的不断进步，对MD5的碰撞攻击可以在几秒钟内计算出来，这使得MD5算法不适合大多数密码学哈希的适用场景。

SHA（通常也被称作SHA-0）是由美国国家标准与技术研究所（NIST）设计，并于1993年作为联邦信息处理标准发布的。在随后的应用实践中被发现存在安全缺陷，1995年，NIST发布了SHA-0的改进版SHA-1，SHA算法的基本框架与MD4类似。2002年，NIST发布了修订版的SHA-2算法，其中包括了SHA-256、SHA-384和SHA-512，三种算法分别产生256、384和512比特的哈希值。2010年，一项研究表明SHA-1的安全性并没有理论上的那么可靠，大约需要2 ⁸⁰ 次搜索便可以找到一个碰撞，这也加速了目前应用领域从SHA-1到SHA-2的过渡。

SM3是一种中国密码哈希函数标准，于2010年12月17日由国家密码管理局发布。在商用密码体系中，SM3可用于数字签名及验证、消息认证码生成及验证、随机数生成等算法中。SM3算法作为一种公开哈希算法，其安全性及效率与SHA-256相当。

1.2.5 消息认证码

消息认证码（Message Authentication Code，MAC）是密码学中的一种认证技术。MAC函数的形式化定义如下：

T =MAC（ K ， M ）

式中， T 表示生成的消息认证标记（Tag）， K 表示发送方与接收方的密钥， M 表示发送方发送的任意长度的消息。通常消息认证码是一个固定长度的短数据块，由密钥和消息产生并附加在消息之后，与消息一起从发送方传递到接收方。接收方对收到的消息进行和发送方一样的计算，通过比较计算出的消息认证码 T' 与接收到的 T 是否相等，实现消息认证。

消息认证包含两方面的信息确认：一方面 接收方可以验证消息本身并没有被修改， 如果存在中间攻击者修改了消息内容，由于攻击者不知道密钥 K ，无法通过修改后的消息生成新的消息认证码 T' 使得其与收到的消息认证码 T 相等；另一方面， 接收方验证了消息发送方的身份， 这是由于其他人都不知道消息认证码的密钥，因此其他人不能生成正确的 T 。

在MAC函数中，由于 K 是发送方和接收方共享的密钥，双方均能正向生成 T ，因此MAC函数不能作为数字签名算法。这也意味着消息的发送方和接收方必须在初始化通信之前就密钥达成一致，这与对称加密的情况相同。

1.MAC函数的性质

在讨论MAC函数的安全性时需要从多方面考虑，分析其可能面对的各种类型的攻击。由于MAC算法往往是公开的，因此假设攻击者知道MAC函数，却不知道收发双方的密钥 K ，一个安全的MAC函数应当具有以下三条性质：①对于任意 M 和对应的 T ，攻击者构造出 M' 使得MAC（ K ， M ）=MAC（ K ， M' ）= T 是计算上不可行的；②对于不同的消息输入，MAC函数应当使输出结果 T 均匀地分布于消息认证码空间，即对于随机选择的 M ₁ 、 M ₂ ， Pr ［MAC（ K ， M ₁ ）=MAC（ K ， M ₂ ）］=2 ^-n ，其中 n 是消息认证码的位数；③对于消息的任意变换 f 都保持输出的随机性，即 Pr ［MAC（ K ， M ）=MAC（ K ， f （ M ））］=2 ^-n 。

第一条性质要求在攻击者不知道密钥的情况下无法构造出与给定的MAC相匹配的一个新消息。第二条性质使得针对MAC算法的穷举攻击代价与消息认证码值域大小线性相关，穷举攻击者需要 O （2 ⁿ ）步才能找到给定MAC对应的消息。第三条性质要求MAC函数对于消息的各个部分应当是公平的，攻击者无法通过消息的某个部分或是消息的某个结构对MAC函数发起攻击。

2.常见的MAC算法

常见的MAC算法主要分为两类： 基于哈希函数 的MAC算法（Hash-based MAC，HMAC）和 基于密码 的MAC算法（Cipher-based MAC，CMAC）。

密码学哈希函数的执行速度比较快，并且由于密码学哈希函数拥有广泛的适用性，现有的哈希函数库比较完备，HMAC算法在很长一段时间内被广泛讨论。但是由于哈希函数本身在设计时并不依赖密钥，所以需要对原有的哈希方案进行改进。目前，基于改进后带密钥的HMAC方案已被广泛应用，其作为NIST的标准（FIPS 198），是IP协议族中的重要组成部分，并且在SSL协议中也有使用。

CMAC算法（也被称为OMAC1）是一种基于分组密码的MAC算法，被NIST于2005年作为标准发布。它是CBC-MAC算法的改进，CBC-MAC算法只保障固定长度消息算法的安全性，而CMAC算法可以保障任意长度消息算法的安全性。

1.2.6 数字签名：替代手写签名

数字签名是公钥密码发展过程中的一个重要产物，不同于一般的公钥加解密方案，数字签名无需保证消息的机密性，却能保证消息对发送方身份和数据完整性的认证。相较于上一节中提到的消息认证，数字签名具有不可否认性，也就是说，只要发送方对某消息进行了数字签名，就无法否认自己曾经发送过该条消息。

在消息认证的方案中，由于通信双方共享消息认证码的生成密钥，接收方可以伪造任意消息的消息认证码并称消息由发送方发出。此外，由于接收方拥有伪造消息的能力，所以无法证明发送方是否发送过某条消息，进而发送方可以否认发送过的某条消息。在收发双方不能完全诚实可信的情况下，为了实现消息认证码所无法实现的功能，数字签名必须具备以下的性质： 能够验证签名者的身份和签名的时间戳；能够认证被签名的消息内容的完整性；签名能够被第三方所验证。

数字签名方案的形式化定义通常包括三个算法：密钥生成算法、签名算法和签名验证算法。密钥生成算法从密钥空间中随机选择一个私钥，输出私钥和相应的公钥。签名算法接收消息和私钥作为输入，产生消息对应的签名。签名验证算法以消息、公钥和签名作为输入，根据签名是否通过验证输出接收或拒绝。

公钥密码体制中数字签名过程包括如下几步。

1）签名者产生一对钥匙 pk 、 sk ，其中 pk 是公钥， sk 是私钥。

2）签名者将验证用的公钥 pk 予以公开，签名的私钥 sk 自己保存。

3）签名者使用私钥 sk 对消息 m 进行签名，表示为 σ =Sign _sk （ m ），其中 σ 是签名，Sign是签名算法。验证者接收到消息和签名对（ m ， σ ）后，用签名者的公钥 pk 验证，表示为0 / 1=Verify _pk （ m ， σ ），其中Verify是验证算法，1表示验证成功，0表示验证失败。

数字签名算法（Digital Signature Algorithm，DSA）的结构如图1-17所示。

数字签名算法被美国NIST作为数字签名标准（Digital Signature Standard，DSS），是Schnorr和ElGamal两种签名算法的变种，其安全性基于整数有限域离散对数难题。 i7c2+G9zHzWIWSUtDpdfyw9+CEAfWqwVCp1xVrZpLbGAvprJl9HVcTbZ8Qj++AlQ