Diffie Hellman 密钥交换原理及ElGamal加密算法

密钥交换指的是两名用户在不安全信道中，在没有任何预先消息的情况下商量出一个密钥，从而建立一个安全信道。

Diffie和Hellman是两个人，他们在1976年发明了这个算法。

算法安全性基于离散对数问题：已知p是质数，g和x是整数，计算$y=g^x\ mod\ p$快。但是已知p，g，y，计算x很困难。

过程

1. Alice和Bob先选择一个质数p和一个整数g（公开）
2. Alice选择一个秘密整数a，计算$A=g^a\ mod\ p$，然后将A发送给Bob（A公开）
3. Bob选择一个秘密整数b，计算$B=g^b\ mod\ p$，然后将B发送给Alice（B公开）
4. Alice计算$K_a=B^a\ mod\ p=g^{ab}\ mod\ p$。
5. Bob计算$K_b=A^b\ mod\ p=g^{ab}\ mod\ p$。
6. 可知$K_a=K_b$

ElGamal加密算法

本原根

满足$a^m\equiv1(mod\ n)$，且$m=\phi(n)$，则$a$是$n$的本原根。

Elgamal加密算法是基于Diffie Hellman 密钥交换的非对称加密算法，过程如下：

1. 选择质数$p$，公开
2. 计算模$p$情况下的本原根$g$，公开
3. 选择整数$X_A<p$作为私钥
4. 计算公钥$Y_A=g^{X_A}\ mod\ p$
5. 设明文$M$，随机选择整数$k$，使$k$与$p-1$互质
6. 计算$C_1=g^k\ mod\ p$
7. 计算$C_2=(Y_A)^kM\ mod\ p$
8. 密文为$(C_1,C_2)$
9. 解密明文为$M=\frac{C_2}{C_1^{X_A}}\ mod\ p$