首页
论坛
专栏
课程

[原创]第十题 开启时间之轮 wp

2019-6-24 12:34 1275

[原创]第十题 开启时间之轮 wp

2019-6-24 12:34
1275

程序对用户输入首先验证格式,必须是'.*XXXX[0-9]*',之后将XXXX的前后分为两个部分,就叫做input1和input2吧。输入数据经过处理传入到sub_404270函数里。这个函数做了主要的验证,函数的返回值传入sub_43770内。sub_43770会根据输入的二进制位'1'的个数选择解密不同的密文,当输入为0的时候,解密flag正确的密文,此时输入的flag正确。

首先需要明白sub_404270的参数。前两个参数没有实际作用,第三个参数v28由下图的do-while循环处理,表示输入的input1,input2和携带的另一个字符串cipher,同时v28还有进制,增加值和最大长度信息。v22是一个数组,在sub_404270中可以看到,v22表示了2^255-19这个素数。最后的输入v12和cipher组合起来用于验证,暂且叫int_v12。


接下来主要就是sub_404270。主要的验证有两个。

1. 按照题目所给的进制展开input1, input2,使其满足

x = input2 -input1

mod = 2^255-19

(3 + (x^2)%mod + (64x^4)%mod)%mod == input1

只要得到input1,就能通过GF上的多项式求根得到input2。在已知input1之后,同样用sage计算,秒出了input2的值。1548396171915056368526513804948765619094392315806578461796159505215278288254

2. check2的过程和RSA类似,不过只有一个素数。而且题目给出了p, 明文, 密文,需要获得RSA中的e和d。

input1 = base26(input1)

is_prime(input1)

e = input1

d = input1 ^ -1 (mod p-1)

int_v12 ^ e = cipher mod p

cipher ^ d = int_v12 mod p

这个题也可以看成是计算离散对数,已知cipher和int_v12,求e和d。求离散对数的算法bsgs的时间复杂度大概是​,正好对input1的最大长度有限制,计算一下发现可以解这个离散对数。于是用sage就解出来了。

from sage.groups.generic import bsgs

K = GF(2^255-19)
e = K.gen()

base = e * 38377684164112914669201831650756813551072223314592288217929947158283532270268
ans = e * 0x66

bsgs(base, ans, (0, 25**11))
用服务器跑了一会,得到了input1:79821823136933,做一下进制转化就得到了flag的第一段:KCTFREADYK

最后结合两段flag,得到最终的flag
KCTFREADYKXXXX1548396171915056368526513804948765619094392315806578461796159505215278288254




[公告]安全服务和外包项目请将项目需求发到看雪企服平台:https://qifu.kanxue.com

最新回复 (0)
游客
登录 | 注册 方可回帖
返回