ElGamal 1985：把迪菲–赫尔曼密钥交换改写成加密与签名

破除误解：不是迪菲–赫尔曼本身，也不是一份已证明安全的方案#

第一种误读，把 ElGamal 加密当成迪菲–赫尔曼 1976的另一个名字。1976 年那篇给出的是密钥交换：双方各出一个随机指数，在公开信道上算出同一个共享值。它提出了公钥加密与签名的设想，却没有给出基于离散对数的加密或签名方案。埃尔加迈勒的做法是把交换的一方固定下来，写进公开目录，作为公钥；发送方每发一条消息，就临时完成另一半交换，用得到的共享值去乘明文。交换变成了加密，代价是发送方每次都要重新抽一个随机数。

第二种误读，把它当成第一个概率公钥加密。随机化的公钥加密，以及要求密文不泄露明文任何部分信息的语义安全定义，出自戈德瓦塞尔与米卡利 1984。那套方案逐比特加密，效率很低。ElGamal 加密天然是随机的，密文只比明文长一倍，但四页并没有把它和语义安全联系起来。

第三种误读，以为“在 $\mathbb{Z}_p^*$ 里直接用”就满足后来的安全定义。并非如此。在整个乘法群里，生成元是二次非剩余，公钥和密文第一部分的勒让德符号都可以公开计算，由此能算出共享值是否为二次剩余，从而泄露明文的二次剩余性这一位信息。要得到语义安全，需要在素数阶子群里工作，并依赖判定性迪菲–赫尔曼假设；这一结论出自 1998 年前后的文献，不在四页里。

第四种误读，以为四页里的签名就是 DSA。美国国家标准与技术研究院 1991 年提出、1994 年发布为 FIPS 186 的数字签名算法，是在 ElGamal 签名的基础上，结合施诺尔在素数阶子群里工作的做法改出来的。签名方程的形状相近，参数和群的选择不同。

装置：每条消息一次临时交换#

设公开参数为素数 $p$ 和模 $p$ 的生成元 $\alpha$。用户 A 秘密取 $x_A$，公开 $y_A = \alpha^{x_A} \bmod p$。

要给 A 发送明文 $m$（$0 \le m \le p-1$），发送方随机取 $k$，算出共享值 $K = y_A^{\,k} \bmod p$，送出一对数 $c_1 = \alpha^k \bmod p$ 与 $c_2 = K m \bmod p$。A 收到后用自己的秘密算出 $K = c_1^{\,x_A}$，再除掉它，得到 $m$。窃听者看到 $\alpha^{x_A}$ 与 $\alpha^k$，要算出 $K$，就是要解迪菲–赫尔曼问题。原文据此说明，从密文恢复明文与破解迪菲–赫尔曼交换等价。

随机数 $k$ 必须每条消息新取。原文指出，若两条消息用了同一个 $k$，共享值 $K$ 相同，两段 $c_2$ 相除就得到两条明文之比，知道其中一条就知道另一条。这是方案的结构，不是实现失误。密文长度是明文的两倍，也来自这一结构：$c_1$ 不携带消息，只负责把这次临时交换的一半交给收信人。

签名换了一套方程。A 要对 $m$ 签名，随机取与 $p-1$ 互素的 $k$，令 $r = \alpha^k \bmod p$，再解出 $s$，使 $m \equiv x_A r + k s \pmod{p-1}$。签名是 $(r, s)$。验证者检查 $\alpha^m \equiv y_A^{\,r} r^{\,s} \pmod p$ 是否成立。签名者需要知道 $x_A$ 才能解出 $s$；验证者只用公开值。同样，$k$ 绝不能重复，也不能泄露：一旦知道某次签名所用的 $k$，从方程里就能直接解出 $x_A$。

原文讨论了几类已知攻击，并据此给出参数建议，例如 $p-1$ 应当含有大素因子，以免波利格–赫尔曼算法把离散对数拆成小问题求解。四页签名的对象是 $m$ 本身。后来的实用版本先对消息求哈希，再签名摘要，因为对未经哈希的原始方案，攻击者不需要私钥就能凑出某些无意义消息的合法签名。

随机数为什么是整套方案的命门#

加密和签名都依赖每次新抽的 $k$，而两者对 $k$ 出错的后果不一样。加密时重复使用 $k$，泄露的是明文之间的关系；签名时重复使用 $k$，泄露的是私钥本身。两次签名若共用 $k$，它们的 $r$ 相同，两条签名方程相减就消掉了 $x_A r$ 以外的未知数，先解出 $k$，再解出 $x_A$。DSA 与椭圆曲线上的 ECDSA 继承了同一结构，也继承了同一弱点。2010 年底，研究者在混沌通信大会上公布，索尼 PlayStation 3 的固件签名在 ECDSA 里始终使用同一个随机数，由此算出了索尼的签名私钥。这一事件常被用来说明，四页里那句“$k$ 必须每次新取”并非可有可无的提醒。

后来的标准因此出现了“确定性随机数”的做法：不再依赖设备的随机数发生器，而是由私钥和消息摘要按固定规则推导出 $k$，既保证每条消息不同，又保证同一消息可重复验证。这是对本页结构弱点的工程补丁，不改变方程本身。

参数的大小也由这四页的群决定。素数域上的离散对数有亚指数时间的指标演算法，因此 $p$ 必须取得很大，密文和签名都随之变长。椭圆曲线群上目前没有已知的同类算法，同等安全水平下群元素短得多，这是后来密码实现普遍转向椭圆曲线的主要原因。

十三年后补上的安全证明#

四页没有安全定义，第一份严格的证明要等到 1998 年。那年二月在横滨举行的第一届公钥密码学实践与理论研讨会（PKC '98）上，GTE 实验室的齐乌尼斯（Yiannis Tsiounis）与莫蒂·扬（Moti Yung）发表《On the Security of ElGamal Based Encryption》，证明：只要明文取自一个子群、不加任何修改，ElGamal 加密的语义安全就由判定性迪菲–赫尔曼假设推出；反过来，语义安全也蕴含这一假设，两者等价。论文还给出了归约效率的精确分析。

这一结果解释了前面那条“在整个 $\mathbb{Z}_p^*$ 里会漏一位”的限制从何而来：在整个乘法群里，判定性迪菲–赫尔曼假设本身就不成立，因为勒让德符号能把真实的共享值与随机元素部分地区分开。实际部署因此要么取 $p = 2q+1$ 这样的安全素数，在 $q$ 阶的二次剩余子群里工作，并把消息编码进子群；要么改用椭圆曲线上的素数阶群。

从四页到投票系统与邮件加密#

ElGamal 加密很少直接加密整条消息，它更常见的身份是两类系统里的零件。

第一类是加密邮件。1997 年发布的 PGP 5.0 引入以 DSA 签名、ElGamal 加密为主的密钥类型（PGP 界面上称为 Diffie–Hellman/DSS），作为 RSA 之外的选择；后来的 GnuPG 长期默认生成“DSA 主密钥加 ElGamal 加密子密钥”的组合。OpenPGP 标准 RFC 4880 给 ElGamal 加密分配了算法编号 16。在这些系统里，ElGamal 只加密一把随机生成的会话密钥，正文用对称密码加密，这也绕开了密文长一倍和消息必须落在群里的不便。

第二类是电子投票。把明文放进指数，即加密 $\alpha^m$ 而不是 $m$，乘法同态就变成加法同态：选票密文相乘，得到的是票数之和的加密。1997 年克拉默、珍纳罗（Rosario Gennaro）与舍恩马克斯（Berry Schoenmakers）在欧洲密码学年会上据此设计了多机构选举方案，解密由多个机构共同完成，任何单一机构都看不到个人选票；2008 年阿迪达（Ben Adida）发布的 Helios 网络投票系统也采用了指数 ElGamal。代价是解密时要求一个小范围内的离散对数，所以只适合票数这类小整数。

签名一侧的后代是数字签名算法。美国国家标准与技术研究院 1991 年 8 月公布 DSA 草案，1994 年定为 FIPS 186。它保留了 ElGamal 签名方程的形状，但把运算放进 $p$ 的一个 160 位素数阶子群，签名因此从两个与 $p$ 等长的数缩短为两个 160 位的数；消息先经 SHA 哈希再签名。草案公布时，RSA 的专利持有方与部分学者公开反对，理由包括最初只允许 512 位模数，后来标准把上限放宽到 1024 位。

四页对参数的那条建议也有出处。1978 年波利格（Stephen Pohlig）与赫尔曼在同一份汇刊上发表算法，说明当 $p-1$ 只有小素因子时，离散对数可以分解到各个小因子上分别求解。ElGamal 要求 $p-1$ 含有大素因子，正是为了防这一招。参数的陷阱不止这一处：1996 年布莱兴巴赫尔（Daniel Bleichenbacher）在欧洲密码学年会上指出，如果生成元 $\alpha$ 选得不当，例如满足某些整除条件，攻击者不知道私钥也能为自己选定的消息造出能通过验证的 ElGamal 签名。椭圆曲线上的对应要求是群阶含有一个大素因子、余因子很小，并且生成元落在大素数阶子群里。

测到了什么，没有测到什么#

四页测到的是两个可以直接写出、直接实现的方案，以及它们与离散对数、迪菲–赫尔曼问题之间的关系。加密被说明为“破解它等于破解迪菲–赫尔曼”；签名被说明为“伪造似乎需要求离散对数”，后者是论证，不是证明。

它没有测到选择密文下的行为。ElGamal 加密具有乘法同态性：把 $c_2$ 乘上任意已知数，解密结果就乘上同一个数。攻击者不用知道明文就能把一份密文改成另一份相关的密文。对需要抵抗主动攻击的场合，这是缺陷；克拉默与肖普 1998在同一类群上加入一段用哈希做的核验，才在标准模型里挡住自适应选择密文攻击。同一性质在另一些场合又是优点：电子投票与混合网络正是利用这种同态，把选票密文相乘或重新随机化，而不解开任何一张。

它也没有测到签名在选择消息攻击下的安全。这类定义由戈德瓦塞尔、米卡利与里维斯特在 1984 年提出，期刊版 1988 年发表，四页没有用它来分析签名。施诺尔签名后来有了随机预言机模型中的证明，ElGamal 签名本身的形式化分析则复杂得多，部分变体至今没有干净的归约。

四页还没有覆盖群的选择。原文工作在素数域 $\mathbb{Z}_p^*$ 上；同一套方程可以搬到任何离散对数困难的循环群，包括 1985 年前后由米勒（Victor Miller）与科布利茨（Neal Koblitz）分别提出的椭圆曲线群。今天椭圆曲线上的密钥交换与签名，结构上都是这四页和施诺尔方案的后代。离散对数问题在量子计算机上可以由肖尔算法有效求解，这是后量子密码要替换这一整族方案的原因。

跨域连接#

• 迪菲–赫尔曼 1976：交换协议本身。本页的加密就是“固定一方、临时补另一方”的交换，安全性与迪菲–赫尔曼问题等价。1976 年设想了公钥加密与签名，本页给出了基于离散对数的具体方案。
• 克拉默–肖普 1998：同一类群上的加密，多了一段抗碰撞哈希的核验。核验专门对付本页的乘法同态带来的可延展性，代价是密文多出几个群元素。
• 戈德瓦塞尔–米卡利 1984：给出语义安全的定义与第一个满足它的方案。本页的加密是随机的，但要到素数阶子群与判定性迪菲–赫尔曼假设下才满足那个定义；在整个 $\mathbb{Z}_p^*$ 里会漏出一位。
• RSA 公钥密码：RSA 的教科书加密是确定性的，同一明文总得到同一密文；本页的加密每次都随机。RSA 签名是“用私钥做一次逆运算”，本页的签名则靠一个随机数和一条线性同余方程，不存在可以直接倒过来用的陷门置换。
• 菲亚特–沙米尔 1986：另一条通往签名的路：从识别协议出发，用哈希代替挑战。施诺尔签名走的是那条路，DSA 的方程则保留了本页的形状，两条线在数字签名标准里汇合。
• 加密基础：入门页讲公钥加密时，通常先讲 RSA。本页给出另一种思路：加密不是对明文做一次可逆变换，而是借一次临时的密钥交换得到一次性的乘数。混合加密里“先协商密钥、再用对称密码加密正文”的做法，结构上与此相通。
• 数论：方案用到的全部工具都在初等数论里：模素数的乘法群是循环群，生成元即原根；费马小定理保证指数可以按 $p-1$ 取模，签名方程因此写在模 $p-1$ 上。数论页里的原根与离散对数，是读懂这四页的前置知识。
• 全同态加密：本页的方案只对乘法同态，这一点在投票和混合网络里被反复利用。全同态加密要求加法与乘法都能在密文上做，走的是格上的另一套构造。

参考文献#

• Taher ElGamal, "A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms", IEEE Transactions on Information Theory 31(4), July 1985, pp. 469–472. DOI: 10.1109/TIT.1985.1057074. —— 本文对象。
• Taher ElGamal, "A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms", Advances in Cryptology — CRYPTO '84, LNCS 196, Springer, 1985, pp. 10–18. DOI: 10.1007/3-540-39568-7_2. —— 会议版本。
• Whitfield Diffie & Martin E. Hellman, "New Directions in Cryptography", IEEE Transactions on Information Theory 22(6), 1976, pp. 644–654. DOI: 10.1109/TIT.1976.1055638. —— 密钥交换。
• Shafi Goldwasser & Silvio Micali, "Probabilistic Encryption", Journal of Computer and System Sciences 28(2), 1984, pp. 270–299. DOI: 10.1016/0022-0000(84)90070-9. —— 语义安全的定义。
• Ronald Cramer & Victor Shoup, "A Practical Public Key Cryptosystem Provably Secure against Adaptive Chosen Ciphertext Attack", Advances in Cryptology — CRYPTO '98, LNCS 1462, Springer, 1998, pp. 13–25. DOI: 10.1007/BFb0055717. —— 同类群上的选择密文安全方案。
• Yiannis Tsiounis & Moti Yung, "On the Security of ElGamal Based Encryption", Public Key Cryptography — PKC '98, LNCS 1431, Springer, 1998, pp. 117–134. DOI: 10.1007/BFb0054019. —— 语义安全与判定性迪菲–赫尔曼的等价。
• Stephen C. Pohlig & Martin E. Hellman, "An Improved Algorithm for Computing Logarithms over GF(p) and Its Cryptographic Significance", IEEE Transactions on Information Theory 24(1), 1978, pp. 106–110. —— $p-1$ 需含大素因子的原因。
• Daniel Bleichenbacher, "Generating ElGamal Signatures Without Knowing the Secret Key", Advances in Cryptology — EUROCRYPT '96, LNCS 1070, Springer, 1996, pp. 10–18. DOI: 10.1007/3-540-68339-9_2. —— 生成元选择不当时的签名伪造。

延伸阅读#

• 与 迪菲–赫尔曼 1976 对读：交换与加密之间只隔着“把一方写进公开目录”这一步。
• 与 克拉默–肖普 1998 对读：同一个群，一边可延展，一边加了核验。