既然是个逆向题,就一定有逆向的做法
学习链接:https://bbs.pediy.com/thread-229327.htm
把题目中的运算理解成代数运算中的双射:
正向时:已知(a,b,c)可求d,那么逆向是已知d的,a,b,c三个数可以“知二求一”
也即,a、b、c、d四个数知三求一
于是,构造CM的逆运算成为了可能,倒过来算20步可以把Input运算出来(再正向检验)
逆向思路:
我们要从数列的第Xn项,逆向算到数列的第1项,本质上是一个重复的不断爆破密钥a,b,c的过程
由于a,b,c满足题意中的某种数学关系,导致暴力枚举成为了可能(64 * 64 *64,且满足出现频率的关系)
深度固定的while循环爆破
所以,如果全部爆破,每个数有64种选择,总共要爆破出来16个数,达到了64 ^ 16的计算量,还得计算20次,这样做是不现实的,于是,可以提前把表格打好进行预先处理
result[0]: 0 1 2
result[1]: 3 4 0
result[2]: 5 6 0
result[3]: 5 7 1
result[4]: 4 6 1
result[5]: 8 2 3
result[6]: 9 2 4
result[7]: 7 10 3
result[8]: 8 12 5
result[9]: 11 13 6
result[10]: 12 13 7
result[11]: 11 14 9
result[12]: 14 8 10
result[13]: 15 9 10
result[14]: 15 11 12
result[15]: 15 13 14
假设,我们已知的值是result[16]这个数组,要求的是前一轮的result,不妨把这16个值设为x0,x1,……,x15
我们对x0,x1进行枚举之后,可以发现:x2不需要枚举,可以通过x0、x1、result[0]求出来,继续这么来的话:
枚举x3之后,x4可以通过x0,x3,result[1]求出
枚举x5之后,x6可以通过x0,x5,result[2]求出(同时需要检验:x1、x4、x6与result[4]的关系)
x7可以通过x1,x5,result[3]求出
x8可以通过x2,x3,result[5]求出
得到如下的爆破代码:
#include <iostream>
#include <stdio.h>
using namespace std;
typedef unsigned char u8;
u8 cube[64][64][64];
u8 GetNumber1[64][64][64];
u8 GetNumber2[64][64][64];
u8 GetNumber3[64][64][64];
u8 result[16] = {0x14,0x22,0x1E,0x10,0x38,0x30,0x18,0x10,4,0x1A,0x24,8,2,0x26,0x38,0x2A};
void Print(int x){
printf("<%d>: ",x);
for(int i = 0; i < 16; i++)
printf("%02X ",result[i]);
char *sz = "abcdefghijklmnopqrstuvwxyz+-ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
for(int i = 0; i < 16; i++)
printf("%c",sz[result[i]]);
puts("");
}
void test(){
u8 x0,x1,x2,x3,x4,x5,x6,x7,x8,x9,x10,x11,x12,x13,x14,x15;
for(x0 = 0; x0 < 64; x0++)
for(x1 = 0; x1 < 64; x1++){
x2 = GetNumber3[x0][x1][result[0]];
for(x3 = 0; x3 < 64; x3++){
x4 = GetNumber2[x3][result[1]][x0];
for(x5 = 0; x5 < 64; x5++){
x6 = GetNumber2[x5][result[2]][x0];
if (x6 == GetNumber2[x4][result[4]][x1]){
x7 = GetNumber2[x5][result[3]][x1];
x8 = GetNumber1[result[5]][x2][x3];
x9 = GetNumber1[result[6]][x2][x4];
x10 = GetNumber2[x7][result[7]][x3];
x12 = GetNumber2[x8][result[8]][x5];
x15 = GetNumber1[result[13]][x9][x10];
x11 = GetNumber2[x15][result[14]][x12];
x14 = GetNumber2[x11][result[11]][x9];
x13 = GetNumber2[x11][result[9]][x6];
if (GetNumber1[result[10]][x13][x7] == x12 &&
GetNumber1[result[12]][x8][x10] == x14 &&
GetNumber1[result[15]][x13][x14] == x15){
result[0] = x0;
result[1] = x1;
result[2] = x2;
result[3] = x3;
result[4] = x4;
result[5] = x5;
result[6] = x6;
result[7] = x7;
result[8] = x8;
result[9] = x9;
result[10] = x10;
result[11] = x11;
result[12] = x12;
result[13] = x13;
result[14] = x14;
result[15] = x15;
return;
}
}
}
}
}
}
int main(){
FILE *f = fopen("Escape.exe","rb");
fseek(f,0xe4f0,0);
fread(cube,64*64*64,1,f);
fclose(f);
for(int i = 0; i < 64; i++)
for(int j = 0; j < 64; j++)
for(int k = 0; k < 64; k++){
GetNumber1[cube[i][j][k]][j][k] = i;
GetNumber2[i][cube[i][j][k]][k] = j;
GetNumber3[i][j][cube[i][j][k]] = k;
}
Print(0);
for(int i = 1; i <= 0x500; i++){
test();
Print(i);
}
return 0;
}