一文读懂ElGamal
![[R_MTFQND]3OLV9XW19WTGW.jpg](https://ucc.alicdn.com/pic/developer-ecology/9bdd7b77f2fd482890d12d72aa9e1bc0.jpg?x-oss-process=image/resize,w_1400/format,webp "[R_MTFQND]3OLV9XW19WTGW.jpg")
一文读懂ElGamal
上篇文章我们聊到了Diffie-Hellman的密钥交换协议，这次来聊一个和Diffie-Hellman相似的一个加密算法--ElGamal加密算法，该算法同样选择一个素数p和它的一个原根作为公开密钥。
算法描述
由于这是一个非对称密码体系，和RSA一样，对于加密和解密的密钥是不一样的，下面来简单看一下具体的计算过程，同样的，这里面所涉及的数学知识，也不再介绍了。
密钥生成
- 选择随机整数, 其中
- 计算: =
- 「私钥」: , 「公钥」:
加密算法
这个同样采取了取模的运算，因此和RSA类似，这个对于明文的长度也是有要求的，假设需要加密的信息是M, 其中M满足: , 如果消息内容过长，同样可以采取分组的方案。
- 选择随机整数k, 其中
- 计算一次性密钥:
- 对M按照下面的方法进行加密得到E(M) = ()
解密算法
- 计算K =
- M =
这么只有公式，可能是不好理解，下面来看一个具体的例子，采用的有限域就用GF(19), 然后生成元选择10，先来看一下对数表, 后面图中的有关指数的运算就不用每次都算了，相信手头没有计算器算一个幂还是比较费劲的:
离散对数表
如下图所示, Alice和Bob完成一次加密和解密:
![$OJ}BU2$_WOL9%~HKR]0{WP.png](https://ucc.alicdn.com/pic/developer-ecology/a1e3590dc25247369e386e807580cd2a.png?x-oss-process=image/resize,w_1400/format,webp "$OJ}BU2$_WOL9%~HKR]0{WP.png")
ElGamal加密过程
原理分析
先来看一下为什么, 先来回顾一下Diffie-Hellman的密钥交换算法，Alice和Bob想要最终交换密钥K, 在此之前Alice和Bob分别生成了两个随机的整数, , 然后分别计算, , 最终我们发现, 这样Alice和Bob完成了密钥交换，这里类似，如果令, 整个过程就完全一致了，详细证明过程可以参考之前的Diffie-Hellman的密钥交换协议一文，在这里就不证明了，至于这里为什么用k, 字母不重要蛤。
下面来解释一下为什么可以通过K来恢复明文:
积极攻击
这里采用ElGamal加密的时候要注意一个问题，就是每次随机选择的k一定要不一样，假设采用两个相同的k去加密消息，尽管可能对于消息, 是不同的，但是最终所使用的K是一样的，因此如果攻击者已知, 那么攻击者会轻松的计算出其他的块。
已知:
可以得到:
因此，如果已知M1, 那么可以计算得到:
代码实现
这里简单采用rust实现一下，只实现了算法的主体过程，有关如何去选择一个素数和获得他的原根，这里就不重复实现了，可以参考之前有关素数和离散对数的相关文章。
use num_bigint::{BigUint, RandBigInt}; use num_traits::{zero, one}; pub struct Elgamal {} pub struct PublicKey { alpha: BigUint, p: BigUint, y: BigUint, } pub struct PrivateKey { _alpha: BigUint, p: BigUint, x: BigUint, } #[derive(Clone, Debug, PartialEq)] pub struct ElGamalCiphertext { c1: BigUint, c2: BigUint, } pub fn mod_inv(u: &BigUint, v: &BigUint) -> BigUint { let mut q: BigUint; let mut t1: BigUint; let mut t3: BigUint; let (mut u1, mut u3, mut v1, mut v3) = (BigUint::from(1u8), u.clone(), BigUint::from(0u8), v.clone()); let mut iter: i8 = 1; while &v3 != &zero() { q = &u3 / &v3; t3 = &u3 % &v3; t1 = &u1 + &q * &v1; u1 = v1; v1 = t1; u3 = v3; v3 = t3; iter = -iter; } if &u3 != &one() { return zero(); } if iter < 0 { return v - u1; } u1 } impl Elgamal { fn encrypt(m: &BigUint, pk: &PublicKey) -> ElGamalCiphertext { let mut rng = rand::thread_rng(); let k = rng.gen_biguint_range(&BigUint::from(1u8), &(&pk.p - BigUint::from(1u8))); let key = pk.y.modpow(&k, &pk.p); let c1 = pk.alpha.modpow(&k, &pk.p); let c2 = (key * m) % &pk.p; ElGamalCiphertext { c1, c2, } } fn decrypt(ciphertext: &ElGamalCiphertext, sk: &PrivateKey) -> BigUint { let key = ciphertext.c1.modpow(&sk.x, &sk.p); let m = &ciphertext.c2 * mod_inv(&key, &sk.p) % &sk.p; return m; } } #[cfg(test)] mod test { use num_bigint::BigUint; use crate::elgamal::{PublicKey, PrivateKey, Elgamal}; #[test] fn test() { let p = BigUint::from(19u8); let alpha = BigUint::from(10u8); let x = BigUint::from(5u8); let y = alpha.modpow(&x, &p); let pk = PublicKey { p: p.clone(), alpha: alpha.clone(), y, }; let sk = PrivateKey { p: p.clone(), _alpha: alpha.clone(), x, }; let m = BigUint::from(17u8); let ciphertext = Elgamal::encrypt(&m, &pk); println!("{:?}", ciphertext); let plaintext = Elgamal::decrypt(&ciphertext, &sk); println!("{:?}", plaintext); } }
总结
本文所介绍的ElGamal仅仅是基本的原理，在实际的应用中，同样可以采用RSA的Padding方案，在明文消息当中填充一定数量的随机比特，这样基本可以避免掉上面所述的攻击形式，因为随机填充的内容，攻击者猜到的概率就非常低了，或者很难获取到已知明文对应的密文。
