密码学科普系列之二｜浅谈El-Gamal非对称加密算法
El-Gamal非对称加密算法目前仍然活跃在网络安全领域，并广泛应用于电子签名等场景。El-Gamal的原理是处理所谓的“离散对数”问题，简单的说就是进行模幂运算是简单的，但是解离散对数是困难的。和RSA一样，它的缺陷也是速度较慢。即便如此，也无法掩盖它特有的光芒。希望通过本次介绍能让大家都学会使用这种加密体系，在生活中增添一些乐趣。
01
密钥Keyt
Alice要和Bob通信，首先需要生成密钥，所以她进行了以下步骤：
（1）取一个随机的大素数p，再取这个p的“原根”g，最后取一个随机数k（在2到p-1之间）并且gcd(k,p)=1
（2）计算
公开a,g,p作为公钥，k作为私钥必须严格保密
02
加密Encryption
Bob看到了Alice公开的公钥a,g,p后，也随机取了一个大数r，并且gcd(r,p)=1，之后进行了以下计算，编译得到两段密文：
（1）
（2）
m是明文字符根据ASCII码转译后的数段，必须是2到p-1之间的数，如果过长，可以截取成多个数段，例如（e1,e2）,（e1,e2）...
（3）将密文（e1,e2）发送给Alice
Tips: 如果明文字符很长，转译成多个数段时，r可以取多个随机值，即每个数段(e1,e2)使用不同的r，增加安全系数。另外，r在计算编译成密文后即可销毁
03
解密Decryption
Alice接收到密文后，拿出她不可公开的私钥k进行破译：将e2除以e1的k次幂，即
，从而获取到明文m
通过上述的步骤，是否感受到了破解密文的难度呢？如果没有，那么就再细细品味一番...... 数位越大，破解难度越大，当然速度也越慢：）
本次介绍告一段落，下一次如果再讲加密算法，会分享目前很安全很流行的基于椭圆曲线的CM2算法(是的，就是怀尔斯用来证明费马大定理的那个大名鼎鼎的“椭圆曲线”)，也称之为“国密”算法（用来取代RSA的），尽情期待！
真如自性
探索、发现、认知