[原创]CTF第二题的求解思路
工具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;
}
注意：上传附件及图片大小不得大于30M。
⚠️ 版权声明：
本博客所有内容（含教程、源码、工具）仅供个人技术学习与研究交流使用，严禁商用、倒卖、二次分发及非法用途。
未经作者书面授权，任何组织或个人不得转载、复制或用于其他平台，违者将追究相关责任。
参与讨论
登录后可查看全部回复并参与讨论。
