[MoeCTF 2021]ez_Algorithm

程序逻辑并不复杂，只有一个fuck函数

问题就出在这个fuck函数，它是一个递归函数

在运行时会无限递归导致程序卡死

仔细观察fuck函数

发现结构为fuck(a1) = fuck(a1 - 1) + 2 * fuck(a1 - 2)

可以将递归要用到的每一个 a1 值都存在数组里面

用一个大数组(递推)来代替递归

a1小于等于1时(0, 1) 直接返回a1(0, 1)

因此最小为2，最大为75 * 75 = 5626 + 1

a = [0,1] for i in range(2,5626): a.append(a[i-1] + 2 * a[i-2]) flag = [0x6d, 0x6e, 0x60, 0xc8, 0x5521, 0xaaaacd, 0x5555552e, 0xaaaaaa9f, 0x55555533, 0xaaaaaa9c, 0x55555566, 0xaaaaaad9, 0x5555550a, 0xaaaaaaca, 0x55555564, 0xaaaaaa9a, 0x5555550a, 0xaaaaaa9c, 0x5555553d, 0xaaaaaa9a, 0x55555526, 0xaaaaaaf4, 0x55555562, 0xaaaaaa9a, 0x55555538, 0xaaaaaa98, 0x5555552b, 0xaaaaaaef, 0x55555565, 0xaaaaaaf4, 0x5555552c, 0xaaaaaa9b, 0x55555520, 0xaaaaaaf4, 0x55555527, 0xaaaaaa98, 0x55555534, 0xaaaaaa9a, 0x55555564, 0xaaaaaad1, 0x55555566, 0xaaaaaaf4, 0x55555562, 0xaaaaaac3, 0x55555566, 0xaaaaaaf4, 0x55555538, 0xaaaaaa98, 0x55555534, 0xaaaaaac5, 0x55555564, 0xaaaaaac5, 0x55555532, 0xaaaaaaf4, 0x55555565, 0xaaaaaacd, 0x5555550a, 0xaaaaaaff, 0x55555564, 0xaaaaaac6, 0x55555566, 0xaaaaaaf4, 0x55555536, 0xaaaaaa9b, 0x55555538, 0xaaaaaadb, 0x55555564, 0xaaaaaa98, 0x5555552d, 0xaaaaaa9a, 0x55555562, 0xaaaaaad2, 0x5555556a, 0xaaaaaa94, 0x5555556a, 0xaaaaaad6, 0x0, 0x0, 0x0, 0x0] for i in range(76): print(chr((a[i * i] ^ flag[i]) & 0xFF), end="")

moectf{4f73r_a11_7h1s_71m3~D0_y0u_r3a11z3_7h3_m3an1ng_0f_T1m3_c0mp13x17y???}

总结

程序使用了递归函数，并且靠大数值使得运行指数级递归导致卡死，逆向时必须用递推代替递归