[SUCTF2019] SignIn

知识点

gmp库
RSA加密

用IDA打开

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

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

出现了奇奇怪怪的函数

__gmpz_init_set_str、__gmpz_powm、__gmpz_cmp。搜索gmpz发现存在gmp库。在官方网站翻函数

5.3 Combined Initialization and Assignment Functions
为方便起见，GMP 提供了一系列并行的初始化和设置函数，这些函数初始化输出然后将值存储在那里。这些函数的名称具有以下形式mpz_init_set…

下面是一个使用的例子：

{
  mpz_t pie;
  mpz_init_set_str (pie, "3141592653589793238462643383279502884", 10);
  …
  mpz_sub (pie, …);
  …
  mpz_clear (pie);
}
一旦整数被任何mpz_init_set… 函数初始化，它就可以用作普通整数函数的源或目标操作数。不要在已经初始化的变量上使用初始化和设置函数！

功能：void mpz_init_set (mpz_t rop , const mpz_t op )
功能：void mpz_init_set_ui (mpz_t rop , unsigned long int op )
功能：void mpz_init_set_si (mpz_t rop , signed long int op )
功能：void mpz_init_set_d (mpz_t rop , double op )
用肢体空间初始化rop并从op设置初始数值 。

函数：int mpz_init_set_str (mpz_t rop , const char * str , int base )
初始化rop并将其值设置为mpz_set_str（有关详细信息，请参阅上面的文档）。

如果字符串是正确的碱基号，该函数返回0; 如果发生错误，则返回 -1。 即使发生错误，rop也会被初始化。（即，您必须调用mpz_clear它。）

这三个参数分别是多精度整数变量，字符串，进制。
这个函数的作用就是将 str 字符数组以 base 指定的进制解读成数值并写入 rop 所指向的内存。

mpz_powm

5.7 幂函数
功能：void mpz_powm (mpz_t rop , const mpz_t base , const mpz_t exp , const mpz_t mod )
功能：void mpz_powm_ui (mpz_t rop , const mpz_t base , unsigned long int exp , const mpz_t mod )
将rop设置为( base提升为exp ) modulo mod。

负EXP如果逆支持基地-1 MOD MOD存在（见mpz_invert在 数论函数）。如果不存在逆，则被零除。

功能：void mpz_powm_sec (mpz_t rop , const mpz_t base , const mpz_t exp , const mpz_t mod )
将rop设置为( base提升为exp ) modulo mod。

要求exp > 0且mod为奇数。

这个函数被设计为对任何两个相同大小的参数花费相同的时间并具有相同的缓存访问模式，假设函数参数被放置在相同的位置并且机器状态在函数进入时是相同的。此功能用于加密目的，需要对侧信道攻击具有弹性。

功能：void mpz_pow_ui (mpz_t rop , const mpz_t base , unsigned long int exp )
功能：void mpz_ui_pow_ui (mpz_t rop , unsigned long int base , unsigned long int exp )
将rop设置为base提升到exp。情况 0^0产生 1。

其实就是
void mpz_powm (mpz_t rop, const mpz_t base, const mpz_t exp, const mpz_t mod) [Function]
Set rop to base^exp mod mod.
但看官方文档看不明白

其实就是计算 base 的 exp 次方，并对 mod 取模，最后将结果写入 rop 中
这个运算的过程和RSA的加密过程一样。

一看就是比较函数gmpz_cmp

RSA

加密：

C = M^E mod N

C为密文，M是明文，E是公钥（E和 φ(N)互为质数），N是公共模数（质数 P*Q得到N），MOD就是模运算
解密：

M = C^D mod N

图中的C是密文，M是明文，D是私钥（私钥由这个公式计算得出E * D % φ(N) = 1），N是公共模数（质数 P*Q得到N），MOD就是模运算，φ(N)是欧拉函数（由这个公式计算得出φ(N) = (P-1)(Q-1)）。

了解了加密解密的概念,

开始写脚本

脚本

已知

C = 0xad939ff59f6e70bcbfad406f2494993757eee98b91bc244184a377520d06fc35
N = 103461035900816914121390101299049044413950405173712170434161686539878160984549
E = 65537

首先需要由N得到P和Q，使用yafu工具

>>.\yafu-x64.exe                                 
factor(103461035900816914121390101299049044413950405173712170434161686539878160984549)


fac: factoring 103461035900816914121390101299049044413950405173712170434161686539878160984549
fac: using pretesting plan: normal
fac: no tune info: using qs/gnfs crossover of 95 digits

starting SIQS on c78: 103461035900816914121390101299049044413950405173712170434161686539878160984549

==== sieving in progress (1 thread):   36224 relations needed ====
====           Press ctrl-c to abort and save state           ====
36248 rels found: 18898 full + 17350 from 185925 partial, (4669.49 rels/sec)

SIQS elapsed time = 44.9578 seconds.
Total factoring time = 44.9838 seconds


***factors found***

P39 = 282164587459512124844245113950593348271
P39 = 366669102002966856876605669837014229419

ans = 1

得到p和q和e我们就能计算欧拉函数，然后我们就可以通过欧拉函数φ(N)和公钥E计算出私钥D。
使用python的gmpy2库计算私钥。(E * D % φ(N) = 1)

d = gmpy2.invert(e,(p-1)*(q-1))

d = 91646299298871237857836940212608056141193465208586711901499120163393577626813

计算私钥d我们就可以对密文C进行解密，解密算法（C的撕咬D次方对公共模数N取余）

使用python的gmpy2库计算明文

m = gmpy2.powmod(c,d,n)

m = 185534734614696481020381637136165435809958101675798337848243069

把m转为字符串即可

# 已知 C N E
# 由 N 分解 P和Q
import gmpy2
import binascii
c = 0xad939ff59f6e70bcbfad406f2494993757eee98b91bc244184a377520d06fc35
n = 103461035900816914121390101299049044413950405173712170434161686539878160984549
e = 65537
p = 282164587459512124844245113950593348271
q = 366669102002966856876605669837014229419
d = gmpy2.invert(e, (p-1)*(q-1))
m = gmpy2.powmod(c, d, n)
print(binascii.unhexlify(hex(m)[2:]).decode(encoding="utf-8"))
# suctf{Pwn_@_hundred_years}

[SUCTF 2019] SignIn

知识点

RSA

脚本