0x00 口胡

前面我们对公钥密码体制进行了一个总体的介绍，然后对公钥密码的一个典型代表-RSA进行了详细介绍，知道了为什么好多从事密码事业的人并不是计算机相关专业科班出身，而是数学专业科班出身。反正你数学不好，你想在密码上有所造诣，不是说没可能，我只能说难，好吧(语气词)。

RSA的安全性来自于求一对大素数的乘积很容易，但要对这个乘积进行因式分解则非常困难，也就是所谓的大整数分解问题。

而我们今天的主角ElGamal公钥密码算法，它的安全性来源于另一个数学难题-离散对数难题，即已知g为Zp*(乘法群)的生成元(对于乘法群的生成元的概念，给两个链接-1、2)，y∈ Zp ，求x使得y=g^x mod p，这个x在现阶段是不可求的，这就是ElGamal公钥密码算法安全性的来源，如果求离散对数问题是容易的，则获得y能够解出x，则这类算法完全破译

0x01 ElGamal算法流程

1. 密钥产生过程

首先选择一大素数p, 原根g和小于p的随机数x，计算y≡g^x mod p，以(y, g, p)作为公开密钥，x作为秘密密钥.
这里说明一下，g是模p的原根，原根的概念，数论姿势那有讲，再补充一点，原根是乘法群的一个生成元，所以说ElGamal公钥密码算法中生成元一般取原根

2. 加密过程

设欲加密明文消息为M(如果M长度超过p则进行分组) . 随机选与p-1互素的整数k，1< k<p-1
计算密文对: C = {C1,C2}, 发送给接收者.C1≡g^k mod p, C2≡(y^k) x M mod p.

3. 解密过程

直接po图：

这里对图中说的k 需要永久保密，且不能重复使用进行说明：

1. 攻击者若已知k，可以计算y^k,然后用C2/y^k就得到明文；
2. 若是k重复使用，则C2/C2’=M/M’,知道其中的一个明文，另一个可求。

下面我们举一个比较贴近现实(就是数字很大)的例子:

这可以算是ElGamal公钥密码算法的具体应用了，下面我们再以一个数字较小的例子来直观的感受下，里面的运算涉及到幂运算，求逆元，这些都是前面介绍过的。

0x02 ElGamal与RSA的对比

到这，ElGamal公钥密码算法就算介绍完了，最后po张ElGamal与RSA的对比图：