elgamal基于基于离散对数难题.
ElGamal密码体制是T. ElGamal于1984年提出的，它至今仍然是一个安全性良好的公钥密码体制。
密钥产生过程
选择一个大素数p以及两个小于p的随机数g和x，计算y≡gx mod p。以(y,g,p)作为用户公钥，x作为用户私钥。
加密过程
如果想将明文消息M加密后发给该用户，则计算过程如下：随机选取一个与p-1互素的整数k，计算C1≡gk mod p，C2≡yk mod p，密文为C=(C1,C2)。
解密过程
当用户收到密文(C1,C2)=(gk mod p, yk mod p)后，计算C2C1-x mod p就可以得到正确的解密结果。
同许多其它的公钥密码体制一样，ElGamal密码算法的安全性是建立在有限域上的离散对数的难解性这一数学难题的基础上的。
设p是一个素数，α∈Zpx，α是一个本原元，β∈Zpx。已知α和β，求满足αn≡β(mod n)的唯一整数n，0≤n≤p–2。这一问题称为有限域上的离散对数问题，常将n记为logαβ。
ElGamal公钥密码体制可以在计算离散对数困难的任何群中实现，不过通常使用的是有限域，但不局限于有限域。
关于有限域上的离散对数问题，已经进行了许多深入的研究，取得了许多重要成果，但到目前为止，还没有找到一个非常有效的多项式时间算法来计算有限域上的离散对数。一般而言，只要素数p选取适当，有限域Zp上的离散对数问题是难解的。反过来，已知α和n，计算β=αn mod p是容易的。因此，对于适当的素数p，模p指数运算是一个单向函数。
在ElGamal公钥密码体制中，β=αd mod p，从公开的α和β，求保密的解密密钥d，就是计算一个离散对数，因此，ElGamal公钥密码体制的安全性主要是基于有限域Zp上离散对数问题的难解性。
为了抵抗目前已知的一些对ElGamal公钥密码体制的攻击，素数p按十进制表示，至少应该有150位数字，并且p-1至少应该有一个大的素因子。