CTF2017 第十题 海风月影cm

反汇编

通过查看字符串发现用的是 gmp 库，对比源码分析出程序 main 函数

int main(int argc, char* argv[])
{
  printf("=========================================================================\n");
  printf("                     看雪CTF2017 CrackMe by 海风月影\n\n");
  printf("    请输入序列号：");
  scanf("%s", iptkey);
  printf("\n\n");
  keylen = -1i64;
  do
    ++keylen;
  while ( iptkey[keylen] );
  if ( (_DWORD)keylen == 70 )
  {
    j = 0i64;
    i = 0i64;
    while ( 1 )
    {
      cc = iptkey[i];
      if ( (unsigned __int8)(cc - '0') > 9u && (unsigned __int8)(cc - 'A') > 25u )
        break;                                  // 要求数字和大写字母
      if ( ++i >= 70 )
      {
        *(_DWORD *)hex_x = *(_DWORD *)iptkey;
        *(_WORD *)&hex_x[4] = *(_WORD *)&iptkey[4];// 注意这里 hex_x 只有 6 字节
        do
        {
          v8 = iptkey[j + 6];
          hex_y[j++] = v8;
        }
        while ( v8 );                           // hex_y 有 70-6 = 64 字节
        mpf_init_set_str(&x, hex_x, 16u);
        mpf_init_set_str(&y, hex_y, 16u);
        if ( mpz_millerrabin(&y, 500u) )        // 检测是素数
        {
          if ( mpz_millerrabin(&x, 500u) )
          {
            mpf_init_set_si(&z, 0i64);
            mpf_init_set_str(
              &p,
              "6248BC3AB92A33B000FDB88568F19727F92F79EB68FF6AD73203EFD20A3E331BE941C7AA288095F33BC4B255FD983114D480EFFBEE"
              "2E313E6218A57F9CCC8189",
              16u);
            mpf_init_set_str(
              &q,
              "2476A7F02588913F228923E1F36F963F29708C07B117396817A6B94C336FC77FF7D381925EB40CFED8FBE894570155E41569B4EC69"
              "B26CB0320105A29651CB4B",
              16u);
            mpf_init_set_si(&t, 0i64);
            mpz_mod(&t, &p, &y);
            if ( !(unsigned int)mpz_cmp_ui(&t, 0i64) )// p % y == 0
            {
              mpz_divexact(&z, &p, &y);         // z = p / y  ->   p = y * z
              if ( (signed int)mpz_cmp(&y, &z) <= 0 )// y <= z  注意 y 比 z 小
              {
                mpz_sub_ui(&y, &y, 1ui64);
                mpz_sub_ui(&z, &z, 1ui64);
                mpz_mul(&t, &y, &z);            // t = (y - 1) * (z - 1)
                mpz_invert(&t, &x, &t);
                ok = mpz_cmp(&q, &t);           // q * x = 1 (mod t)
                msg = "注册成功!!!\n\n";
                if ( !ok )
                  goto LABEL_16;
              }
            }
          }
        }
        break;
      }
    }
  }
  msg = "注册失败\n\n";
LABEL_16:
  printf((char *)msg);
  system("pause");
  return 0i64;
}

解题

这题和第八题差不多都是考的同余式的一些性质和相关定理，如果你看了我第八题的解题报告，应该也能解出这道题

代码

import gmpy2
p = long("6248BC3AB92A33B000FDB88568F19727F92F79EB68FF6AD73203EFD20A3E331BE941C7AA288095F33BC4B255FD983114D480EFFBEE2E313E6218A57F9CCC8189", 16)
q = long("2476A7F02588913F228923E1F36F963F29708C07B117396817A6B94C336FC77FF7D381925EB40CFED8FBE894570155E41569B4EC69B26CB0320105A29651CB4B", 16)
tmp1 = tmp2 = gmpy2.powmod(2, q, p)
for x in xrange(1, 0xFFFFFF):
    if tmp2 == 2:
        break
    # 这里用余等性质枚举比每次都模幂要快
    tmp2 = tmp2 * tmp1 % p
print "x:", x
tmp1 = x * q - 1
n = 1
while True:
    if tmp1 % n == 0:
        t = tmp1 / n
        if t < p:
            break
    n += 1
print "n:", n
m = p - t + 1
y = (m - gmpy2.isqrt(m*m - 4*p)) / 2
# 输出结果
print "key:", (hex(x)[2:].rstrip("L") + hex(y)[2:].rstrip("L")).upper()

[培训]《安卓高级研修班(网课)》月薪三万计划，掌握调试、分析还原ollvm、vmp的方法，定制art虚拟机自动化脱壳的方法