-
-
[原创] 第十题 生命的馈赠 WP
-
2021-12-12 12:04
17680
-
这题一看文件还不小，但是ida打开基本没看到有用的东西。好在字符串都是明文，基本很容易就断住读取输入和输入判断的地方。但是很奇怪的是text段全程没用到，很让人怀疑里面藏了什么东西。
算法部分加了混淆，提取的过程没啥技术含量。根据运行速度看没有太复杂的运算量，所以只要F7一路跟下来，跟上几遍就梳理出来了。转成python代码如下：
1 2 3 4 5 6 7 8 9 10 11 | def Fun(a):
b = a * a
b = (b >> 128) * 0x1A994BC5D + (b & ((1<<128) - 1))
b = (b >> 128) * 0x1A994BC5D + (b & ((1<<128) - 1))
b = b * 0x6805A57D5B006445AC1B0675EB188435 + 0x4362F6846292652664A4CBBDC44FD283
b = (b >> 128) * 0x1A994BC5D + (b & ((1<<128) - 1))
b = (b >> 128) * 0x1A994BC5D + (b & ((1<<128) - 1))
b = b * b
b = (b >> 128) * 0x1A994BC5D + (b & ((1<<128) - 1))
b = (b >> 128) * 0x1A994BC5D + (b & ((1<<128) - 1))
return b
|
这是一个二次剩余的问题，sagemath基本是立等可解，而且基本每一步都是两个解。相应的代码如下
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | def sol(b):
p=2^128-0x1A994BC5D
R = Integers(p)
if not R(b).is_square():
return 0
tmp=mod(b,p).sqrt()
tmp =int(tmp)
tmp_p = p - tmp
tmp = (tmp-0x4362F6846292652664A4CBBDC44FD283)%p
tmp = (tmp * 203054504892225387319251330678447746504)%p
tmp_p = (tmp_p-0x4362F6846292652664A4CBBDC44FD283)%p
tmp_p = (tmp_p * 203054504892225387319251330678447746504)%p
if R(tmp).is_square():
return int(mod(tmp,p).sqrt())
if R(tmp_p).is_square():
return int(mod(tmp_p,p).sqrt())
return 0
|
但是因为最终结果是用户名的md5值，而不是前面算法生成的，所以实际上反推到第6步就进行不下去了。在这里纠结了好几天，最后才发现这两个常量是根据KCTF的md5值经过精心构造的，原运算还可能存在溢出的问题，手动把每一步可能溢出的情况考虑到，排除掉不会发生溢出的解，就是答案了。
[CTF入门培训]顶尖高校博士及硕士团队亲授《30小时教你玩转CTF》，视频+靶场+题目！助力进入CTF世界
