[GUET-CTF2019]number

[GUET-CTF2019]number_game[数独]

题目

学到的知识点：

题目

在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; // rax

  result = 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; // rax

  byte_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]*10
 
for i in range(10):
    flag[map[i]] = chr(v7[i])
flag=''.join(flag)
print('flag{'+flag+'}')
# 1134240024