看雪2022 KCTF 秋季赛 | 第二题设计思路及解析

WriteUp 2年前 (2022) admin

634 0 0

看雪 2022 KCTF秋季赛 已于11月15日中午12点正式开始！比赛延续上一届的模式并进行优化，对每道题设置了难度值、火力值、精致度等多类积分，用规则引导题目的难度和趣味度。大家请注意：签到题将持续开放，整个比赛期间均可提交答案，获得积分哦～

今日中午12点，第二题《盗贼作乱》已截止答题，共计围观人数3000+，

想必不少小伙伴对该赛题本身也充满兴趣，接下来和我一起来看看该赛题的设计思路和相关解析吧~

出题团队简介

第二题《盗贼作乱》出题方 HU1 战队，战队成员id：lelfei

看雪2022 KCTF 秋季赛 | 第二题设计思路及解析

赛题设计思路

一道简单的算法题，算法原型是：一个num范围内的数n，自我累加cnt次后，模num结果与原数相差1，问这个数是多少？

解法为：累加cnt次后，为什么会出现模n与原数相差1呢，是因为累加cnt-1次时，结果应为num*x+1或num*x-1，由于n<num，累加cnt-1次时n*(cnt-1)<num*(cnt-1)，可以得到x<=cnt-1，可以编程检测在范围(1,cnt)中的x，判断num*x+1或num*x-1能否被cnt-1整除，只需要检测cnt次：

sbase = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz'def baseConv(a):    s = ''    l = len(sbase)    while(a > 0):        s += sbase[a % l]        a //= l    return sdef calc(num, cnt):    for x in range(1, cnt):        if (num * x + 1) % (cnt - 1) == 0:            n = (num * x + 1) // (cnt - 1)            print(n, x, "+1", baseConv(n))        if (num * x - 1) % (cnt - 1) == 0:            n = (num * x - 1) // (cnt - 1)            print(n, x, "-1", baseConv(n))

这里取num=10**19，cnt=32，计算calc(10**19, 32)结果为：

3870967741935483871 12 +1 ZSxZerX4xb46129032258064516129 19 -1 jyvP7x12lI7

故此题答案为ZSxZerX4xb4-jyvP7x12lI7。

程序实现时，获取用户输入的key并用“-”切分成二部分，按62进制转换成2个大数sn1和sn2，再指定一个初始化大数num=(b62)IRtzloZ6iuB=10**19，要求sn1<num、sn2<num、sn1<sn2，然后循环0x200000次对sn1和sn2累加，当出现模num结果与sn1、sn2相差1时flag值增加1，发现flag为10时注册成功。然后在大数计算的二个函数BigNumMul和BigNumDiv中，发现flag>0时，检测循环次数，当正好是31时再分别把flag增加4，达到注册成功条件。在大数计算的函数中有一些干扰计算，分析时跳过即可。

此题难点在于分析过程，由于范围num和累加次数cnt与注册码没有明显联系，需要分析数的特性并用脚本穷举。只需要分析出对于给定的num和cnt，符合累加模num结果与原数相差1的数可以简单计算出来，就可以轻松求解。

程序在VC6+WIN7中编译通过。

key: ZSxZerX4xb4-jyvP7x12lI7

赛题解析

本赛题解析由看雪论坛会员 poyoten 给出：

题目把输入以-分成两部分，以62进制数转换成自定义的大数结构，最后通过两个等式验证结果：

a*x -1 = x (mod n)b*y +1 = y (mod n)n = 10000000000000000000

相当于：

(a-1)*x = 1 (mod n)(b-1)*y = n-1 (mod n)

但是程序要求两个式子的成立次数总和为10，且总循环次数也有要求，远小于n，似乎从理论上不太成立。转机在于大数运算的乘和除函数的后半段，伪代码如下：

BN_new_int_401630(&g_temp_1_40A988, 4);BN_lshift_4023A0(&g_temp2_40A9AC, &g_temp_1_40A988, 3);if ( count_r_40A9F8 > 0 && *&bn_const_40A9D0._data[g_temp2_40A9AC._data[0]] == g_temp2_40A9AC._data[0] ){  BN_add_401730(&g_temp_1_40A988, &g_temp_1_40A988, &g_temp2_40A9AC);  v13 = BN_mod_int_402360(&g_temp_1_40A988, g_count_40A9F4);  bn_const_40A9D0._data[g_temp_1_40A988._data[0]] += 4;  BN_lshift_4023A0(&g_temp_1_40A988, &g_temp_1_40A988, v13);  BN_sub_401820(&g_temp2_40A9AC, &g_temp_1_40A988, &g_temp2_40A9AC);

此处在循环为32次的时候，可以使等式成立次数加4，如果两个函数都触发一次，正好等式成立次数为10，且经计算，a,b都为32时等式是可解的，此时的等式成为：

31*x = 1 (mod n)31*y = n-1 (mod n)

解算代码如下：

import gmpy2 t = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz' def int_2_64(n):    out = ''    while True:        out += t[n%62]        n /= 62        if n == 0:            break    return out def main():    n = 10000000000000000000    x = gmpy2.invert(31,n)    for i in range(100):        if (i*n-1) % 31 == 0:            break    y = (i*n-1) / 31    print int_2_64(x)+'-'+int_2_64(y) if __name__ == '__main__':    main()