网鼎杯-幸运的数字

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

_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;    
}    

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

__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
2
3
4
5

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函数中可见    

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

#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    

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

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    

1
2
3
4
5
6
7

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    

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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