-
-
[原创]守株待兔
-
发表于: 2020-5-12 14:07 5808
-
1. 由题目给出两个定值求两个值猜测可能是椭圆曲线
2. 发现重构代码里有一部分用于求取类似斜率的值,理解了题目是要求取点key的两个坐标值,其中(2^8+1)key=point,point是点,有两个坐标值且已知
2.0 椭圆曲线更多知识参考https://www.cnblogs.com/qcblog/p/8998045.html
2.1 查找 椭圆曲线(Elliptic curve)的加法定义,最先发现python实现的Elliptic curve代码如下(ref:https://gist.github.com/bellbind/1414867,这里还有mul的定义,后续求解key要用到):
if p1.x == p2.x:
# p1 + p1: use tangent line of p1 as (p1,p1) line
l = (3 * p1.x * p1.x + self.a) * inv(2 * p1.y, self.q) % self.q#点p1==p2时,椭圆曲线定义的加法是该点切线与曲线的另一交点的对称点(或叫逆元)
pass
else:
l = (p2.y - p1.y) * inv(p2.x - p1.x, self.q) % self.q#点p1!=p2时,椭圆曲线定义的加法是p1与p2做直线与曲线的另一交点的对称点
pass
x = (l * l - p1.x - p2.x) % self.q
y = (l * (p1.x - x) - p1.y) % self.q
2.2 再利用重构代码通过两种方法实现4倍点的计算,一种是做两次倍点运算,一种是做一次倍点运算,再加两次本来的点,若相等,则可从另一个角度验证了就是椭圆曲线上的加法
3. 虽然以上都说明该题目是椭圆曲线上的问题,但是该题目的模数p并不是素数,那么为求取key=((2^8+1)^(-1))*point有两个思路,一个是分解模数p,然后按照一般方法求取椭圆曲线的阶,另一个是尝试实现Schoof-Elkies-Atkin Algorithm,直接求取阶,可参考https://people.cs.nctu.edu.tw/~rjchen/ECC2009/30_SchoofElkiesAtkin.pdf。
幸运的是,在factdb.com网址里直接把320比特长的大数p给分解了。分解了p后,可以在sage上直接求取有限域下的Weierstrass equation的阶(ref:https://doc.sagemath.org/pdf/en/reference/curves/curves.pdf page:103;https://en.wikipedia.org/wiki/Elliptic_curve),求取两个阶的最小公倍数视作我们这个题目的阶即可求取(2^8+1)^(-1),再计算((2^8+1)^(-1))*point就可得到key,这里用到了int与点的乘法,上文提到了一种实现方式,这里也可以自己实现椭圆曲线下的倍乘程序(原理与快速幂乘一样)。
第二种方法暂时还没有实现。
2. 发现重构代码里有一部分用于求取类似斜率的值,理解了题目是要求取点key的两个坐标值,其中(2^8+1)key=point,point是点,有两个坐标值且已知
2.0 椭圆曲线更多知识参考https://www.cnblogs.com/qcblog/p/8998045.html
2.1 查找 椭圆曲线(Elliptic curve)的加法定义,最先发现python实现的Elliptic curve代码如下(ref:https://gist.github.com/bellbind/1414867,这里还有mul的定义,后续求解key要用到):
if p1.x == p2.x:
# p1 + p1: use tangent line of p1 as (p1,p1) line
l = (3 * p1.x * p1.x + self.a) * inv(2 * p1.y, self.q) % self.q#点p1==p2时,椭圆曲线定义的加法是该点切线与曲线的另一交点的对称点(或叫逆元)
pass
else:
l = (p2.y - p1.y) * inv(p2.x - p1.x, self.q) % self.q#点p1!=p2时,椭圆曲线定义的加法是p1与p2做直线与曲线的另一交点的对称点
pass
x = (l * l - p1.x - p2.x) % self.q
y = (l * (p1.x - x) - p1.y) % self.q
2.2 再利用重构代码通过两种方法实现4倍点的计算,一种是做两次倍点运算,一种是做一次倍点运算,再加两次本来的点,若相等,则可从另一个角度验证了就是椭圆曲线上的加法
3. 虽然以上都说明该题目是椭圆曲线上的问题,但是该题目的模数p并不是素数,那么为求取key=((2^8+1)^(-1))*point有两个思路,一个是分解模数p,然后按照一般方法求取椭圆曲线的阶,另一个是尝试实现Schoof-Elkies-Atkin Algorithm,直接求取阶,可参考https://people.cs.nctu.edu.tw/~rjchen/ECC2009/30_SchoofElkiesAtkin.pdf。
幸运的是,在factdb.com网址里直接把320比特长的大数p给分解了。分解了p后,可以在sage上直接求取有限域下的Weierstrass equation的阶(ref:https://doc.sagemath.org/pdf/en/reference/curves/curves.pdf page:103;https://en.wikipedia.org/wiki/Elliptic_curve),求取两个阶的最小公倍数视作我们这个题目的阶即可求取(2^8+1)^(-1),再计算((2^8+1)^(-1))*point就可得到key,这里用到了int与点的乘法,上文提到了一种实现方式,这里也可以自己实现椭圆曲线下的倍乘程序(原理与快速幂乘一样)。
第二种方法暂时还没有实现。
[注意]传递专业知识、拓宽行业人脉——看雪讲师团队等你加入!
赞赏
他的文章
- [原创]第十二题 深入内核 4065
- [原创]第十一题 步步逼近 4527
- [原创]第八题 AI核心地带 3455
- [原创] 第七题 智能联盟计划 3625
- 第六题 至暗时刻 10390
看原图
赞赏
雪币:
留言: