基于DH的ElGamal 加密 dh加密算法安全吗

我们先来看wiki 对Elgamal 的概括. In cryptography, the ElGamal encryption system is an asymmetric key encryption algorithm for public-key cryptography which is based on the Diffie–Hellman key exchange (基于DH的非对称加密算法)

我们来看ElGamal加密流程,又是如何基于DH 实现的

1. 先会看DH 的流程

g, p 是协商的, 我们可以认为是public key. x 可以认为是private key

有了这个初步认识 我们再看Elgamal. g, p 都是public key

我们推倒一下 这个式子是否正确

M = b / a^x
= Y^k * M / (g^k)^x
= (g^a)^k * M /(g^k)^x
= g^ak * M / g^ak
= M

最后我们举例说明

p = 1009, g= 11

注意最后一点M 的计算是在乘法群 mod p上的操作, 跟我们普通乘法略微不同

之前我们在推倒的时候都把mod操作去掉了但在具体计算的时候都要加上
我们先看178^447
178 ^ 447 = 178^447 mod 1009 = 986

我们知道除法就是乘法的倒数, 我们普通乘法就是ab=1, ab 互为倒数. 在这里略微不同, 要求ab mod p = 1

986 的倒数(这种说法不太标准为了理解) = 658

986 * 658 mod 1009 == 1

M = 549 / 986  mod 1009 =  549 * 658 mod 1009 =  20 

上述过程我们用python 计算一下

import libnum

ax = libnum.invmod(pow(178, 447, 1009), 1009)   # 658

M = 549 * 658 % 1009