从群到 ElGamal 加密算法

群的定义和性质#

一个群是一个有序对 $(G, \ast)$， 其中 $G$ 是一个非空集合，$\ast$ 是定义在 $G$ 上的二元运算。我们要求该运算须满足以下四条公理：

1. 封闭性（Closure）：对于任意 $a, b \in G$，都有 $a * b \in G$。一般地，当我们说 $*$ 是定义在 $G$ 上的二元运算时，封闭性通常已经隐含。
2. 结合律（Associativity）：对于任意的 $a, b, c \in G$，都有 $(a * b) * c = a * (b * c)$。
3. 单位元（Identity element）：存在某个元素 $e \in G$，使得对于任意 $a \in G$，都有 $e * a = a * e = a$。
4. 逆元（Inverse element）：对于任意 $a \in G$，存在某个元素 $a^{-1} \in G$ 使得 $a * a^{-1} = a^{-1} * a = e$。

群不能只看作一个集合或一个运算，它必须是两者的结合，同时满足上面的公理。如果一个群满足交换律（即 $a * b = b * a$ 对于任意 $a, b \in G$ 成立），则我们称该群为 阿贝尔群（Abelian group）。

群可以分为有限群和无限群。有限群的集合 $G$ 中元素个数有限，记作 $\lvert G \rvert = n$，称为群的阶，即群的集合内元素的数量：例如 $(\mathbb{Z}_n, +)$，即模 $n$ 的整数加法群，其阶为 $n$。无限群的集合元素个数无限：例如 $(\mathbb{Z}, +)$，即整数加法群。

对于一个群 $(G, \ast)$，其中 $\ast$ 是群的二元运算，如果 $H$ 是 $G$ 的一个非空子集，并且 $H$ 在运算 $\ast$ 下也构成一个群，则称 $H$ 为 $G$ 的一个 子群，记作 $H \leq G$。

我们判定一个群 $G$ 的非空子集 $H$ 是子群，当且仅当同时满足以下三个条件：

1. 封闭性：对于任意 $a, b \in H$，有 $a * b \in H$。
2. 单位元：$G$ 的单位元 $e$ 也属于 $H$。
3. 逆元：对于任意 $a \in H$，有 $a$ 的逆元 $a^{-1} \in H$。

设 $G$ 是一个群，$S$ 是 $G$ 的一个非空子集。所有包含 $S$ 的 $G$ 的子群中最小的那个记作 $\langle S \rangle$，它由所有形如 $s_1^{\epsilon_1} s_2^{\epsilon_2} \cdots s_k^{\epsilon_k}$ 的元素构成，其中 $s_i \in S$，$\epsilon_i = \pm 1$，$k$ 为任意非负整数；$k = 0$ 时的空乘积约定为单位元。如果 $\langle S \rangle = G$，我们就称 $S$ 是群 $G$ 的一个生成集。如果一个元素 $g$ 就能生成整个群，即 $G = \langle g \rangle$，则称 $G$ 为循环群，$g$ 为这个群的一个生成元。一般生成集中的元素不一定能单独生成整个群。

ElGamal 可以定义在循环群上。本文从模素数乘法群 $\mathbb{Z}_p^\ast$ 入手：它的元素严格说是模 $p$ 的非零剩余类，我们用 $1, 2, \cdots, p - 1$ 作为代表。群运算是模 $p$ 的乘法，即将两个代表数相乘后取模 $p$。我们将在下文证明它满足群的四条公理；算法部分则会选用它的一个合适的子群。

一个经典结论是：对于任意素数 $p$，群 $\mathbb{Z}_p^\ast$ 都是循环群。本文引用这一结论，不展开证明。这意味着，存在一个原根，也就是整个群的生成元 $g \in \mathbb{Z}_p^\ast$，使得

恰好覆盖 $\mathbb{Z}^*_p$ 集合中的所有元素。

模 p 乘法群的运算满足四条公理#

以下固定素数 $p$，记 $G = \mathbb{Z}_p^\ast$，并继续用 $1, 2, \cdots, p - 1$ 表示其中的元素。

从共享秘密到消息掩蔽#

设 Bob 的私钥为 $x$，公钥中的一个元素为 $y = g^x$。Alice 加密时另外选取随机数 $k$，并发送 $c_1 = g^k$。于是，两人可以分别算出

这里先用群中的幂运算表示；在下文选取的模乘法群中，所有结果都要取模 $p$。

两人算出的同一个群元素记为 $s$。Alice 用乘法把它与消息结合，得到 $c_2 = ms$；Bob 则乘上 $s^{-1}$，撤销这层掩蔽。这说明了逆元为什么能保证解密的正确性。但旁观者从 $g,g^x,g^k$ 中能否得到 $s$，以及密文是否泄露消息的信息，需要另行讨论。

选取群与参数#

为了把算法和后面的安全讨论统一起来，我们选用模素数乘法群中的一个素数阶子群：

其中 $p,q$ 都是素数，$q$ 足够大，$g$ 的阶恰好为 $q$，即 $g^q \equiv 1 \pmod p$ 且 $g \ne 1$。此处的 $g$ 只需要生成子群 $G$，不再要求它是整个 $\mathbb{Z}_p^\ast$ 的原根。

具体参数不能仅凭「$p,q$ 都很大」就认定安全，还需要所选群中的相关计算问题足够困难。本文先在这样的群中说明算法，再解释安全假设。

消息必须是一个群元素 $m \in G$，而不是任意整数、文本或文件。如何把一般消息编码到群中并无歧义地恢复，是另外需要处理的问题，不能简单地把任意数据取模 $p$。实际应用通常采用经过安全分析的混合加密方案。

密钥生成#

Bob 使用合适的公开群参数 $(p,q,g)$，然后生成密钥：

1. 使用密码学安全的随机数生成器，均匀选取私钥 $x \in \{1,2,\cdots,q-1\}$；
2. 计算 $y = g^x \bmod p$。

Bob 公开公钥 $(p,q,g,y)$，并将私钥 $x$ 保密。群参数可以由协议统一规定，不必由每个接收方重新生成。

加密#

Alice 要向 Bob 发送消息 $m \in G$：

1. 获取 Bob 的公钥 $(p,q,g,y)$，并通过可信方式确认它确实属于 Bob；
2. 使用密码学安全的随机数生成器，独立、均匀地选取临时随机指数 $k \in \{1,2,\cdots,q-1\}$；
3. 计算第一部分密文 $c_1 = g^k \bmod p$；
4. 计算共享秘密 $s = y^k \bmod p$，以及第二部分密文 $c_2 = ms \bmod p$；
5. 将密文 $(c_1,c_2)$ 发送给 Bob。

每次加密都要重新采样 $k$，不能复用以前的值。独立随机采样理论上仍可能碰撞，因此随机空间也必须足够大。$k$ 通常不随密文发送，密文中公开的是 $g^k \bmod p$。

解密与正确性#

对于按上述方式生成的合法密文，Bob 使用私钥 $x$ 解密：

1. 计算共享秘密 $s = c_1^x \bmod p$；
2. 计算 $s$ 的模 $p$ 逆元 $s^{-1}$，使得 $ss^{-1} \equiv 1 \pmod p$；
3. 恢复消息 $m = c_2s^{-1} \bmod p$。

为什么双方能得到同一个 $s$？因为

而 $s \in G$，所以逆元一定存在。于是

由于我们用 $1,2,\cdots,p-1$ 中的数代表群元素，$c_2s^{-1}\bmod p$ 就恰好等于原消息 $m$。

一个小例子#

为了便于手算，取 $p=23,q=11,g=2$。因为 $2^{11}\equiv1\pmod{23}$，$2\ne1$，而 $11$ 是素数，所以 $2$ 的阶为 $11$。

Bob 选取私钥 $x=6$，得到 $y=2^6\bmod23=18$。Alice 要发送 $m=9$，它确实属于 $G$，因为 $9=2^5\bmod23$。选取 $k=3$ 后，

Bob 收到 $(8,2)$ 后，算出 $s=8^6\bmod23=13$。由于 $13\cdot16\equiv1\pmod{23}$，所以 $s^{-1}=16$，最终恢复

安全性依赖什么#

如果旁观者能从 $g$ 和 $g^x$ 求出 $x$，也就是解决 离散对数问题，就能得到 Bob 的私钥。但「离散对数难求」还不足以直接推出完整的消息保密结论。

这里需要区分两个相关问题：

• 计算 Diffie–Hellman 问题（CDH）：给定 $g,g^a,g^b$，计算 $g^{ab}$。这与旁观者能否直接算出共享秘密有关。
• 判定 Diffie–Hellman 问题（DDH）：给定 $g,g^a,g^b$ 和一个候选元素 $T$，判断 $T$ 是 $g^{ab}$，还是独立均匀选取的群元素。

在合适的群中，若 DDH 假设成立，即对适当随机选取的指数，上述两种情况在计算上难以区分，基础 ElGamal 可以达到 选择明文攻击下的语义安全（IND-CPA）。直观地说，即使攻击者能选择两条候选消息，也难以从挑战密文判断加密的是哪一条。这里不展开形式化安全实验与证明。

这也是不能随便选群的原因。对于奇素数 $p$，整个 $\mathbb{Z}_p^\ast$ 上的 DDH 可以利用二次剩余性质来区分。一个非零元素如果能写成某个非零元素的平方，就叫作 二次剩余；这一性质可以高效判定。若 $g$ 是整个群的原根，则 $g^t$ 是二次剩余，当且仅当 $t$ 为偶数。于是，公开的 $y=g^x$ 和 $c_1=g^k$ 会暴露 $x,k$ 的奇偶性，进而暴露掩码 $g^{xk}$ 的二次剩余性质，再结合 $c_2=mg^{xk}$，就能判断 $m$ 是否为二次剩余。

因此，直接在整个 $\mathbb{Z}_p^\ast$ 中掩蔽任意非零消息，虽然可以正确解密，却会泄露消息的一项性质，不能满足上述安全要求。选用合适的素数阶子群可以避开这里的二次剩余区分，但 素数阶本身并不自动保证 DDH 困难，仍需使用经过分析的群和参数。

为什么不能复用加密随机数#

若同一公钥下两次加密使用了相同的 $k$，就会使用相同的掩码 $s=y^k$。设两条消息分别为 $m,m'$，则

所以

这会暴露两条明文之间的关系。一旦其中一条明文 $m$ 已知，就可以直接恢复另一条：

基础 ElGamal 不提供什么#

基础 ElGamal 本身不提供消息完整性或发送者身份认证，也不具备选择密文安全性。例如，攻击者可以选取 $t\in G$，把密文 $(c_1,c_2)$ 改为

接收方解密得到的就会是 $tm\bmod p$。这种可以有规律地改变明文的性质，称为 可塑性。而且公钥是公开的，任何人都可以向 Bob 加密，解密成功并不能证明消息来自 Alice。

实际实现还必须处理公钥和密文的群成员检查、参数验证、侧信道等问题。对于任意文本或文件，通常使用经过安全分析的混合加密方案，将公钥机制与密钥派生、认证加密等组件正确组合，而不是直接套用这里的乘法公式，也不能假定随意增加一个组件就能补齐安全性。

总结起来：群和逆元解释了 ElGamal 为什么能正确解密；计算困难性假设、随机数和协议设计，才决定它能提供怎样的安全保障。

欧几里得算法 / 辗转相除法#

先设 $a,b$ 为正整数，不妨设 $a\geq b$。对 $a$ 除以 $b$，写成

我们要证明

设 $d$ 为正整数。若 $d\mid a$ 且 $d\mid b$，则 $d\mid(a-bk)$，即 $d\mid c$。反过来，若 $d\mid b$ 且 $d\mid c$，则 $d\mid(bk+c)$，即 $d\mid a$。因此，$(a,b)$ 和 $(b,c)$ 拥有完全相同的正公约数，最大公约数自然相同。

反复应用这个等式，就得到欧几里得算法。非零余数构成严格递减的正整数序列，所以算法必然在有限步后结束，最后一个非零余数就是最大公约数。如果一开始 $b\mid a$，则第一步余数为 $0$，直接得到 $\gcd(a,b)=b$。

裴蜀定理的正式证明#

设 $a,b$ 为不全为 $0$ 的整数，记 $d=\gcd(a,b)>0$。因为 $a=du,b=dv$，其中 $u,v$ 为整数，所以对任意整数 $x,y$，都有

因此 $d\mid(ax+by)$。下面证明存在整数 $x,y$，使得 $ax+by=d$。

如果 $b=0$，则 $a\ne0$ 且 $d=|a|$。当 $a>0$ 时取 $(x,y)=(1,0)$；当 $a<0$ 时取 $(x,y)=(-1,0)$。$a=0$ 的情形类似。

如果 $a,b$ 都非零，可以先对 $|a|,|b|$ 证明：因为 $\gcd(a,b)=\gcd(|a|,|b|)$，对绝对值得到的系数可以通过调整符号转化为原整数对应的系数。因此以下只需考虑 $a,b$ 都为正数的情况，交换两者后不妨设 $a\geq b$。

若 $b\mid a$，直接取 $(x,y)=(0,1)$ 即可。否则，令 $r_{-1}=a,r_0=b$，将欧几里得算法统一写为

记最后一个非零余数为 $r_n$，下一步余数为 $r_{n+1}=0$。根据前面证明的最大公约数不变性，

现在要说明，每一个余数都能表示成 $a,b$ 的整数线性组合。先为初始两项选取系数：

假设前两项已写成 $r_{i-2}=s_{i-2}a+t_{i-2}b$ 和 $r_{i-1}=s_{i-1}a+t_{i-1}b$，则

因此可以递推定义整数系数

从上述初值出发，归纳可得每个 $r_i$ 都满足 $r_i=s_i a+t_i b$，特别地，

取 $x=s_n,y=t_n$ 就得到了所需的整数解，裴蜀定理得证。沿着欧几里得算法同时递推这些系数，就是 扩展欧几里得算法。