既然是个逆向题,就一定有逆向的做法

学习链接: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;
}