i春秋"巅峰极客"2020密码学部分详解

文章目录

1. tryecc
   1. 题目信息
   2. 分析
   3. 解题
2. 后记

tryecc

题目信息

附件是一个sage脚本与一个文本文件，Gitee备份在此

分析

$$E_{1}: y^{2}\equiv x^{3}+ax+c\ \textrm{mod}\ N$$ $$E_{2}: y^{2}\equiv x^{3}+ax+b\ \textrm{mod}\ N$$

我们总结一下已知量和未知量：

已知	未知
$N,C,P_{1},P_{2},P_{3},P_{4}$	$A,B,m_{1},m_{2}$

那么已知$P_{1}(x_{1},y_{1}),P_{2}(x_{2},y_{2})$就可以计算出$a,b$：

$$y_{1}^{2}\equiv x_{1}^{3}+a\cdot x_{1}+c\ \textrm{mod}\ N$$ $$y_{2}^{2}\equiv x_{2}^{3}+a\cdot x_{2}+b\ \textrm{mod}\ N$$ $$a=(y_{1}^{2}-x_{1}^{3}-c)\cdot x_{1}^{-1}\ \textrm{mod}\ N$$ $$b=y_{2}^{2}-x_{2}^{3}-a\cdot x_{2}\ \textrm{mod}\ N$$

好在$x_{1}$在模$N$下有逆，于是$a,b$就可以解出，到此得到了$E_{1},E_{2}$；

$$P_{3}=m_{1}\cdot P_{2}\ in\ E_{2}$$ $$P_{4}=m_{2}\cdot P_{2}\ in\ E_{2}$$

丢到sgaemath里面去解离散对数，结果发现解不出来！

但是发现$N$不是素数，用yafu分解一下$N$，发现$N$是两个素数的乘积，记为$N=p\cdot q$，那么椭圆曲线$E_{2}$可重写为

$$E_{2}: y^{2}\equiv x^{3}+ax+b\ \textrm{mod}\ p\cdot q$$

这样$E_{2}$上的点也满足下面两个等式：

$$E_{p}: y^{2}\equiv x^{3}+ax+b\ \textrm{mod}\ p$$

即$E_{2}$上的点同时在$E_{p}$与$E_{q}$上(试了一下，我们可以求解$P_{3},P_{4}$在椭圆曲线$E_{p},E_{q}$上关于基点$P_{2}$的离散对数)

$$P_{3}=m_{1}\cdot P_{2}\ in\ E_{2}$$

则有：

$$P_{3}=m_{1}\cdot P_{2}\ \ in\ E_{p}$$ $$P_{3}=m_{1}\cdot P_{2}\ \ in\ E_{q}$$

那是不是意味着我们解出$P_{3}$在椭圆曲线$E_{p}$上关于基点$P_{2}$的离散对数就是$m_{1}$呢？非也！我们解出的只是$m_{1}\ \textrm{mod}\ order_{E_{p}}(P_{2})$，即$m_{1}$模了$P_{2}$在椭圆曲线$E_{p}$上的阶之后的值！

要想解出$m_{1}$，需要将$P_{3}$在椭圆曲线$E_{p},E_{q}$上关于基点$P_{2}$的离散对数结合起来！

$$m_{1}\equiv s_{p}(1)\ \textrm{mod}\ order_{E_{p}}(P_{2})$$ $$m_{1}\equiv s_{q}(1)\ \textrm{mod}\ order_{E_{q}}(P_{2})$$

这里$s_{p}(1),s_{q}(1)$分别是$P_{3}$在椭圆曲线$E_{p},E_{q}$上关于基点$P_{2}$的离散对数；

使用中国剩余定理解上述方程组即可解出$m_{1}$，同理解出$m_{2}$

解题

上述链接中的solve.sage为解题的脚本；程序运行结果如下(运行时间有点长，稍微等一下)：

$ sage solve.sage
  ***   Warning: increasing stack size to 2000000.
flag{de7a89ab1d074ef3930fb3054c0e3ac8}

后记

一直在等师傅们关于密码学题目的writeup，结果一直没有找到；就只能把自己唯一做出来的一道题目的writeup写一下。