看雪 2022·KCTF 秋季赛第二题盗贼作乱 WP

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

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，似乎从理论上不太成立。转机在于大数运算的乘和除函数的后半段，伪代码如下：

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	`31x` `=` `1` `(mod n)` `31y` `=` `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()