【密码学】基于椭圆曲线的半同态加密算法

之前一篇文章当中，我们介绍了Paillier的半同态加密方案，这一篇文章呢，我又来水文章了，我们来看一下，基于椭圆曲线离散对数的半同态加密算法，同样的，这个算法本身还是来源于铜锁(Tongsuo)这一个库。

前言

本文需要一点点椭圆曲线的知识，有关椭圆曲线呢，我在其他的文章当中已经讲过了，因此呢，这一篇文章又是一篇比较好水的文章，不熟悉的读者可以翻一翻我之前写的椭圆曲线的介绍。

前置知识

因为，这个算法用到了ECDLP问题的求解，这里先简单介绍一下ECDLP问题的求解方案，因为这里用到的曲线，一定不会采用不安全的曲线，因此，之类考虑通用的方案，不考虑特殊的曲线攻击方案，如果读者有兴趣，可以自行查阅一下相关资料，这里只介绍Pollard's Rho的方案。

在Pollard's Rho方案当中，我们需要找到两组数字(a, b)和使得满足如下等式

其中P和Q是我们已知的点，我们最终的目标是找到一个x使得如下等式成立

找到，上述等式结果后，我们可以很轻松的利用椭圆曲线运算性质来得到x，具体推导过程如下

消掉P我们很容易得到最终的x

接下来，我们来看一下Pollard's Rho算法的具体过程。

• 生成一系列随机的点其中，每个点满足

为什么要定义一个序列呢，核心是因为，我们需要用到前一个点来确定下一个点。这样，我们会在序列中得到一个循环，也就是，我们一定可以找到一个和一个其中使得，至于为什么，因为我们是再有限域当中做运算，而序列是无限的，因此，我们必然会得到循环，一旦触发循环，那么问题就变得简单多了，我们就可以用之前的知识来得到x。

接下来，我们一起来看一下，如何有效的拿到那个循环，这里就要用到另一个算法，Floyd's环检测算法，他还有另外一个名字叫快慢指针法，或者叫做龟兔赛跑法，有关这个算法呢，其实并不是我们本文的一个重点，那么我们简单的提一下。

Floyd's环检测算法核心就是我们可以通过不同的速度在一个序列当中同时并排的走，当两个指针对于不同的整数找到同一个点的时候，我们问题就解决了。

算法过程

接下来，简单的描述一下算法的过程吧，这个其实要比Paillier要简单不少。

参数

• G: 椭圆曲线的基点
• d: 私钥(SK)，0到椭圆曲线的阶之间的随机数
• dG: 公钥(PK)，也就是计算的倍点

加密过程

• 密文:

解密过程

• 计算mG的ECDLP， 获取明文m，从这里看出，我们需要求解ECDLP, 因此这个m不能太大，否则会解不出来。

同态运算

假设有两个密文

密文加法

标量乘法

假设，另一个明文a，我们可以得到标量乘法的运算

总结

这个，因为主要是点的运算，其实并不太涉及太多数学的原理，不过在运算过程中要求解ECDLP问题，虽然限制了，我们可以取比较小的m，来使我们可以得到结果，但是总感觉还是差点啥，好了，水文一篇，溜了溜了。

参考资料

• https://www.yuque.com/tsdoc/misc/ec-elgamal
• https://andrea.corbellini.name/2015/05/17/elliptic-curve-cryptography-a-gentle-introduction/