程序是静态编译的，全是黑函数。看了下入口call,jmp应该是VC写的，但是多了个push pop的过程。
查看字符串，发现了ctf2017，附近还有注册成功之类的，定位到关键算法所在，在字符串中还发现了GNU MP: Cannot allocate memory之类，经查为gmp计算库。
其实本来由于前面精力用太多，感觉很累，想放了这题的，看了个开头就没看了。准备试试ida的符号加载，去掉一些黑函数，下载编译了个gmp，试了一晚上也没有成功。
后来又想看题了，就对照gmp的源码，把部分函数比对了下，如下
printf_140006EA0("=========================================================================\n");
printf_140006EA0(" 看雪CTF2017 CrackMe by 海风月影\n\n");
printf_140006EA0(" 请输入序列号：");
scanf_140006F00("%s", &input_140051F20);
printf_140006EA0("\n\n");
v0 = -1i64;
do
++v0;
while ( *((_BYTE *)&input_140051F20 + v0) );
if ( (_DWORD)v0 == 70 )
{
v1 = 0i64;
v2 = 0i64; while ( 1 )
{
v3 = *((_BYTE *)&input_140051F20 + v2);
if ( (unsigned __int8)(v3 - 0x30) > 9u && (unsigned __int8)(v3 - 0x41) > 0x19u )// >9 >Z
break;
if ( ++v2 >= 70 )
{
dword_140052F98 = input_140051F20;
word_140052F9C = word_140051F24;
do
{
v4 = *((_BYTE *)&input_140051F20 + v1 + 6);
Src[v1++] = v4; // 输入的后64位
}while ( v4 );
mpz_set_str_140007990(&stru_140051F10, &dword_140052F98, 0x10ui64);// 输入前6以16进制转成数字
mpz_set_str_140007990(&stru_140052F20, Src, 0x10ui64);// 输入后64 以16进制转成数字
if ( mpz_prime_140007350((__int64)&stru_140052F20, 0x1F4u) )
{
if ( mpz_prime_140007350((__int64)&stru_140051F10, 0x1F4u) )
{
mpz_init_140007AD0(&stru_140051EF0, 0i64);
mpz_set_str_140007990(
&stru_140051EE0, "6248BC3AB92A33B000FDB88568F19727F92F79EB68FF6AD73203EFD20A3E331BE941C7AA288095F33BC4B255FD983114D480EFFBEE"
"2E313E6218A57F9CCC8189",
0x10ui64);
mpz_set_str_140007990(
&stru_140051F00, "2476A7F02588913F228923E1F36F963F29708C07B117396817A6B94C336FC77FF7D381925EB40CFED8FBE894570155E41569B4EC69"
"B26CB0320105A29651CB4B",
0x10ui64);
mpz_init_140007AD0(&a2, 0i64);
mpz_mod_140007B10(&a2, &stru_140051EE0, &stru_140052F20);
if ( !(unsigned int)mpz_cmp_ui_____1400075D0(&a2, 0i64) )
{
mpz_div_1400071E0(&stru_140051EF0, &stru_140051EE0, &stru_140052F20);
if ( (signed int)mpz_cmp_140007560(&stru_140052F20, &stru_140051EF0) <= 0 )// a1<=a2
{
mpz_sub_1400079F0(&stru_140052F20, &stru_140052F20, 1ui64);
mpz_sub_1400079F0(&stru_140051EF0, &stru_140051EF0, 1ui64);
mpz_mul_140007610(&a2, &stru_140052F20, &stru_140051EF0);
mpz_invert_1400073B0(&a2, &stru_140051F10, &a2);
v5 = mpz_cmp_140007560(&stru_140051F00, &a2);// 校验
v6 = "注册成功!!!\n\n";
if ( !v5 )
goto LABEL_16;
}
}
}
}
break;
}
}
}
v6 = "注册失败\n\n";
LABEL_16:
printf_140006EA0(v6);
sub_14002D1B4("pause");
return 0i64;先检查输入长度为70，再检查大于`Z``的字符为70。
然后把输入分别6byte和64byte两部分，按16进制字符转成数字，并检查其为素数，再进行一些算术运算，最近与常量数字比较。
从整体看是RSA的密钥生成过程。计输入的两部分分别为e,p，记代码中的常量分别为n,d。则计算过得是这样的：
q=n/p
N = (p-1)*(q-1)
d1 = invert(e,N)
d1 == d?
其中的invert是求模反元素的函数调用。
看完到这，直接将n去数据库里查，没有结果。又拿出yafu分解了两个小时没有结果。果断停了，开始想办法爆破，试了几次都不理想。又整理下公式及思路。
n = pq
N = (p-1)(q-1)
ed = 1(mod N)
那么，
ed -1 = kN (k为整数)
kN = k(p-1)(q-1)
kN/n = k(p-1)(q-1)/n = k(pq-p-q+1)/(pq)
kN/n = k(1-1/p-1/q+1/(pq))
上面两条/为带小数的除法
由于p,q很大，1-1/p-1/q+1/(pq)无限接近于1，kN/n无限接近于k，那么，
(ed-1)/n = k1 此处为整除
则k1 = k-1 ，所以
(ed-1)/(k1+1) = N = pq-p-q+1
(ed-1)/(k1+1)-n = 1-p-q
p+q = 1-(ed-1)/(k1+1)+n
再结合pq=n，就可以由这个二元一次方程求出p,q。所以解题思路就出来了，爆破e，如果(ed-1)%(k1+1)==0，则e为可能解，再由于n为512bit，p和q应该比较接近（p为256bit，q也应该为256bit左右），限制p+q 为264bit以下，代码如下：
# -*- condig = utf-8 -*-
# author: poyoten @ ChaMd5安全团队
import gmpy2
n = gmpy2.mpz(0x6248BC3AB92A33B000FDB88568F19727F92F79EB68FF6AD73203EFD20A3E331BE941C7AA288095F33BC4B255FD983114D480EFFBEE2E313E6218A57F9CCC8189)
d = gmpy2.mpz(0x2476A7F02588913F228923E1F36F963F29708C07B117396817A6B94C336FC77FF7D381925EB40CFED8FBE894570155E41569B4EC69B26CB0320105A29651CB4B)
e = gmpy2.mpz(0x100000)
while True:
e = gmpy2.next_prime(e)
m = gmpy2.mul(e,d)-1
count = gmpy2.div(m,n)
if m%(count+1) == 0:
r = 1-m/(count+1)+n
if r<0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff:
print 'e = '+hex(e)+' ; p+q = '+hex(r)
不到一分钟出了一个结果:
e = 0xf552b3
p+q = 0x13f40bc9da5c21ae87dd77a150d9feca2b17b4a84db1108fe9d4dda6a9c7d9086
用matlab解算出p,q，因为题目中限制了p<=q，取小值为p：
p = 64111581030502014729907148975807553274150008894301323553363399183151805372611
q = 80290597658186981463023471970341877717671071586519890660723213036500314978243
转成16进制，与e拼接，再转成大写（题目中有字符检查）,结果为：
F552B38DBDDE72E2E693B2AED5C769C0DCB3DA83534480A80E652FFE53544CD91A18C3
[培训]《安卓高级研修班(网课)》月薪三万计划，掌握调试、分析还原ollvm、vmp的方法，定制art虚拟机自动化脱壳的方法
