恢复未知椭圆曲线参数：基于采样点的射影三次拟合与Weierstrass化

题干

​

首先分析题干，主要是分析给出的几个定义。最开始的时候给定了大素数模数p，也就是说后续运算都在有限域 𝔽_p中进行

其中have定义了一个二元运算，它接受两个点的坐标，返回一个点的坐标，而且过程中的运算是通过多项式的乘逆这种形式实现的，因而根据其特征判断该函数类似于一个黑盒群加法

其中的fun函数，接受一个点的坐标，输出一个点的坐标，而且也是有理函数，在这里只看特征可能不好判断该函数的作用，可以暂时保留一下，先看下面的函数

这个have_fun函数是关键，它的结构与常规的ECC标准二进制标量乘，即double-and-add极其类似，但是初始值不是无穷远点而是g1点，据此可推测出，在这个黑盒群当中，g1即为单位元或承担单位元的作用

然后fun就与倍增函数类似，是用于计算一定倍数的给定点的。然后已知have_fun函数的实质之后可以把这个函数写成更加熟悉的形式， have_fun(g2, key) 就是平常遇到的key·g2

此时就可以对问题进行初步的定性了，本题中需要解决一个基本等价于椭圆曲线群的定义在𝔽_p上的代数群问题。然后给出了零元g1与生成元g2，给出小于2^54的随机数key，给出y=key·g2，需要求解key的值，也就是说需要解决一个DLP离散对数问题

然后解出来key之后就是拿来解决一个类似AES的问题，不过这里不知道为什么做的这么抽象。第一，key本来就小于2^54，相对于常见的来说偏小不够安全，其次还直接转字符取了前16位作为AES key，也就是说有效空间大致只有 log_2(10^16)≈16×3.32≈53.15 bit ，而且还不考虑key小于16位时导致的报错问题。

由于key的范围比较小，可以尝试考虑用BSGS算法，用该算法降低计算复杂度后应该理论上也是能解的，但是运算量还是比较大，所以在这里只示例一下如何用一种更加高级的方法来解决这个问题

我的整体思路是先将黑盒群拟合成为平面曲线，再把它等价变换到Weierstrass椭圆曲线上，也就是先恢复曲线方程，然后再用Sage内置的 discrete_log 函数解DLP，最后当成常规的AES解密得到flag

其中恢复曲线方程的一步是本题的核心所在，我将从以下几个方面展开论述一下为什么这一步要拟合一个三次齐次多项式F(X,Y,Z)=0

首先分析下已知的信息，给出的点是二元元组，所以这是平面代数群，群元素是 (x,y) ，其中x,y均属于𝔽_p，用的have_fun函数是标准的double-and-add标量乘，所以群是交换群，而have函数与fun函数即群运算都是由有理函数进行运算的。根据这些特点吗可以确定这是一个定义在有限域上的代数群一个定义在有限域上的代数群而非抽象群

其次元素由x,y两个坐标表示，但是两坐标取值并非自由，实际点明显落于低维度的子集当中，否则加法不封闭(这是阿贝尔交换群，对加法应该是封闭的)。因此这是一个一维代数群

而一维代数群主要分为以下三种，即加法群，乘法群以及椭圆曲线群。

对于加法群而言，该群上的标量乘应该是线性的，不可能构成本题的这种DLP问题，此外的，题目中的have函数包含乘法、除法、高次项，非线性，非仿射变换，所以显然不符合题意，可以排除

对于乘法群而言，乘法群的genus为0，是有理曲线，若是乘法群的话那么必然存在低次数的有理参数化，通过观察have函数能观测出来，在参数域里，应当只出现乘法和平方，不会出现大量混合的线性项和二次项的分式叠加

此外通过另一种方式也能证明，直接对椭圆曲线，也就是对平面三次曲线进行拟合，如果结果是光滑的三次方程，那么genus=1，是椭圆曲线方程，如果是奇异的三次方程，那么就是有理曲线，就很有可能是由乘法群跟加法群的变体

通过如下的sagemath脚本检测拟合到的曲线是否存在奇异点，得到返回结果为空，说明是光滑的，也可以确定本题中的曲线就是椭圆曲线，拟合到的就是正确的曲线方程

在此之前还有一个曲线拟合的具体过程，我这里是用插值implicitization的方法来做的

首先在利用have、fun和have_fun函数可以基于g2点生成一批候选的点，然后混合嵌套一下，保证数量足够多，分布足够分散，能够唯一确定一条低次数曲线，而不是只落在某一子群导致拟合退化

然后又有一个需要理解的细节，这是三次方程，而之前给出的坐标都是二维的 (x,y) ，并且群运算永远返回这种形式，这里我的理解是题目不是建立在完整曲线上的，而是对于建立在一个z不等于0的仿射片之上，因此有仿射坐标(x,y)=(x/z, y/z)，不妨取z=1

把每个采样点P=(x,y)代入射影点(X,Y,Z)=(x,y,1)，然后得到下式，其中只有c_i是未知量，m_i是 fit_projective_cubic 函数中的全部可能的10个齐次三次单项式基

也就是说，需要解决一个形式为M·c=0的方程，其中的c与M如下

只需用SageMath内置的 M.right_kernel 函数即可完成计算，该函数的作用是返回所有满足M⋅v=0的列向量v，也就是要求的向量c

求解完之后拟合得到一条曲线，此时可以用 K.dimesion 来确定一下，这里得到结果为1，说明除了整体倍数之外，只有这一条三次曲线能同时通过这些点，排除了偶然拟合的可能性

到这里我们就已经成功恢复曲线的方程了，到这一步可能有人会有疑问，为什么只拟合了三次项却能恢复完整的曲线方程，如果你也对此而困惑的话，不如将下式中的z换成1再看一看这是不是三次方程的标准式

以下是这一部分的完整sage代码实现

然后开始正式求解，第一步是把题目当中的点映射到这条椭圆曲线上面，也就是进行同构下的群元素对应。通过上个步骤求到的F为

这里需要做一步改写，写成了广义Weierstrass形式，因为这个方程并不是sagemath直接可用的标准形式，需要将式子左边的 Cy^2 变成 y'^2 这种标准形式，也就是说，需要把y^2前面的系数想方法变成1。这里引入一个量s，满足 s^2=-C ，那么就有 y'=s*y ，然后就可以将式子的左边变成 y'^2+(Bx+E)y'/s ，就得到了标准的椭圆曲线形式

这里还有一个点需要注意一下，这里C或-C必定是一个平方数，否则该曲线就不是椭圆曲线了(任何在𝔽_p上定义的椭圆曲线，都同构于某个Weierstrass形式)，只是一个普通的二次扭曲曲线，这里可以在代码里加一句验证一下

改写完之后用 E = EllipticCurve(Fp, [a1, a2, a3, a4, a6]) 就可以直接让sage识别这个椭圆曲线了，然后利用内置的函数将g1,g2和y映射到这个曲线上了，代码实现参考 Px = E(x[0], s*x[1])

这里也可以加一步验证一下，用assert检测这几个映射后的点是否在这个椭圆曲线E上

到这里就做好准备了，然后重新来整理问题，我们要解的其实就是这个式子

这是一个标准椭圆曲线离散对数问题，key区间在2到2^54之内，用已知区间的离散对数算法可以直接解出key，复杂度约为 O(2^27) ，完全是可行的。代码方面用内置的discrete_log函数就可以，指定边界bounds与算法(这里用的是lambda)

解出key之后先用have_fun函数验证一下g2与key的返回结果是否为y，然后按照加密逻辑生成AES key并解密AES即可得到flag