【密码学】公钥密码之 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 加密算法 - 维基百科
T. ElGamal. A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms. CRYPTO ’84
T. ElGamal. A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms. TIT ’85

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$

本文采用 CC BY-NC-SA 4.0 许可协议,转载请注明来自 ComyDream
本文链接:http://comydream.github.io/2020/12/19/cryptography-dh-elgamal/