rctf2018 babyre2 | Stay foolish,stay hungry!

逻辑

scanf(“%127s”, &v7)
strcpy(s, “Welcome to RCTF 2018! Here is a BabyRE challenge for you.”)

sub_400BA0(unsigned int128 a1, unsigned int64 a2, unsigned __int64 a3):
if ( a2 <= a1的高64位)
{
if ( !a2 )
v3 = 1 / 0uLL; (_QWORD )&v17 = a1; ((_QWORD )&v17 + 1) = ((_QWORD *)&a1 + 1) % v3;
v5 = v17 % v3;
}
else //大概率会走此处，因为a2为0xFFFFFFFFFFFFFFC5
{
v5 = a1 % a2;
}
result = v5;
}
return result;

(_QWORD )&v39(64bit) = sub_400BA0(v7 (unsigned __int128)(unsigned __int64 *)s, 0xFFFFFFFFFFFFFFC5LL, 0LL);
假如输入为abcdefghij… v7为前八个字符的小端ascii值(hgfedcba)的ascii码乘以( emocleW)也就是Welcome 的小端ascii值
v39和v39+1一起组成128位int
v8是输入的第二组八个字符，v24是”Welcome to RCTF 2018! Here is a BabyRE challenge for you.”的第二组八个字符
后面依次类推

((_QWORD )&v39 + 1) = sub_400BA0(v8 (unsigned __int128)v24, 0xFFFFFFFFFFFFFFC5LL, 0LL);
v40.m128i_i64[0] = sub_400BA0(v9 (unsigned int128)v25, 0xFFFFFFFFFFFFFFC5LL, 0LL);
v40.m128i_i64[1] = sub_400BA0(v10 * (unsigned int128)v26, 0xFFFFFFFFFFFFFFC5LL, 0LL);
(_QWORD )&v41 = sub_400BA0(v11 (unsigned __int128)v27, 0xFFFFFFFFFFFFFFC5LL, 0LL); ((_QWORD )&v41 + 1) = sub_400BA0(v12 (unsigned int128)v28, 0xFFFFFFFFFFFFFFC5LL, 0LL);
(_QWORD )&v42 = sub_400BA0(v13 * (unsigned int128)v29, 0xFFFFFFFFFFFFFFC5LL, 0LL);
((_QWORD )&v42 + 1) = sub_400BA0(v14 (unsigned __int128)v30, 0xFFFFFFFFFFFFFFC5LL, 0LL); (_QWORD )&v43 = sub_400BA0(v15 (unsigned int128)v31, 0xFFFFFFFFFFFFFFC5LL, 0LL);
((_QWORD )&v43 + 1) = sub_400BA0(v16 * (unsigned int128)v32, 0xFFFFFFFFFFFFFFC5LL, 0LL);
(_QWORD )&v44 = sub_400BA0(v17 (unsigned __int128)v33, 0xFFFFFFFFFFFFFFC5LL, 0LL); ((_QWORD )&v44 + 1) = sub_400BA0(v18 (unsigned int128)v34, 0xFFFFFFFFFFFFFFC5LL, 0LL);
(_QWORD )&v45 = sub_400BA0(v19 * (unsigned int128)v35, 0xFFFFFFFFFFFFFFC5LL, 0LL);
((_QWORD )&v45 + 1) = sub_400BA0(v20 (unsigned __int128)v36, 0xFFFFFFFFFFFFFFC5LL, 0LL);
v46.m128i_i64[0] = sub_400BA0(v21 (unsigned int128)v37, 0xFFFFFFFFFFFFFFC5LL, 0LL);
v3 = sub_400BA0(v22 * (unsigned int128)v38, 0xFFFFFFFFFFFFFFC5LL, 0LL);
v4 = _mm_load_si128((const __m128i *)&v39); // v39=7BA58F82BD8980352B7192452905E8FB
v46.m128i_i64[1] = v3;

限制条件
//v3=0x55555555555559A3
v39=7BA58F82BD8980352B7192452905E8FB
v46=55555555555559A355555555555559A3
v45=55555555555559A355555555555559A3
v44=55555555555559A355555555555559A3
v43=55555555555559A355555555555559A3
v42=0AAAAAAAAAA975D1CA2845FE0B3096F8E
v41=0DCDD8B49EA5D7E14ECC78E6FB9CBA1FE
v40=163F756FCC221AB0A3112746582E1434

猜测sub_400BA0就是取余 因为大部分情况下会走< 0xFFFFFFFFFFFFFFC5的条件

解题脚本

逆出来很容易，128位算术我佛啦。

z3和爆破都不用想了

后来师傅告诉我可以乘法逆元，膜

def fastExpMod(b, e, m):
    result = 1
    while e != 0:
        if (e&1) == 1:
            # ei = 1, then mul
            result = (result * b) % m
        e >>= 1
        # b, b^2, b^4, b^8, ... , b^(2^n)
        b = (b*b) % m
    return result

def r(d,b):
	c = 0xFFFFFFFFFFFFFFC5
	s=d*fastExpMod(b,(c-2),c) % c
	return s

print hex(r(0x2B7192452905E8FB,0x20656D6F636C6557))[2:-1].decode('hex')
print hex(r(0x7BA58F82BD898035,0x2046544352206F74))[2:-1].decode('hex')
print hex(r(0xA3112746582E1434,0x6548202138313032))[2:-1].decode('hex')
print hex(r(0x163F756FCC221AB0,0x2061207369206572))[2:-1].decode('hex')
print hex(r(0xECC78E6FB9CBA1FE,0x6320455279626142))[2:-1].decode('hex')
print hex(r(0xDCDD8B49EA5D7E14,0x65676E656C6C6168))[2:-1].decode('hex')
print hex(r(0xA2845FE0B3096F8E,0x756F7920726F6620))[2:-1].decode('hex')
print hex(r(0xAAAAAAAAAA975D1C,0xFFFFFFFFFFFFFFFF))[2:-1].decode('hex')
print hex(r(0x55555555555559A3,0xFFFFFFFFFFFFFFFF))[2:-1].decode('hex')
print hex(r(0x55555555555559A3,0xFFFFFFFFFFFFFFFF))[2:-1].decode('hex')
print hex(r(0x55555555555559A3,0xFFFFFFFFFFFFFFFF))[2:-1].decode('hex')
print hex(r(0x55555555555559A3,0xFFFFFFFFFFFFFFFF))[2:-1].decode('hex')
print hex(r(0x55555555555559A3,0xFFFFFFFFFFFFFFFF))[2:-1].decode('hex')
print hex(r(0x55555555555559A3,0xFFFFFFFFFFFFFFFF))[2:-1].decode('hex')
print hex(r(0x55555555555559A3,0xFFFFFFFFFFFFFFFF))[2:-1].decode('hex')
print hex(r(0x55555555555559A3,0xFFFFFFFFFFFFFFFF))[2:-1].decode('hex')



#a*b%c=d
#a=d*b**(c-2)%c