当前位置：首页 > news >正文

[GUET-CTF2019]number_game[数独]

news 2025/6/29 5:42:42

题目

学到的知识点：

题目

在buu上看到了一道数独题，没见过，记录一下

下载附件，查壳，无壳，在IDA中打开，直接找到主函数

unsigned __int64 __fastcall main(int a1, char **a2, char **a3)
{__int64 v4; // [rsp+8h] [rbp-38h]__int64 input; // [rsp+10h] [rbp-30h] BYREF__int16 v6; // [rsp+18h] [rbp-28h]__int64 v7; // [rsp+20h] [rbp-20h] BYREF__int16 v8; // [rsp+28h] [rbp-18h]char v9; // [rsp+2Ah] [rbp-16h]unsigned __int64 v10; // [rsp+38h] [rbp-8h]v10 = __readfsqword(0x28u);input = 0LL;v6 = 0;v7 = 0LL;v8 = 0;v9 = 0;scanf("%s", &input);if ( function(&input) )                       // 0<v5[i]<=4并且len(v5)==10{v4 = function_1(&input, 0LL, 10LL);         // 建树function_2(v4, &v7);                        // 令v7=input// 中序遍历  递归v9 = 0;function_3(&v7);                            // 将中序遍历后的数据存入到一段内存中if ( function_4() )                         // 这里进行判断是是将中序遍历转换后的字符串{                                           // 实际上就是根据中序遍历求出原本的输入puts("TQL!");printf("flag{");printf("%s", &input);puts("}");}else{puts("your are cxk!!");}}return __readfsqword(0x28u) ^ v10;
}

大致理一下思路，可以看到

首先输入一串字符串，在function函数中进行了判断（确保输入的值在字符‘0’~‘4’之间，并且长度要为10）

接着在function_1中进行建树

_QWORD *__fastcall sub_400758(__int64 input, int i, signed int len)
{char cnt; // [rsp+1Fh] [rbp-11h]_QWORD *v6; // [rsp+28h] [rbp-8h]cnt = *(i + input);if ( cnt == ' ' || cnt == '\n' || i >= len )  // 判段输入不为空格和换行符return 0LL;v6 = malloc(0x18uLL);                         // 申请一块内存*v6 = cnt;                                    // 存储根结点v6[1] = function_1(input, 2 * i + 1, len);    // 递归调用，存储左子树和右子树v6[2] = function_1(input, 2 * (i + 1), len);return v6;
}

再在function_2中进行中序遍历的变换

__int64 __fastcall sub_400807(__int64 v4, __int64 v7)
{__int64 result; // raxresult = v4;if ( v4 ){function_2(*(v4 + 8), v7);                  // 左子树*(v7 + dword_601080++) = *v4;               // 保存根结点return function_2(*(v4 + 16), v7);          // 右子树}return result;
}

把经过中序变换的数据在fnction_3里面存储到一段内存中

__int64 __fastcall sub_400881(char *a1)
{__int64 result; // raxbyte_601062 = *a1;byte_601067 = a1[1];byte_601069 = a1[2];byte_60106B = a1[3];byte_60106E = a1[4];byte_60106F = a1[5];byte_601071 = a1[6];byte_601072 = a1[7];byte_601076 = a1[8];result = a1[9];byte_601077 = a1[9];return result;
}

最后进入function_4函数，function_4函数是一个数独游戏函数，代码如下

__int64 sub_400917()
{unsigned int v1; // [rsp+0h] [rbp-10h]int i; // [rsp+4h] [rbp-Ch]int j; // [rsp+8h] [rbp-8h]int k; // [rsp+Ch] [rbp-4h]v1 = 1;for ( i = 0; i <= 4; ++i )                    // 5*5数独游戏{for ( j = 0; j <= 4; ++j ){for ( k = j + 1; k <= 4; ++k ){if ( *(&unk_601060 + 5 * i + j) == *(&unk_601060 + 5 * i + k) )// 每行数无重复元素v1 = 0;if ( *(&unk_601060 + 5 * j + i) == *(&unk_601060 + 5 * k + i) )// 每列数无重复元素v1 = 0;}}}return v1;
}

5*5的数独函数，两个if语句判断要求每行元素不重复，每列元素不重复

大致思路就是输入一段字符串，进行给定二叉树的存储，然后再中序遍历存储，最后判断是否满足数独函数，满足则输出正确，反之，错误

二叉树如何存储的呢？树的结构与对应输入树的值存储关系如下

用0~9的数输入来测试输出的顺序。经过变换后的结果是：7381940526

数独矩阵为

手动解出结果为：0421421430，只要使输入的结果经过变换后满足此顺序即可

借用一下大佬的脚本解密

map = [7, 3, 8, 1, 9, 4, 0, 5, 2, 6] # 对应关系
v7 = [48, 52, 50, 49, 52, 50, 49, 52, 51, 48]
flag=[0]*10for i in range(10):flag[map[i]] = chr(v7[i])
flag=''.join(flag)
print('flag{'+flag+'}')
# 1134240024