前一篇讲了RSA，这一篇介绍下另一个经典的公钥系统，Elgamal。与RSA基于大数分解不同，Elgamal基于离散对数问题(DLP-Discrete Logarithm Problem)。

1 Discrete Logarithm Problem

对于\(q\)阶乘法循环群\(G\)，已知其生成元\(g\)及元素\(h\)，求\(x\)使得\(h=g^x \pmod{q}\)是困难的。

2 Algorithms

2.1 Key Generation

假设\(G\)是一个\(q\)阶循环群，\(g\)是其生成元，\(x\)是\(Z_q^*\)上的一个随机数，则

\[PK=\{G,q,g,h=g^x mod\ q\}, SK=\{x\}\]

2.2 Encryption

\[c=<c_1,c_2>=<g^y,m\cdot h^y>\]

其中，\(y\)是\(Z_q^*\)上的一个随机数。

2.3 Decryption

\[m=c_2/c_1^x\]

3 intrinsic random

与RSA不同，Elgmal本身就是随机的，RSA则要借助于random padding实现probabilistic encryption。

4 Elgamal Signature

由于Elgamal没有RSA那种加解密间的对称性，上述算法不能直接用于签名，但是可以简单修改得到一个签名算法。

\[Sign(m)=(r,s), r=g^k \pmod{q}, s=(m-xr)k^{-1}\pmod{q-1}\]

\[Verify(m, (r,s))=\ g^m=?y^rr^s \pmod{q}\]

5 Homomorphic encryption

Elgamal本身是乘法同态的，

\[E(m_1)E(m_2)=(c_1'c_1'',c_2'c_2'')=(g^{y_1+y_2},(m_1m_2)h^{y_1+y_2})=E(m_1m_2)\]

使用\(g^m\)作为映射函数也可以将Elgamal变成加法同态：

\[E(m)=(c_1,c_2)=(g^y,g^m\cdot h^y)\]

\[E(m_1)E(m_2)=(c_1'c_1'',c_2'c_2'')=(g^{y_1+y_2},g^{m_1+m_2}h^{y_1+y_2})=E(m_1+m_2)\]

可以预先打表缓存\((m, g^m)\)，解密时反查。