看雪2022 KCTF 秋季赛 | 第二题设计思路及解析
2022-11-18 17:59:40 Author: mp.weixin.qq.com(查看原文) 阅读量:15 收藏

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

今日中午12点，第二题《盗贼作乱》已截止答题，共计围观人数3000+，
想必不少小伙伴对该赛题本身也充满兴趣，接下来和我一起来看看该赛题的设计思路和相关解析吧~

出题团队简介

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

赛题设计思路

一道简单的算法题，算法原型是：一个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()
最终flag为：ZSxZerX4xb4-jyvP7x12lI7
第三题《水患猖獗》比赛正在进行
https://bbs.pediy.com/thread-275204.htm
欢迎参与和围观

- End -

球分享

球点赞

球在看

戳“阅读原文”查看详情！

文章来源: https://mp.weixin.qq.com/s?__biz=MjM5NTc2MDYxMw==&mid=2458484331&idx=1&sn=25d81809434e06573694707cd8f6d1c6&chksm=b18e4ee186f9c7f70501b8319ab9a661d66d75cda03e5a9fc419ca68c38a1b5a3994d76e3176#rd
如有侵权请联系:admin#unsafe.sh