![]()
-
-
[原创]看雪 2022·KCTF 秋季赛 第二题 盗贼作乱 WP
-
1天前
109
-
[原创]看雪 2022·KCTF 秋季赛 第二题 盗贼作乱 WP
题目把输入以-分成两部分，以62进制数转换成自定义的大数结构，最后通过两个等式验证结果：
1 2 3 | a*x -1 = x (mod n)
b*y +1 = y (mod n)
n = 10000000000000000000
|
相当于：
1 2 | (a-1)*x = 1 (mod n)
(b-1)*y = n-1 (mod n)
|
但是程序要求两个式子的成立次数总和为10，且总循环次数也有要求，远小于n，似乎从理论上不太成立。转机在于大数运算的乘和除函数的后半段，伪代码如下：
1 2 3 4 5 6 7 8 9 | 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时等式是可解的，此时的等式成为：
1 2 | 31*x = 1 (mod n)
31*y = n-1 (mod n)
|
解算代码如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | 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
看雪招聘平台创建简历并且简历完整度达到90%及以上可获得500看雪币～
文章来源: https://bbs.pediy.com/thread-275204.htm
如有侵权请联系:admin#unsafe.sh