鹅厂极客技术挑战赛 - 题解

发表于 分类于 Disqus： 本文字数： 5.2k 阅读时长 ≈ 5 分钟

0x00 缘由

端午假期看到我在鹅厂做安全的推送发了一道很有意思的比赛推送：

一道即将尘封十几年的封印，不来尝试解开吗？

赛题通过AES加密层层包裹起来，很有意思，于是试着做了一下，直接断断续续用了两天的时间最终搞定，遂记录下解题步骤。

0x01 题目

需python3运行环境，代码请保存为UTF8格式文件，若提示缺失AES库，则通过pip工具安装AES库，Linux：pip3 install pycrypto, Windows: pip install pycryptodome：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
from Crypto.Cipher import AES
import base64
import time
import gzip
from hashlib import md5
import sys
import io
sys.stdout = io.TextIOWrapper(sys.stdout.detach(), encoding='utf-8', line_buffering=True)

def Decrypt(key:str, text:str) -> str:
  if len(key) < 32: key += ' ' * (32 - len(key))
  elif len(key) > 32: key = key[0:32]
  cipher = AES.new(bytes(key,encoding='utf-8'), AES.MODE_CBC, bytes(AES.block_size))
  return str(gzip.decompress(bytes.strip(cipher.decrypt(base64.b64decode(text)))), encoding='utf-8')


def Pass(id, priv_key):
  prefix = str(id) + str(int(time.time()))
  pub_key = prefix + md5(bytes(prefix + priv_key, 'utf8')).hexdigest()
  print('恭喜通过第%d关,通关公钥:%s' % (id, pub_key))

key=input('1+1=')
exec(Decrypt(key,'

0x02 题解

试题一共八道，用AES层层包裹起来，上一道题的答案是下一道题相关代码的解密密钥。

第一题

1
1+1=

最简单的问题，输入2进入下一题

第二题

1
(x*18-27)/3-(x+7496)=0, x=

一个一次方程，应该是小学高年级的问题，x=1501

第三题

1
41*x-31*x^2+74252906=0,(x^2表示x的2次方,下同),x的某个根=

二次方程，需要求根公式求解，输入那个整数的解：x=-1547

第四题

1
(1234567^12345678901234567890)%999999997=

大数高次方求余，可以参考快速幂取模的算法:https://stackoverflow.com/questions/8496182/calculating-powa-b-mod-n。

第五题

1
1_2_3_4_5_6_7_8_9=-497,每处_填入1个运算符+-*/,且4个运算符必须都用上,使得等式成立(答案保证唯一),表达式为?

通过python写一个脚本，通过eval函数执行算式。

P.s Python真的对大数支持和这种算式处理的支持超棒，前面用C++哼哧哼哧写了半天，回头来python一个函数解决问题。

第六题

1
x^5-2*x^4+3*x^3-4*x^2-5*x-6=0, x(精确到小数点后14位)=

五次方程是没有求根公式的，只能通过Newton-Raphson法去接近正确解。（这个也是当年卡西欧991计算器上的传统艺能了）

第七题

1
请输入8位数字PIN码:

从这题开始就需要看源代码的基础上解题了，通过查看上一题输入密钥之后解密出来的Python代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
def Hash(context):
        result = md5(bytes(context, 'utf8'))
        for i in range(0, 10000000):
                result = md5(result.digest())
        return result.hexdigest()

Pass(6, 'xxxxxxxxxxx')  # xxx为上一题私钥
key=input('请输入8位数字PIN码:')
print("验证中……")
if Hash(key) == '5f4654140971c47658de19d62ba472b6':
        exec(Decrypt(key,'rO0WHILNhxy......')) # 此处密文省略
else:
        print("PIN码错误")

也就是输入的PIN码做一千万遍哈希之后需要得到5f4654140971c47658de19d62ba472b6才行。这……想想暴力方法每个PIN算一千万次MD5再来对照，需要尝试40多年，除非搞个像比特币挖矿一样的集群来算了。加速很难，逆向MD5一次还行，10000000也没人建彩虹表，想了想出题人精妙的把这些路堵死了，一定就留了 特殊の解題方式 。

仔细一看可以发现解密并不依赖Hash函数产出的结果，直接PIN码尝试能否在Decrypt函数里正确作为AES密钥解密密文即可。时间被压缩到了几十分钟量级，同时搜索也可以直接并行进行。为了避免Mac风扇呼呼呼乱转，直接去腾讯云开了个八核计时收费的实例【并没有收到腾讯云广告费】,八进程算了5分钟左右得到答案。

运算

第八题

第八题一来就是：

1
计算第8关密钥中,时间可能非常长...

等你等了一天发现还没出来题目，你就发现中计了。
代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
print('计算第8关密钥中,时间可能非常长...')
stack = []
ins_len = [1] * 5 + [2] * 9 + [9, 1]
reg = [0] * 16
code = base64.b64decode('zyLpMs8CL9Oy/3QDdRlURZRGFHQHdRhURZFGIL/lv+MiNi+70AXRBtMD1wfYCNkJ5v3/iV14RWMB0n+/xgk=')
while True:
        ins, r0 = code[reg[15]] >> 4, code[reg[15]] & 15
        length = ins_len[ins]
        if length > 1:
                arg = code[reg[15] + 1 : reg[15] + length]
                if length == 2: r1 = arg[0] >> 4; r2 = arg[0] & 15
        reg[15] += length
        if 0 == ins : break
        elif 1 == ins : stack.append(reg[r0])
        elif 2 == ins : reg[r0] = stack.pop()
        elif 3 == ins : 
                if not reg[r0] : reg[15] += ins_len[code[reg[15]] >> 4]
        elif 4 == ins : reg[r0] = 0 if reg[r0] else 1
        elif 5 == ins : reg[r0] = reg[r1] + reg[r2]
        elif 6 == ins : reg[r0] = reg[r1] - reg[r2]
        elif 7 == ins : reg[r0] = reg[r1] * reg[r2]
        elif 8 == ins : reg[r0] = reg[r1] / reg[r2]
        elif 9 == ins : reg[r0] = reg[r1] % reg[r2]
        elif 10 == ins : reg[r0] = 1 if reg[r1] < reg[r2] else 0
        elif 11 == ins : stack.append(reg[r0]); reg[r0] += int.from_bytes(arg, byteorder='little', signed=True)
        elif 12 == ins : reg[r0] += int.from_bytes(arg, byteorder='little', signed=True)
        elif ins in (13, 14) : reg[r0] = int.from_bytes(arg, byteorder='little', signed=True)

key = str(reg[0])+str(reg[1])
exec(Decrypt(key,'F4lqUHz...')) # 同上，省略密文

这这这…… 直接代码写了个处理器加指令集啊。一时间仿佛回到当时刷CS:APP bomb lab的时光。（如果要补充此题需要的背景知识，推荐刷下《深入理解计算机系统》第三章）

base64的那段机器码变成十六进制如下：

1
2
code = base64.b64decode('zyLpMs8CL9Oy/3QDdRlURZRGFHQHdRhURZFGIL/lv+MiNi+70AXRBtMD1wfYCNkJ5v3/iV14RWMB0n+/xgk=')
# cf22e932cf022fd3b2ff740375195445944614740775185445914620bfe5bfe322362fbbd005d106d303d707d808d909e6fdff895d78456301d27fbfc609

翻译出来结构基本如下：
code

1
2
3
4
5
6
7
8
9
10
11
12
13
void Calcu(__int128_t *x, __int128_t *y, const int t) {
  if (t == 0) return;
  __int128_t tmp_x = (3 * (*x) + 9 * (*y)) % kDiv;
  *y = (7 * (*x) + 8 * (*y)) % kDiv;
  *x = tmp_x;
  Calcu(x, y, t - 1);
  Calcu(x, y, t - 1);
  return;
}

int main(int argc, char const *argv[]) {
  Calcu(5, 6, 127)
}

第一阶段的计组知识考查结束，接下来就是如何算出结果的问题了，很多人的思路在优化运算速度上，但看看Calcu这个函数的递归方式，一个127层高的树，总计需要调用函数2^127 - 1次，差不多在 10^38 量级，从宇宙大爆炸到现在是断然算不完的。

我们可以把Calcu函数变成循环的形式：

1
2
3
4
5
6
7
8
9
10
11
12
13
void CalcuN(__uint128_t *x, __uint128_t *y, const int t) {
  // 1 -> 1
  // 2 -> 1 + 1 + 1 -> 3
  // 3 -> 1 + 3 + 3 -> 7
  unsigned long long times = pow(2, t) - 1;
  std::cout << "cal times:" << times << std::endl;
  for (unsigned long long i = 0; i < times; ++i) {
    __uint128_t tmp_x = (3 * (*x) + 9 * (*y)) % kDiv;
    *y = (7 * (*x) + 8 * (*y)) % kDiv;
    *x = tmp_x;
  }
  return;
}

接下来可以看到下面x、y的迭代方式很熟悉，可以改成矩阵的形式：

而前面的高次矩阵的幂求余也是可以通过快速幂优化的（做题的时候卡在这里很久，甚至还自己证明了一遍矩阵的模的分解律）。参考第六题解法，直接就能快速求得结果。

P.S.这里也是发现，用C++本来是想加快求解速度，但大数处理各种系统不支持__uint128_t的hash函数等各种问题卡了很久，写出来之后还发现不管是暴力求解还是妄图寻找到一个循环规律都没有办法，看到99999999999999997是质数之后估计出题人是希望结果均匀分布减少循环出现，才想到从数学理论角度推导下有没简单方法。想出解题办法后反倒是python方便调试也快速取得了结果。事实证明码力不到压榨语言极限的程度，用c++真的是自寻烦恼[旺财]。

各题答案

  • 2
  • 1501
  • -1547
  • 42031180
  • 1/234-5+6-789
  • 2.19488134060852
  • 79547124
  • 3298258025528854553625821261494113