看雪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