1.  IDA 反编译后结果如下代码。

见后面。

2.  分析发现使用了gmp运算库，做了sig 加载， 但是在main里，大部分不识别。

于是打开gmp文档， 结合文档，推断函数功能， 确定了大部分的函数：

https://gmplib.org/gmp-man-6.1.2.pdf

发现2个大数，记为 N， E ， 根据经验推理出大概的函数流程。考虑到可能采用RSA，

但是推理过程并未发现PowMod运算。考虑可能是取模 or 求商。

S1 + S2  一共70 bytes的 大写 Hex-Digits。

其中 S1  6 bytes， S2 64bytes。 S2恰好为N 长度的一半， 不妨记录为P。

要求 ：   N /P = Q， 并且S2是其中小的因子，  P < Q 。

然后求得 Phi = （P - 1） * (Q - 1)

最后求  E模Phi 的逆 ，与 S1进行比较相等， 也就是   S1 * E = 1  mod （Phi）

3. 那么，结论就是

根据 E，N 求出 D， P  。  在RSA参数(N, E,  D ) 中， 已知大指数E， 针对小指数D的攻击至少有两种方法。

方法1:

Wiener's attack  通用方法， 针对  D < N^0.25

该算法原理参考wiki：

https://en.wikipedia.org/wiki/Wiener's_attack

python 代码， g到一份如下：

https://github.com/pablocelayes/rsa-wiener-attack

结合Wiener's_attack ， 得到 D 。然后 通过 （N , E, D）来计算 P ， Q。

特别说明:  RDLP有这个功能, 只要把N , E填入, 点击 WIENER , 即可计算出 D 以及 P ，Q。

RDLP： RSA, Rabin, DSA/DSS Keygenerator and DLP Tool

参考：RDLP-Readme.txt 在压缩包RDLP.rar内

http://bbs.pediy.com/thread-66678.htm

http://tools.pediy.com/windows/Cryptography/calculator/rdlp/RDLP.rar

方法2:

考虑到小指数   d很小， E，N已知。   令 y = 2 , c = y^e mod N ,  建立一个离散对数方程来求解d：

这里：

c= 17E73D7E3DCD777132626E613037545FCCDE058B667FF426A196093C98CF43017AF53EB957D9C
997411A1E4DD376B3AFE445567E294CD45DCB59FC3964C75E4A

n= 6248BC3AB92A33B000FDB88568F19727F92F79EB68FF6AD73203EFD20A3E331BE941C7AA28809
5F33BC4B255FD983114D480EFFBEE2E313E6218A57F9CCC8189
y= 2

建立离散对数方程：

c^d = y  mod n

解得： Discrete log  d = F552B3

用 Pollard's lambda method （kangaroo 算法） ， 求解小指数 d , d 的区间 [1， 2^32]

此算法的复杂度为 O(d^1/2)   ， 在这里， 步数大约是 16 bits， 也就是10万次的数量级。

经测试512 bits 的N， d < 32 bits， 3 秒左右可以完成计算。

这种方法较为繁琐（此处从略）。

4.  从 (N,E,D) 计算P ，Q 。 也有至少2种方法。

这里采用了一个 （N , E, D） 快速计算 （P ，Q）的算法如下： 

我没有搜到这个算法的原始出处， 但是考虑到这个算法如此简朴快捷，一定有不少的人发现过这个算法。

方法1：

当  E ,D 其中有一个较小者 bits 不大于N的一半时：

min(E, D ) < N^0.5

只需要 几步除法即可计算出 P，Q。

观察如下两个等式：

(1) ed - 1 = k*phi = k(p-1)(q-1)  =    k*n -  k*(q + p - 1)

(2) ed - 1 = A*n + B   =  (A+1)n - (n - B)

（1） 与 （2） 是等价的：

因此， 令 A = (ed-1)/n , 0 < B < n , k < min(e , d) < max(e, d) < phi
我们得到： 

k = A+1 ,  phi = (ed-1)/k   , 这里要检查 余数为0。

 然后用 韦达定理 求解一元二次方程的两个根， x1， x2 = p ， q：

 x^2 - bx + N = 0
 其中： b= p+q , N = p*q

另外，有一个常规的方法， 从（N , E, D） 计算（P ，Q） ，对 E ，D 的 size 没有任何要求。这个算法应该在很多书里有记载。

方法2：

伪代码描述如下：

// 通过求解 w^2 = 1 mod n, we get p=gcd(w-1, n)，有1/2概率求出非平凡因子p，一般2次即可
// k*phi = ed -1 = r * 2^s
// a = rand(n)
// w = a^r (mod n)
// for ( j = 0 ; j < s ; j++)
// if (w != 1) &&   (w != n-1 )
//    if w^2 = 1 (mod n)
//      gcd(w-1,n) or gcd(w+1 ,n ) will have 1/2 chance to get p.q
// 随机选择a,一般 2-3次, 即可求出p

python 代码在附件里： 需要安装 gmpy2

https://pypi.python.org/pypi/gmpy2

编写cm10.py 运行 如下：

D:\data\pediy\rsa-wiener-attack-master>cm10.py
Hacked!
d= 0xf552b3
rem= 0x0
-------------------------
n= 0x6248bc3ab92a33b000fdb88568f19727f92f79eb68ff6ad73203efd20a3e331be941c7aa288
095f33bc4b255fd983114d480effbee2e313e6218a57f9ccc8189
p= 0xb182de2ac2db8735cf01b2ab4cc338c82e2806043302a3ce9efa861dc36377c3
q= 0x8dbdde72e2e693b2aed5c769c0dcb3da83534480a80e652ffe53544cd91a18c3
p*q - n = 0x0
SN=
F552B38DBDDE72E2E693B2AED5C769C0DCB3DA83534480A80E652FFE53544CD91A18C3

#
# https://en.wikipedia.org/wiki/Wiener's_attack
#
# https://github.com/pablocelayes/rsa-wiener-attack
# https://pypi.python.org/pypi/gmpy2
#

import gmpy2, RSAwienerHacker

if __name__ == "__main__":

    n = gmpy2.mpz("6248BC3AB92A33B000FDB88568F19727F92F79EB68FF6AD73203EFD20A3E331BE941C7AA288095F33BC4B255FD983114D480EFFBEE2E313E6218A57F9CCC8189", 16)
    e = gmpy2.mpz("2476A7F02588913F228923E1F36F963F29708C07B117396817A6B94C336FC77FF7D381925EB40CFED8FBE894570155E41569B4EC69B26CB0320105A29651CB4B", 16)

    # try  Wiener 's attack

    d = RSAwienerHacker.hack_RSA(e, n)
    print("d= " + hex(d))

    # calc phi(n) = (p - 1)*(q - 1)  from (n, e, d)
    #
    # 1. trial divide method :
    # fast method to calc phi(n) from (n, e, d)  
    # if  min(e, d ) < n^0.5
    #
    # (1) ed - 1 = k*phi = k(p-1)(q-1) = k*n - k*(p1)
    #
    # (2) ed - 1 = A*n + B  = (A+1)n - (n - B)
    #
    # A = (ed-1)/n , 0 < B < n , k < min(e , d) < max(e, d) < phi
     #
    # => k = A+1 ,  phi = (ed-1)/k
    #
    # 2. general method:
    #  e*d - 1 = r * 2^s
    #  choose random a ,  w = pow(a, r),  p = gcd(w, n )  if w != 1
    #
    ed = e*d - 1
    k = ed/n + 1
    phi = ed / k
    rem = ed % k
    print("rem= " + hex(rem))

    # x^2 - bx + N = 0
    # b= p+q , N = p*q
    b = n + 1 - phi
    m = gmpy2.isqrt(b*b - 4*n)
    p = (b + m)/2
    q = (b - m)/2

    print("-------------------------")
    print("n= " + hex(n))
    print("p= " + hex(p))
    print("q= " + hex(q))
    print("p*q - n = " + hex(p*q - n))

    sn1=hex(d).upper()[2:8]
    sn2=hex(q).upper()[2:]
    print("SN=\n" + sn1 + sn2)

__int64 main_0()
{
  signed __int64 len; // rax@1
  __int64 i; // r8@4
  __int64 j; // rdx@4
  char c; // cl@5
  char c_char; // al@9
  int v5; // eax@14
  const char *v6; // rcx@14
  char phi; // [rsp+20h] [rbp-18h]@12

  printf("=========================================================================\n");
  printf("                     看雪CTF2017 CrackMe by 海风月影\n\n");
  printf("    请输入序列号：");
  sscanf("%s", SN);
  printf("\n\n");
  len = -1i64;
  do
    ++len;
  while ( SN[len] );
  if ( (_DWORD)len == 70 )                      // len = 70 = 6 + 64 bytes
  {
    i = 0i64;
    j = 0i64;
    while ( 1 )
    {
      c = SN[j];
      if ( (unsigned __int8)(c - '0') > 9u && (unsigned __int8)(c - 'A') > 25u )
        break;
      if ( ++j >= 70 )
      {
        p_SN = *(_DWORD *)SN;
        word_140052F9C = word_140051F24;
        do
        {
          c_char = SN[i + 6];
          p_char[i++] = c_char;                 // p_char:  64 bytes (from  sn[6] to sn[69])
        }
        while ( c_char );
        mpz_init_set_str(&E, (__int64)&p_SN, 16u);
        mpz_init_set_str(P, (__int64)p_char, 16u);
        if ( (unsigned int)sub_140007350((__int64)P, 500u) )
        {
          if ( (unsigned int)sub_140007350((__int64)&E, 500u) )
          {
            mpz_init(&Q, 0i64);
            mpz_init_set_str(
              &rsa_N,
              (__int64)"6248BC3AB92A33B000FDB88568F19727F92F79EB68FF6AD73203EFD20A3E331BE941C7AA288095F33BC4B255FD983114D"
                       "480EFFBEE2E313E6218A57F9CCC8189",
              16u);
            mpz_init_set_str(
              &D,
              (__int64)"2476A7F02588913F228923E1F36F963F29708C07B117396817A6B94C336FC77FF7D381925EB40CFED8FBE894570155E41"
                       "569B4EC69B26CB0320105A29651CB4B",
              16u);
            mpz_init(&phi, 0i64);
            mpz_mod(&phi, &rsa_N, P);
            if ( !(unsigned int)sub_1400075D0(&phi, 0i64) )// N/P remains 0
            {
              _gmpz_divexact(&Q, &rsa_N, P);
              if ( (signed int)mpz_cmp((__int64)P, (__int64)&Q) <= 0 )
              {
                mpz_sub_ui(P, (__int64)P, 1ui64);
                mpz_sub_ui((signed int *)&Q, (__int64)&Q, 1ui64);
                mpz_mul((signed int *)&phi, P, (signed int *)&Q);
                mpz_invert(&phi, &E, &phi);
                v5 = mpz_cmp((__int64)&D, (__int64)&phi);
                v6 = "注册成功!!!\n\n";
                if ( !v5 )
                  goto LABEL_16;
              }
            }
          }
        }
        break;
      }
    }
  }
  v6 = "注册失败\n\n";
LABEL_16:
  printf(v6);
  sub_14002D1B4("pause");
  return 0i64;
}

[培训]二进制漏洞攻防（第3期）；满10人开班；模糊测试与工具使用二次开发；网络协议漏洞挖掘；Linux内核漏洞挖掘与利用；AOSP漏洞挖掘与利用；代码审计。