1.4 密码算法

现代密码学理论中，算法是密码技术的核心。常见的密码算法包括对称密码算法、公钥密码算法和密码杂凑算法三个类别，如图1-5所示。习惯上，对称密码算法简称为“对称密码”，公钥密码算法简称为“公钥密码”，密码杂凑算法简称为“杂凑算法”。

本节将结合上述三类密码算法，主要介绍五种已经以密码行业标准或国家标准形式公布的商用密码算法：ZUC、SM2、SM3、SM4和SM9，以及常见的国外密码算法。

1.4.1 对称密码算法

对称密码算法加密过程与解密过程使用相同的或容易相互推导得出的密钥，即加密和解密两方的密钥是“对称”的。这如同往一个上了锁的箱子里放物品，放入时需要用钥匙打开；想要取出物品时，还需要用同样的钥匙开锁。早期的密码算法都是对称形式的密码算法。

对称密码加密和解密基本流程如图1-6所示。用户通过加密算法将明文变换为密文。密文的具体值由密钥和加密算法共同决定。只有掌握了同一个密钥和对应解密算法的用户才可以将密文逆变换为有意义的明文。

针对不同的数据类型和应用环境，对称密码有两种主要形式：一是序列密码（也称“流密码”，stream cipher），二是分组密码（也称“块密码”，block cipher）。我国发布的商用密码算法中的序列密码算法和分组密码算法分别是ZUC和SM4算法。常见的国外序列密码算法有SNOW（如SNOW 2.0、SNOW 3G）、RC4等；分组密码算法有数据加密标准（DES），三重数据加密算法（TDEA，也称3DES），高级加密标准（AES）等。

1．序列密码和分组密码

1）序列密码和分组密码的区别

序列密码和分组密码都属于对称密码，其加密流程对比如图1-7所示。序列密码和分组密码的区别在于序列密码是将密钥和初始向量（Initial Vector，IV）作为输入，通过密钥流生成算法输出密钥流（也称扩展密钥序列），然后将明文序列和密钥流进行异或，得到密文序列。分组密码首先对明文消息根据分组大小进行分组，再将明文分组、密钥和初始向量（如果有）一起作为输入，通过分组加密算法直接输出密文分组。

通过图1-7可以看出，序列密码的特点在于密钥流可以在明文序列到来之前生成。序列密码对每个明文序列的加密操作仅仅是一次异或，因此序列密码的执行速度通常很快，对计算资源的占用也较少，常用于功耗或者计算能力受限的系统中，如嵌入式系统、移动终端等，也可用于实时性要求高的场景（如语音通信、视频通信等）。

2）初始向量

如图1-7所示，在对称密码的实际应用场景中，初始向量是一个在加密过程中起到引入随机性作用的随机数，即在加密一批明文数据之前，加密方先要随机生成一个初始向量，并将它和密钥一起输入到加密算法中。每次加密初始向量都必须重新生成，初始向量的引入使得多次分别对同一明文数据使用相同的密钥进行加密，得到的密文是不同的。初始向量在加密完成后可随着密文一起通过非安全信道传输，即使攻击者截获了初始向量，也不会对保密性构成威胁。在后续介绍的分组密码的工作模式及ZUC序列密码算法中均会用到初始向量。

2．分组密码的工作模式

我国于2008年发布了规定分组密码算法工作模式的国家标准GB/T 17964-2008《信息安全技术 分组密码算法的工作模式》。在分组密码算法中，根据分组数据块链接的组合模式不同，可以分为以下七种工作模式：电码本（Electronic Code Book，ECB）模式、密文分组链接（Cipher Block Chaining，CBC）模式、密文反馈（Cipher Feedback，CFB）模式、输出反馈（Output Feedback，OFB）模式、计数器（Counter，CTR）模式、分组链接（Block Chaining，BC）模式、带非线性函数的输出反馈（Output Feedback with a Nonlinear Function，OFBNLF）模式。本节重点介绍常用的ECB、CBC、CTR模式。

注：分组密码算法还有一种带鉴别功能的加密模式，即可鉴别的加密模式（Authenticated Encryption Mode），可同时实现数据的保密性、完整性以及对数据源真实性的鉴别。相关国家标准GB/T 36624-2018《信息技术安全技术 可鉴别的加密机制》已经发布，包括CCM（Counter with CBC-MAC）、GCM（Galois/Counter Mode）等模式。

ECB、CBC、CTR各模式的参数含义如下：P1，P2，P3，…，Pq为q个明文分组；IV为初始向量；EK表示以K为密钥的加密算法；DK表示以K为密钥的解密算法；C1，C2，C3，…，Cq为q个密文分组。

一般分组密码加密分组大小为一固定长度，如128比特。如果消息长度超过固定分组长度时，在进行加密前，消息将被按照分组长度进行分块；如果消息长度不是分组长度的整数倍，则在分块后必须将其填充为分组长度的整数倍。

1）ECB模式

ECB模式是一种最直接的消息加密方法，ECB模式的加密和解密流程如图1-8所示。

通过图1-8的加密和解密流程，可以看出ECB模式具有如下性质：

①对某一个分组的加密或解密可独立于其他分组进行；

②对密文分组的重排将导致明文分组的重排；

③不能隐蔽数据模式，即相同的明文分组会产生相同的密文分组；

④不能抵抗对分组的重放、嵌入和删除等攻击。

因此，不推荐在应用中使用ECB模式。上述问题可以通过在加密处理中引入少量的“记忆”来克服，如下面要介绍的CBC模式。

2）CBC模式

CBC模式的加密和解密流程如图1-9所示。在CBC模式下，每个明文分组在加密之前，先与反馈至输入端的前一组密文分组按位异或后，再送至加密模块进行加密。其中，IV是一个初始向量，无须保密，但须随着消息的更换而更换，且收发双方必须选用同一个IV。显然，计算的密文分组不仅与当前明文分组有关，而且通过反馈作用还与以前的明文分组有关。在解密过程中，初始值IV用于产生第一个明文输出；之后，前一个密文分组与当前密文分组解密运算后的结果进行异或，得到对应的明文分组。

CBC模式具有如下性质：

①链接操作使得密文分组依赖于当前的和以前的明文分组，因此对密文分组的重新编排不会导致对相应明文分组的重新编排。

②加密过程使用IV进行了随机化，每次加密IV都必须重新生成，并且要保证IV的随机性。使用不同的IV可以避免ECB模式下每次对相同的明文使用相同的密钥加密生成相同的密文的弊端。

③加密过程是串行的，无法并行化；在解密过程中，通过两个相邻的密文分组执行解密操作可以获得明文分组，因此解密过程可以并行化。

此外，CBC模式还有一个重要用途：生成消息鉴别码（Message Authentication Code，MAC），即使用最后一个分组的输出结果作为MAC。MAC可以用于检验消息的完整性、验证消息源的真实性等。需要注意的是，基于CBC模式的MAC有许多安全特性与CBC模式并不相同，包括不能使用初始向量（初始向量为全0），以及只能为约定好长度的消息产生鉴别码等。

3）CTR模式

CTR模式通过将逐次累加的计数器值进行加密来生成密钥流。CTR模式的加密和解密流程如图1-10所示。每个明文分组P1，P2，P3，…，Pq对应一个逐次累加的计数器值T1，T2，T3，…，Tq，并通过对计数器值进行加密来生成密钥流。最终的密文分组C1，C2，C3，…，Cq是通过将计数器值加密得到的比特序列与明文分组进行异或得到的。需要注意的是，该模式下的消息长度可以不是分组长度的整数倍，即在加密前不需要进行填充操作。为保证每次每个分组的密钥流都是不同的，每次加密用到的计数器值都互不相同，即用同一个密钥加密不同消息，要保证一个计数器值只能用一次。

此外，还有一种用法是将一个单独的IV与计数器值拼接在一起作为生成密钥流的输入分组，此时计数器值一般从0或1开始。例如，对于分组长度是128比特的分组密码算法，IV和计数器值各占用其中的64比特。需要注意的是，将IV与计数器值直接相加或异或后作为输入是不安全的，这样会导致选择明文攻击。

CTR模式具有如下性质：

①支持加密和解密并行计算，可事先生成密钥流，进行加密和解密准备。

②只用到了分组密码算法的分组加密操作。

③错误密文中的对应比特只会影响解密后明文中的对应比特，即错误不会传播。

3．ZUC序列密码算法

ZUC（祖冲之密码算法）是我国发布的商用密码算法中的序列密码算法，该算法以中国古代数学家祖冲之的拼音（ZU Chongzhi）首字母命名，可用于数据保密性保护、完整性保护等。ZUC算法密钥长度为128比特，由128比特种子密钥和128比特初始向量共同作用产生32比特位宽的密钥流。

ZUC算法标准包括三个部分，相对应的国家和密码行业标准分别为GB/T 33133.1-2016《信息安全技术 祖冲之序列密码算法 第1部分：算法描述》、GM/T 0001.2-2012《祖冲之序列密码算法 第2部分：基于祖冲之算法的机密性算法》、GM/T 0001.3-2012《祖冲之序列密码算法 第3部分：基于祖冲之算法的完整性算法》。

2011年9月，在第53次第三代合作伙伴计划（3GPP）系统架构组会议上，我国以ZUC算法为核心的加密算法128-EEA3和完整性保护算法128-EIA3，与美国AES、欧洲SNOW 3G共同成为了4G移动通信密码算法国际标准。这是我国商用密码算法首次走出国门参与国际标准竞争，并取得重大突破。目前，我国正推动256比特版本的ZUC算法进入5G通信安全标准，这一版本算法采用256比特密钥与184比特的初始向量，可产生32/64/128比特三种不同长度的认证标签，从而保障后量子时代较长时期内移动通信的保密性与完整性。

1）ZUC算法的结构

ZUC算法由线性反馈移位寄存器（LFSR）、比特重组（BR）、非线性函数F三个基本部分组成，如图1-11所示。ZUC算法结构在逻辑上分为上、中、下三层，其中上层是16级LFSR，中间层是BR，下层是非线性函数F。

上层：LFSR以一个有限域GF（231-1）上的16次本原多项式为连接多项式，输出具有良好的随机统计特性。LFSR的输出作为中层BR的输入。

中间层：BR从LFSR的状态中取出128比特，拼成4个字（X0，X1，X2，X3），供下层的非线性函数F和输出密钥序列使用。BR实现LFSR数据单元到非线性函数F和密钥输出的数据转换，其主要目的是破坏LFSR在素域GF（231-1）上的线性结构。结合下层的非线性函数F，BR可使得一些在素域GF（231-1）上的密码攻击方法变得非常困难。

下层：非线性函数F从中层的BR接收3个字（X0，X1，X2）作为输入，经过内部的异或、循环移位和模232加法运算，以及两个非线性S盒变换，最后输出一个32比特W。由于非线性函数F是ZUC算法中唯一的非线性部件，所以非线性函数F就成为确保ZUC算法安全性的关键。S盒通常是对称密码算法唯一的非线性部件，它的非线性性质与密码算法整体强度有着直接关系，可以说一个好的算法都会有一个好的S盒。S盒一般实现一个小规模的非线性映射，例如，8比特到8比特的映射，或者轻量级算法中经常用到的4比特到4比特的映射。在算法描述中，S盒通常用一个代换表表示，不同的对称密码算法S盒的数量、构造方法也会不同。

最后，非线性函数F输出的W与BR输出的X3异或，形成ZUC算法的输出密钥字序列Z。

2）ZUC算法的使用

在生成密钥流时，ZUC算法采用128比特的初始密钥和128比特的IV作为输入参数，共同决定LFSR里寄存器的初始状态。随着电路时钟的变化，LFSR的状态被比特重组之后输入非线性函数F，每一拍时钟输出一个32比特的密钥流Z。随后，密钥流与明文按位异或生成密文。

3）基于ZUC的两种算法

基于ZUC的两种算法包括机密性算法128-EEA3和完整性算法128-EIA3。

（1）基于ZUC的机密性算法128-EEA3。主要用于4G移动通信中移动用户设备和无线网络控制设备之间的无线链路上通信信令和数据的加密和解密。

（2）基于ZUC的完整性算法128-EIA3。主要用于4G移动通信中移动用户设备和无线网络控制设备之间的无线链路上通信信令和数据的完整性校验，并对信令源进行鉴别。其主要技术手段是利用完整性算法128-EIA3产生MAC，通过对MAC进行验证，实现对消息的完整性校验。

4）ZUC算法的安全性

ZUC算法在设计中引入了素数域运算、比特重组、最优扩散的线性变换等先进理念和技术，体现了序列密码设计上的发展趋势。通过对其三层结构的综合运用，ZUC算法具有很高的理论安全性，能够有效抵抗目前已知的攻击方法，具有较高的安全冗余，并且算法速度快，软/硬件实现性能都比较好。

4．SM4分组密码算法

SM4算法是我国发布的商用密码算法中的分组密码算法。为配合WAPI无线局域网标准的推广应用，SM4算法于2006年公开发布，并于2012年3月发布为密码行业标准，2016年8月转化为国家标准GB/T 32907-2016《信息安全技术SM4分组密码算法》。

1）SM4算法描述

SM4分组密码算法是一个迭代分组密码算法，数据分组长度为128比特，密钥长度为128比特。加密算法与密钥扩展算法都采用32轮非线性迭代结构（非平衡Feistel结构）。Feistel结构的特色是加密和解密的算法结构完全一致，在硬件实现上加密和解密使用完全相同的电路。解密过程只需要把加密过程中产生的轮密钥逆序排列就能从密文分组中恢复出明文分组。

迭代加密算法的基本结构如图1-12所示。明文分组经过迭代加密函数变换后的输出又成为下一轮迭代加密函数的输入，如此迭代32轮，最终得到密文分组。每一轮迭代的函数是相同的，不同的是输入的轮密钥。

SM4算法中密钥扩展算法和加密算法的结构如图1-13所示。

详细描述如下：

（1）密钥扩展算法。

128比特的密钥表示为。密钥扩展算法迭代32轮，每轮产生一个轮密钥，轮密钥由加密密钥生成。首先进行初始化：

式中，是规定的128比特常数，⊕表示比特异或。对i=0，1，2，…，31执行：

得到轮密钥，其中，函数T的含义如图1-13（a）所示，CKi是32个32比特的固定常数。

（2）加密算法。

设明文输入为，密文输出为。加密时，对i=0，1，2，…，31执行：

密文为：

式中，R为反序变换函数。函数T′的含义如图1-13（b）所示。

2）SM4算法的性能和安全性

SM4算法具有安全高效的特点，在设计和实现方面具有以下优势：

①在设计上实现了资源重用，密钥扩展过程和加密过程类似。

②加密过程与解密过程相同，只是轮密钥使用顺序正好相反，它不仅适用于软件编程实现，更适合硬件芯片实现。

③轮变换使用的模块包括异或运算、8比特输入8比特输出的S盒，还有一个32比特输入的线性置换，非常适合32位处理器的实现。

通过对SM4密码算法的安全性分析结果表明：SM4算法的S盒设计具有较高的安全特性，线性置换的分支数达到了最优，可以抵抗差分分析、线性分析、代数攻击等密码分析方法。

在安全性上，SM4算法的密钥长度是128比特，其安全性与AES-128是相当的（AES还支持更高的安全强度）。在实现效率方面，由于SM4密钥扩展和加密算法基本相同，且解密时可以使用同样的程序，只需将密钥的顺序倒置即可，因此SM4算法实现起来较为简单；而AES算法的加密算法与解密算法不一致，实现起来更复杂一些。

5．国外对称密码算法AES介绍

常见的国外对称密码算法主要有DES、TDEA和AES。本节将重点对目前使用最广泛的AES算法进行介绍。

AES算法又称为Rijndael算法，是美国联邦政府采用的一种分组密码算法标准（据了解，美国联邦政府使用的密码算法标准与美国商用的基本一致，只是在密钥管理策略上不一样），用来替代DES并被广泛使用。AES算法的分组长度是128比特，密钥长度支持128比特、192比特或256比特。支持不同密钥长度的AES算法分别用AES-128、AES-192、AES-256表示，三者密钥的长度不同，加密的轮数也不同，如表1-3所示。AES-128、AES-192和AES-256的加/解密思路基本一样，只是密钥扩展算法的过程略有不同，加密和解密的轮数会适当增加，但加/解密的操作是一样的。

1.4.2 公钥密码算法

公钥密码算法又称非对称密码算法，既可用于加密和解密，也可用于数字签名，打破了对称密码算法加密和解密必须使用相同密钥的限制，很好地解决了对称密码算法中存在的密钥管理难题。公钥密码算法包括公钥加密和私钥签名（数字签名）两种主要用途。SM2、SM9算法是我国颁布的商用密码标准算法中的公钥密码算法，其中，基于SM2算法的数字签名技术已在我国电子认证领域广泛应用。

1．公钥密码模型

公钥加密算法加密和解密使用不同的密钥。其中加密的密钥可以公开，称为公钥；解密的密钥需要保密，称为私钥。公钥、私钥是密切关联的，从私钥可推导出公钥，但从公钥推导出私钥在计算上是不可行的。

公钥密码算法一般建立在公认的计算困难问题之上。这样的公钥密码具有可证明安全性，即如果所依赖的问题是困难的，那么所设计的算法就可证明是安全的。目前，公钥密码体制包括基于大整数因子分解困难性的RSA密码算法，基于离散对数问题困难性的密码算法（包括有限域上的离散对数问题，如ElGamal；椭圆曲线上的离散对数问题，如SM2），以及目前正在开展研究的后量子密码（如基于格的密码）。

1）公钥加密算法

由于公钥密码运算操作（如模幂、椭圆曲线点乘）计算复杂度较高，公钥加密算法的加密速度一般比对称加密算法的加密速度慢很多，因此公钥加密算法主要用于短数据的加密，如建立共享密钥。在执行公钥加密操作前，需要先查找接收者的公钥，然后用该公钥加密要保护的消息。当接收方接收到消息后，用自己的私钥解密出原消息。

2）数字签名算法

数字签名算法主要用于确认数据的完整性、签名者身份的真实性和签名行为的不可否认性等。与公钥加密算法使用公钥、私钥的顺序不同，数字签名使用私钥对消息进行签名，使用公钥对签名进行验证。

需要注意的是，为提升效率和安全性，数字签名算法中一般都需要先使用密码杂凑算法对原始消息进行杂凑运算，再对得到的消息摘要进行数字签名。

2．SM2椭圆曲线公钥密码算法

SM2椭圆曲线公钥密码算法（简称SM2算法）是基于椭圆曲线离散对数问题。由于基于椭圆曲线上离散对数问题的困难性要高于一般乘法群上的离散对数问题的困难性，且椭圆曲线所基于的域的运算位数要远小于传统离散对数的运算位数，因此，椭圆曲线密码体制比原有的密码体制（如RSA）更具优越性。

SM2算法于2010年年底由国家密码管理局发布，于2012年成为密码行业标准，于2016年转化为国家标准。SM2数字签名算法于2017年被ISO采纳，成为国际标准ISO/IEC 14888-3的一部分。SM2算法的国家标准包括以下五个部分：

• GB/T 32918.1-2016《信息安全技术SM2椭圆曲线公钥密码算法第1部分：总则》；

• GB/T 32918.2-2016《信息安全技术SM2椭圆曲线公钥密码算法第2部分：数字签名算法》；

• GB/T 32918.3-2016《信息安全技术SM2椭圆曲线公钥密码算法第3部分：密钥交换协议》；

• GB/T 32918.4-2016《信息安全技术SM2椭圆曲线公钥密码算法第4部分：公钥加密算法》；

• GB/T 32918.5-2017《信息安全技术SM2椭圆曲线公钥密码算法第5部分：参数定义》。

1）椭圆曲线密码基础知识

密码学家Neal Koblitz和Victor Miller在1985年分别提出了椭圆曲线密码学（Elliptic Curve Cryptography，ECC）的思想，使其成为构造公钥密码体制的一个有力工具。

椭圆曲线并不是椭圆，之所以称为椭圆曲线是因为它们是用三次方程来表示的，且该方程与计算椭圆周长的方程相似。椭圆曲线可以定义在不同的有限域上，常用的是定义在素域GF（p）上的椭圆曲线和定义在扩域或二元扩域GF（2m）（m是一个正整数）上的椭圆曲线，我国的公钥密码算法标准SM2算法的推荐参数是定义在256比特素域上的。

椭圆曲线上的两个基本运算是点加和倍点，它们用来构造点乘（标量乘）算法。点乘运算是椭圆曲线机制最核心，也是最耗时的运算。ECC的数字签名、加密、密钥交换算法都要求计算椭圆曲线点乘运算，其计算效率直接决定着签名/验证、加/解密运算的速度。

2）SM2算法介绍

SM2算法主要包括数字签名算法、密钥交换协议和公钥加密算法三个部分。在使用SM2算法之前，各通信方先设定相同的公开参数，包括p、n、E和G，其中p是大素数，E是定义在有限域GF（p）上的椭圆曲线，G=（xG，yG）是E上n阶的基点。下面主要对SM2的数字签名算法、密钥交换协议和公钥加密算法进行介绍。

（1）SM2数字签名算法。

在执行签名的生成过程之前，要用密码杂凑函数对用户的可辨别标识、部分椭圆曲线系统参数和用户的公钥杂凑值以及待签名消息进行压缩；在验证过程之前，要用密码杂凑函数对用户的可辨别标识、部分椭圆曲线系统参数和用户的公钥杂凑值及待验证消息进行压缩。

GB/T 32918.2-2016规定了SM2数字签名算法，包括数字签名生成算法和验证算法，并给出了数字签名与验证示例及相应的流程，可以满足多种密码应用中的身份鉴别和数据完整性、信息来源真实性的安全需求。密钥生成、签名生成及验证过程简述如下：

①密钥生成。

a）随机产生一个秘密变量d，。

b）计算P=dG，并将P作为公钥公开，d作为私钥保存。

②签名生成。

a）签名者选取随机数，计算kG=（x1，y1）。

b）计算r=（H（M）+x1）mod n，其中M=ZA||m，ZA是关于用户的可辨别标识、部分椭圆曲线系统参数和用户的公钥杂凑值，m是待签名消息；H为国家密码管理局核准的杂凑函数，如SM3；若r=0或r+k=n，则重新选取随机数k。

c）计算s=（1+d）-1（k-rd）mod n；若s=0，则重新选取随机数k，否则，将（r，s）作为签名结果。

③签名验证。

a）验证者接收到M和（r，s）后，先检查且；然后计算。

b）计算；判断r′与r是否相等，若相等则签名验证通过，否则，验证失败。

（2）SM2密钥交换协议。

密钥交换，又称密钥协商，是两个用户A和B通过交互的信息传递，用各自的私钥和对方的公钥来商定一个只有他们知道的秘密密钥。这个共享的秘密密钥通常用在对称密码算法中。

GB/T 32918.4-2016规定了SM2密钥交换协议，并给出了密钥交换与验证示例及相应的流程，可满足通信双方经过两次或可选三次信息传递过程，计算获取一个由双方共同决定的共享秘密密钥（会话密钥）。

P A、PB和dA、dB分别表示用户A、B的公钥、私钥，ZA和ZB分别表示A、B的唯一标识，||表示数据拼接，&表示两个整数的按比特与运算，KDF（ks，klen）是密钥派生函数：以ks为种子、产生klen比特的伪随机序列，记w为大于或等于（log2n+1）/2的最小整数。

用户A：

（A.1）选取随机数，计算RA=rAG=（x2，y2）并发送给用户B。

用户B：

（B. 1）选取随机数，计算RB=rBG=（x3，y3）并发送给用户A。

（B. 2）计算xB=2w+（x3&（2w-1））和tB=（dB+xBrB）mod n。

（B.3）验证接收到的RA是椭圆曲线E上的点，验证通过后计算xA=2w+（x2&（2w-1））。

（B. 4）计算V=tB（PA+xARA）=（xV，yV）；若V是椭圆曲线E上的无穷远点，则重新选取rB、重新协商。

（B. 5）计算KB=KDF（xV||yV||ZA||ZB，klen）。

用户A：

（A.2）计算xA=2w+（x2&（2w-1））和tA=（dA+xArA）mod n。

（A.3）验证接收到的RB是椭圆曲线上的点，验证通过后计算xB=2w+（x3&（2w-1））。

（A.4）计算U=tA（PB+xBRB）=（xU，yU）；若U是椭圆曲线E上的无穷远点，则重新选取rA、重新协商。

（A.5）计算KA=KDF（xU||yU||ZA||ZB，klen）。

通过以上协商，A、B双方协商出共享密钥KA=KB。作为一个可选项，双方在密钥协商完毕后还可以进行密钥确认，即确认二者协商到的密钥是一致的。

（3）SM2公钥加密算法。

GB/T 32918.3-2016规定了SM2公钥加密算法，并给出了消息加密和解密示例以及相应的流程。

下述SM2公钥加密算法中，M是比特长度为mlen的明文。

①加密算法。

• 选取随机数，分别计算C1=lG=（x4，y4）和lP=（x5，y5）；

• 计算e=KDF（x5||y5，mlen）；

• 计算C2=M⊕e和C3=H（x5||M||y5）；

• 输出密文C=C1||C3||C2。

②解密算法。

• 验证C1是否在椭圆曲线上，计算dC1=（x5，y5）；

• 计算e=KDF（x5||y5，mlen）；

• 计算M=C2⊕e；

• 计算，并验证是否成立，若不成立则报错退出；

• 输出明文M。

3）SM2算法的安全性和效率

以SM2公钥加密算法为例，它的安全性主要体现在三个方面：①算法具备单向性，即未授权的第三方在未得到私钥的情况下，从密文计算出明文在计算上是不可行的；②算法产生的明文和密文具备不可区分性，即恶意第三方对于给定的密文无法区分出其是由给定的两个明文中的哪一个加密而来；③密文具备不可延展性，即第三方无法在不解密密文的前提下，通过简单扩展密文来构造出新的合法密文。

与RSA算法相比，SM2算法具有以下优势：

①安全性高。256比特的SM2算法密码强度已超过RSA-2048（私钥长度为2048比特的RSA算法），与RSA-3072相当。

②密钥短。SM2算法使用的私钥长度为256比特，而RSA算法通常至少需要2048比特，甚至更长（如3072比特）。

③私钥产生简单。RSA私钥产生时需要用到两个随机产生的大素数，除了需要保证随机性外，还需要用到素数判定算法，产生过程复杂且速度较慢；而SM2私钥的产生只需要生成一个一定范围内的256比特的随机数即可，因此产生过程简单，存在的安全风险也相对较小。

④签名速度快。同等安全强度下，SM2算法在用私钥签名时，速度远超RSA算法。

4）SM2算法的使用

为规范SM2算法的使用，2012年我国发布了GM/T 0009-2012《SM2密码算法使用规范》和GM/T 0010-2012《SM2密码算法加密签名消息语法规范》，2017年发布更新版本国家标准GB/T 35276-2017《信息安全技术SM2密码算法使用规范》和国家标准GB/T 35275-2017《信息安全技术SM2密码算法加密签名消息语法规范》。这些标准为SM2密码算法的使用制定了统一的数据格式和使用方法。

GM/T 0009-2012定义了SM2算法的密钥数据格式、加密数据格式、签名数据格式和密钥对保护数据格式，并对生成密钥、加密、解密、数字签名、签名验证、密钥协商等计算过程进行了规范。GM/T 0010-2012定义了使用SM2密码算法的加密签名消息语法。

3．SM9标识密码算法

标识密码（Identity-Based Cryptography，IBC）是在传统的公钥基础设施（Public Key Infrastructure，PKI）基础上发展而来的，除了具有PKI的技术优点外，主要解决了在具体安全应用中PKI需要大量交换数字证书的问题，使安全应用更加易于部署和使用。IBC使用的是公钥密码体制，加密与解密使用两套不同的密钥，每个人的公钥就是他的身份标识，如E-mail地址，因此IBC中的密钥管理相对简单。

密码学家Shamir在1984年提出了IBC的概念。在标识密码系统中，用户的私钥由密钥生成中心根据主密钥和用户标识计算得出，用户的公钥由用户标识唯一确定，用户不需要通过第三方保证其公钥来源的真实性。与基于证书的公钥密码系统相比，标识密码系统中的密钥管理环节可以得到适当简化。由于标识密码系统的密钥生成中心可计算出用户私钥，因此需要保证密钥生成中心是完全值得信任的。

1999年，Negishi、Sakai和Kasahara等人提出了用椭圆曲线对构造基于标识的密钥共享方案。2001年，Boneh和Franklin及Sakai、Ohgishi和Kasahara等人独立提出了用椭圆曲线对构造的标识公钥加密算法。这些工作引发了标识密码的新发展，出现了一批用椭圆曲线对实现的标识密码算法，其中包括数字签名算法、密钥交换协议、密钥封装机制和公钥加密算法等。

2016年，我国发布了标识密码算法标准GM/T 0044-2016《SM9标识密码算法》。同SM2数字签名算法一起，SM9数字签名算法也在2017年被ISO采纳，成为国际标准ISO/IEC 14888-3的一部分。

1）SM9算法介绍

SM9密码算法标准共分为5个部分，分别为：

• GM/T 0044.1-2016《SM9标识密码算法第1部分：总则》；

• GM/T 0044.2-2016《SM9标识密码算法第2部分：数字签名算法》；

• GM/T 0044.3-2016《SM9标识密码算法第3部分：密钥交换协议》；

• GM/T 0044.4-2016《SM9标识密码算法第4部分：密钥封装机制和公钥加密算法》；

• GM/T 0044.5-2016《SM9标识密码算法第5部分：参数定义》。

（1）SM9算法采用的基本技术。

SM9密码算法涉及有限域和椭圆曲线、双线性对及安全曲线、椭圆曲线上双线性对的运算等基本知识和技术。SM9密码算法的应用与管理不需要数字证书、证书库或密钥库。

（2）SM9数字签名算法。

用椭圆曲线对实现的基于标识的数字签名算法包括数字签名生成算法和验证算法。签名者持有一个标识和一个相应的私钥，该私钥由密钥生成中心通过主私钥和签名者的标识结合产生。签名者用自身私钥对数据产生数字签名，验证者用签名者的标识生成其公钥，验证签名的可靠性，即验证发送数据的完整性、来源的真实性和数据发送者的身份。

（3）SM9密钥交换协议。

该协议可以使通信双方通过对方的标识和自身的私钥经两次或可选三次信息传递过程，计算获取一个由双方共同决定的共享秘密密钥。该秘密密钥可作为对称密码算法的会话密钥，协议中可以实现密钥确认。

参与密钥交换的发起方用户A和响应方用户B各自持有一个标识和一个相应的私钥，私钥均由密钥生成中心通过主私钥和用户的标识结合产生。用户A和用户B通过交互的信息传递，用标识和各自的私钥来商定一个只有他们知道的秘密密钥，用户双方可以通过可选项实现密钥确认。这个共享的秘密密钥通常用在某个对称密码算法中。

（4）SM9密码密钥封装机制和加密算法。

密钥封装机制使得封装者可以产生和加密一个秘密密钥给目标用户，而唯有目标用户可以解封装该秘密密钥，并把它作为进一步的会话密钥。用椭圆曲线对实现基于标识的密钥封装机制，封装者利用解封装用户的标识产生并加密一个秘密密钥给对方，解封装用户则用相应的私钥解封装该秘密密钥。用椭圆曲线对实现的基于标识的加密与解密算法，使消息发送者可以利用接收者的标识对消息进行加密，唯有接收者可以用相应的私钥对该密文进行解密，从而获取消息。

（5）SM9密码算法参数定义。

SM9密码算法使用256比特的Barreto-Naehrig（BN）曲线。该算法标准的第5部分定义了曲线参数，并给出了数字签名算法、密钥交换协议、密钥封装机制、公钥加密算法示例。

2）SM9算法的安全性和效率

目前，没有发现明显影响双线性对密码系统应用的安全性风险。SM9密码算法能够避免弱椭圆曲线的选取问题，并抵抗常见的针对椭圆曲线的攻击方式，安全性远远高于同类算法。例如，SM9采用256比特素域上的椭圆曲线时，离散对数的复杂性约为2128次基本运算，理论上是同类椭圆曲线算法的272倍，破解难度大大增加，即安全性大幅提高。

SM9的安全性也和嵌入次数有关，即嵌入次数越多安全性越高，双线性对的计算越困难。目前SM9采用了嵌入次数适中且达到安全性标准的椭圆曲线。

4．国外公钥密码算法RSA介绍

常见的国外公钥密码算法有RSA、椭圆曲线数字签名算法（Elliptic Curve Digital Signature Algorithm，ECDSA）等。下面重点对RSA进行介绍。

1）RSA算法简介

RSA算法基于大整数因子分解难题设计，因其原理清晰、结构简单，是第一个投入使用，也是迄今为止应用最广泛的公钥密码算法，可用于数字签名、安全认证等。1992年，RSA算法纳入了国际电信联盟制定的X.509系列标准。RSA算法的公钥相当于两个素数的乘积，而私钥则相当于两个独立的素数。

RSA算法加解密过程如下：

（1）密钥生成。

选取两个随机的大素数p和q，计算n=pq和φ（n）=（p-1）（q-1）；

选择随机数e，满足：e与φ（n）互素；

计算d=e-1mod φ（n）；

公开（n，e）作为公钥，保留（d，p，q）作为私钥。

（2）加密过程。

对于明文P，计算密文C=Pemod n。

（3）解密过程。

对于密文C，计算明文P=Cdmod n。

在实际使用中e的取值很小，有效长度不超过32比特，甚至在很多时候，e的值为65537（十六进制表示为0x10001）。而d的有效长度接近于n的有效长度。所以，RSA算法的加密（或签名验证）计算速度要比解密（或签名）计算速度快许多倍。

在实际应用RSA算法时，应确保两个素数是随机产生的，否则会导致安全风险。例如，如果计算两个不同的乘积n时用到了相同的素数，则通过计算公因子的方法就可以将n进行因子分解，从而破解算法。2013年2月，研究人员发现在700万个实验样本中有2.7万个公钥并不是按随机理论产生的，每1000个公钥中可能会有两个公钥存在安全隐患。

2）算法安全性和效率

需要注意的是，1024比特及以下密钥长度（n的长度）的RSA算法目前已经不推荐使用。在当前应用中，为保证安全，n应该至少选用2048比特，即选用RSA-2048算法。在效率方面，由于达到相当安全强度时，RSA密钥长度要远长于ECC算法（如SM2），因此私钥计算的执行效率（如计算数字签名）要比ECC算法慢数倍。

1.4.3 密码杂凑算法

密码杂凑算法也称作“散列算法”或“哈希算法”，现在的密码行业标准统称其为密码杂凑算法，简称“杂凑算法”或“杂凑函数”。密码杂凑算法对任意长度的消息进行压缩，输出定长的消息摘要或杂凑值，该过程表示为：

h=H（M）

式中，M是输入消息；h是经过杂凑算法H处理后的杂凑值，其长度通常是固定的，取决于所使用的杂凑算法。

一般来说，杂凑算法具有如下性质：

①抗原像攻击（单向性）。为一个给定的输出找出能映射到该输出的一个输入在计算上是困难的，即给定杂凑值h，找到消息M使得h=H（M）是困难的。杂凑函数是单向的，从消息计算杂凑值很容易，但从杂凑值推出消息是困难的。

②抗第二原像攻击（弱抗碰撞性）。为一个给定的输入找出能映射到同一个输出的另一个输入在计算上是困难的，即给定消息M1，找到另外一个消息M2使得H（M2）=H（M1）是困难的。输入的任何微小变化都会使杂凑结果有很大不同。

③强抗碰撞性。要发现不同的输入映射到同一输出在计算上是困难的，即找到两个消息M1，M2（M1不同于M2）使得H（M1）=H（M2）是困难的。

1．密码杂凑算法的结构

杂凑算法有多种构造方式，常用的是Merkle-Damgård结构（简称M-D结构）、海绵结构。MD5、SHA-1、SHA-2和我国的SM3都采用了M-D结构，SHA-3采用的是海绵结构。下面主要对M-D结构进行简要介绍。

M-D结构，先对经过填充后的消息进行均匀的分组，而后消息分组顺序进入压缩函数F，如图1-14所示。压缩函数F先由初始向量进行初始化，结合上一组消息的结果和本组消息产生一个中间值，最后一个压缩函数的结果即是最终的杂凑值。这样，很长的消息也很容易被压缩到一个固定的比特长度。它的安全性取决于压缩函数的安全性。研究表明，如果压缩函数具有抗碰撞能力，那么杂凑算法也具有抗碰撞能力（其逆不一定为真）。因此，要设计安全杂凑函数，最重要的是设计具有抗碰撞能力的压缩函数。

2．密码杂凑算法的应用

密码杂凑算法的直接应用就是产生消息摘要，进一步可以检验数据的完整性，被广泛应用于各种不同的安全应用和网络协议中。例如，用户收到消息后，计算其杂凑值，并与发送方提供的结果做比对，如果二者一致，则基本认为消息在传送过程中没有遭到篡改（由于“抗第二原像攻击”的性质）。需要注意的是，单独使用杂凑算法并不能保证数据的完整性，因为在传输信道不安全的情况下，攻击者可以将消息和杂凑值一同篡改，即在修改或替换消息后重新计算一个杂凑值。因此，用于完整性保护时，杂凑算法常常与密钥一同使用，生成的杂凑值称为MAC，这样的杂凑算法称为带密钥的杂凑算法（Keyed-hash Message Authentication Code，HMAC）。此外，杂凑算法也与公钥密码算法一同使用来产生数字签名。

3．SM3密码杂凑算法

我国商用密码标准中的密码杂凑算法是SM3算法。SM3于2012年发布为密码行业标准GM/T 0004-2012《SM3密码杂凑算法》，并于2016年转化为国家标准GB/T 32905-2016《信息安全技术SM3密码杂凑算法》。2018年10月，SM3算法正式成为国际标准。

1）SM3算法介绍

SM3算法采用M-D结构，输入消息（长度L＜264）经过填充、扩展、迭代压缩后，生成长度为256比特的杂凑值。SM3算法的实现过程主要包括填充分组和迭代压缩等步骤。

（1）填充分组。

填充分组是将任意长度的输入消息在尾部按一定规则填补至512比特的整数倍长度，再将填充好的输入串按512比特长度分为若干组的过程。

对于输入长度为L的消息，首先在消息末尾填充比特“1”，然后填充k个“0”，k是使得L+k+1=448mod 512的最小非负整数，最后填充64比特的二进制串，该二进制串为长度L的二进制表示。

例如，对于长度L=24的输入01100001 01100010 01100011，填充结果如图1-15所示。

将填充完成后的消息输入消息分成n个长度为512比特的分组：B0，B1，…，Bn-1，其中n=（L+k+65）/512。

（2）消息扩展。

每个512比特的输入消息分组在迭代压缩输入压缩函数前，需先进行消息扩展，生成的132个消息字W0，W1，…，W67和作为压缩函数的输入。其中W0，W1，…，W15就是输入的消息分组，其余扩展的消息字表达式为：

式中，<<<表示循环左移；P1是消息扩展中的置换函数，表达式为：

（3）迭代过程。

令压缩函数为CF，每一次迭代过程的输入由一个512比特的输入消息分组和上一次迭代过程的256比特输出组成，每一次迭代过程的输出长度为256比特。执行一次SM3算法，需要进行n次迭代，迭代过程为Vi+1=CF（Bi，Vi），0≤i≤n-1，其中，初始迭代值V0是规定的256比特的常量IV。当全部n个消息输入分组都经过迭代压缩后，所得到的Vn就是SM3杂凑算法输出的256比特杂凑值。

（4）压缩函数。

SM3算法中的单次迭代压缩过程如图1-16所示，令A、B、C、D、E、F、G、H为32比特变量寄存器，SS1、SS2、TT1、TT2为中间变量。单次迭代过程包含64轮迭代的压缩，函数CF执行过程如下：

其中，FFj、GGj是布尔函数，Tj表示每轮的常数，P0是压缩函数中的置换函数，这些函数的表达式分别为：

式中，∧、∨、分别表示按位的与、或、非运算。

2）SM3算法的安全性和效率

SM3算法在M-D结构的基础上，新增了16步全异或操作、消息双字介入、加速雪崩效应的P置换等多种设计技术，能够有效避免高概率的局部碰撞，有效抵抗强碰撞性的差分分析、弱碰撞性的线性分析和比特追踪等密码分析方法。公开文献表明，SM3算法能够抵抗目前已知的攻击方法，具有较高的安全冗余。在实现上，SM3算法运算速率高，灵活易用，支持跨平台的高效实现，具有较好的实现效能。

SM3算法在结构上和SHA-256相似，消息分组大小、迭代轮数、输出长度均与SHA-256相同。但相比于SHA-256，SM3算法增加了多种新的设计技术，从而在安全性和效率上具有优势。在保障安全性的前提下，SM3算法的综合性能指标与SHA-256在同等条件下相当。

3)HMAC

HMAC是利用杂凑算法，将一个密钥和一个消息作为输入，生成一个消息摘要作为输出。HMAC可用作数据完整性检验，检验数据是否被非授权修改；也可用作消息鉴别，保证消息源的真实性。例如，IPSec和SSL协议中均用到了HMAC，将其用于完整性校验和数据源身份鉴别。我国国家标准GB/T 15852.2-2012《信息技术安全技术消息鉴别码第2部分：采用专用杂凑函数的机制》对HMAC算法进行了规范。关于采用分组密码和泛杂凑函数的MAC产生机制分别见GB/T 15852.1-2008和GB/T 15852.3-2019。

HMAC计算时调用了两次完整的杂凑函数H，对于密钥K、消息D，计算公式如下：

其中，m表示MAC长度，应是一个正整数且不大于杂凑值的比特长度；函数MSBm（X）表示取比特串X最左边m比特。密钥K的长度为k：为消息分组比特长度，L2为杂凑值的比特长度。对于SM3，L1=512，L2=256。

在HMAC计算过程中，首先对密钥进行填充，在密钥K的右侧填充L1-k个0，所得的长度为L1的比特串为。将十六进制的值“36”（二进制表示为“00110110”）重复L1/8次连接起来，所得的比特串记作IPAD，然后将和比特串IPAD相异或，将异或值和待杂凑的消息D相连接，并将连接后的值进行第一次杂凑运算。将十六进制的值“5C”（二进制表示为“01011100”）重复L1/8次连接起来，所得比特串记作OPAD，然后将和比特串OPAD相异或，将异或值与第一次杂凑值相连接，并将连接后的值作为第二次杂凑运算的输入。取第二次杂凑运算输出的最左边m比特，作为HMAC的输出。

4．国外杂凑算法介绍

常见的国外杂凑算法有MD5密码杂凑算法和安全杂凑算法（Secure Hash Algorithm，SHA）系列算法。SHA系列算法主要包括SHA-0、SHA-1、SHA-2和SHA-3。

MD5算法：MD5是由麻省理工学院计算机科学实验室的Rivest提出的，其前身有MD2、MD4等密码算法。MD5算法可用于数字签名、完整性保护、安全认证、口令保护等。MD5算法首先将输入的信息划分成若干个512比特的分组，再将每个分组划分成16个32比特的子分组，经一系列变换后，最终输出128比特的消息摘要。根据王小云教授提出的分析方法，2005年国际密码学家给出了MD5算法的碰撞实例，后来又成功伪造了SSL数字证书。目前，一部智能手机仅用30秒就可以找到MD5算法的碰撞。这些研究成果的碰撞案例表明MD5算法已不再适合实际应用。

SHA-1算法：SHA-1算法是1995年由美国国家安全局（NSA）和NIST提出的标准算法。SHA-1设计思想基于MD4算法，在很多方面也与MD5算法有相似之处，其输入长度应小于264比特，消息摘要长度为160比特。2005年，我国王小云教授首次给出了SHA-1的碰撞攻击，复杂度为269次运算。2017年2月，荷兰计算机科学与数学研究中心和谷歌研究人员合作找到了世界首例针对SHA-1算法的碰撞实例，生成了两个SHA-1算法消息摘要完全相同但内容截然不同的文件，针对SHA-1算法的攻击从理论变为现实，继续使用SHA-1算法存在重大安全风险，这标志着SHA-1算法继MD5算法后也将退出历史舞台。2017年4月，国家密码管理局发布了使用SHA-1密码算法的风险警示，要求相关单位遵循密码国家标准和行业标准，全面支持和应用SM3等密码算法。

SHA-2算法：SHA-2算法是由NSA和NIST于2001年提出的标准算法。SHA-2算法虽然也是基于M-D结构，但是增加了很多重大变化以提升安全性。SHA-2算法支持224、256、384和512比特四种长度的输出，包含6个算法：SHA-224、SHA-256、SHA-384、SHA-512、SHA-512/224、SHA-512/256。其 中，SHA-256和SHA-512是主要算法，其他算法都是在这两者基础上输入不同初始值，并对输出进行截断。目前没有发现对SHA-2算法的有效攻击。

SHA-3算法：与MD5、SHA-1、SHA-2算法等采用经典M-D结构不同，SHA-3算法在设计上采用了新的结构——“海绵”结构。与SHA-2算法类似，SHA-3算法也包含多个算法：SHA3-224、SHA3-256、SHA3-384、SHA3-512、SHAKE128、SHAKE256。

1.4.4 密码算法分析概要

现代密码学有一个著名的假设，称为柯克霍夫斯（Kerckhoffs）原则：评估一个密码算法安全性时，必须假定攻击者不知道密钥，但知道密码算法的所有细节。基于此准则，密码算法的安全性应该基于密钥的保密（即密钥不被攻击者所知），而不是所用算法的隐蔽性。

密码算法分析的目的是通过各种攻击方式，找到密码算法的弱点或者不完美的地方。密码分析和密码编码是对立统一、互不可缺的两个方面。密码编码为密码分析提供对象，并且以抵抗现有的分析方法为设计目标；密码分析为密码编码提供表示安全强度的具体数据，同时促进密码编码不断发展。

1．基本概念

以加密算法为例，按照攻击者获取信息的能力，可以将密码分析划分为唯密文攻击、已知明文攻击、选择明文攻击和选择密文攻击四种方式。

（1）唯密文攻击。攻击者只能获得密文的信息。这是在公开的网络中能获得的最现实的能力。

（2）已知明文攻击。攻击者拥有某些密文以及相应的明文。例如，假设攻击者截获了一份加密的通信稿，并在第二天看到了解密后的通信稿。对许多弱密码系统来说，知道一些明密文对就足以找到密钥了。即使是对于第二次世界大战中使用的恩尼格玛密码机这样比较强的密码系统，这种信息对破译恩尼格玛密码机也起到了很大的作用。

（3）选择明文攻击。攻击者有接触加密机器的机会，不能打开机器找到密钥，但可以加密大量经过精心挑选的明文，然后利用所得的密文推断密钥的信息或试图对其他密文进行解密。

（4）选择密文攻击。攻击者有接触解密机器的机会，对选择的密文进行解密操作，然后试着用所得结果推断密钥或试图对其他密文进行解密。

2．对称密码的分析

自20世纪80年代差分攻击技术提出以来，差分类攻击和线性类攻击便成为分析对称密码最有效的分析方法。基于差分攻击演化出一系列密码分析方法，包括相关密钥差分攻击、截断差分攻击、统计饱和攻击、不可能差分攻击、高阶差分攻击、飞去来器攻击、多差分分析和线性差分分析、多线性分析和线性区分攻击等。以分组密码分析为例，攻击者一般是先构造一个区分器，将分组密码和随机置换区分开，然后利用这一区分器，进行密钥恢复攻击。通常对于全轮的分组密码算法，有效的攻击方法是几乎不可能的，一般从分析低轮的算法入手，一步步向全轮算法逼近。针对流密码的攻击包括相关攻击、猜测确定攻击等。

3．公钥密码的分析

公钥密码的设计一般依赖于计算困难的数学问题。这些问题包括大整数因子分解、离散对数、格中向量问题、子集和问题、线性纠错码译码、多变量多项式方程组求解、组合群论及椭圆曲线上的双线性Diffie-Hellman问题等。在现实世界中，这些问题被证明或公认是实际难解的，它们可以提供正确设计的公钥密码系统理论上的安全性。公钥密码的设计一般都可以做到可证明安全，即证明了如果底层的数学问题是困难的，上层的公钥密码方案也是安全的。因此，对公钥密码分析多集中于对底层困难问题的分析，以及上层方案实际安全性的分析。

格理论和算法在密码学领域有着广泛的应用，在公钥密码分析领域也是一种很强大的工具。LLL算法等格基约化算法的提出，极大推动了对公钥密码算法的分析，特别是对RSA、DSA/ECDSA等算法的分析。

4．杂凑函数的分析

杂凑函数和分组密码的分析方法在很多时候都是相通的，分析杂凑函数经常用到的攻击方法主要包括差分攻击、模差分攻击、中间相遇攻击等，都是围绕杂凑函数的三个性质开展的。

5．侧信道分析

上述对密码算法的分析都是基于数学理论的分析方法，其特点是假定密码算法在一个封闭、可信的计算环境里运行，攻击者既不能观察运算过程中的内部状态也不能修改或干扰它。除此之外，有针对密码的实现方式和应用方式提出的侧信道分析，这种分析是基于物理实现的分析方法。在实际应用中，密码系统会通过物理装置泄露一些信息，如能量消耗、电磁辐射、运行时间等。由于无须实施入侵或破解密码算法就可以分析获得密钥等敏感数据，侧信道分析对密码算法实现的实际安全构成了巨大威胁，密码实现的抵抗侧信道分析能力也成为密码产品检测中重要的考量指标。