Elgamal加密原理
Rsa是基于大质数分解难题；而Elgamal是基于G上的离散对数难题
局限性：如加密及解密计算量大，密文长度是明文的两倍等
基础知识
1.阶
有n>1, a与n互质，则必存在一 x（1≤x≤n-1）, 使得a^x = 1 mod n
满足等式的最小x称为，a模n的阶，表示为Ord_n(a)
又可知φ(n)是方程一解，但不一定为最小解，当φ(n)为最小解时，称a为n的一个本原元。
加密过程
1.密钥生成
私钥：a 公钥：(p,g,A)
选择一个大整数p ，一个g为p的本原元，
选择一整数a（1≤a≤p-1），计算A = g^a mod p
2.加密过程
Alice公开公钥（p,g,A）Bob选择明文M（1<M<p），Bob选择整数k，计算
C1 = g^k mod p , C2 = M*(A^k) mod p 并将（C1，C2）发给Alice。
3.解密过程
Alice收到（C1，C2），使用a进行解密。
M = C2 * (C1^a )^(-1) mod p