[SUCTF2019]SignIn – RSA

发布于 2020-10-23  1188 次阅读


[SUCTF2019]SignIn

__int64 __fastcall main(__int64 a1, char **a2, char **a3)
{
  char v4; // [rsp+0h] [rbp-4A0h]
  char v5; // [rsp+10h] [rbp-490h]
  char v6; // [rsp+20h] [rbp-480h]
  char v7; // [rsp+30h] [rbp-470h]
  char v8; // [rsp+40h] [rbp-460h]
  char v9; // [rsp+B0h] [rbp-3F0h]
  unsigned __int64 v10; // [rsp+498h] [rbp-8h]

  v10 = __readfsqword(0x28u);
  puts("[sign in]");
  printf("[input your flag]: ", a2);
  __isoc99_scanf("%99s", &v8);
  sub_96A(&v8, (__int64)&v9);
  __gmpz_init_set_str((__int64)&v7, (__int64)"ad939ff59f6e70bcbfad406f2494993757eee98b91bc244184a377520d06fc35", 16LL);
  __gmpz_init_set_str((__int64)&v6, (__int64)&v9, 16LL);
  __gmpz_init_set_str(
    (__int64)&v4,
(__int64)"103461035900816914121390101299049044413950405173712170434161686539878160984549",
    10LL);
  __gmpz_init_set_str((__int64)&v5, (__int64)"65537", 10LL);
  __gmpz_powm(&v6, &v6, &v5, &v4);
  if ( (unsigned int)__gmpz_cmp((__int64)&v6, (__int64)&v7) )
    puts("GG!");
  else
    puts("TTTTTTTTTTql!");
  return 0LL;
}

首先查阅__gmpz开头的函数,发现其是GNU库中的高进度算法库,实际操作的内容与我们这题无关。

看到最后的__gmpz_powm(&v6, &v6, &v5, &v4); 基本上就可以推测是RSA了。

v6是输入的明文,v4相当于输入的n,v5相当于RSA中的e,v6经过这个过程后变成RSA中的密文c,于是有:

\(c≡m^e \;mod\,n\)

在factordb中尝试分解n,发现其可以成功分解为p,q

于是有:

\(ed=1\,mod\,\phi(n)\)

求出d后便可计算出明文。

import gmpy2
import rsa

import binascii

e = 65537
n = 103461035900816914121390101299049044413950405173712170434161686539878160984549
p =  282164587459512124844245113950593348271
q = 366669102002966856876605669837014229419
enc = 0xad939ff59f6e70bcbfad406f2494993757eee98b91bc244184a377520d06fc35
phi=(p-1)*(q-1)
d =gmpy2.invert(e,phi)
m = gmpy2.powmod(enc,d,p*q)
print(binascii.unhexlify(hex(m)[2:]).decode(encoding="utf-8"))
#print(hex(m)[2:].decode('hex'))
key =rsa.PrivateKey(n, e, int(d), p, q)
rsa.decrypt(enc.to_bytes(),key)


等风来,不如追风去。