2.5 公钥密码

公钥密码体制是密码学领域的研究分支之一，其研究历史最早可追溯到1976年。公钥密码的思想与分组密码有很大的差异：从一个显而易见的点来看，分组密码只有一类密钥，即加密和解密使用同一密钥。而公钥密码具有两类密钥，即公钥和私钥。虽然公钥密码只是比分组密码多了一类密钥，其实用性却得到了质的提升。例如，在公钥密码体制出现之前，若用户Alice想要给Bob发送秘密消息，则需要使用分组密码对秘密消息进行保护。Alice在对Bob共享秘密消息密文的同时，需要向Bob共享分组密码的密钥。那么，分组密码的密钥该怎么安全地发送至Bob呢？公钥密码体制的出现解决了以上问题。如图2-26所示，Alice在需要向Bob共享秘密消息时，只需使用Bob的公钥对秘密消息加密后发送至Bob即可，Bob使用自己的私钥便能对密文进行解密。以上过程不涉及密钥的传输，这解决了分组密码中密钥共享困难的问题。

随着公钥密码体制的不断发展，其适用的应用场景也不断增多。例如，身份基加密和属性基加密可应用在秘密数据权限控制场景中，代理重加密可应用在云加密数据高效安全共享场景中，同态加密可应用在外包数据安全计算场景中，秘密共享可应用在多方安全计算和区块链场景中，不同的公钥密码也可组合应用在隐私计算场景中。

2.5.1 数学基础知识

公钥密码体制通常建立在近世代数之上，例如基于整数环的RSA、ElGamal、Diffie-Hellman等算法，基于椭圆曲线素数群的SM2算法，基于多项式环的全同态加密算法等。因此，为了深入理解公钥密码学，需要系统学习相关的近世代数知识。本节将首先介绍近世代数中的群环域，然后给出模算术基本理论，最后浅析多项式算术理论。

1.群环域

群（Group）、环（Ring）和域（Field）是数学的一个分支，即近世代数的基本要素 ^［60-63］ 。近世代数关注的是那些可以对集合元素进行代数运算的集合；也就是说，可以将集合中的两个元素结合起来（也许以多种方式结合），以某些计算方法获得集合的第三个元素。

如图2-27所示，根据不同规则，可以将集合划分为不同的类别。例如，满足加法封闭性、加法结合律，且具有加法单位元和加法逆元要求的集合被称为群（Group）；若集合满足群中的性质，同时满足加法或“*”法的交换律，该集合被称为加法或“*”法阿贝尔群（Abelian Group）。若集合满足加法阿贝尔群中的性质，且同时满足乘法封闭性、乘法结合律、乘法分配律，该集合被称为环（Ring）；若集合满足环的性质，同时满足乘法交换律，该集合被称为交换环（Commutative Ring）；若集合满足交换环的性质，同时无零因子，具有乘法单位元，该集合被称为整环（Integral Domain）；若集合满足整环的性质，同时具有乘法逆元，则该集合被称为域（Field）。

1）群

群 G （有时用｛ G ，·｝表示），是一组具有二进制运算的元素。使用运算符“·”（运算符“·”是通用的，可以指加法、乘法或其他一些数学运算），能够将 G 中的每个有序元素对（ a ， b ）与 G 中的元素（ a · b ）关联起来，从而遵循以下条件。

条件1： G 满足封闭性，即如果 a ， b ∈ G ，那么 a · b ∈ G 。

条件2： G 满足结合律，即对于 G 中的所有 a 、 b 、 c ，有（ a · b ）· c = a ·（ b · c ）。

条件3： G 具有单位元，即 G 中有一个元素 e ，使得对于 G 中的所有 a ，有 a · e = e · a = a 。

条件4： G 具有逆元，即对于 G 中的每个 a ， G 中都有一个元素 a' ，使得 a · a' = a' · a = e 。

若某集合为群，且具有有限数量的元素，则我们称该集合为有限群，该有限群的阶数等于该集合中元素的数量。若某集合为群，且具有无限数量的元素，则我们称该集合为无线群，其阶数为无穷大。

若某集合为有限群，同时对于集合中的所有 a 、 b ，有 a · b = b · a ，则该集合被称为有限阿贝尔群（Finite Abelian Group）。

为了更容易理解，下面给出一些群示例。

示例1： 加法下的整数集合 Z 构成一个无限阿贝尔群，标记为（ Z ，+）。

示例2： 整数模 n （ n 表示一个大于0的整数），表示为 Z / n Z ，构成加法下的 n 阶加法阿贝尔群。

示例3： （ Z / n Z ） ^* = Z / n Z -｛0｝构成乘法阿贝尔群。这是因为由整数的同余理论可知，若 a 模 p 非零，则存在 b ∈ Z ，有 ab ≡1mod p 。

示例4： 乘法下的集合｛-1，1｝⊂ Z ，该集合是一个有限阿贝尔群。

2）环

环 R （有时用｛ R ，+，·｝表示），是一个有两个二元运算（加法和乘法）的元素集合，对于 R 中的所有 a 、 b 、 c ，环 R 遵守以下条件。

条件5： R 是一个非线性加法群，使用0表示单位元，用- a 表示 a 的逆元，有0≡（- a ）+ a mod p ，其中 p 表示群的阶。

条件6： R 是一个非线性加法群，满足加法下的封闭性，即对于所有 a ， b ∈ R ，有 a + b ∈ R 。

条件7： R 是一个非线性加法群，满足加法的结合律，即对于所有 a ， b ， c ∈ R ，有 a +（ b + c ）=（ a + b ）+ c 。

条件8： R 是一个非线性加法群，满足加法的交换律，即对于所有 a ， b ∈ R ，有 a + b = b + a 。

条件9： R 满足乘法下的封闭性，即对于所有 a ， b ∈ R ，有 a · b ∈ R 。

条件10： R 满足乘法的结合律，即对于所有 a ， b ， c ∈ R ，有 a ·（ b · c ）=（ a · b ）· c 。

条件11： R 满足乘法的分配律，即对于所有 a ， b ， c ∈ R ，有 a ·（ b + c ）= a · b + a · c 和（ a + b ）· c = a · c + b · c 。

如果 R 同时满足条件5～条件11，且满足 a ， b ∈ R ，有 a · b = b · a ，则我们称 R 是交换环（Commutative Ring）。

如果环 R 同时具备以下两个性质，则 R 被称为整环（Integral Domain）：

性质1： 具有乘法单位元 e ∈ R ，即对于所有 a ∈ R ，有 a · e = e · a = a 。

性质2： R 没有零因子，即如果有 a ， b ∈ R 和 a · b =0，那么 a =0或 b =0。

3）域

域 F （有时用｛ F ，+，·｝表示），是一个有两个二元运算（加法和乘法）的元素集合，对于 F 中的所有 a 、 b 、 c ，域 F 遵守以下条件。

条件12： F 是一个非线性加法群，使用0表示单位元，用- a 表示 a 的逆元，有0≡（- a ）+ a mod p ， p 表示群的阶。

条件13： F 是一个非线性加法群，满足加法下的封闭性，即对于所有 a ， b ∈ F ，有 a + b ∈ F 。

条件14： F 是一个非线性加法群，满足加法的结合律，即对于所有 a ， b ， c ∈ F ，有 a +（ b + c ）=（ a + b ）+ c 。

条件15： F 是一个非线性加法群，满足加法的交换律，即对于所有 a ， b ， c ∈ F ，有 a + b = b + a 。

条件16： F 是整环（Integral Domain），满足乘法下的封闭性，即对于所有 a ， b ∈ F ，有 a · b ∈ F 。

条件17： F 是整环（Integral Domain），具有乘法单位元 e ∈ F ，即对于所有 a ∈ F ，有 a · e = e · a = a 。

条件18： F 是整环（Integral Domain），满足乘法的结合律，即对于所有 a ， b ， c ∈ F ，有 a ·（ b · c ）=（ a · b ）· c 。

条件19： F 是整环（Integral Domain），满足乘法的分配律，即对于所有 a ， b ， c ∈ F ，有 a ·（ b + c ）= a · b + a · c 和（ a + b ）· c = a · c + b · c 。

条件20： F 是整环（Integral Domain），且 F 是交换环，即对于所有 a ， b ∈ F ，有 a · b = b · a 。

条件21： F 是整环（Integral Domain），没有零因子，即如果有 a ， b ∈ F 和 a · b =0，那么 a =0或 b =0。

条件22： F 具有乘法逆元，即对于所有 a ∈ F ，除了0之外， F 中都有一个元素 a ^-1 ，使得 a · a ^-1 = a ^-1 · a = e 。

实质上，域是一个集合，且对于该域中的加法、减法、乘法和除法都具有封闭性。除法的定义如下： a / b = a · b ^-1 。常见的域的例子如下：有理数域、实数域和复数域。请注意，所有整数的集合不是一个域，因为在整数中只有元素1和-1具有乘法逆元。

2.模算术

模算术是近世代数中的重要分支，它是研究一般群环域中的加法和乘法运算的一种数学方法。模算术的基本原理是，将群环域中的元素分为 n 个等价类，并用一个整数 m 来表示这 n 个等价类，即模 m 。模算术的基本定理是，在模 m 的群环域中，所有元素的加法和乘法运算都可以表示为模 m 的算术运算。

从形式化的角度来看，模算术指的是，给定任何正整数 n 和任何非负整数 x ，如果将 x 除以 n ，会得到一个整数商 q 和一个服从以下关系的整数余数 r ^［64-65］ ：

x = qn + r ，其中0≤ r ＜ n

实际上，每个学生在小学期间都会遇到模算术问题，例如“时钟算术”，当达到12时，下一个数字是1。这导致了一些奇怪的等式，如7+8=3和3-5=10。这些等式看起来很奇怪，但使用时钟算法时它们是正确的，例如10点是3点之前的5小时。所以我们真正要做的是首先计算3-5=-2，然后在答案上加12，即3-5+12=10。

同余理论是数论中的一种强大方法，该理论基于时钟运算的简单思想。例如，假设 a 、 b 、 m 同是整数，且 m ≥1，如果 a - b 可以被 m 整除，则整数 a 和 b 是模 m 同余的，即 a ≡ b （mod m ）。以上时钟示例可以用模 m =12表示，例如7+8=15≡3（mod 12），3-5=2≡10（mod 12）。同余理论具有以下性质。

性质1： 假设存在整数 a 1 、 a 2 、 b 1 、 b 2 、 m ，且满足 m ≥1， a 1 ≡ a 2 （mod m ）和 b 1 ≡ b 2 （mod m ），则有 a 1 ± b 1 ≡ a 2 ± b 2 （mod m ）和 a 1 · b 1 ≡ a 2 · b 2 （mod m ）。

性质2： 假设 a 、 b 为整数，且 b ≠0，若gcd（ a ， m ）=1，则有 ab ≡1（mod m ），其中gcd为求解最大公约数函数。

性质3： 假设 a 、 b 1 、 b 2 为整数，若 a · b 1 ≡ a · b 2 ≡1（mod m ），则 b 1 ≡ b 2 （mod m ）。 b 1 、 b 2 被称为 a 模 m 的乘法逆元。

3.多项式算术

多项式算术是近世代数中的重要分支，它是研究多项式环的数学方法。多项式环是一种特殊的环，它的元素是多项式，其加法和乘法运算也是多项式的加法和乘法运算。多项式算术的基本定理是，在多项式环中，所有多项式的加法和乘法运算都可以被表示为多项式的算术运算。多项式算术的应用非常广泛，它可以用来解决线性方程组、多项式拟合、密码学等问题。

与单个变量 x 相关的常见多项式算术 ^［66］ 有以下两类：

· 普通多项式算术，使用代数的基本规则。

· 模整数 p 的多项式算术，多项式的系数在GF（ p ）中，其中GF（ p ）表示模素数 p 下的伽罗瓦域（Galois Field）。其中，GF（ p ）也被称为有限域，即｛0，1，…， p -1｝。

1）普通多项式算术

n 次多项式（ n ＞0）是以下形式的表达式：

其中， a i 是指定整数集合 S 中的元素，集合 S 被称为系数集合（ a n ≠0）。

多项式运算包括加法、减法和乘法运算。其中，在执行除法运算时，集合 S 必须是域（Field）。多项式加法和减法是多项式运算的两种基本操作。多项式加法指的是将两个或多个多项式相加，得到一个新的多项式。在加法运算中，同类项相加，不同项直接合并。例如，将多项式2 x ³ +4 x ² +3 x +1和3 x ³ -2 x ² +5 x -7相加，得到新的多项式5 x ³ +2 x ² +8 x -6。多项式减法指的是将两个多项式相减，得到一个新的多项式。在减法运算中，需要先将减数取相反数，然后进行加法运算。例如，将多项式2 x ³ +4 x ² +3 x +1减去3 x ³ -2 x ² +5 x -7，需要将减数取相反数，即-（3 x ³ -2 x ² +5 x -7），然后进行加法运算，得到新的多项式- x ³ +6 x ² -2 x +8。

乘法运算较为复杂，需要两个多项式的系数逐一相乘，即：

其中 c i 的值如图2-28所示。

除法的定义类似，但要求 S 是一个域（Field）。假设 A （ x ）= x ³ + x ² +2， B （ x ）= - x +1。 的计算过程如图2-29所示。

2）模整数p的多项式算术

现在考虑某种多项式，其系数是某个域 F 中的元素，我们将其称为域 F 上的多项式。在这种情况下，很容易证明这类多项式的集合是一个环，即多项式环。也就是说，如果认为每个不同的多项式都是集合的一个元素，那么这个集合就是一个环。

域上的多项式能够执行多项式加、减、乘、除运算，其运算与普通多项式的运算方法相似，唯一的不同点在于，若计算后的 c i mod p =0，则令 c i =0。例如，假设 A （ x ）=2 x ⁴ +x ² + 2， B （ x ）= x ² +1， p =3，则：

· A （ x ）+ B （ x ）=（2mod3） x ⁴ + （2mod3） x ² + （3mod3）=2 x ⁴ +2 x ²

· A （ x ）- B （ x ）=（2mod3） x ⁴ + （1mod3）=2 x ⁴ +1

· A （ x ）· B （ x ）=（2mod3） x ⁶ + （3mod3） x ⁴ + （3mod3） x ² + （2mod3）=2 x ⁶ + 2

· A （ x ）/ B （ x ）=（2mod3） x ² +（-1mod3）……3mod3=2 x ² +2，这里“……”表示余数。

2.5.2 RSA算法

RSA是1977年由Ron Rivest（罗纳德·李维斯特）、Adi Shamir（阿迪·萨莫尔）和Leonard Adleman（伦纳德·阿德曼）一起提出的密码算法，RSA就是他们三人姓氏开头字母的组合。RSA是最有影响力和最常用的公钥加密算法。它可以抵抗迄今为止已知的绝大多数的安全攻击，并已被国际标准化组织（International Organization for Standardization，简写为ISO）推荐为公钥数据加密标准。该算法基于大整数因子分解困难问题。公钥由两个大整数组成，其中一个大整数是两个大素数的积，而私钥也是使用以上两个素数派生而来的。因此，如果攻击者在多项式时间内可以高效分解公钥中的大整数，则私钥就会被泄露。因此，加密强度完全取决于密钥大小，如果将密钥大小增加1倍或3倍，加密强度将呈指数级增长。RSA密钥的通常长度为1024或2048比特，但研究者认为，1024比特密钥可能会在不久的将来被破解。但到目前为止，这似乎是一项不可能完成的任务。

在隐私计算领域，RSA不仅可以被当作传统的非对称加密、签名算法来使用，例如基于RSA盲签名的隐私集合求交协议；还可以被作为乘法同态加密来使用，例如基于RSA乘法同态加密的密文检索协议。

1.背景知识

1）大整数因子分解困难问题

大整数因子分解困难问题指的是，假设存在大素数 p 1 ， p 2 ，…， p n ，令 P = p 1 × p 2 ×···× p n ，在多项式时间内，通过 P 寻找 p 1 ， p 2 ，…， p n 是困难的。

RSA的安全性假设便是建立在该困难问题之上的。

2）模运算

计算模 n 的余数，此操作被称为取模运算。注意，取模运算的结果是0到 n -1之间的整数。模算术是满足分配律、结合律和交换律的：

（ a + b ）mod m =（（ a mod m ）+（ b mod m ））mod m

（ a - b ）mod m =（（ a mod m ）-（ b mod m ））mod m

（ a × b ）mod m =（（ a mod m ）×（ b mod m ））mod m

（ a ×（ b + c ））mod m =（（ a × b ）mod m +（ a × c ）mod m ）mod m

从古代的恺撒密码到现代常用的RSA、ElGamal和椭圆曲线密码（Elliptic Curve Cryptography，简写为ECC）等，它们的实现过程都采用取模运算。

3）模逆

假设存在任意3个整数 a 、 b 、 N ，如果满足 a × b mod N =1，则整数 b 被称为整数 a 关于模 N 的乘法逆元。

4）欧拉函数

在数论中，对于正整数 n ，欧拉函数 φ （ n ）是小于或等于 n 且与 n 互素的正整数的个数。该函数以其第一位研究人员欧拉命名，也被称为 φ 函数（由高斯命名）。根据以上性质易得 φ （1）=1，但对于 n ＞1， φ （ n ）便是1，2，…， n -1与 n 互素的正整数的个数。因此，如果 n 为素数，则 φ （ n ）= n -1。欧拉函数具有以下性质。

性质1： 若 m = m 1 · m 2 （ m ∈ N ^* ），且 m 1 ， m 2 有相同的素数因子，其中 m 1 ≤ m 2 ，则有 φ （ m ）= m 2 · φ （ m 1 ）。

性质2： 若 m = m 1 · m 2 （ m ∈ N ^* ），且 m 1 ， m 2 互素，则有 φ （ m ）= φ （ m 1 ）· φ （ m 2 ）。

性质3： 假设∀ m ∈ ，则有 ， d | m 表示 d 整除 m 。

性质4： 假设∀ m ∈ ，且 p 为素数，则有 。

由欧拉函数可引出欧拉定理，即假设 a 、 m 互素，则有 a ^{φ （ m ）} ≡1（mod m ）。

5）扩展欧几里得算法

欧几里得算法可以说是最古老、最广为人知的算法之一。这是一种计算两个整数 a 和 b 的最大公约数（Greatest Common Divisor，简写为GCD）的方法。它允许计算机完成各种简单的数论任务，也可以作为更复杂的数论算法的基础。

欧几里得算法基本上是整数除法算法的连续重复。关键是重复将除数除以余数，直到余数为0。GCD是该算法中的最后一个非零余数。下面的示例演示了使用欧几里得算法找到102和38的GCD的计算过程：

102=2×38+26

38=1×26+12

26=2×12+2

12=6×2+0

GCD是2，因为它是算法终止之前出现的最后一个非零余数。

扩展欧几里得算法是一种计算 ax + by =gcd（ a ， b ）中整数 x 和 y 的算法，其中 a 和 b 已知，gcd（·）表示求最大公约数算法。扩展的欧几里得算法可以被看作模幂的逆。通过反转欧几里得算法中的步骤，可以找到 x 和 y 。下面的示例演示了求解47 x +30 y =1的整数解的计算过程：

可得， x =-7和 y =11。

2.算法细节

RSA是基于以上背景知识构建的公钥密码算法，具体描述如下。

步骤1： 假设选定两个大素数 p 和 q ，计算 n = p × q 和 φ （ n ）=（ p -1）（ q -1）。

步骤2： 假设选定大整数 e ，使得gcd（ e ， φ （ n ））=1，输出（ n ， e ）为公钥。

步骤3： 通过（ d · e ）mod φ （ n ）=1寻找 d ，即 d · e = kφ （ n ）+1。其中， k 是大于1的任意整数。因此，如果给出 e 和 φ （ n ），则非常容易计算出 d 。输出（ n ， d ）为私钥。

步骤4： 使用公钥（ n ， e ）对明文 m 加密，即 c =Enc n ， e （ m ）= m ^e mod n 。

步骤5： 使用私钥（ n ， d ）对密文 c 解密，即 m =Dec n ， d （ c ）= c ^d mod n 。

为了方便读者理解和验证算法的正确性，如图2-30所示，现将上述算法中的符号替换成整数，并逐一执行以上计算流程。（由于这里不讨论安全性，为了便于理解，在此使用小整数代替大整数来描述计算过程。）

步骤1： 首先选择两个素数 p =11和 q =17，然后计算 n = p × q =11×17=187和 φ （187）=（11-1）×（17-1）=10×16=160。

步骤2： 选择整数 e =7，其中gcd（ e ， φ （ n ））=gcd（7，160）=1，输出（ n ， e ）=（187，7）为公钥。

步骤3： 通过（ d · e ）mod φ （ n ）=1寻找 d ，这里选择 d =23。输出（ n ， d ）=（187，23）为私钥。

步骤4： 使用公钥（ n ， e ）=（187，7）对明文 m =88加密，如下所示。

步骤5： 使用私钥（ n ， d ）=（187，23）对密文 c =11解密，如下所示。

3.算法总结

RSA的安全性依赖于其密钥的长度，RSA密钥越长，安全性就越高。使用素因式分解，研究人员设法破解了768比特密钥长度的RSA算法，但他们花了两年时间，消耗了数千个工时和巨大的计算能力。因此，RSA中目前使用的密钥长度仍然是安全的。NIST 现在建议最小密钥长度为 2048比特，但许多组织一直在使用长度为4096比特的密钥。尽管 RSA是应用最广泛的公钥密码算法之一，但RSA中仍然存在许多可被攻击者利用的漏洞，如下所示。

1）弱随机数生成器

当算法实现中随机数的生成使用弱随机数生成器时，这样创建的素数更容易被分解，从而使攻击者更容易破解算法。

2）弱密钥生成

RSA密钥对的生成有某些特殊的要求。如果两个素数 p 和 q 太接近，或者这两个素数中的任意一个数值太小，那么密钥可能更容易被破解。

3）侧信道攻击

侧信道攻击不会攻击算法本身，而是转向攻击运行加密算法的系统，即攻击者可以分析正在使用的硬件功率，使用分支预测或使用定时攻击来确定算法中使用的密钥方法，从而破坏数据。

2.5.3 椭圆曲线密码

在隐私计算领域中，基于椭圆曲线的公钥密码体制应用广泛，其不仅可以被当作传统的非对称加密、签名算法来使用，同样可以被用来构造更高级的密码协议、算法等。例如，基于椭圆曲线迪菲-赫尔曼密钥交换（Elliptic Curve Diffie-Hellman key exchange，简写为ECDH密钥交换）的隐私集合求交协议。

1.背景知识

1）椭圆曲线

在形式上，数域 K 上的椭圆曲线是两个变量 x 、 y 的非奇异三次曲线（曲线与 x 轴的交点有1个或3个），该椭圆曲线具有数域 K 上的有理点（可以是无穷远点），使得 f （ x ， y ）=0。数域 K 通常被认为是复数域 C 、实数域 R 、有理数域 Q 、 Q 的代数扩张域、 p 进数域 Q p 或有限域。某个域（域的特征值不等于2或3）上的椭圆曲线可以被表示为一般三次曲线：

Ax ³ + Bx ² y + Cxy ² + Dy ³ + Ex ² + Fxy + Gy ² + Hx + Iy + J =0

其中 A ， B ，…， J 是数域 K 中的元素，通过适当改变变量，上式可以被表示为 y ² = x ³ + ax + b ，其中4 a ³ +27 b ² ≠0。为了更容易理解，设置不同的 a 和 b 的取值，能够得到图2-31中的不同椭圆曲线。

由图2-31容易看出，椭圆曲线是关于 x 轴对称的。实际上，每个椭圆曲线的实例还具有一个无穷远点，这个点在图2-31中不易被看出。为了便于理解，将用符号0（零）表示无穷远点。如果需要清晰地明确无穷远点，则可以将椭圆曲线的定义细化如下：

｛（ x ， y ）∈ R ² | y ² = x ³ + ax + b ，4 a ³ +27 b ² ≠0｝∪｛0｝

2）椭圆曲线上的群论

可以在椭圆曲线上定义一个群，例如：

· 该群的元素是椭圆曲线的点。

· 单位元是无穷远点0。

· 一个点的逆元是其关于 x 轴的对称点。

· 加法由以下规则给出：如图2-32所示，取某一直线与椭圆曲线相交的3个非零点 P 、 Q 、 R ，它们的和是 P + Q + R =0。其中，

P + Q + R = P +（ Q + R ）= Q +（ P + R ）=0

请注意，在加法规则中有 P + Q + R = P +（ Q + R ）= Q +（ P + R ）=0，因此该椭圆曲线群可以被看作一个阿贝尔群（Abelian Group）。通过该性质，便可计算求得两个任意点的和 P + Q =- R ：如图2-33所示，连接点 P 和点 Q 获得直线，并相交于椭圆曲线，得到点 R ，最终找到 R 关于 x 的对称点- R 。

以上加法是通过几何的方法表示的，会存在以下问题。

问题1： 如果 P =0或者 Q =0，则无法连接两点来获得直线，因为0不在 x 轴和 y 轴组合的平面上。但鉴于上文已经将0定义为单位元，对于任何 P 和任何 Q ，应有 P +0= P ， Q +0= Q 。

问题2： 如果 P =- Q ，则穿过这两点的线是垂直的，不与任何第三点相交。但是如果 P 是 Q 的逆元，那么有 P + Q = P +（- P ）=0。

问题3： 如果 P = Q ，则有无限多条线通过该点。这里的事情开始变得更复杂。但考虑点 Q' ≠ P ，如果让 Q '越来越接近 P ，会发生什么情况？当 Q' 趋向于 P 时，穿过 P 和 Q '的线与曲线相切。显而易见，可以有 P + P =2 P =- R ，如图2-34所示，其中 R 是曲线与通过 P 点曲线切线之间的交点。

代数加法是椭圆曲线加法的另一种表示方法。如果想让计算机执行点加法操作，需要把几何方法变成代数方法。假设 P 1 =（ x 1 ， y 1 ）和 P 2 =（ x 2 ， y 2 ）分别是椭圆曲线 E 的两个点，执行以下计算求得 P 1 和 P 2 的和：

其中，

分别设置 P 1 和 P 2 的值，可以将以上求和运算转换为乘法运算。例如，通过设置 P 1 = P 2 ，则有

3）椭圆曲线上的离散对数困难问题

椭圆曲线上的离散对数困难问题（Elliptic Curve Discrete Logarithm Problem，简写为ECDLP）指的是，假设 P 为大素数， E 为椭圆曲线，若给定 P 和 Q ，在此 Q = kP ， k ＜ P ，则求解 k 是困难的。

4）编码方法

由上文可以看出，椭圆曲线的计算是具有特定规则的。若想将普通计算转换为椭圆曲线计算，则需要将输入数据映射到椭圆曲线上。映射方法如下：

· 首先借助密码哈希函数，将输入数据映射到椭圆曲线的 x 坐标；

· 根据椭圆曲线定义，使用 x 坐标值计算 y 坐标值，具体过程如图2-35所示。

2.算法细节

假设素数域 F P 上的椭圆曲线 E =（ P ， a ， b ， x ， y ， n ），其中 P 为椭圆曲线素数域上的点的个数， a 、 b 、 x 、 y 同为大整数，且 x 、 y 表示椭圆曲线基点 G 的横、纵坐标， n 表示基点 G 的阶。使用以上椭圆曲线，对明文 m 进行加/解密的过程如下。

1）编码明文

将明文 m 映射到 F P 上，即将 m 编码为椭圆曲线 E 上的点 m' 。

2）生成密钥对

随机选择大整数 k ，计算 Q = kP ，定义私钥sk= k ，公钥pk= Q 。其中， Q = kP 可以通过加法实现，即

3）加密

随机选择整数 r ，计算 c 1 = rP ，使用公钥pk计算 c 2 = m' + r ·pk，定义密文为 c =（ c 1 ， c 2 ）。

4）解密

使用私钥sk，计算 c 2 -sk· c 1 = m' + r ·（ kP ）- k ·（ rP ）。由于 kP = rP ，因此 c 2 -sk· c 1 = m' 。

5）解码明文

将椭圆曲线上的点 m' ，重新映射回 m 。

椭圆曲线密码的发展时间较短，还需要更长时间的验证。椭圆曲线密码的另一个不足点与专利有关。黑莓公司拥有130多项与椭圆曲线密码相关的专利（通过2009年收购Certicom得来），这些专利涵盖椭圆曲线密码的诸多用途。在这些专利中的许多专利已被一些私人组织甚至美国国家安全局所拥有。这让一些开发者对他们的椭圆曲线密码（ECC）实现是否存在侵权产生了疑虑。

2.5.4 SM2算法

中国国家密码管理局（SCA）于2010年12月颁布了国家椭圆曲线密码算法标准，即SM2 ^［67］ 。SM2是中国在特殊素数域上定义的椭圆曲线密码算法，该算法已被广泛用来实现公钥密码系统 ^［68］ 。在隐私计算领域中，SM2可用作代替国际社会中常用的椭圆曲线密码，实现密码技术的安全和自主可控 ^［69］ 。

1.背景知识

SM2基于椭圆曲线密码构造，因此需要选取椭圆曲线并定义其参数。

1）椭圆曲线选取

对于素数有限域GF（ p ）， p 为大于3的整素数，有椭圆曲线方程 E ： y ² = x ³ + ax + b ，其中 a 和 b 小于 p 。 E 上的点用# E 表示。

2）参数定义

在选定曲线方程后，定义参数（ p ， a ， b ， n ， G x ， G y ）。其中， G x 和 G y 分别表示基点 G 的横、纵坐标， n 表示基点 G 的阶。图2-36给出了椭圆曲线方程和其参数选择。

3）密钥派生函数

如图2-37所示，密钥派生函数（Key Derived Function，简写为KDF）是一种特殊的密钥生成函数，它的输入是一个密钥源，输出是用于加密和解密的密钥。密钥派生函数的详细构造如下。

步骤1： 选定密码哈希函数 H ℓ （·）。其中，ℓ表示该密码哈希函数的输出值长度。

步骤2： 输入随机串 m 和密钥长度keylen。其中，keylen＜（2 ³² -1）·ℓ。

步骤3： 定义一个计数器counter。该计算器为整数类型，初始值为1，其长度为32比特。

步骤4： 循环执行「keylen/ℓ」次以下计算：

· 计算 D i = H ℓ （ m ||counter）。其中， i 指当前循环的次数。

· counter=counter+1。

步骤 5： 如果keylen能够被ℓ整除，则令 ；否则，定义 等于 的前keylen- 比特。

步骤6： 最后，输出密钥 K = D 1 || D 2 ||… 。

2.算法细节

下面以一个实际场景，详细叙述SM2的设计方案。如图2-38所示，假设Alice需要向Bob传递秘密消息，两方执行以下流程。

步骤1： Bob选定椭圆曲线方程 E ： y ² = x ³ + ax + b ，并选取 G 作为曲线的基点。

步骤2： Bob选择整数 ，定义私钥为sk= k 。计算公钥pk=sk· G = k · G 。Bob将椭圆曲线参数（ E ， G ）和公钥pk传递给Alice。

步骤3： Alice接收到Bob的消息后，将明文 m 编码到曲线 E 上，即计算 m '= m · G 。Alice选择随机数 ，进行下列计算。

其中，|| 表示拼接操作，keylen表示密钥数据的比特长度， H 表示普通哈希函数，KDF（·）表示密钥派生函数。KDF（·）的具体计算过程在本节的背景知识中已经给出。

步骤4： Alice定义密文（ c 1 ， c 2 ， c 3 ），并将其发送至Bob。

步骤5： Bob接收（ c 1 ， c 2 ， c 3 ）。

步骤6： Bob计算sk· c 1 = k · c 1 =（ x 2 ， y 2 ）， t =KDF（ x 2 || y 2 ，keylen）。

步骤7： Bob计算 m '= c 2 ⊕ t ，并计算 u = H （ x 2 || m' || y 2 ）。若 u ≠ c 3 ，则输出解密失败；否则，输出明文为 m '。

2.5.5 ElGamal算法

1985年，塔希尔·盖莫尔使用迪菲-赫尔曼密钥交换（Diffie-Hellman key exchange，简写为DH密钥交换）协议构建了ElGamal公钥密码算法，该算法的安全性依赖于有限域上的离散对数困难问题（Discrete Logarithm Problem，简写为DLP）。该算法对密码协议在现实世界应用的推进具有重要意义。该算法至今仍是一个安全性良好的公钥密码算法，它既可用于加密，又可用于数字签名。

在隐私计算领域中，与RSA类似，ElGamal算法不仅可以被当作传统的非对称加密、签名算法来使用，同样可以被作为乘法同态加密算法来使用。另外，ElGamal在改进后，能够实现加法同态算法。例如，ElGamal的变体——指数ElGama（lExponential ElGamal）便是国际标准化组织（International Organization for Standardization，简写为ISO）同态加密国际标准（ISO/IEC 18033-6：2019）中指定的加法半同态加密算法。

1.背景知识

1）素数的原根

给定素数 p ，假设存在整数 x ，若满足 x mod p 的阶为 φ （ p ），则将 x 定义为素数 p 的原根。

2）离散对数困难问题

在了解离散对数困难问题之前，首先了解何为离散对数。

离散对数：假设存在整数 y ，同时存在素数 p 的一个整数原根 x ，若能够找到唯一指数 a ，使得 y = x ^a （mod p ），这里有0≤ a ≤ p -1，则将 a 称作整数 y 的以 x 为基数的模素数 p 的离散对数。

离散对数困难问题指的是，假设存在大素数 p 和其原根 x ，在给出整数 y 后，计算 a 是困难的。

3）Diffie-Hellman密钥交换协议

Whitfield Diffie和Martin Hellman在1976年开发了Diffie-Hellman密钥交换协议，以解决密钥交换的安全问题。它使想要相互通信的双方能够在运行协议后得到同一个对称密钥，该密钥可用于加密和解密。值得注意的是，由于安全性需求，Diffie-Hellman密钥交换协议只能用于密钥交换过程，不能用于加密和解密过程。下面给出Diffie-Hellman密钥交换协议的具体构造步骤。

假设Alice和Bob尝试计算共享密钥 k 。首先，Alice和Bob共同确定一些公共参数，包含大素数 p ，模 p 下的群 G ，其中 G 的生成元为 g 。

步骤1： Alice和Bob分别生成随机密钥 k a 和 k b 。

步骤2： Alice计算 A = ，Bob计算 B = 。

步骤3： Alice将 A = 发送至Bob，同时Bob把 B = 发送至Alice；

步骤4： Alice计算 ，Bob计算 。

至此协议结束。由第4步可知，Alice和Bob在没有泄露自己密钥的情况下，生成了相同的共享密钥 。

为了便于理解，下面给出协议的具体计算示例。如图2-39所示，首先，Alice和Bob共同指定一些公共参数，包含素数 p =13（为了便于描述，这里选取 p 为小素数），模 p 下的群 G ，其中 G 的生成元为 g =6。

步骤1： Alice和Bob分别生成随机密钥 k a =5和 k b =4。

步骤2： Alice计算 A = mod p =6 ⁵ mod13=2，Bob计算 B = mod p =6 ⁴ mod13=9。

步骤3： Alice将 A =2发送至Bob，同时Bob把 B =9发送至Alice。

步骤4： Alice计算 mod p = mod p =9 ⁵ mod13=3，Bob计算 mod p = mod p =2 ⁴ mod13=3。

至此协议结束。由第4步可知，Alice和Bob在没有泄露自己密钥的情况下，生成了相同的共享密钥 。

2.算法细节

ElGamal作为公钥加密算法，由3个子算法组成，即密钥对的生成子算法KeyPairGen、公钥加密子算法Encrypt和私钥解密子算法Decrypt。下面通过一个两方交互协议示例，叙述ElGamal算法的执行流程。为了体现公钥加密算法的优势，将密钥对的生成子算法和解密子算法放在Alice端，将加密子算法放置于Bob端。

1）密钥对生成

Alice生成密钥对〈pk，sk〉，具体步骤如下。

步骤1： Alice选择大素数 p 和生成元 g ∈ ，其中 表示乘法循环群。

步骤2： Alice选择随机整数 a 。

步骤3： Alice计算 A = g ^a mod p 。

步骤4： Alice保存 a ，并将其定义为私钥，即sk= a 。

步骤5： Alice公开公钥（ p ， g ， A ），即pk=（ p ， g ， A ）。

2）加密

由于Alice的公钥pk=（ p ， g ， A ）是公开的，因此，Bob能够获取Alice的公钥，并对数据执行加密计算，这里假设需要加密的数据为整数 m ，且 m ∈ 。

步骤1： Bob选择随机整数 b 。

步骤2： Bob计算共享密钥 s = A ^b mod p ，同时计算密文的第一部分 c 1 = g ^b mod p 。

步骤3： Bob加密 m ，即计算 c 2 = m · s = m · g ^ab mod p 。

步骤4： Bob定义密文对为（ c 1 ， c 2 ），并将密文对发送至Alice。

3）解密

Alice输入私钥 a 、素数 p 、生成元 g 和 A = g ^a mod p ，并执行解密计算。

步骤1： Alice接收的密文对为（ c 1 ， c 2 ）。

步骤2： Alice计算共享密钥 s = mod p ，并计算 s 的逆元 。

步骤3： Bob计算 mod p = 。由于 mod p = g ^ba mod p ，因此 m = c 2 · s ^-1 mod p 。

为了便于理解，在此给出协议的具体计算示例。如图2-40的ElGamal加/解密协议示例所示，首先，Alice和Bob共同指定一些公共参数，包含素数 p =37（为了便于描述，这里选取 p 为小素数），模 p 下的群 G ，其中 G 的生成元为 g =2。

· 示例：密钥对生成

Alice生成密钥对：

· 示例：加密

假设需要加密的数据为整数 m =29，具体加密步骤如下。

步骤1： Bob选择随机整数 b =7。

步骤2： Bob计算共享密钥 s =32 ⁷ mod37，同时计算密文的第一部分 c 1 = g ^b mod p =2 ⁷ mod37=17。

步骤3： Bob加密 m =29，即计算密文的第二部分 c 2 = m · s =29·32 ⁷ mod37=33。

步骤4： Bob定义密文对为（ c 1 ， c 2 ）=（17，33），并将密文对发送至Alice。

· 示例：解密

Alice输入私钥 a =5、素数 p =37、生成元 g =2和 A = g ^a mod p =2 ⁵ mod 37=32，并执行解密计算。

步骤1： Alice接收的密文对为（ c 1 ， c 2 ）=（17，33）。

步骤2： Alice计算共享密钥 s = mod p =17 ⁵ mod37，并计算 s 的逆元 =17 ^-5 mod37。

步骤3： Alice计算 m = c 2 · s ^-1 mod p =33·17 ^-5 mod37=33·2mod37=29。

3.指数ElGamal

ElGamal算法依赖于有限域上的离散对数困难问题，其效率较低。在了解了椭圆曲线密码后，我们可以将有限域上的ElGamal转化为椭圆曲线上的指数ElGamal（Exponential ElGamal），在保证安全性且大幅提高效率的前提下，让算法具备加法同态的性质。下面简单描述一下指数ElGamal的算法设计。

步骤1： 选定椭圆曲线 y ² = x ³ + ax + b mod p 。其中， p 为大素数，曲线的基点为 G 。

步骤2： 选择随机数 k ∈［0， N ）。其中， N 表示椭圆曲线素数群的阶。

步骤3： 选择随机数 r 为私钥sk。其中， r ＜ p ，计算公钥pk= r · G 。

步骤4： 执行加密计算（ c 1 ， c 2 ）=Enc（pk， m ）=（ k · G ， m + k · r · G ）。

步骤5： 执行解密计算Dec（ c 1 ， c 2 ）= c 2 - r · c 1 = m + k · r · G - r · k · G = m 。

ElGamal的主要缺点是需要随机性，速度较慢（尤其是签名）。ElGamal系统的另一个潜在缺点是，在加密过程中会将消息膨胀至两倍。然而，如果密码系统仅用于交换密钥，则这种消息膨胀可以忽略不计。 9nLzDXUpg3TvRMm/HDFz8KZ+/hTrWTgm89wm+Q7v0ggRGsyW4coiiq5VB1eLFsrZ