【密码学】公钥密码之ElGamal

Author Avatar
source. 12月 19, 2020
  • 在其它设备中阅读本文章

神奇的离散对数问题,老师提出了密钥交换,学生在此基础上提出公钥加密算法。

Diffie-Hellman密钥交换协议

迪菲-赫尔曼密钥交换 - 维基百科

迪菲-赫尔曼密钥交换(Diffie-Hellman key-exchange,DH)基于离散对数问题,可以让通信双方在完全没有对方任何预先信息的条件下,通过不安全信道创建一个密钥。于1976年首次发表。

这里的离散对数问题,指的是:

  • 已知$a,b,n$,计算$a^b\bmod n$是简单的。
  • 已知$a,(a^b\bmod n),n$,计算$b$是困难的。

Diffie-Hellman密钥交换过程:

  1. Alice和Bob选定一个素数$p$,以及它的一个原根$g$。
  2. Alice选择一个密钥$a$,计算$A=g^a\bmod p$,发给Bob。
  3. Bob选择一个密钥$b$,计算$B=g^b\bmod p$,发给Alice。
  4. Alice计算$s=B^a\bmod p$,Bob计算$s=A^b\bmod p$,这样,Alice和Bob就共享了一个密钥$s=g^{ab}\bmod p$。

通俗理解:在调色板上将两种颜色混合容易,而将两种颜色分开是困难的。

1200px Diffie Hellman Key Exchange.svg

由于离散对数问题是数学困难问题,在选择了合适的$p$和$g$时,Diffie-Hellman密钥交换协议被认为是「窃听安全」的。攻击者Eve在已知$p,~g,~(g^a\bmod p),~(g^b\bmod p)$的情况下,难以计算出$s=g^{ab}\bmod p$。

缺陷:无法抵抗中间人攻击

最初,DH本身没有提供任何身份认证,因此容易遭受中间人攻击。

  • 中间人Eve假装自己是Bob与Alice通信 $s_1=g^{ac}\bmod p$。
  • 中间人Eve假装自己是Alice与Bob通信 $s_2=g^{bc}\bmod p$。
  • Eve将Alice发来的消息用$s_1$解密,使用$s_2$加密,发送给Bob。
  • Eve将Bob发来的消息用$s_2$解密,使用$s_1$加密,发送给Alice。
  • Alice和Bob对此一无所知,还无知地以为在与对方通信。

因此,亟需一种能验证通信双方身份的机制(如签名)来防止这类攻击。

ElGamal加密算法

ElGamal加密算法 - 维基百科

ElGamal加密算法是一个基于DH的非对称加密算法(基于离散对数难题),于1985年被提出。

本质上就是用DH获得一个密钥,然后用它加解密消息。

密钥生成:

  1. Alice和Bob选定一个素数$p$,以及它的一个原根$g$。
  2. Alice选择一个私钥$X_A$,计算公钥$Y_A=g^{X_A}\bmod p$,公开
  3. Bob选择一个私钥$X_B$,计算公钥$Y_B=g^{X_B}\bmod p$,公开

假如Bob要给Alice发送一条消息$m$,加密过程:

  1. Bob计算密钥$k=(Y_A)^{X_B}\bmod p=g^{X_A X_B}\bmod p$
  2. Bob发送$c_1=Y_B,~c_2=km\bmod p$

Alice收到密文,解密过程:

  1. Alice计算密钥$k=(c_1)^{X_A}\bmod p=(Y_B)^{X_A}\bmod p=g^{X_A Y_A}\bmod p$
  2. Alice解密消息$m=(c_2\cdot k^{-1})\bmod p$

反思

那么多有关密码学的文章,怎么能没有DH和ElGamal呢?

耗子尾汁,好好反思。

赶快补上。

禁止商业用途,非商业分享转载请注明来源。
本文链接:http://comydream.github.io/2020/12/19/cryptography-dh-elgamal/