首页
社区
课程
招聘
[原创]看雪CTF2017 第十题分析
2017-6-20 23:03 5542

[原创]看雪CTF2017 第十题分析

2017-6-20 23:03
5542

ida打开cm.exe,定位到main函数后f5反编译

            mp_set_str(
              &N,
              (__int64)"6248BC3AB92A33B000FDB88568F19727F92F79EB68FF6AD73203EFD20A3E331BE941C7AA288095F33BC4B255FD983114D"
                       "480EFFBEE2E313E6218A57F9CCC8189",
              0x10u);
            mp_set_str(
              &D,
              (__int64)"2476A7F02588913F228923E1F36F963F29708C07B117396817A6B94C336FC77FF7D381925EB40CFED8FBE894570155E41"
                       "569B4EC69B26CB0320105A29651CB4B",
              0x10u);
            sub_140007AD0(&T, 0i64);
            mpz_mod((__int64)&T, (__int64)&N, (__int64)&p);
            if ( !(unsigned int)mpz_cmp_ui((__int64)&T, 0i64) )
            {
              mpz_divexact(&q, (__int64)&N, (__int64)&p);
              if ( (signed int)mpz_cmp((__int64)&p, (__int64)&q) <= 0 )
              {
                mpz_sub_ui(&p, (__int64)&p, 1ui64);
                mpz_sub_ui(&q, (__int64)&q, 1ui64);
                mpz_mul((__int64)&T, (__int64)&p, (__int64)&q);
                mpz_invert(&T, (__int64)&e, (__int64)&T);
                v10 = mpz_cmp((__int64)&D, (__int64)&T);
                v11 = "注册成功!!!\n\n";
                if ( !v10 )
                  goto LABEL_16;
              }
            }

通过对比gmp大数库,重命名函数名。

分析发现这是RSA算法,提供了N和D,输入e和p进行匹配。其计算公式如下:

N = p * q
T = (p-1)*(q-1)
D = invert(e, T)

p,q,e必须为素数,这题e的取值范围是2-0xffffff,对于e可采用穷举方法。

下面通过D,e计算求得T

∵ e*d=1(modφ(n))
∴ e*d=k*φ(n)+1,其中K为任意整数。
floor((e*d-1)/n) + 1 = k
T = (e * d - 1)/k = φ(n)

再根据下述公式计算p,q

N = p * q
T = (p-1)*(q-1)


穷举程序如下:

#include "stdafx.h"
#include "gmp.h"
#include <assert.h>
void test(mpz_t N, mpz_t D)
{
	mpz_t e;
	mpz_init(e);
	mpz_t a, b, c, x, T;
	mpz_init(a);
	mpz_init(b);
	mpz_init(c);
	mpz_init(x);
	mpz_init(T);
	mpz_t p, q;
	mpz_init(p);
	mpz_init(q);
	for(int i = 0xFFFFFF; i >= 2; i--)
	{
		mpz_set_ui(e, i);
		if(mpz_probab_prime_p(e, 500))
		{
			gmp_printf("e = %ZX\r", e);
			// t=??
			mpz_mul(a, e, D);
			mpz_sub_ui(x, a, 1);		// x = e * d - 1
			mpz_div(a, x, N);
			mpz_add_ui(b, a, 1);		// b = x / n + 1
			
			mpz_div(T, x, b);			// T = x / b
			// N-T+1
			mpz_sub(x, N, T);
			mpz_add_ui(a, x, 1);		// a = N - T + 1
			// a * a
			mpz_mul(b, a, a);
			// 4N
			mpz_mul_ui(x, N, 4);
			// 
			mpz_sub(c, b, x);
			mpz_sqrt(x, c);				// x = sqrt(a ^ 2 - 4N)
			mpz_mul(b, x, x);
			if(mpz_cmp(b, c) == 0)
			{
				mpz_add(b, x, a);
				mpz_div_ui(q, b, 2);	// q = (x + a) / 2
				mpz_sub(b, a, x);
				mpz_div_ui(p, b, 2);	// p = (a - x) / 2
				mpz_mul(c, p, q);
				if(mpz_cmp(N, c) == 0)	// N = p * q
				{
					printf("\n");
					gmp_printf("p = %ZX\n", p);
					gmp_printf("q = %ZX\n", q);
					break;
				}
			}
		}
	}
	printf("\nover.\n");
}
int _tmain(int argc, _TCHAR* argv[])
{
	mpz_t N, D;
	//mpz_init_set_str(N, "02C9", 16);
	//mpz_init_set_str(D, "011B", 16);
	mpz_init_set_str(N, "6248BC3AB92A33B000FDB88568F19727F92F79EB68FF6AD73203EFD20A3E331BE941C7AA288095F33BC4B255FD983114D480EFFBEE2E313E6218A57F9CCC8189", 16);
	mpz_init_set_str(D, "2476A7F02588913F228923E1F36F963F29708C07B117396817A6B94C336FC77FF7D381925EB40CFED8FBE894570155E41569B4EC69B26CB0320105A29651CB4B", 16);
	test(N, D);

	getchar();
	return 0;
}

//e = F552B3

//p = 8DBDDE72E2E693B2AED5C769C0DCB3DA83534480A80E652FFE53544CD91A18C3

//q = B182DE2AC2DB8735CF01B2AB4CC338C82E2806043302A3CE9EFA861DC36377C3

//sn = F552B38DBDDE72E2E693B2AED5C769C0DCB3DA83534480A80E652FFE53544CD91A18C3



[培训]科锐软件逆向50期预科班报名即将截止,速来!!! 50期正式班报名火爆招生中!!!

收藏
免费 1
打赏
分享
最新回复 (4)
雪    币: 1185
活跃值: (458)
能力值: ( LV13,RANK:360 )
在线值:
发帖
回帖
粉丝
Ericky 6 2017-6-21 14:24
2
0

我也试了下这个C。。感觉和汇编操作寄存器一样  哈哈

雪    币: 1467
活跃值: (2562)
能力值: ( LV9,RANK:156 )
在线值:
发帖
回帖
粉丝
whydbg 2017-6-21 18:59
3
0
能不能提供编译好的gmp大数库?
雪    币: 3053
活跃值: (891)
能力值: ( LV13,RANK:1300 )
在线值:
发帖
回帖
粉丝
HighHand 11 2017-6-23 08:56
4
0
whydbg 能不能提供编译好的gmp大数库?

我只有64位的GMP库

上传的附件:
雪    币: 1467
活跃值: (2562)
能力值: ( LV9,RANK:156 )
在线值:
发帖
回帖
粉丝
whydbg 2017-6-23 10:55
5
0
谢谢                         
游客
登录 | 注册 方可回帖
返回