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

本文最后更新于:2022年7月21日 下午

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$