看雪CTF2017第10题WP

这是看雪CTF2017比赛的第10题。题目地址:传送门

程序是静态编译的,全是黑函数。看了下入口call,jmp应该是VC写的,但是多了个push pop的过程。查看字符串,发现了ctf2017,附近还有注册成功之类的,定位到关键算法所在,在字符串中还发现了GNU MP: Cannot allocate memory之类,经查为gmp计算库。
其实本来由于前面精力用太多,感觉很累,想放了这题的,看了个开头就没看了。准备试试ida的符号加载,去掉一些黑函数,下载编译了个gmp,试了一晚上也没有成功。
后来又想看题了,就对照gmp的源码,把部分函数比对了下,如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
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, (__int64)&stru_140051EE0, (__int64)&stru_140052F20);
if ( (signed int)mpz_cmp_140007560(&stru_140052F20, &stru_140051EF0) <= 0 )// a1<=a2
{
mpz_sub_1400079F0(&stru_140052F20, (__int64)&stru_140052F20, 1ui64);
mpz_sub_1400079F0(&stru_140051EF0, (__int64)&stru_140051EF0, 1ui64);
mpz_mul_140007610((__int64)&a2, (__int64)&stru_140052F20, (__int64)&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以下,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# -*- 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)

不到一分钟出了一个结果:

1
2
e = 0xf552b3
p+q = 0x13f40bc9da5c21ae87dd77a150d9feca2b17b4a84db1108fe9d4dda6a9c7d9086

用matlab解算出p,q,因为题目中限制了p<=q,取小值为p:

1
2
p = 64111581030502014729907148975807553274150008894301323553363399183151805372611
q = 80290597658186981463023471970341877717671071586519890660723213036500314978243

转成16进制,与e拼接,再转成大写(题目中有字符检查),结果为:

1
F552B38DBDDE72E2E693B2AED5C769C0DCB3DA83534480A80E652FFE53544CD91A18C3

说明:本文首发于看雪论坛。

×

纯属好玩

扫码支持
扫码打赏,你说多少就多少

打开支付宝扫一扫,即可进行扫码打赏哦

文章目录
,