首页
论坛
课程
招聘
[原创] 第十题 生命的馈赠 WP
2021-12-12 12:04 16129

[原创] 第十题 生命的馈赠 WP

xym 活跃值
4
2021-12-12 12:04
16129

这题一看文件还不小,但是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值经过精心构造的,原运算还可能存在溢出的问题,手动把每一步可能溢出的情况考虑到,排除掉不会发生溢出的解,就是答案了。


【公告】 讲师招募 | 全新“预付费”模式,不想来试试吗?

收藏
点赞0
打赏
分享
最新回复 (0)
游客
登录 | 注册 方可回帖
返回