Make it Possible

ElGamal (一)实现

ElGamal算法的安全性是基于求解离散对数问题的困难性,于1984年提出,也是一种双钥密码体制,既可以用于加密又可用于数字签名。
假设p是一个大素数,并且p-1有大素因子,\alphaZ^{\ast}_p的生成元.,并且y\in Z^{\ast}_p,那么要寻找a,使\alpha^a\equiv y\pmod p是很难实现的,我们把a记为a=\log _{\alpha}{y}.

算法实现

我们先选取一个大质数p,取Z_p^\ast乘法运算生成元\alpha.
选取a,计算\beta = \alpha^a\pmod p
其中私钥为(a),公钥为(\alpha, \beta, p)
加密时选取一个随机数k,定义e_k(m,k) = (y_1,y_2)
其中y_1=\alpha^k\bmod p,\ y_2 = m\beta^k\bmod p=m\alpha^{ak}\bmod p
同时定义解密函数d_k(y_1,y_2)=m
m = y_2(y_1^a)^{-1}\bmod p
y_2(y_1^a)^{-1}\bmod p=m\alpha^{ak}(\alpha^{ak})^{-1}\bmod p=m

要求m就必须求(\beta^k)^{-1}\bmod p也就必须求\beta^k\bmod p=\alpha^{ak}\bmod p,从密文和公钥中可以获取到\beta=\alpha^a\bmod p,a^k\bmod p,但是并不能很快的求出\beta^k\bmod p

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据