ElGamal 密码体制简记

离散对数问题

给定乘法群 $(G, \quad\cdot)$ ，一个 $n$ 阶元素 $\alpha \in G$ 和元素 $\beta \in\langle\alpha\rangle$ 。要求找到惟一的整数 $a,0 \leq a \leq n-1$ ，满足 $\alpha^{a}=\beta$ 。一般将这个整数 $a$ 记为 $a=\log _{\alpha} \beta$ 。

通常取 $G$ 为有限域 $\mathbb{Z}_{p}$ 的乘法群（$p$ 为素数），$\alpha$ 为模 $p$ 的本原元，这时 $n=|\langle\alpha\rangle|=p-1$ 。或取 $\alpha$ 为乘法群 $\mathbb{Z}_{p}^{*}$ 的一个素数 $q$ 阶元素，$q | p-1$ 。

ElGamal 密码体制定义

考虑 $\mathbb{Z}_{p}^{*}$ 上的情况，设 $p$ 是一个素数，使得 $\left(\mathbb{Z}_{p}^{*}, \quad\cdot\right)$ 上的离散对数问题是难解的，令 $\alpha \in \mathbb{Z}_{p}^{*}$ 是一个本原元。另 $P=\mathbb{Z}_{p}^{*}, C=\mathbb{Z}_{p}^{*} \times \mathbb{Z}_{p}^{*}$ ，定义
$$
K=\left\{(p, \alpha, a, \beta): \beta \equiv \alpha^{a} \bmod p\right\}
$$
其中 $(p, \alpha, \beta)$ 是公钥， $a$ 是私钥。对 $k=(p, \alpha, a, \beta)$ ，以及一个秘密的随机数 $s \in \mathbb{Z}_{p-1}$ ，定义加密
$$
e_{k}(x, s)=\left(y_{1}, y_{2}\right),\quad y_{1}=\alpha^{s} \bmod p,\quad y_{2}=x \beta^{s} \bmod p
$$
对 $y_{1}, y_{2} \in \mathbb{Z}_{p}^{*}$ ，定义解密
$$
d_{k}\left(y_{1}, y_{2}\right)=y_{2}\left(y_{1}^{a}\right)^{-1} \bmod p
$$
注意： 这里我们在加密时使用了一个随机选取的变量 $s$ ，但是解密时并不需要知道这一参数。更换 $s$ 的值，可以为同一段明文生成多个不同的密文，但这对解密过程没有任何影响。

加解密示例

设 $p=2597$ ，$\alpha=2$ 是模 $p$ 的本原元。令 $a=765$ ，则可以算出 $\beta=2^{765} \bmod 2579=949$ 。于是 Bob 发布公钥 $(p, \alpha, \beta)$ ，保留私钥 $a$ 。

若 Alice 想加密明文 $x=1299$ 并发送给 Bob 密文 $y$ ，选择随机数 $s=853$ （由 Alice 随机选取，不需要告诉 Bob），她将计算
$$
y_{1}=2^{853} \bmod p=435,\quad y_{2}=1299 \cdot 949^{853} \bmod p=2396
$$
于是密文为 $y=(435,2396)$ 。

Bob 收到密文 $y$ 后利用私钥 $a$ 来解密：$x=2396 \cdot\left(435^{765}\right)^{-1} \bmod p=1299$ 。