2.3 公钥加密算法_商用密码权威指南：技术详解、产品开发与工程实践-QQ阅读中文短篇网

上QQ阅读APP看本书，新人免费读10天

设备和账号都新为新人

2.3 公钥加密算法

2.3.1 公钥加密算法介绍

在对称密码体制中，通信双方需共享同一个秘密密钥，该密钥既用于加密也用于解密通信内容。然而，随着系统中用户数量增多，密钥管理将变得较为复杂。例如，在有n个用户的系统中，若每对用户之间都需要加密通信，则针对每个用户需存储n-1个不同的密钥，系统中的密钥总数将达到n（n-1）/2。

与之不同，公钥加密体制最大的特点是采用两个相互关联的密钥，将加密与解密分开，其中一个密钥是公开的，被称为“公开密钥或公钥”，用于加密，另外一个密钥为用户专有，是保密的，被称为“秘密密钥或私钥”，用于解密。当系统中有n个用户时，只需每个用户各自拥有自己的公私钥对，并公开自己的公钥，即可实现两两之间的加密通信（见图2-21）。例如，当用户1需要将消息m加密发送给用户t时，用户1使用用户t的公钥Pub_t对消息m加密得密文，然后将密文c发送给用户t。用户t收到密文c后，使用自己的私钥sk_t解密得到明文，从而实现用户1与用户t之间的加密通信。

图2-21 多用户公钥加密通信示意图

公钥加密体制降低了密钥管理的复杂度，每个用户只需维护自己的公私钥对。因为公钥是公开的，所以任何人都能用它来加密信息并发送给持有私钥的用户，实现安全的加密通信。公钥加密体制为密钥分发和管理提供了更大的便利性。

公钥加密体制需满足以下要求。

1）产生一对公私钥对在计算上是可行的；

2）使用公钥对明文加密在计算上是可行的；

3）使用私钥对密文解密在计算上是可行的；

4）由公钥计算私钥在计算上是不可行的；

5）由密文和公钥恢复明文在计算上是不可行的；

6）加密与解密次序可交换（可选的）。

公钥加密体制常基于数学困难问题设计，如整数分解、离散对数问题等。公钥加密体制的安全强度依赖于这些数学困难问题的求解难度。尽管公钥加密体制提供了更灵活的密钥管理方式，但公钥密码的加解密速度常常远低于对称密码体制的加解密速度。在实际应用中，通常将公钥密码与对称密码结合使用，如可以使用公钥密码加密传输用于对称加解密的密钥，然后使用对称密码算法实现大量数据的加密传输。

2.3.2 公钥密码的设计原理

公钥密码体制的安全性主要依赖加密函数的单向性，即计算该函数的值是容易的，而对于求给定值的原像是困难的。

设f（x）是定义域A到值域B的函数，如果已知x∈A，计算f（x）的值是容易的，而给定y∈B，计算x∈A使得f（x）=y是困难的，则称f（x）为单向函数。计算容易与计算困难指根据当前的计算能力，若在输入值的多项式时间内可计算，则为计算容易；若未找到有效算法在输入长度多项式时间内完成计算，则为计算困难。

对于单向函数，若存在陷门信息，使不知道陷门信息时求逆是困难的，而知道陷门时求逆是容易的，则称该单向函数为“单向陷门函数”。如果一个函数是单向陷门函数，我们可以使用陷门信息作为解密密钥，而求函数值的算法作为加密算法，从而构造一个公钥密码算法。

公钥密码的安全性早期主要考虑单向性，即由密文求取明文或由公钥求私钥，后来随着密码学中安全理论研究的深入，公钥密码的安全性理论不断成熟，产生了语义安全和密文不可区分等安全概念和形式化定义。语义安全是香农保密思想在计算安全模型下的类比，指在有限计算能力下由密文得不到明文的任何信息。密文不可区分指攻击者在给定两个密文和其中任意某个密文的条件下，无法区分哪个密文是该明文的密文。语义安全的概念无法用于安全性论证。理论研究证明，在比较强的攻击能力（即适应性选择密文攻击）条件下，语义安全和密文不可区分是等价的。因此，在适应性选择密文攻击下，密文不可区分成为公钥密码的标准定义。

2.3.3 常见的公钥加密算法

1.RSA

RSA算法是由Ron Rivest、Adi Shamir和Leonard Adleman于1977年在MIT一起提出的。RSA算法是最早公开的公钥密码体系之一，也是目前使用最广泛的公钥算法之一。RSA算法的安全性基于大整数分解困难问题。

RSA算法具体过程如下。

（1）用户B的公私钥对生成

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

2）随机选取e，满足1<e<φ（n），gcd（e，φ（n））=1；

3）利用扩展欧几里得算法计算e模φ（n）的逆元d，即寻找d，使其满足ed≡1 modφ（n），1<d<φ（n）；

4）公钥为（n，e），私钥为（n，d）。

（2）加密

假设用户A要向用户B发送消息m，其中，0≤m<n（若消息m不在该范围内，可将其分成几部分后发送），则用户A使用用户B的公钥（n，e）对该消息的加密过程为：

c=m^emod n

并将密文c发送给用户B。

（3）解密

当用户B收到密文c后，用自身私钥（n，d）对其解密，解密过程如下：

m′=c^dmod n

易知，m′=c^dmod n=m^edmod n=m^ed^modφ（ⁿ^）mod n=m，从而可以解密得用户A所发送的消息。注：解密过程的正确性利用了费马小定理，即对任意正整数a、n，有a^φ（ⁿ^）=1 mod n。

在RSA算法公私钥对生成时，我们可利用扩展欧几里得算法求元素的逆元。设a、b为两个正整数，则存在整数u、v满足gcd（a，b）=ua+vb。我们使用扩展欧几里得算法求整数u、v，不妨设a≥b，首先使用带余除法得以下关系：

易知gcd（a，b）=gcd（b，r₁）=gcd（r₁，r₂）=…=gcd（r_n_-1，r_n）=r_n

则可得gcd（a，b）=r_n

=-q_nr_n_-1+r_n_-2，记f_n_-1=-q_n，g_n_-2=1

=f_n_-1（-q_n_-1r_n_-2+r_n_-3）+g_n_-2r_n_-2，记f_n_-2=-q_n_-1f_n_-1+g_n_-2，g_n_-3=f_n_-1

=…

=f₂r₂+g₁r₁

=f₂（b-q₂r₁）+g₁r₁=（-q₂f₂+g₁）r₁+f₂b，记f₁=-q₂f₂+g₁，g₀=f₂

=f₁（a-bq₁）+g₀b

=f₁a+（g₀-f₁q₁）b

因此，我们可得u=f₁，v=g₀-f₁q₁，其中，f_i_-2=-q_i_-1f_i_-1+g_i_-2，g_i_-3=f_i_-1，i=3，4，…，n，且f_n_-1=-q_n，g_n_-2=1。

当gcd（a，b）=1时，我们可以使用上述方式找到u、v满足ua+vb=gcd（a，b）=1，从而得到a的逆元u≡a^-1mod b。

RSA算法的安全性基于两个数学问题：

• 在已知n的情况下，寻找p和q的因子分解。

• 在已知n和e的情况下，计算d的离散对数。

由于这两个问题的计算复杂度随着p和q的增大呈指数级增加，因此选择足够大的p和q会使得问题变得在计算上不可解决。

随着技术的发展，如量子计算的进步，Shor量子算法可在多项式时间内分解大整数，RSA算法的安全受到严重威胁。因此，我们需关注新技术的发展对算法安全的影响，并随时调整算法的应用场景。

RSA算法的应用广泛，具体如下。

• 安全通信：用于加密和解密敏感数据的传输。

• 数字签名：用于验证数据的完整性和用户身份。

• 证书签发：用于生成和验证数字证书。

• 安全协议：在TLS/SSL等协议中用于密钥交换和加密。

• 数字货币：在加密货币中用于生成密钥对和数字签名等。

2.ElGamal

ElGamal加密算法由Taher Elgamal于1985年提出，其安全性基于有限域上的离散对数困难问题。给定n阶有限群G及其生成元g，离散对数困难问题指：对任意给定元素y∈G，寻找整数a使得y=g^a是计算困难的；而对任意给定的G中元素h及整数x，0≤x≤n，计算h^x是容易的。

在ElGamal算法中，加密运算是随机的，每次加密均需要选取一个随机数，因此，对同一个明文加密所得密文存在多种不同可能。ElGamal算法具体过程如下。

（1）用户B的公私钥对生成

1）生成阶为q的循环群G，设g为G的生成元，使得循环群G上的离散对数问题是困难的；

2）选择随机数x∈{1，2，…，q-1}；

3）计算h=g^x；

4）公钥为（G，q，g，h），私钥为x。

（2）加密

假设用户A使用公钥（G，q，g，h）加密消息m发送给用户B，不妨设m∈G，若m∉G，则双方约定将消息通过可逆映射将其映射到G中元素的方法。下面我们只考虑m∈G情况。加密过程如下。

生成随机数y∈{1，2，…，q-1}，具体为

a）计算s=h^y；

b）计算c₁=g^y；

c）计算c₂=m·s；

d）将密文（c₁，c₂）发送给用户B。

（3）解密

假设用户B收到密文（c₁，c₂），使用私钥x解密：

1）计算；

2）计算m′=c₂·s′^-1。

易知，，从而用户B可以解密出用户A所发送的消息。

ElGamal算法的安全性基于离散对数问题的困难性。对于离散对数问题，目前已知最好的求解算法是数域筛法，给定长度为n的模数，求解复杂度约为O（2ⁿ^/2）。若使用ElGamal算法每次加密均选择新的随机数，则ElGamal算法被认为是选择明文攻击安全的。单纯的ElGamal加密算法易受选择密文攻击，但可以通过使用适当的填充方案或结合其他密码技术加以改进。与RSA算法基于的证书分解问题类似，Shor量子算法也能在多项式时间内求解离散对数问题，因此，我们可关注量子计算技术的研究进展，评估其对ElGamal算法的安全影响。

3.SM2公钥加密算法

SM2是国家密码管理局于2010年12月17日发布的椭圆曲线公钥密码算法，并于2012年成为密码行业标准GM/T 0003《SM2椭圆曲线公钥密码算法》，2016年成为国家标准GB/T 32918《信息安全技术SM2椭圆曲线公钥密码算法》。SM2算法的安全性基于有限域上椭圆曲线群离散对数困难问题。

有限域F_p上的椭圆曲线方程为y²=x³+ax+b，a，b∈F_p，且（4a³+27b²）mod p≠0。椭圆曲线E（F_p）定义为满足椭圆曲线方程的所有点以及无穷远点构成的集合，即

E（F_p）={（x，y）|x，y∈F_p，y²=x³+ax+b）∪{O}

其中，O表示无穷远点。椭圆曲线E（F_p）上的点的数目用#E（F_p）表示，被称为“椭圆曲线E（F_p）的阶”。

给定椭圆曲线E（F_p），定义椭圆曲线上的点的加法运算规则：

1）O+O=O；

2）∀P=（x，y）∈E（F_p）\{O}，P+O=O+P=P；

3）∀P=（x，y）∈E（F_p）\{O}，P的逆元-P=（x，-y），P+（-P）=O；

4）两个非互逆的不同点的加法运算规则如下：

a）设P₁=（x₁，y₁）∈E（F_p）\{O}，P₂=（x₂，y₂）∈E（F_p）\{O}，且x₁≠x₂；

b）设P₃=（x₃，y₃）=P₁+P₂，则

其中，。

5）两个相同点的加法运算（倍点运算）规则如下：

a）设P₁=（x₁，y₁）∈E（F_p）\{O}，且y₁≠0；

b）设P₃=（x₃，y₃）=P₁+P₁，则

其中，。

椭圆曲线上同一个点的多次加被称为“该点的多倍点运算”。设k为一正整数，P为椭圆曲线上的点，称点P的k次加为点P的k倍点运算，记为。

椭圆曲线E（F_p）关于上述点的加法运算构成加法群。椭圆曲线离散对数问题指：给定椭圆曲线群（E（F_p），+）及阶为n的点G，对任意点，确定整数l∈[0，n-1]使得Q=[l]G成立。其中，表示由点G生成的n阶循环群。

SM2公钥加密算法所使用的椭圆曲线参数包括有限域F_p，曲线方程y²=x³+ax+b中的两个参数a、b，E（F_p）上的基点G=（x_G，y_G），G的阶n。参数具体取值如下：

p=FFFFFFFE FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF 00000000 FFFFFFFF FFFFFFFF

a=FFFFFFFE FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF 00000000 FFFFFFFF FFFFFFFC

b=28E9FA9E 9D9F5E34 4D5A9E4B CF6509A7 F39789F5 15AB8F92 DDBCBD41 4D940E93

n=FFFFFFFE FFFFFFFF FFFFFFFF FFFFFFFF 7203DF6B 21C6052B 53BBF409 39D54123

x_G=32C4AE2C 1F198119 5F990446 6A39C994 8FE30BBF F2660BE1 715A4589 334C74C7

y_G=BC3736A2 F4F6779C 59BDCEE3 6B692153 D0A9877C C62A4740 02DF32E5 2139F0A0

SM2公钥加密算法过程如下。

（1）用户B的公私钥对生成

1）用随机数发生器生成整数d_B∈[1，n-2]；

2）计算点P_B=[d_B]G；

3）公钥为P_B，私钥为d_B。

（2）加密

假设用户A需要向用户B发送的消息为比特串M，klen为M的比特长度，使用公钥P_B加密消息M的过程如下。

1）用随机数发生器产生随机数k∈[1，n-1]；

2）计算椭圆曲线点C₁=[k]G=（x₁，y₁），将C₁的数据类型转换为比特串；

3）计算椭圆曲线点S=[h]P_B，若S是无穷远点，则报错并退出；

4）计算椭圆曲线点[k]P_B=（x₂，y₂），将坐标（x₂，y₂）的数据类型转换为比特串；

5）计算t=KDF（x₂||y₂，klen），若t为全0比特串，则返回步骤1）；

6）计算C₂=M⊕t；

7）计算C₃=Hash（x₂‖M‖y₂）；

8）输出密文C=C₁‖C₂‖C₃。

（3）解密

假设用户B收到密文C=C₁‖C₂‖C₃，其中C₂的比特长度为klen，则使用私钥d_B的解密过程如下。

1）从C中取出比特串C₁，将C₁的数据类型转换为椭圆曲线上的点，验证C₁是否满足椭圆曲线方程，若不满足则报错并退出；

2）计算椭圆曲线点S=[h]C₁，若S是无穷远点，则报错并退出；

3）计算，将坐标的数据类型转换为比特串；

4）计算，若t为全0比特串，则报错并退出；

5）从C中取出比特串C₂，计算M′=C₂⊕t′；

6）计算，从C中取出比特串C₃，若u≠C₃，则报错并退出；

7）输出明文M′。

易知，，因此，t′=t，M′=C₂⊕t′=C₂⊕t=M，即用户B可以解密出用户A所发送的消息。

SM2加密算法中需使用随机数发生器生成随机数，随机数发生器需为国家密码管理局批准的随机数发生器。SM2加密算法还需要使用杂凑算法Hash计算消息指纹以抵抗攻击，并且需使用国家密码管理局批准的密码杂凑算法，如SM3密码杂凑算法。在SM2公钥加密算法中，使用密钥派生函数KDF生成消息长度klen等长的密钥流序列t，然后与明文异或实现对消息的加密或解密。设密码杂凑算法为H_v()，其输出杂凑值长度为v比特。如使用SM3算法，v=256，密钥派生函数KDF（Z，klen）计算过程如下。

1）输入：比特串Z，整数klen，klen<（2³²-1）v。

2）输出：长度为klen的密钥数据比特串K。

3）初始化一个32比特的计数器ct为0x00000001。

4）对i从1到[klen/v]：

a）计算Ha_i=H_v（Z‖ct）；

b）ct++。

5）若klen/v是整数，令，否则令为最左边的比特。

6）令。

SM2公钥加密算法的安全性基于椭圆曲线离散对数困难问题。与ElGamal算法基于的有限域上的离散对数困难问题不同，椭圆曲线离散对数困难问题目前没有亚指数求解算法，即没有比复杂度O（2ⁿ）更低的已知算法。因此，SM2公钥加密算法具有更小的参数规模，如256位的椭圆曲线离散对数问题的安全强度大约等同于3072位RSA或3072位离散对数问题的安全强度。SM2算法可以基于更小的密钥规模与带宽消耗实现与RSA、ElGamal等算法同样的安全性。椭圆曲线离散对数问题也受Shor量子算法影响，且由于参数规模更小，Shor量子算法求解复杂度更低，因此我们需关注量子计算技术的研究进展，评估量子攻击的影响。

4.SM9加密算法

2016年3月，国家密码管理局发布GM/T 0044《SM9标识密码算法》，标志着SM9算法成为我国密码行业推荐标准之一。2020年4月，SM9算法成为国家推荐标准GB/T 38635—2020《信息安全技术SM9标识密码算法》。

SM9是基于标识的密码（IBC，Identity-Based Cryptography）算法。与传统的公钥密码算法如RSA、ECC等不同，基于标识的密码算法的公钥不是无实际意义的随机字符串，而是由能唯一确定用户身份的标识构成。这些标识通常是用户无法否认的信息，如电子邮箱、身份证号码等。

在基于标识的密码系统中，用户的私钥由密钥生成中心（KGC，Key Generation Center）根据主密钥和用户标识计算生成。用户的公钥由用户标识唯一确定，而标识的真实性由标识管理者负责保证。用户的身份标识直接作为公钥，使得基于标识的密码学在应用上比传统公钥密码学更为简便。然而，这种简便性是以算法设计和计算的复杂性为代价的。IBC算法除了需要进行RSA和ECC算法中常见的大数运算和椭圆曲线点群运算之外，还额外引入了双线性对的计算，这增加了算法的复杂度。

下面简要介绍我国商用密码标准SM9算法的加解密过程。

SM9算法的系统参数包括曲线的识别符cid、椭圆曲线基域F_q的参数、椭圆曲线方程参数a和b、扭曲线参数β（若cid的低4位为2）、曲线阶的素因子N和相对于N的余因子cf、曲线E（F_q）相对于N的嵌入次数k、（d₁整除k）的N阶循环子群G₁的生成元P₁、（d₂整除k）的N阶循环子群G₂的生成元P₂、双线性对e的识别符eid，以及（可选）G₂到G₁的同态映射ψ。双线性对e的值域为N阶乘法循环群G_T。SM9公钥密码算法使用256位的BN曲线，椭圆曲线方程为y²=x³+b，相关参数如下。

• 基域特征q：B6400000 02A3A6F1 D603AB4F F58EC745 21F2934B 1A7AEEDB E56F9B27 E351457D。

• 方程参数b：05。

• 群G₁、G₂的阶N：B6400000 02A3A6F1 D603AB4F F58EC744 49F2934B 18EA8BEE E56EE19C D69ECF25。

• 余因子cf：1。

• 嵌入次数k：12。

• 扭曲线的参数。

• k的因子d₁=1，d₂=2。

• 曲线识别符cid：0x12。

• 群G₁的生成元：

坐标为93DE051D 62BF718F F5ED0704 487D01D6 E1E40869 09DC3280 E8C4E4817C66DDDD，

坐标为21FE8DDA 4F21E607 63106512 5C395BBC 1C1C00CB FA602435 0C464CD70A3EA616。

• 群G₂的生成元：

坐标为

（85AEF3D0 78640C98 597B6027 B441A01F F1DD2C19 0F5E93C4 54806C11 D8806141，37227552 92130B08 D2AAB97F D34EC120 EE265948 D19C17AB F9B7213B AF82D65B），

坐标为

（17509B09 2E845C12 66BA0D26 2CBEE6ED 0736A96F A347C8BD 856DC76B 84EBEB96，

A7CF28D5 19BE3DA6 5F317015 3D278FF2 47EFBA98 A71A0811 6215BBA5 C999A7C7）。

• 双线性对的识别符eid：0x04。

SM9算法过程如下。

（1）系统主密钥和用户加密密钥的产生

KGC产生随机数ke∈[1，N-1]作为加密主私钥，计算G₁中的元素P_pub-e=[ke]P₁作为加密主公钥，则加密主密钥对为（ke，P_pub-e）。KGC秘密保存ke，公开P_pub-e。

KGC选择并公开用一个字节表示的私钥生成函数识别符hid。

用户A和用户B的标识分别为ID_A、ID_B。为产生用户A的加密私钥de_A，KGC首先在有限域F_N上计算t₁=H₁（ID_A‖hid，N）+ke，若t₁=0，则需重新产生主私钥，计算和公开主公钥，并更新已有用户的私钥；否则计算，然后计算de_A=[t₂]P₂。为产生用户B的加密私钥de_B，KGC首先在有限域F_N上计算t₃=H₁（ID_B‖hid，N）+ke，若t₃=0，则需重新产生主私钥，计算和公开主公钥，并更新已有用户的私钥；否则计算，然后计算de_B=[t₄]P₂。

（2）加密

设用户A需要向用户B发送的消息为比特串M，mlen为M的比特长度，K₁_len为分组密码算法中密钥K₁的比特长度，K₂_len为函数MAC（K₂，Z）中密钥K₂的比特长度。作为加密者的用户A应完成以下运算。

1）计算群G₁中的元素Q_B=[H₁（ID_B‖hid，N）]P₁+P_pub-e。

2）产生随机数r∈[1，N-1]。

3）计算群G₁中的元素C₁=[r]Q_B，将C₁的数据类型转换为比特串。

4）计算群G_T中的元素g=e（P_pub-e，P₂）。

5）计算群G_T中的元素w=g^r，将w的数据类型转换为比特串。

6）按加密明文的算法分类进行计算：

①如果加密明文的算法是基于密钥派生函数的序列密码算法，则

a）计算整数klen=mlen+K₂_len，然后计算K=KDF（C₁‖w‖ID_B，klen）。令K₁为K最左边的mlen比特，K₂为剩下的K₂_len比特，若K₁为全0比特串，则返回步骤2）；

b）计算C₂=M⊕K₁。

②如果加密明文的算法是结合密钥派生函数的分组密码算法，则

a）计算整数klen=K₁_len+K₂_len，然后计算K=KDF（C₁‖w||ID_B，klen）。令K₁为K最左边的K₁_len比特，K₂为剩下的K₂_len比特，若K₁为全0比特串，则返回步骤2）；

b）计算C₂=IV‖Enc（K₁，M，IV），C₂的结构中前16个字节为IV值，当且仅当分组密码算法工作模式为非ECB（分组密码的工作模式见GB/T 17964-2021）时，初始向量IV才有效，其中Enc分组密码算法遵循GB/T 32907。填充方式为GB/T17964-2021附录C.2规定的填充方法1，即在明文字节串的右侧填充a个字节的“a”，使明文长度达到分组长度的整数倍，且a≥1.