欢迎光临散文网 会员登陆 & 注册

对ElGamal加密方案的纠结

2023-07-23 17:40 作者:way_key  | 我要投稿

1. 正宗的ElGamal方案构造是书上12.16


图1

正宗的方案地位极高,又因为和DDH困难问题可以等价,常常被当做各种典范,没有二话。

2.  lifted 版本

据说是因为担心要加密的m不在群G中,还有是实现加法同态,为啥说加法同态更有用呢。

改变之处在加密和解密算法:

图2

最后一句话是说穷举吗?

成立的理由是:m是小数据,如果太大则根据离散对数问题是难解的。

这个问题就比较无赖,说能解密就能解密,说不会泄密就不会泄密。双重标准吗。大数据小数据怎么分开的?

3.  

还有一种变体是ECC-Elgamal,椭圆曲线上的版本。不过是乘法变加法,乘方变数乘。

密钥生成: 私钥 x, 公钥Y=xP。 P是椭圆曲线一点。

加密: (C1,C2)=(rP, m+rY),  m是曲线上一点

解密:m=C2-C1*x 

这也没毛病,只要m是曲线上一个点就行了。

4. 

如果m不是曲线上的点呢,如果m只是一个数值呢?有下列变体:

密钥生成: 私钥 x, 公钥Y=xP.  P是椭圆曲线一点。

加密: (C1,C2)=(rP, mP+rY) , m是一数值。

解密:mP=C2-C1*x,然后,为了解到m,还是要用攻击算法。也是合理的。

和版本2一样,感觉挺奇怪的,用攻击算法来解密?!

 

既然因为m不是一个点,那么把m转换成一个点,用版本3来解m行吗?因为曲线方程是公开的,把x=m代入曲线方程,求一个点(x,y)可以吗?用这个点去参与运算可行吗?是因为曲线点只取有限域上的?这个m不一定求出一个点来吗??那么找一个x坐标与m最接近的点来代替m进行运算,最后解密再倒回来。如果这样做,找一个与m最近的点,也得穷举?大概是这样。

 

之所以写出来,是因为看到不止一篇文章中有这种用攻击算法解密的例子,一直犯嘀咕。现在看来他们是对的,虽然看似不太磊落。







对ElGamal加密方案的纠结的评论 (共 条)

分享到微博请遵守国家法律