elliptic_encoding

问题发现

最近在实现一个椭圆曲线加密算法[1]时遇到一个问题，就是如下图，$m$是待加密的二进制信息，想要对其加密，就必须先将其转化为椭圆群上的一个点，以参与之后的运算。

那么问题来了，如何设计一个方案，在不消耗过多计算资源的情况下，使得二进制的消息能够和椭圆群中的元素进行一一对应呢？

不可用的方案

编码为x

最直观的想法是将$m$看成很大的二进制整数，然后调用JPBC库的setFromByteX将其看成点的横坐标，JPBC库会自动求出其纵坐标。想法很美好，但是当时没想到一件事，就是椭圆曲线上的点是有限的、离散的，对于下面这个椭圆曲线的公式，并不是对于所有x都可以求出一个y。

$$y^2 \equiv x^3+ax+b$$

也就是并不是所有的$x$都是二次剩余的，所以该方法作罢。

哈希

发现JPBC库的setFromHash可以保证得出来的元素一定是合法的，然而哈希的话就无法解密，解密出来的也只能是哈希之后的值，也作罢。

幂运算

素数阶上每个点都是循环元，所以可以考虑取一个循环元$g$，然后把$m$编码成一个大整数$k$，以$g^k$来代替$m$运算。

这样正向编码是没有问题的，但是反向编码就意味着要从$g^k$求出$g$，这相当于解决椭圆曲线的离散对数问题，也作罢。

可用的方案

硬编码

使用打表的方法，每$w$位编码为一个单位，然后逐个查表进行编码。

该方法是可行的，但是还是有一定短板：

1. 一个消息不得不被编码为多个元素
2. 如果$w$太小，就会编码出很多元素，占用过多空间，运算也复杂
3. 如果$w$太大，则表的长度过长，也会影响效率

Sengupta的方案[2]

做法是这样的，在原来的消息后面填充$n$个0，成为$m'$，然后正常执行编码操作。如果发现$m'$编码成的横坐标不是二次剩余的，那么就令$m'$自增一个单位，直至横坐标是二次剩余的为止。

解码也很简单，将$x$坐标解密成$m'$，然后把最后的$n$位去除即可。

论文中对$n$的选择进行了探讨，毕竟$n$取小了的话接下来的$2^n$个数可能都找不到一个二次剩余的。众所周知，椭圆曲线中合法点的横坐标不是完全均匀分布的，但是毕竟椭圆群是一个有限群，肯定存在一个相邻合法点坐标的最大间隔。根据前人的实验，可以得知没有两点之间横坐标的间隔超过$2^8=256$，所以$n=8$是一个保险的值。

参考文献

[1]W. Li, W. Susilo, C. Xia, L. Huang, F. Guo and T. Wang, “Secure Data Integrity Check Based on Verified Public Key Encryption With Equality Test for Multi-Cloud Storage,” in IEEE Transactions on Dependable and Secure Computing, vol. 21, no. 6, pp. 5359-5373, Nov.-Dec. 2024, doi: 10.1109/TDSC.2024.3375369.

[2]Sengupta, A., and Ray, U. K. (2016) Message mapping and reverse mapping in elliptic curve cryptosystem. Security Comm. Networks, 9: 5363–5375. doi: 10.1002/sec.1702.