【密码学】公钥密码之ElGamal

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

Diffie-Hellman密钥交换协议

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

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

这里的离散对数问题，指的是：

• 已知a,b,n，计算abmodn是简单的。
• 已知a,(abmodn),n，计算b是困难的。

Diffie-Hellman密钥交换过程：

1. Alice和Bob选定一个素数p，以及它的一个原根g。
2. Alice选择一个密钥a，计算A=gamodp，发给Bob。
3. Bob选择一个密钥b，计算B=gbmodp，发给Alice。
4. Alice计算s=Bamodp，Bob计算s=Abmodp，这样，Alice和Bob就共享了一个密钥s=gabmodp。

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

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

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

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

• 中间人Eve假装自己是Bob与Alice通信 s1=gacmodp。
• 中间人Eve假装自己是Alice与Bob通信 s2=gbcmodp。
• Eve将Alice发来的消息用s1解密，使用s2加密，发送给Bob。
• Eve将Bob发来的消息用s2解密，使用s1加密，发送给Alice。
• Alice和Bob对此一无所知，还无知地以为在与对方通信。

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

ElGamal加密算法

ElGamal加密算法 - 维基百科

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

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

密钥生成：

1. Alice和Bob选定一个素数p，以及它的一个原根g。
2. Alice选择一个私钥XA，计算公钥YA=gXAmodp，公开
3. Bob选择一个私钥XB，计算公钥YB=gXBmodp，公开

假如Bob要给Alice发送一条消息m，加密过程：

1. Bob计算密钥k=(YA)XBmodp=gXAXBmodp
2. Bob发送c1=YB, c2=kmmodp

Alice收到密文，解密过程：

1. Alice计算密钥k=(c1)XAmodp=(YB)XAmodp=gXAYAmodp
2. Alice解密消息m=(c2⋅k−1)modp

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

耗子尾汁，好好反思。

赶快补上。

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