TOC

参考链接

https://l0x1c.github.io/2020/05/15/2020-5-14/

libgmp库

静态链接去符号表文件,首先制作sig导入,但是可能因为库版本和libc版本问题,能够识别的函数并不是很多,只有参照源码+调试

代码解析

关键函数在sub_401F8Asub_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