好耶!

花了半个月时间,把这题出了.但是毕竟题还是要自己做嘛,不能给脚本和flag.那就失去了学习的必要了.做题毕竟还是为了学习嘛,对吗?

先说这题.其他算法不必多说,文章将聚焦于其中素数域椭圆曲线的攻击,不提供题目相关思路和flag.

本文的代码在语法上不保证能够100%正确运行,所以请各位喜欢ctrl-c+ctrl-v的大师傅们用之前记得改一改啊...#(滑稽)

下文为方便,pollard-rho算法和pollard-kangaroo算法均简称为rho和kangaroo.

听说,有个工具叫sagemath.听说,他是用python写的.听说,核心代码是09年的.#(滑稽)

于是,我开始了逆向...

不行了,他的python代码一大堆注释,而且代码结构松散...老开源都这样...

这是修改后的rho(少量优化):

这是修改后的kangaroo(又叫lambda)(少量优化):

自动生成曲线测试下rho的速度...

好慢啊...

rho跑2^32域的速度大约为2秒一个,勉强能跑...

kangaroo范围大一点就出不来了...就不贴出来了...

不行不行...这怎么做题,题目的域可是2^64级的...

转成c先,部分算法采用汇编实现...

以下代码全部最大域限制为2^64...

整数除法,128位除以64位...

整数平方根...

齐次坐标转仿射坐标...

倍点...

倍点对应的c代码(不完全对应)...

点加...

点加对应的c代码(不完全对应)...

模n,模p 加,减,素数模乘法逆元...

模乘...

点乘标量...

kangaroo汇编版...

kangaroo c版...

由于kangaroo只有在高并发下才能发挥优势,所以上了线程池....我的机器是8核的,但是效果仍然不咋样...应该是并发数还是太少...

rho好多了,在我的机器上3秒钟能跑2^28级的数据256次,2^40的数据3次,10秒钟能跑2^48的数据一次.

传播安全知识、拓宽行业人脉——看雪讲师团队等你加入！