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}\)的概率选取到原根，所以实际上不会花费很多时间。