网鼎杯-幸运的数字
2020-05-18 本文已影响0人
SamiraG
参考链接
https://l0x1c.github.io/2020/05/15/2020-5-14/
libgmp库
静态链接去符号表文件，首先制作sig导入，但是可能因为库版本和libc版本问题，能够识别的函数并不是很多，只有参照源码+调试
代码解析
关键函数在sub_401F8A和sub_401C7D，其中sub_401C7D是一个RSA函数，处理后的sub_401F8A如下:
_BOOL8 sub_401F8A()
{
char input_str; // [rsp+0h] [rbp-1F0h]
int v2; // [rsp+60h] [rbp-190h]
int v3; // [rsp+64h] [rbp-18Ch]
char v4; // [rsp+70h] [rbp-180h]
char v5; // [rsp+F0h] [rbp-100h]
struct mpz_num n; // [rsp+110h] [rbp-E0h]
struct mpz_num q; // [rsp+120h] [rbp-D0h]
struct mpz_num p; // [rsp+130h] [rbp-C0h]
char v9; // [rsp+140h] [rbp-B0h]
char v10; // [rsp+150h] [rbp-A0h]
char v11; // [rsp+160h] [rbp-90h]
struct mpz_num v12; // [rsp+170h] [rbp-80h]
char v13; // [rsp+180h] [rbp-70h]
char v14; // [rsp+190h] [rbp-60h]
struct mpz_num v15; // [rsp+1A0h] [rbp-50h]
struct mpz_num v16; // [rsp+1B0h] [rbp-40h]
char v17; // [rsp+1C0h] [rbp-30h]
struct mpz_num input_n; // [rsp+1D0h] [rbp-20h]
__int64 v19; // [rsp+1E8h] [rbp-8h]
mpz_init(&v17);
mpz_init_set_str((__int64)&v16, (__int64)"226", 0xAu);
sub_47AC70(&v16, "226");
sub_4430F0((unsigned __int64)&v5);
v19 = sub_444530(&v5, "r");
sub_444290(&v4, 128LL, v19);
sub_443F20(v19);
if ( !(unsigned int)sub_401098(&v4, "hdb") )
return 1LL;
mpz_init(&v13);
mpz_init(&v10);
mpz_init(&v9);
mpz_init(&v11);
sub_403080(&v14, 2LL);
mpz_init(&n);
mpz_init(&v12);
mpz_init_set_str((__int64)&v15, (__int64)"2", 0xAu);
mpz_init_set_str((__int64)&p, (__int64)"170141183460469231731687303715884106303", 0xAu);
mpz_init_set_str((__int64)&q, (__int64)"170141183460469231731687303715884106207", 0xAu);
memset(&input_str, 0, 0x60uLL);
v2 = 0;
getinput((__int64)"%s", &input_str, &v3);
mpz_init_set_str((__int64)&input_n, (__int64)&input_str, 0xAu);
mpz_mul(&n.a1, (__int64)&p, (__int64)&q); // n = p * q
mpz_square((__int64)&input_n, (__int64)&v12); // v12 = inputn * inputn
mpz_div((signed int *)&v11, (__int64)&input_n, (__int64)&v16);// v11 = inputn // 226
mpz_mul((signed int *)&v11, (__int64)&v11, (__int64)&input_n);// v11 * inputn
mpz_sub(&v9, &v12, &v11); // v9 = v12 - v11
sub_404920(&v10, 1LL); // v10 = 1
while ( (unsigned int)sub_402E20((__int64)&v15, (__int64)&v9) != 1 )// v15 <= v9
{
mpz_pow(&v14, &v15, 3LL); // v14 = pow(v15, 3)
mpz_add(&v10, &v10, &v14);
mpz_add1(&v15.a1, (__int64)&v15, 1uLL); // v15 = v15 + 1
}
mpz_mul(&n.a1, (__int64)&p, (__int64)&q);
mpz_mod((__int64)&v10, (__int64)&v10, (__int64)&n);
rsa((__int64)&v13, (__int64)&v10);
gmp_printf((__int64)"%ZX\n", &v13);
mpz_clear(&input_n.a1);
mpz_clear((signed int *)&v17);
mpz_clear(&v16.a1);
mpz_clear((signed int *)&v11);
mpz_clear((signed int *)&v13);
mpz_clear(&v15.a1);
mpz_clear((signed int *)&v10);
mpz_clear((signed int *)&v9);
mpz_clear(&p.a1);
mpz_clear(&q.a1);
mpz_clear(&v12.a1);
sub_47AC70(&v12, &v13);
sub_4430F0((unsigned __int64)&v5);
v19 = sub_444530(&v5, "r");
sub_444290(&v4, 128LL, v19);
sub_443F20(v19);
return (unsigned int)sub_401098(&v4, "hdb") == 0;
}
RSA函数:
__int64 __fastcall rsa(__int64 a1, __int64 a2)
{
__int64 result; // rax
__int64 v3; // r8
__int64 v4; // r9
char v5; // [rsp+10h] [rbp-110h]
char v6; // [rsp+90h] [rbp-90h]
char v7; // [rsp+B0h] [rbp-70h]
char e; // [rsp+C0h] [rbp-60h]
char n; // [rsp+D0h] [rbp-50h]
char v10; // [rsp+E0h] [rbp-40h]
char q; // [rsp+F0h] [rbp-30h]
char p; // [rsp+100h] [rbp-20h]
__int64 v13; // [rsp+118h] [rbp-8h]
mpz_init(&p);
mpz_init(&q);
mpz_init(&v10);
mpz_init(&n);
sub_403080(&e, 65537LL);
mpz_init(&v7);
sub_404600(&p, "170141183460469231731687303715884105757", 10LL);
sub_404600(&q, "170141183460469231731687303715884106001", 10LL);
mpz_mul((signed int *)&v10, (__int64)&p, (__int64)&q);
sub_47AC70(&v10, &p);
sub_4430F0((unsigned __int64)&v6);
v13 = sub_444530(&v6, "r");
sub_444290(&v5, 128LL, v13);
sub_443F20(v13);
result = sub_401098(&v5, "hdb");
if ( !(_DWORD)result )
return result;
sub_404DA0(&p, &p, 1LL);
sub_404DA0(&q, &q, 1LL);
mpz_mul((signed int *)&n, (__int64)&p, (__int64)&q);
sub_402EC0(&v7, &e, &n);
sub_403670((int *)a1, a2, (__int64)&e, (__int64)&v10, v3, v4);
mpz_clear((signed int *)&q);
mpz_clear((signed int *)&p);
mpz_clear((signed int *)&v10);
mpz_clear((signed int *)&n);
mpz_clear((signed int *)&e);
result = mpz_clear((signed int *)&v7);
return result;
}
从上面解析后的可以比较清晰的看到加密流程:
1. 输入inputn
2. t = input // 226
3. 计算a = input*input - t*input
4. 计算(1^3 + 2^3 + 3^3 + ... + a^3) % n = b，可以化成: (a*(a+1)/2)^2 % n = b
5. 对b进行rsa运算，各种参数在rsa函数中可见
solve
首先解RSA得到b:
#coding=utf-8
import gmpy2
c = 0x37CFC2B07BF92321BFCEAF6330C667D217BB881B0911A8810D28D9986CA52E2F
p = 170141183460469231731687303715884105757
q = 170141183460469231731687303715884106001
e = 65537
n = p * q
phi = (p-1)*(q-1)
d = gmpy2.invert(e, phi)
a = pow(c,d,n) # 解RSA
由于(a*(a+1)/2)^2 % n = b，类似Rabin加密算法，p,q已知，可以求得a*(a+1)/2的值
p = 170141183460469231731687303715884106303
q = 170141183460469231731687303715884106207
n = p * q
a1 = pow(a, (p+1)/4, p)
a2 = pow(a, (q+1)/4, q)
x = gmpy2.invert(p,q)
y = gmpy2.invert(q,p)
z = (y*q*a1+x*p*a2)%n
k = (y*q*a1-x*p*a2)%n
res = [-k%n, z%n, -y%n, x%n]
print res
求出来有四个解，有符合条件的唯一解，需要试，然后a*(a+1)/2的值已知时，需要求a的值，方程是: a^2 + a = 2n => (2a+1)^2=8n+1， 求a:
i = res[0]
v = i * 8
v = v + 1
sq = gmpy2.iroot(v, 2)
ceshi1 = sq[0] - 1
num = gmpy2.c_div(ceshi1, 2)
print num
其中a = input*input - t*input and t = input // 226可以求得input
num1 = num * 226 // 225
num1 = gmpy2.iroot(num1, 2)[0]
x = "flag{"+str(num1) + "}"
print x
sha256 = hashlib.sha256()
x = sha256.update(x.encode('utf-8'))
h = sha256.hexdigest()
print h
# flag{244466666888888108}
# 0a4b7f6c8baf4b16465975218d547f820a3802972b1512e8e6f704893cdccb2e
