首页
社区
课程
招聘
[原创]CTF 2019Q2 readyu crackme 设计思路
发表于: 2019-5-4 19:34 6297

[原创]CTF 2019Q2 readyu crackme 设计思路

2019-5-4 19:34
6297

算法基于二次剩余与离散对数, 建立了2个方程 (1) (2)  见下文。并且模同一个素数。所以暂定取名 “一石二鸟”。

本题算法主要涉及公钥密码学的基础知识。 Win32程序, 无壳, 无Anti。 暂定取名 “一石二鸟”。
(2) 方程

算法基于二次剩余与离散对数, 建立了2个方程 (1) (2)  见下文。并且模同一个素数。所以暂定取名 “一石二鸟”。

P=2^255-19 是一个素数, base16 或者base10如下:
G^d = Y  mod P      ... (2)
G,Y 是已知数, 范围 [ 1, P-1]:

[培训]内核驱动高级班,冲击BAT一流互联网大厂工作,每周日13:00-18:00直播授课

最后于 2019-6-24 18:07 被kanxue编辑 ,原因:
上传的附件:
收藏
免费 3
支持
分享
最新回复 (5)
雪    币: 11705
活跃值: (975)
能力值: ( LV12,RANK:779 )
在线值:
发帖
回帖
粉丝
2
解压密码为 readyu2019q2

附件是 基于miracl运算库的 Pollard's kangaroos 方法求 离散对数源代码以及编译好可运行的demo,  验证输出如下:
( 比赛结束以后公布)

算法描述见 wiki :
https://en.wikipedia.org/wiki/Pollard%27s_kangaroo_algorithm

LIMIT64 = 95367431640625 , LEAPS= 9765626
solve discrete logarithm problem - using Pollard's kangaroos
find d in:  y = g^d mod n, given(y, g , n), if: d < 64 bits

y= 100
g= 9230197858975018299629857977411527954550899478307510809210520967346958600039
n= 57896044618658097711785492504343953926634992332820282019728792003956564819949

setting trap ....

trap set! jumps = 9765626
Time cost 18 seconds 362ms

speed 531 K/s

Gotcha! Time  cost 39 seconds 266 ms

jumps = 21326452, speed = 543 K/s

Discrete log: d =
79821823136933

最后于 2019-5-5 09:57 被readyu编辑 ,原因:
上传的附件:
2019-5-4 19:36
0
雪    币: 10868
活跃值: (3282)
能力值: (RANK:520 )
在线值:
发帖
回帖
粉丝
3
初步检查正常
2019-5-5 12:30
0
雪    币: 11705
活跃值: (975)
能力值: ( LV12,RANK:779 )
在线值:
发帖
回帖
粉丝
4
补充说明:
G^d = Y  mod P      ... (2)
d=4898F769D4A5
这个d碰巧有个特点: d = ED970F * 4E390B
因此题目里加上一个条件判断:d不含0xFFFF 内的小素数因子。

其实这个判断是可有可无的。
2019-6-24 10:49
0
雪    币: 10845
活跃值: (1054)
能力值: (RANK:190 )
在线值:
发帖
回帖
粉丝
5
数学功底真好
感觉这才是好出题方式,值得学习
2019-6-25 10:58
0
游客
登录 | 注册 方可回帖
返回
//