基于Elgamal 的同态加密 基于同态加密的图像编辑

上文我们演示了加法同态最后我们让大家自己构造一个函数实现乘法同态

这里我们给大家一个例子

加密函数E= x^3

E(a) * E(b) = a^3 * b^3 = (a*b)^3 = E(a*b)

上面的例子同样不安全, 只是做到了同态没有加密. 今天介绍的基于Elgamal的方法就是乘法的同态加密. 我们可以回头看一下 Elgamal加密

我们来看Elgamal 加密流程

公钥Public Key (Y, g, p) Y = g^x mod p

私钥 x

加密流程 (r 是随机数 M 是message)

a = g ^ r mod p

b = Y^ r * M mod p

所以加密函数我们可以写成

E(g^r, Y^r*M)

现在我们来验证是否符合同态乘法
E(m1) * E(m2) = E(g^r1, Y^r1* m1) * E(g^r2, Y^r2 * m2) = E(g^(r1+r2), Y^(r1+r2) * (m1*m2)) = E(g^r3, Y^r3*m)

所以Elgamal 是符合同态乘法的

我们知道乘法和除法是逆运算, 所以Elagmal 也是可以支持同态除法的. 但是Elgamal 是基于离散对数问题 提出的一套非对称加密体系. 仅支持正整数, 同样除法也仅支持可以整除的情况. 感兴趣的可以自己用python 去验证一下