对ElGamal加密方案的纠结
1. 正宗的ElGamal方案构造是书上12.16

正宗的方案地位极高,又因为和DDH困难问题可以等价,常常被当做各种典范,没有二话。
2. lifted 版本
据说是因为担心要加密的m不在群G中,还有是实现加法同态,为啥说加法同态更有用呢。
改变之处在加密和解密算法:

最后一句话是说穷举吗?
成立的理由是: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最近的点,也得穷举?大概是这样。
之所以写出来,是因为看到不止一篇文章中有这种用攻击算法解密的例子,一直犯嘀咕。现在看来他们是对的,虽然看似不太磊落。