首页
论坛
课程
招聘
[原创]CTF第二题的求解思路
2017-10-27 20:23 1077

[原创]CTF第二题的求解思路

2017-10-27 20:23
1077
工具IDA,OD,VC++

不知道如果最后扫描不出来结果可不可以通过

求解主要是获取到两个变量v1和v2,同时满足以下等式

5 * (v1 - v0) + v1 == -1890567614 && 13 * (v1 - v0) + v0 == -279954878

17 * (v1 - v0) + v1 == -207009661 && 7 * (v1 - v0) + v0 == 866732163

可以看出
v1 mod 5 = -1890567614 mod 5
v1 mod 17 = -207009661 mod 17
v0 mod 13 = -279954878 mod 13
v0 mod 7 = 866732163 mod 7
根据剩余定理可以推测出v1和v0的可能的一系列值,然后再暴力尝试可能的值,最后确定出v1和v0的值
破解代码如下:
#include "stdafx.h"
#include "stdio.h"


//中国剩余定理  
struct node {
	int divisor;            //表示除数  
	int  remainder;     //表示余数  
}T[1000];

//求最大公约数  
int gcd(int n, int m)
{
	return m ? gcd(m, n%m) : n;
}

int v1[0x7ffffff] = { 0 };
int v0[0x7ffffff] = { 0 };

int getV(int b0, int b1, int l0, int l1, int* v) {
	//MAX_NUM表示的是所求的解的范围的最大值,MIN_NUM表示所求的解的范围的最小值,  
	//n表示的是同于方程的个数,m表示的是三个除数的乘积,gcd_max表示的是两个数的最大公约数,因为三个除数是互素的  
	//所以gcd_max=1;  
	int i, j, n, t = 0, m = 1, sum = 0, gcd_max = 0, MAX_NUM, MIN_NUM;


	//printf("请输入有几个方程:\n");   //如上题韩信点兵。输入3  
	//scanf_s("%d", &n);
	printf("请输入每组数据(  余数 除数):\n"); // 3 2 5 4 7 6  
	n = 2;
	T[0].remainder = b0 % l0;
	T[0].divisor = l0;

	T[1].remainder = b1 % l1;
	T[1].divisor = l1;
	//printf("请输入所求值的值域:min max\n");
	//scanf_s("%x%x", &MIN_NUM, &MAX_NUM);
	//求出三个除数的乘积m  
	for (i = 0; i < n; i++) {
		gcd_max = gcd(T[i].divisor, gcd_max);
		m = m * T[i].divisor;
	}
	gcd_max *= m;
	//求mI  
	for (i = 0; i < n; i++)
	{
		t = 0; m = 1;
		for (j = 0; j < n; j++)
		{
			if (j != i)
			{
				t = gcd(T[j].divisor, t);
				m = m * T[j].divisor;
			}
		}
		t = m * t;
		m = t;
		while (m % T[i].divisor != 1)
			m += t;
		sum += m * T[i].remainder;
	}
	printf("最小的值为:\n");
	printf("%d\n", sum % gcd_max);
	printf("在所求的值域内值:\n");
	printf("%x\n", sum);
	int count = 0;
	while (sum < 0x7e7e7e7e) {
		if (sum >= 0x20202020) {
			//&& (sum & 0xff000000) >= 0x20000000 && (sum & 0xff000000) <= 0x7e000000
			//&& (sum & 0x00ff0000) >= 0x00200000 && (sum & 0x00ff0000) <= 0x007e0000
			//&& (sum & 0x0000ff00) >= 0x00002000 && (sum & 0x0000ff00) <= 0x00007e00
			//&& (sum & 0x000000ff) >= 0x00000020 && (sum & 0x000000ff) <= 0x0000007e) {
			//printf("0x%x   \n", sum);
			v[count] = sum;
			count += 1;
		}

		sum += gcd_max;

	}
	printf("%x\n", sum);
	printf("%d\n", count);
	return count;
}

int main()
{
	int b0 = 0x8F503a42;
	int b1 = 0xEF503a42;
	int b2 = 0xF3A94883;
	int b3 = 0x33A94883;

	printf("%i<->5\n", b0 % 5);
	printf("%i<->17\n", b2 % 17);

	printf("%i<->13\n", b1 % 13);
	printf("%i<->7\n", b3 % 7);

	int len1 = getV(b0, b2, 5, 17, v1);
	int len0 = getV(b1, b3, 13, 7, v0);

	for (int i = 0; i < len1; ++i) {
		for (int j = 0; j < len0; ++j) {
			if ((5 * (v1[i] - v0[j]) + v1[i]) == b0
				&& (13 * (v1[i] - v0[j]) + v0[j]) == b1
				&& (17 * (v1[i] - v0[j]) + v1[i]) == b2
				&& (7 * (v1[i] - v0[j]) + v0[j]) == b3) {
				printf("*********\n");
				printf("v1=0x%x\n", v1[i]);
				printf("v0=0x%x\n", v0[j]);
			}
		}
	}
	

	printf("No Solution!\n");
	return 0;
}
#include "stdafx.h"
#include "stdio.h"


//中国剩余定理  
struct node {
	int divisor;            //表示除数  
	int  remainder;     //表示余数  
}T[1000];

//求最大公约数  
int gcd(int n, int m)
{
	return m ? gcd(m, n%m) : n;
}

int v1[0x7ffffff] = { 0 };
int v0[0x7ffffff] = { 0 };

int getV(int b0, int b1, int l0, int l1, int* v) {
	//MAX_NUM表示的是所求的解的范围的最大值,MIN_NUM表示所求的解的范围的最小值,  
	//n表示的是同于方程的个数,m表示的是三个除数的乘积,gcd_max表示的是两个数的最大公约数,因为三个除数是互素的  
	//所以gcd_max=1;  
	int i, j, n, t = 0, m = 1, sum = 0, gcd_max = 0, MAX_NUM, MIN_NUM;


	//printf("请输入有几个方程:\n");   //如上题韩信点兵。输入3  
	//scanf_s("%d", &n);
	printf("请输入每组数据(  余数 除数):\n"); // 3 2 5 4 7 6  
	n = 2;
	T[0].remainder = b0 % l0;
	T[0].divisor = l0;

	T[1].remainder = b1 % l1;
	T[1].divisor = l1;
	//printf("请输入所求值的值域:min max\n");
	//scanf_s("%x%x", &MIN_NUM, &MAX_NUM);
	//求出三个除数的乘积m  
	for (i = 0; i < n; i++) {
		gcd_max = gcd(T[i].divisor, gcd_max);
		m = m * T[i].divisor;
	}
	gcd_max *= m;
	//求mI  
	for (i = 0; i < n; i++)
	{
		t = 0; m = 1;
		for (j = 0; j < n; j++)
		{
			if (j != i)
			{
				t = gcd(T[j].divisor, t);
				m = m * T[j].divisor;
			}
		}
		t = m * t;
		m = t;
		while (m % T[i].divisor != 1)
			m += t;
		sum += m * T[i].remainder;
	}
	printf("最小的值为:\n");
	printf("%d\n", sum % gcd_max);
	printf("在所求的值域内值:\n");
	printf("%x\n", sum);
	int count = 0;
	while (sum < 0x7e7e7e7e) {
		if (sum >= 0x20202020) {
			//&& (sum & 0xff000000) >= 0x20000000 && (sum & 0xff000000) <= 0x7e000000
			//&& (sum & 0x00ff0000) >= 0x00200000 && (sum & 0x00ff0000) <= 0x007e0000
			//&& (sum & 0x0000ff00) >= 0x00002000 && (sum & 0x0000ff00) <= 0x00007e00
			//&& (sum & 0x000000ff) >= 0x00000020 && (sum & 0x000000ff) <= 0x0000007e) {
			//printf("0x%x   \n", sum);
			v[count] = sum;
			count += 1;
		}

		sum += gcd_max;

	}
	printf("%x\n", sum);
	printf("%d\n", count);
	return count;
}

int main()
{
	int b0 = 0x8F503a42;
	int b1 = 0xEF503a42;
	int b2 = 0xF3A94883;
	int b3 = 0x33A94883;

	printf("%i<->5\n", b0 % 5);
	printf("%i<->17\n", b2 % 17);

	printf("%i<->13\n", b1 % 13);
	printf("%i<->7\n", b3 % 7);

	int len1 = getV(b0, b2, 5, 17, v1);
	int len0 = getV(b1, b3, 13, 7, v0);

	for (int i = 0; i < len1; ++i) {
		for (int j = 0; j < len0; ++j) {
			if ((5 * (v1[i] - v0[j]) + v1[i]) == b0
				&& (13 * (v1[i] - v0[j]) + v0[j]) == b1
				&& (17 * (v1[i] - v0[j]) + v1[i]) == b2
				&& (7 * (v1[i] - v0[j]) + v0[j]) == b3) {
				printf("*********\n");
				printf("v1=0x%x\n", v1[i]);
				printf("v0=0x%x\n", v0[j]);
			}
		}
	}
	

	printf("No Solution!\n");
	return 0;
}



[培训]12月3日2020京麒网络安全大会《物联网安全攻防实战》训练营,正在火热报名中!地点:北京 · 新云南皇冠假日酒店

收藏
点赞0
打赏
分享
最新回复 (0)
游客
登录 | 注册 方可回帖
返回