ELGamal算法及其原根的求取

ELGamal 是 RSA 之外的另一个公钥加密体系，于 1985 年提出。相较于 RSA，ELGamal 的运算速度更慢，密文长度更大；其优势是对于质数大小的要求更低一些，而且由于随机数的选取，即使是同一个私钥，加密同样的信息，也会得到不同的结果，提高了安全性。

数学基础

群

设$G$是一个具有代数运算$\circ$的非空集合，满足：

• 结合律：$\forall a,b,c\in G$，有$(a\circ b)\circ c=a\circ(b\circ c)$；
• 单位元：$\exists e\in G$，满足$\forall a\in G,e\circ a=a\circ e=a$；
• 逆元：$\forall a\in G$，存在$a^{-1}\in G,a\circ a^{-1}=a^{-1}\circ a=e$；

称$G$关于$\circ$构成一个群（group）。满足交换律的群称为交换群（阿贝尔群）。根据元素是否有限，群分为有限群和无限群；有限群$G$中的元素个数称为群的阶，记为$|G|$。

在模$m$的简化剩余系中，考虑模$m$意义下的乘法运算；乘法满足结合律，$1$是单位元，且由扩展欧几里得算法每个元素都有模$m$意义下的乘法逆元。因此，模$m$的简化剩余系关于模$m$意义下的乘法构成一个群，记作$Z_m^\ast$。

循环群

在群上定义幂运算，即$a^n=a\circ a\circ…\circ a$（共$n$个$a$），同时规定：

• $a^0=e$
• $a^{-n}=(a^{-1})^n$

对于群中的元素$a$，其阶$|a|$指的是使$a^m=e$成立的最小正整数$m$。若群$G$中存在元素$a$，使得$G$中所有元素都能由$a$的幂表示，则称$G$为循环群，元素$a$为$G$的生成元，记作$G=\langle a\rangle$。

原根

设$gcd(a,m)=1$，若使$a^d\equiv 1\pmod m$成立的最小正整数$d=\varphi(m)$，则称$a$是模$m$的原根。藉由原根的概念，我们来证明当$m$有原根时，模$m$的简化剩余系乘群是一个循环群，其生成元为$m$的原根。

显然$|Z_m^\ast|=\varphi(m)$，考虑$m$的一个原根$a\in Z_m^\ast$，若要证明$Z_m^\ast$是以$a$为生成元的循环群，则只需证

$$a^0,a^1,...,a^{\varphi(m)-1}$$

在模$m$意义下两两不同。设正整数$x,y$满足

$$0\leq x<y\leq\varphi(m)-1,$$

若

$$a^x\equiv a^y\pmod m,$$

则有$a^{y-x}\equiv1\pmod m$，易知$0<y-x<\varphi(m)$，这与$a$是模$m$的原根矛盾，因此

$$a^0,a^1,...,a^{\varphi(m)-1}$$

在模$m$意义下两两不同。反之，这也证明$Z_m^\ast$中不是$m$原根的元素一定不是生成元。

上面我们证明了$Z_m^\ast$的生成元和$m$的原根是一一对应的关系，与此同时，我们还容易证明有限循环群$G$生成元的个数为$\varphi(|G|)$，进而可以得到$m$原根的个数恰为$\varphi(\varphi(m))$。另外，并非所有正整数都有原根，只有当$m=2,4,p^n,2p^n$（$p$为奇素数，$n$为正整数）时，$m$才有原根。

离散对数问题

设$G=\langle a\rangle$，群$G$中的离散对数问题是指：给定$G$中元素$h$，找到正整数$k$满足

$$h=a^k.$$

我们把$k$称为$h$相对于生成元的离散对数，记作

$$k=log_ah.$$

$Z_m^\ast$中，已知生成元和指定元素，求离散对数的问题是一个困难问题；如同 RSA 中蕴含的困难问题是大数质因数分解，ELGamal 的安全性基于离散对数的求解难题。

算法流程

密钥生成

1. 取一个较大素数$p$；
2. 求$Z_p^\ast$的一个生成元$g$；
3. 任取$1<\alpha<p-1$，计算$\beta=g^\alpha\bmod p$；

其中$(p,g,\beta)$作为公钥，$\alpha$作为私钥。

加密

1. 给定待加密信息$x$，选择随机整数$1<k<p-1$；
2. 计算$E(x,k)=(r,s)$，其中$r=g^k\bmod p$，$s=x\beta^k\bmod p$；

$(r,s)$就是加密完成后的信息。

解密

1. 收到信息$(r,s)$；
2. 计算$D(r,s)=sr^{-\alpha}\bmod p=xg^{\alpha k}g^{-\alpha k}\bmod p=x$；

这样就得到明文$x$。

原根的求取

在实际使用 ELGamal 加密时，一个难点在于如何获取较大素数的原根。我们知道有限群中任意元素的阶整除群的阶，那么对于$Z_p^\ast$而言，所有元素的阶都是$\varphi(p)=p-1$的因数。这为我们提供了一种方法：

1. 随机生成大质数$q$，直到$p=2q+1$也是质数；
2. 随机选取$1<g<p-1$，那么$g$的阶必然是$p-1=2q$的因数，即$g$的阶只有$2,q,2q$三种可能。
3. 若$g^2\equiv1\pmod p$或$g^q\equiv1\pmod p$，说明$g$不是$p$的原根，否则$g$即为求得的一个原根。

随机选取$g$的形式虽然看起来时间开销无法保障，但是对于$p=2q+1$而言，其原根的个数有$\varphi(\varphi(p))=q-1$之多，即每次随机选取有$\frac{1}{2}$的概率选取到原根，所以实际上不会花费很多时间。