2020 0CTF Unlimited

PHP AST + 反混淆 + 矩阵快速幂

唯一带有Web特征的逆向题

题目是一个经过混淆的PHP抽象语法树文件,请点击题目下载

一开始想直接找抽象语法树(AST)转为PHP代码的函数,找到了pretty_printing,但是尝试许久,无法直接将AST初始化

JsonDecoder

继续查资料看到PHP-Parser可以将json字符串和AST进行互转

https://github.com/nikic/PHP-Parser/blob/master/lib/PhpParser/JsonDecoder.php

AST转json脚本如下

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
<?php
require dirname(__FILE__).'/vendor/autoload.php';
use PhpParser\Error;
use PhpParser\ParserFactory;
use PhpParser\PrettyPrinter;
use PhpParser\NodeDumper;

$code = <<<'CODE'
<?php

function printLine($msg) {
echo $msg;
}
CODE;

// PHP转化为AST再转化为Json
$parser = (new ParserFactory)->create(ParserFactory::PREFER_PHP7);
try {
// PHP => AST
$ast = $parser->parse($code);
$dumper = new NodeDumper;
echo $dumper->dump($ast) . "\n";

// AST => Json
$json = json_encode($ast, JSON_PRETTY_PRINT);
echo $json, "\n";

} catch (PhpParser\Error $e) {
echo 'Parse Error: ', $e->getMessage();
}

// Json转化为AST再转化为PHP
$json = file_get_contents("3.json");
// $json = <<<'CODE'
// ]
// CODE;
// Json => AST
$jsonDecoder = new PhpParser\JsonDecoder();
$ast = $jsonDecoder->decode($json);
// AST => PHP
$parser = (new ParserFactory)->create(ParserFactory::PREFER_PHP7);
$prettyPrinter = new PrettyPrinter\Standard;
$code = $prettyPrinter->prettyPrint($ast);
echo $code, "\n";

其中json字符串如下

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
31
32
33
34
35
36
37
38
39
40
41
42
[
{
"nodeType": "Stmt_Function",
"byRef": false,
"name": {
"nodeType": "Identifier",
"name": "printLine"
},
"params": [
{
"nodeType": "Param",
"type": null,
"byRef": false,
"variadic": false,
"var": {
"nodeType": "Expr_Variable",
"name": "msg",
"attributes": {
"startLine": 3,
"endLine": 3
}
},
"default": null,
"flags": 0,
"attrGroups": []
}
],
"returnType": null,
"stmts": [
{
"nodeType": "Stmt_Echo",
"exprs": [
{
"nodeType": "Expr_Variable",
"name": "msg"
}
]
}
],
"attrGroups": []
}
]

AST如下

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
31
32
33
34
array(
0: Stmt_Function(
attrGroups: array(
)
byRef: false
name: Identifier(
name: printLine
)
params: array(
0: Param(
attrGroups: array(
)
flags: 0
type: null
byRef: false
variadic: false
var: Expr_Variable(
name: msg
)
default: null
)
)
returnType: null
stmts: array(
0: Stmt_Echo(
exprs: array(
0: Expr_Variable(
name: msg
)
)
)
)
)
)

根据上面的例子,我们可以观察到要把AST转为Json需要进行以下处理:

  1. array(...)转换为[...]
  2. Stmt_Function(...) 转化为{"nodeType": "Stmt_Function", ...}
  3. 对于全部字符串要加上引号
  4. "nodeType"后面添加"attributes": {}属性

这里给出一个AST转Json的脚本

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
31
32
33
34
35
36
37
38
39
40
41
42
import re

data = open("output.txt", "r").readlines()
out = open("4.json", "w")
lines = len(data)

brackets = []

for line in range(lines):
tmp = data[line].strip("\n")
# 检测 array
res1 = re.findall(r"array\(", tmp)
if res1:
brackets.append("]")
tmp = tmp.replace("array(", "[")
# 检测 class
res2 = re.findall(r"(\w+)\(", tmp)
if res2:
brackets.append("}")
tmp = tmp.replace(res2[0] + "(", "{nodeType: %s, attributes: {}" % res2[0])
# 删除多余标签
res3 = re.findall(r"(\d+: )", tmp)
if res3:
tmp = tmp.replace(res3[0], '')
# 添加引号
res4 = re.findall(r"(flag\{| \}|[\w\-]+)", tmp)
if res4:
for word in res4:
if not (word.isdigit() or word == "null" or word == "true" or word == "false"):
if word == " }":
word = "}"
tmp = tmp.replace(word, '"%s"' % word)
# 匹配右括号
if ")" in tmp:
tmp = tmp.replace(")", brackets.pop())

# 添加逗号
if ((line + 1) < lines) and (not ")" in data[line + 1]) and (not "[" in tmp):
tmp = tmp + ","
# 写进文件
out.write(tmp + "\n")
out.close()

最后再用上面的pretty_printing代码转出一份稍微好看点的混淆过的PHP代码

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
<?php 
$l1IIl1II1l = function ($lII1lI1IlI) {
return function ($II1IlllI11) use($lII1lI1IlI) {
return function ($ll1IlllIIl) use($II1IlllI11, $lII1lI1IlI) {
return $II1IlllI11($lII1lI1IlI($II1IlllI11)($ll1IlllIIl));
};
};
};
$llIIllIlll = function ($lII1lI1IlI) {
return $lII1lI1IlI + 1;
};
$I1lll111II = function ($lIlIll1111) {
return function ($II1IIl1Ill) use($lIlIll1111) {
return function ($II1IlllI11) use($lIlIll1111, $II1IIl1Ill) {
return function ($ll1IlllIIl) use($II1IlllI11, $lIlIll1111, $II1IIl1Ill) {
return $lIlIll1111($II1IlllI11)($II1IIl1Ill($II1IlllI11)($ll1IlllIIl));
};
};
};
};
$I1II11lIl1 = function ($lII1lI1IlI) {
return $lII1lI1IlI - 1;
};
$I1IIlII1Il = function ($II1IlllI11) {
return function ($ll1IlllIIl) {
return $ll1IlllIIl;
};
};
$IIl1II1lIl = function ($lII1lI1IlI) {
return $lII1lI1IlI * 3 % 7;
};
$I1IllI1l11 = function ($lIlIll1111) use($I1lll111II, $I1IIlII1Il) {
return function ($II1IIl1Ill) use($lIlIll1111, $I1lll111II, $I1IIlII1Il) {
return $lIlIll1111($I1lll111II($II1IIl1Ill))($I1IIlII1Il);
};
};
$l1I11lll1l = function ($II1IlllI11) {
return function ($ll1IlllIIl) use($II1IlllI11) {
return $II1IlllI11($ll1IlllIIl);
};
};
$lIl1l1lIlI = function ($lII1lI1IlI) {
return ($lII1lI1IlI + 1) % 1000000007;
};
$l1llIlll1l = array(array($I1lll111II($l1IIl1II1l($I1lll111II($I1lll111II($l1I11lll1l)($I1lll111II($l1I11lll1l)($I1lll111II($l1IIl1II1l($l1I11lll1l))($l1I11lll1l))))($l1I11lll1l)))($l1I11lll1l), $I1lll111II($I1lll111II($l1I11lll1l)($l1IIl1II1l($l1IIl1II1l($l1I11lll1l))))($I1lll111II($l1I11lll1l)($I1lll111II($l1IIl1II1l($l1I11lll1l))($I1lll111II($l1I11lll1l)($l1I11lll1l)))), $l1IIl1II1l($I1lll111II($I1lll111II($l1IIl1II1l($I1lll111II($l1I11lll1l)($I1lll111II($I1lll111II($l1I11lll1l)($I1lll111II($l1I11lll1l)($l1I11lll1l)))($l1I11lll1l))))($l1I11lll1l))($l1I11lll1l)), $I1IllI1l11($l1IIl1II1l($l1I11lll1l))($l1IIl1II1l($l1I11lll1l)), $I1IIlII1Il, $I1IllI1l11($l1IIl1II1l($l1I11lll1l))($I1lll111II($l1I11lll1l)($l1IIl1II1l($l1IIl1II1l($l1I11lll1l)))), $I1lll111II($l1IIl1II1l($l1I11lll1l))($I1lll111II($l1I11lll1l)($I1IllI1l11($I1lll111II($l1I11lll1l)($l1I11lll1l))($l1IIl1II1l($I1lll111II($l1I11lll1l)($l1I11lll1l))))), $l1IIl1II1l($l1IIl1II1l($I1lll111II($l1I11lll1l)($I1lll111II($l1I11lll1l)($l1I11lll1l)))), $I1lll111II($l1I11lll1l)($I1lll111II($l1I11lll1l)($l1I11lll1l))), array($I1lll111II($I1lll111II($l1I11lll1l)($I1lll111II($l1I11lll1l)($l1I11lll1l)))($I1lll111II($l1I11lll1l)($I1lll111II($I1lll111II($l1I11lll1l)($I1lll111II($l1I11lll1l)($l1I11lll1l)))($l1I11lll1l))), $I1IIlII1Il, $l1IIl1II1l($l1IIl1II1l($l1I11lll1l)), $I1lll111II($I1lll111II($I1IllI1l11($I1lll111II($l1IIl1II1l($l1I11lll1l))($l1I11lll1l))($I1lll111II($l1I11lll1l)($l1I11lll1l)))($l1I11lll1l))($l1I11lll1l), $I1IIlII1Il, $l1IIl1II1l($I1lll111II($I1lll111II($l1I11lll1l)($l1I11lll1l))($l1IIl1II1l($l1I11lll1l))), $I1lll111II($I1lll111II($I1lll111II($I1lll111II($l1I11lll1l)($l1IIl1II1l($l1I11lll1l)))($I1lll111II($l1I11lll1l)($l1I11lll1l)))($l1I11lll1l))($I1lll111II($l1I11lll1l)($l1IIl1II1l($l1I11lll1l))), $I1lll111II($I1lll111II($l1I11lll1l)($I1lll111II($l1I11lll1l)($l1I11lll1l)))($I1lll111II($I1lll111II($l1IIl1II1l($l1I11lll1l))($I1lll111II($l1I11lll1l)($l1I11lll1l)))($I1lll111II($l1I11lll1l)($l1I11lll1l))), $I1IllI1l11($l1IIl1II1l($l1I11lll1l))($I1lll111II($l1I11lll1l)($I1lll111II($l1I11lll1l)($l1IIl1II1l($l1I11lll1l))))), array($I1lll111II($I1lll111II($l1I11lll1l)($l1I11lll1l))($l1I11lll1l), $l1IIl1II1l($l1I11lll1l), $I1IIlII1Il, $l1IIl1II1l($I1lll111II($I1IllI1l11($l1IIl1II1l($l1I11lll1l))($I1lll111II($l1I11lll1l)($I1lll111II($l1I11lll1l)($l1I11lll1l))))($l1I11lll1l)), $I1lll111II($l1I11lll1l)($l1I11lll1l), $I1lll111II($l1I11lll1l)($I1lll111II($l1IIl1II1l($I1lll111II($l1I11lll1l)($I1lll111II($l1I11lll1l)($l1I11lll1l))))($l1I11lll1l)), $I1IIlII1Il, $l1I11lll1l, $I1lll111II($l1I11lll1l)($I1lll111II($I1lll111II($I1lll111II($l1I11lll1l)($l1IIl1II1l($l1I11lll1l)))($I1lll111II($l1I11lll1l)($I1lll111II($l1I11lll1l)($l1I11lll1l))))($l1IIl1II1l($l1I11lll1l)))), array($l1IIl1II1l($I1lll111II($I1lll111II($l1IIl1II1l($I1lll111II($l1I11lll1l)($l1I11lll1l)))($l1IIl1II1l($I1lll111II($l1I11lll1l)($l1I11lll1l))))($I1lll111II($l1I11lll1l)($l1I11lll1l))), $I1lll111II($l1IIl1II1l($I1lll111II($I1lll111II($l1I11lll1l)($l1I11lll1l))($l1I11lll1l)))($l1IIl1II1l($I1lll111II($l1I11lll1l)($l1I11lll1l))), $l1IIl1II1l($l1IIl1II1l($l1I11lll1l)), $I1lll111II($l1I11lll1l)($l1I11lll1l), $l1I11lll1l, $I1IIlII1Il, $I1lll111II($l1I11lll1l)($I1IllI1l11($I1lll111II($l1I11lll1l)($l1I11lll1l))($I1lll111II($l1I11lll1l)($l1I11lll1l))), $I1lll111II($l1IIl1II1l($I1IllI1l11($I1lll111II($I1lll111II($l1I11lll1l)($l1I11lll1l))($l1I11lll1l))($I1lll111II($l1I11lll1l)($l1I11lll1l))))($I1lll111II($l1I11lll1l)($l1I11lll1l)), $I1lll111II($I1lll111II($I1lll111II($l1I11lll1l)($I1lll111II($l1I11lll1l)($l1I11lll1l)))($I1lll111II($I1lll111II($l1IIl1II1l($l1I11lll1l))($l1I11lll1l))($l1I11lll1l)))($I1lll111II($l1I11lll1l)($l1I11lll1l))), array($I1lll111II($I1lll111II($I1lll111II($l1I11lll1l)($l1I11lll1l))($l1I11lll1l))($I1lll111II($l1I11lll1l)($I1lll111II($I1lll111II($l1I11lll1l)($l1I11lll1l))($I1lll111II($l1I11lll1l)($l1I11lll1l)))), $I1lll111II($I1lll111II($l1I11lll1l)($l1IIl1II1l($I1lll111II($l1I11lll1l)($l1IIl1II1l($l1I11lll1l)))))($I1lll111II($l1I11lll1l)($l1IIl1II1l($l1I11lll1l))), $I1IllI1l11($I1lll111II($l1IIl1II1l($l1I11lll1l))($l1I11lll1l))($I1lll111II($l1IIl1II1l($l1I11lll1l))($l1I11lll1l)), $I1lll111II($l1I11lll1l)($I1lll111II($l1I11lll1l)($I1lll111II($l1I11lll1l)($l1I11lll1l))), $I1IIlII1Il, $I1lll111II($l1IIl1II1l($l1I11lll1l))($l1I11lll1l), $I1lll111II($I1lll111II($l1I11lll1l)($l1IIl1II1l($l1IIl1II1l($l1I11lll1l))))($l1I11lll1l), $l1I11lll1l, $I1lll111II($l1I11lll1l)($I1lll111II($I1lll111II($l1I11lll1l)($l1I11lll1l))($I1lll111II($l1I11lll1l)($l1I11lll1l)))), array($I1lll111II($l1I11lll1l)($l1I11lll1l), $l1IIl1II1l($I1lll111II($l1IIl1II1l($l1I11lll1l))($I1IllI1l11($I1lll111II($l1IIl1II1l($l1I11lll1l))($l1I11lll1l))($l1IIl1II1l($l1I11lll1l)))), $l1IIl1II1l($l1I11lll1l), $I1IIlII1Il, $I1lll111II($I1IllI1l11($l1IIl1II1l($l1I11lll1l))($l1IIl1II1l($l1I11lll1l)))($I1lll111II($I1lll111II($l1I11lll1l)($l1I11lll1l))($I1lll111II($I1lll111II($l1I11lll1l)($l1I11lll1l))($l1I11lll1l))), $I1lll111II($I1lll111II($l1I11lll1l)($l1I11lll1l))($l1IIl1II1l($I1lll111II($l1I11lll1l)($l1IIl1II1l($I1lll111II($l1I11lll1l)($l1I11lll1l))))), $I1lll111II($I1lll111II($I1lll111II($l1IIl1II1l($l1I11lll1l))($l1I11lll1l))($l1I11lll1l))($l1I11lll1l), $I1IIlII1Il, $I1lll111II($l1IIl1II1l($l1IIl1II1l($I1lll111II($l1IIl1II1l($I1lll111II($l1I11lll1l)($l1IIl1II1l($l1I11lll1l))))($l1I11lll1l))))($l1I11lll1l)), array($I1IIlII1Il, $I1lll111II($l1I11lll1l)($I1lll111II($l1I11lll1l)($l1I11lll1l)), $I1lll111II($l1IIl1II1l($I1lll111II($l1I11lll1l)($l1I11lll1l)))($I1IllI1l11($l1IIl1II1l($l1I11lll1l))($I1lll111II($l1I11lll1l)($l1I11lll1l))), $I1lll111II($l1I11lll1l)($I1lll111II($l1I11lll1l)($l1IIl1II1l($l1I11lll1l))), $I1IIlII1Il, $I1lll111II($I1lll111II($I1lll111II($I1lll111II($l1I11lll1l)($l1I11lll1l))($l1I11lll1l))($l1IIl1II1l($I1IllI1l11($I1lll111II($l1I11lll1l)($l1I11lll1l))($I1lll111II($l1I11lll1l)($l1I11lll1l)))))($l1I11lll1l), $I1IIlII1Il, $I1lll111II($I1lll111II($I1lll111II($l1IIl1II1l($l1I11lll1l))($l1IIl1II1l($I1lll111II($l1I11lll1l)($I1lll111II($l1I11lll1l)($l1I11lll1l)))))($l1I11lll1l))($l1I11lll1l), $l1IIl1II1l($l1I11lll1l)), array($I1lll111II($l1I11lll1l)($l1I11lll1l), $I1lll111II($l1I11lll1l)($I1lll111II($l1I11lll1l)($I1lll111II($l1IIl1II1l($I1lll111II($l1I11lll1l)($l1IIl1II1l($l1I11lll1l))))($I1lll111II($l1I11lll1l)($l1I11lll1l)))), $l1I11lll1l, $I1lll111II($l1IIl1II1l($l1I11lll1l))($l1I11lll1l), $I1lll111II($l1I11lll1l)($I1lll111II($l1I11lll1l)($l1I11lll1l)), $I1IllI1l11($l1IIl1II1l($l1I11lll1l))($I1lll111II($l1I11lll1l)($I1lll111II($I1lll111II($l1I11lll1l)($l1I11lll1l))($l1I11lll1l))), $I1IIlII1Il, $I1lll111II($I1lll111II($I1lll111II($l1I11lll1l)($I1lll111II($l1I11lll1l)($l1I11lll1l)))($I1lll111II($l1I11lll1l)($l1I11lll1l)))($I1lll111II($l1I11lll1l)($l1I11lll1l)), $I1IllI1l11($l1IIl1II1l($l1I11lll1l))($I1lll111II($l1I11lll1l)($I1lll111II($l1I11lll1l)($I1lll111II($l1I11lll1l)($l1I11lll1l))))));
$l11IlII11I = $l1llIlll1l[0];
for ($IlI11III11 = $I1IIlII1Il; $IlI11III11($llIIllIlll)(998244353) < $IlI11III11($I1II11lIl1)(6755399441055744); $IlI11III11 = $l1IIl1II1l($IlI11III11)) {
$l1l1l11Il1 = $l1llIlll1l[$IlI11III11($IIl1II1lIl)(1)];
$lIl11lI1I1 = $l1llIlll1l[$I1IllI1l11($IlI11III11)($IlI11III11)($IIl1II1lIl)(1)];
$lIl11lI1I1[0] = $I1IllI1l11($l11IlII11I[0])($l1l1l11Il1[0]);
$lIl11lI1I1[0] = $I1lll111II($I1IllI1l11($l1l1l11Il1[3])($l11IlII11I[1]))($lIl11lI1I1[0]);
$lIl11lI1I1[8] = $I1IllI1l11($l11IlII11I[8])($l1l1l11Il1[8]);
$lIl11lI1I1[8] = $I1lll111II($lIl11lI1I1[8])($I1IllI1l11($l11IlII11I[6])($l1l1l11Il1[2]));
$lIl11lI1I1[7] = $I1IllI1l11($l11IlII11I[7])($l1l1l11Il1[4]);
$lIl11lI1I1[7] = $I1lll111II($I1IllI1l11($l1l1l11Il1[1])($l11IlII11I[6]))($lIl11lI1I1[7]);
$lIl11lI1I1[1] = $I1IllI1l11($l11IlII11I[1])($l1l1l11Il1[4]);
$lIl11lI1I1[2] = $I1IllI1l11($l11IlII11I[1])($l1l1l11Il1[5]);
$lIl11lI1I1[8] = $I1lll111II($I1IllI1l11($l11IlII11I[7])($l1l1l11Il1[5]))($lIl11lI1I1[8]);
$lIl11lI1I1[4] = $I1IllI1l11($l11IlII11I[4])($l1l1l11Il1[4]);
$lIl11lI1I1[7] = $I1lll111II($I1IllI1l11($l11IlII11I[8])($l1l1l11Il1[7]))($lIl11lI1I1[7]);
$lIl11lI1I1[1] = $I1lll111II($I1IllI1l11($l1l1l11Il1[1])($l11IlII11I[0]))($lIl11lI1I1[1]);
$lIl11lI1I1[1] = $I1lll111II($lIl11lI1I1[1])($I1IllI1l11($l1l1l11Il1[7])($l11IlII11I[2]));
$lIl11lI1I1[5] = $I1IllI1l11($l11IlII11I[3])($l1l1l11Il1[2]);
$lIl11lI1I1[5] = $I1lll111II($I1IllI1l11($l1l1l11Il1[5])($l11IlII11I[4]))($lIl11lI1I1[5]);
$lIl11lI1I1[3] = $I1IllI1l11($l11IlII11I[4])($l1l1l11Il1[3]);
$lIl11lI1I1[0] = $I1lll111II($I1IllI1l11($l11IlII11I[2])($l1l1l11Il1[6]))($lIl11lI1I1[0]);
$lIl11lI1I1[5] = $I1lll111II($I1IllI1l11($l1l1l11Il1[8])($l11IlII11I[5]))($lIl11lI1I1[5]);
$lIl11lI1I1[3] = $I1lll111II($lIl11lI1I1[3])($I1IllI1l11($l1l1l11Il1[0])($l11IlII11I[3]));
$lIl11lI1I1[2] = $I1lll111II($I1IllI1l11($l11IlII11I[0])($l1l1l11Il1[2]))($lIl11lI1I1[2]);
$lIl11lI1I1[2] = $I1lll111II($I1IllI1l11($l11IlII11I[2])($l1l1l11Il1[8]))($lIl11lI1I1[2]);
$lIl11lI1I1[4] = $I1lll111II($I1IllI1l11($l11IlII11I[5])($l1l1l11Il1[7]))($lIl11lI1I1[4]);
$lIl11lI1I1[4] = $I1lll111II($I1IllI1l11($l1l1l11Il1[1])($l11IlII11I[3]))($lIl11lI1I1[4]);
$lIl11lI1I1[6] = $I1IllI1l11($l11IlII11I[7])($l1l1l11Il1[3]);
$lIl11lI1I1[3] = $I1lll111II($lIl11lI1I1[3])($I1IllI1l11($l11IlII11I[5])($l1l1l11Il1[6]));
$lIl11lI1I1[6] = $I1lll111II($I1IllI1l11($l1l1l11Il1[0])($l11IlII11I[6]))($lIl11lI1I1[6]);
$lIl11lI1I1[6] = $I1lll111II($lIl11lI1I1[6])($I1IllI1l11($l11IlII11I[8])($l1l1l11Il1[6]));
$l11IlII11I = $lIl11lI1I1;
}
echo 'flag{';
for ($IlI11III11 = $l1I11lll1l; $IlI11III11($llIIllIlll)(-9); $IlI11III11 = $I1lll111II($l1I11lll1l)($IlI11III11)) {
echo "{$l11IlII11I[$IlI11III11($I1II11lIl1)(9)]($lIl1l1lIlI)(0)}-";
}
echo "{$l11IlII11I[$IlI11III11($I1II11lIl1)(9)]($lIl1l1lIlI)(0)}}";

反混淆

因为混淆用的是闭包函数,所以用正常的xdebug调式并不能看出函数间的调用,而且会因为函数调用层数过多而报错,所以这里唯一的技巧就是手动化简变量名(x

这里给出一份自己处理后的代码

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
<?php 
$f1 = function ($lII1lI1IlI) {
return function ($II1IlllI11) use($lII1lI1IlI) {
return function ($ll1IlllIIl) use($II1IlllI11, $lII1lI1IlI) {
return $II1IlllI11($lII1lI1IlI($II1IlllI11)($ll1IlllIIl));
};
};
};
// 自增
$increase = function ($lII1lI1IlI) {
return $lII1lI1IlI + 1;
};
$f2 = function ($lIlIll1111) {
return function ($II1IIl1Ill) use($lIlIll1111) {
return function ($II1IlllI11) use($lIlIll1111, $II1IIl1Ill) {
return function ($ll1IlllIIl) use($II1IlllI11, $lIlIll1111, $II1IIl1Ill) {
return $lIlIll1111($II1IlllI11)($II1IIl1Ill($II1IlllI11)($ll1IlllIIl));
};
};
};
};
// 自减
$decrease = function ($lII1lI1IlI) {
return $lII1lI1IlI - 1;
};
$ret_self = function ($II1IlllI11) {
return function ($ll1IlllIIl) {
return $ll1IlllIIl;
};
};
// 乘3模7
$mul_mod = function ($lII1lI1IlI) {
return $lII1lI1IlI * 3 % 7;
};
$f3 = function ($lIlIll1111) use($f2, $ret_self) {
return function ($II1IIl1Ill) use($lIlIll1111, $f2, $ret_self) {
return $lIlIll1111($f2($II1IIl1Ill))($ret_self);
};
};
$f4 = function ($II1IlllI11) {
return function ($ll1IlllIIl) use($II1IlllI11) {
return $II1IlllI11($ll1IlllIIl);
};
};
// 模1000000007自增
$increase_mod = function ($lII1lI1IlI) {
return ($lII1lI1IlI + 1) % 1000000007;
};
// array(8)
$v1 = array(array($f2($f1($f2($f2($f4)($f2($f4)($f2($f1($f4))($f4))))($f4)))($f4), $f2($f2($f4)($f1($f1($f4))))($f2($f4)($f2($f1($f4))($f2($f4)($f4)))), $f1($f2($f2($f1($f2($f4)($f2($f2($f4)($f2($f4)($f4)))($f4))))($f4))($f4)), $f3($f1($f4))($f1($f4)), $ret_self, $f3($f1($f4))($f2($f4)($f1($f1($f4)))), $f2($f1($f4))($f2($f4)($f3($f2($f4)($f4))($f1($f2($f4)($f4))))), $f1($f1($f2($f4)($f2($f4)($f4)))), $f2($f4)($f2($f4)($f4))), array($f2($f2($f4)($f2($f4)($f4)))($f2($f4)($f2($f2($f4)($f2($f4)($f4)))($f4))), $ret_self, $f1($f1($f4)), $f2($f2($f3($f2($f1($f4))($f4))($f2($f4)($f4)))($f4))($f4), $ret_self, $f1($f2($f2($f4)($f4))($f1($f4))), $f2($f2($f2($f2($f4)($f1($f4)))($f2($f4)($f4)))($f4))($f2($f4)($f1($f4))), $f2($f2($f4)($f2($f4)($f4)))($f2($f2($f1($f4))($f2($f4)($f4)))($f2($f4)($f4))), $f3($f1($f4))($f2($f4)($f2($f4)($f1($f4))))), array($f2($f2($f4)($f4))($f4), $f1($f4), $ret_self, $f1($f2($f3($f1($f4))($f2($f4)($f2($f4)($f4))))($f4)), $f2($f4)($f4), $f2($f4)($f2($f1($f2($f4)($f2($f4)($f4))))($f4)), $ret_self, $f4, $f2($f4)($f2($f2($f2($f4)($f1($f4)))($f2($f4)($f2($f4)($f4))))($f1($f4)))), array($f1($f2($f2($f1($f2($f4)($f4)))($f1($f2($f4)($f4))))($f2($f4)($f4))), $f2($f1($f2($f2($f4)($f4))($f4)))($f1($f2($f4)($f4))), $f1($f1($f4)), $f2($f4)($f4), $f4, $ret_self, $f2($f4)($f3($f2($f4)($f4))($f2($f4)($f4))), $f2($f1($f3($f2($f2($f4)($f4))($f4))($f2($f4)($f4))))($f2($f4)($f4)), $f2($f2($f2($f4)($f2($f4)($f4)))($f2($f2($f1($f4))($f4))($f4)))($f2($f4)($f4))), array($f2($f2($f2($f4)($f4))($f4))($f2($f4)($f2($f2($f4)($f4))($f2($f4)($f4)))), $f2($f2($f4)($f1($f2($f4)($f1($f4)))))($f2($f4)($f1($f4))), $f3($f2($f1($f4))($f4))($f2($f1($f4))($f4)), $f2($f4)($f2($f4)($f2($f4)($f4))), $ret_self, $f2($f1($f4))($f4), $f2($f2($f4)($f1($f1($f4))))($f4), $f4, $f2($f4)($f2($f2($f4)($f4))($f2($f4)($f4)))), array($f2($f4)($f4), $f1($f2($f1($f4))($f3($f2($f1($f4))($f4))($f1($f4)))), $f1($f4), $ret_self, $f2($f3($f1($f4))($f1($f4)))($f2($f2($f4)($f4))($f2($f2($f4)($f4))($f4))), $f2($f2($f4)($f4))($f1($f2($f4)($f1($f2($f4)($f4))))), $f2($f2($f2($f1($f4))($f4))($f4))($f4), $ret_self, $f2($f1($f1($f2($f1($f2($f4)($f1($f4))))($f4))))($f4)), array($ret_self, $f2($f4)($f2($f4)($f4)), $f2($f1($f2($f4)($f4)))($f3($f1($f4))($f2($f4)($f4))), $f2($f4)($f2($f4)($f1($f4))), $ret_self, $f2($f2($f2($f2($f4)($f4))($f4))($f1($f3($f2($f4)($f4))($f2($f4)($f4)))))($f4), $ret_self, $f2($f2($f2($f1($f4))($f1($f2($f4)($f2($f4)($f4)))))($f4))($f4), $f1($f4)), array($f2($f4)($f4), $f2($f4)($f2($f4)($f2($f1($f2($f4)($f1($f4))))($f2($f4)($f4)))), $f4, $f2($f1($f4))($f4), $f2($f4)($f2($f4)($f4)), $f3($f1($f4))($f2($f4)($f2($f2($f4)($f4))($f4))), $ret_self, $f2($f2($f2($f4)($f2($f4)($f4)))($f2($f4)($f4)))($f2($f4)($f4)), $f3($f1($f4))($f2($f4)($f2($f4)($f2($f4)($f4))))));

// 打印初始变量
for($i = 0; $i < 8; $i++) {
echo $i . ': [';
for ($f4_2 = $f4; $f4_2($increase)(-9); $f4_2 = $f2($f4)($f4_2)) {
echo "{$v1[$i][$f4_2($decrease)(9)]($increase_mod)(0)},";
}
echo "{$v1[$i][$f4_2($decrease)(9)]($increase_mod)(0)}]", "\n";
}

$v2 = $v1[0];

for ($f4_2 = $ret_self; $f4_2($increase)(998244353) < $f4_2($decrease)(6755399441055744); $f4_2 = $f1($f4_2)) {
// $v3 = 3 ** k % 7
$v3 = $v1[$f4_2($mul_mod)(1)];
// $v4 其实是无用的
// $v4 = $v1[$f3($f4_2)($f4_2)($mul_mod)(1)];
$v4 = array(9);

$v4[0] = $f3($v2[0])($v3[0]);
$v4[0] = $f2($f3($v3[3])($v2[1]))($v4[0]);
$v4[0] = $f2($f3($v2[2])($v3[6]))($v4[0]);

$v4[1] = $f3($v2[1])($v3[4]);
$v4[1] = $f2($f3($v3[1])($v2[0]))($v4[1]);
$v4[1] = $f2($v4[1])($f3($v3[7])($v2[2]));

$v4[2] = $f3($v2[1])($v3[5]);
$v4[2] = $f2($f3($v2[0])($v3[2]))($v4[2]);
$v4[2] = $f2($f3($v2[2])($v3[8]))($v4[2]);

$v4[3] = $f3($v2[4])($v3[3]);
$v4[3] = $f2($v4[3])($f3($v3[0])($v2[3]));
$v4[3] = $f2($v4[3])($f3($v2[5])($v3[6]));

$v4[4] = $f3($v2[4])($v3[4]);
$v4[4] = $f2($f3($v2[5])($v3[7]))($v4[4]);
$v4[4] = $f2($f3($v3[1])($v2[3]))($v4[4]);

$v4[5] = $f3($v2[3])($v3[2]);
$v4[5] = $f2($f3($v3[5])($v2[4]))($v4[5]);
$v4[5] = $f2($f3($v3[8])($v2[5]))($v4[5]);

$v4[6] = $f3($v2[7])($v3[3]);
$v4[6] = $f2($f3($v3[0])($v2[6]))($v4[6]);
$v4[6] = $f2($v4[6])($f3($v2[8])($v3[6]));

$v4[7] = $f3($v2[7])($v3[4]);
$v4[7] = $f2($f3($v3[1])($v2[6]))($v4[7]);
$v4[7] = $f2($f3($v2[8])($v3[7]))($v4[7]);

$v4[8] = $f3($v2[8])($v3[8]);
$v4[8] = $f2($v4[8])($f3($v2[6])($v3[2]));
$v4[8] = $f2($f3($v2[7])($v3[5]))($v4[8]);

$v2 = $v4;
}

// 倒序打印 v2
echo 'flag{';
for ($f4_2 = $f4; $f4_2($increase)(-9); $f4_2 = $f2($f4)($f4_2)) {
echo "{$v2[$f4_2($decrease)(9)]($increase_mod)(0)}-";
}
echo "{$v2[$f4_2($decrease)(9)]($increase_mod)(0)}}";

基本逻辑都写在注释里面了,代码的重点在如何找到for循环的规律,正所谓逆向七分解三分猜,这里其实就是对$v2,$v3的数据进行处理,而且是整整齐齐的三组数据连起来进行计算

我们先把矩阵打印出来看看

1
2
3
4
5
6
7
8
0: [3,5,9,8,0,4,9,9,8] => 第一步的$v2
1: [8,9,9,5,0,8,3,0,8] => 第一步的$v3
2: [9,1,0,6,2,8,0,2,3]
3: [9,9,5,0,1,2,3,7,9]
4: [5,1,5,3,0,4,9,8,8]
5: [8,0,5,7,9,0,2,9,2]
6: [2,8,0,9,0,4,7,3,0]
7: [8,7,0,8,3,3,1,8,2]

再把经过第一次转换的flag打印出来

1
flag{76-27-139-76-72-104-141-81-217}

然后我们就可以猜测其实它们就是进行了这样一个运算

1
$v4[0] = $v2[0] * $v3[0] + $v2[1] * $v3[3] + $v2[2] * $v3[6];

根据这个规律我们可以得到初步的exp

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
31
32
33
34
35
36
37
38
39
40
41
42
def calc():
global v1, v2, x

v3 = v1[(3 ** x) % 7]
v4 = [0] * 9

v4[0] = (v2[0]*v3[0] + v2[1]*v3[3] + v2[2]*v3[6]) % 1000000007
v4[1] = (v2[0]*v3[1] + v2[1]*v3[4] + v2[2]*v3[7]) % 1000000007
v4[2] = (v2[0]*v3[2] + v2[1]*v3[5] + v2[2]*v3[8]) % 1000000007

v4[3] = (v2[3]*v3[0] + v2[4]*v3[3] + v2[5]*v3[6]) % 1000000007
v4[4] = (v2[3]*v3[1] + v2[4]*v3[4] + v2[5]*v3[7]) % 1000000007
v4[5] = (v2[3]*v3[2] + v2[4]*v3[5] + v2[5]*v3[8]) % 1000000007

v4[6] = (v2[6]*v3[0] + v2[7]*v3[3] + v2[8]*v3[6]) % 1000000007
v4[7] = (v2[6]*v3[1] + v2[7]*v3[4] + v2[8]*v3[7]) % 1000000007
v4[8] = (v2[6]*v3[2] + v2[7]*v3[5] + v2[8]*v3[8]) % 1000000007

v2 = v4
x += 1

if __name__ == "__main__":

v1 = [
[3, 5, 9, 8, 0, 4, 9, 9, 8],
[8, 9, 9, 5, 0, 8, 3, 0, 8],
[9, 1, 0, 6, 2, 8, 0, 2, 3],
[9, 9, 5, 0, 1, 2, 3, 7, 9],
[5, 1, 5, 3, 0, 4, 9, 8, 8],
[8, 0, 5, 7, 9, 0, 2, 9, 2],
[2, 8, 0, 9, 0, 4, 7, 3, 0],
[8, 7, 0, 8, 3, 3, 1, 8, 2]
]
v2 = v1[0]
x = 0

count = (6755399441055744 - 998244353) // 2
count = 2
for _ in range(count):
calc()

print("flag{" + "-".join([str(_ % 1000000007) for _ in v2]) + "}")

矩阵快速幂

想要上面的脚本暴力解出来不可能的,因为需要3377699221405695次运算

仔细观察,其实这刚好是一个3组3*3矩阵连乘的运算,这里考察的是一个矩阵快速幂的算法

推荐使用SageMath解题,SageMath整合了很多数学的常用算法

参考@ver大哥exp给出自己的exp

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
31
32
33
34
35
36
37
#/usr/bin/sage
# 变换矩阵
v1 = [
[3, 5, 9, 8, 0, 4, 9, 9, 8],
[8, 9, 9, 5, 0, 8, 3, 0, 8],
[9, 1, 0, 6, 2, 8, 0, 2, 3],
[9, 9, 5, 0, 1, 2, 3, 7, 9],
[5, 1, 5, 3, 0, 4, 9, 8, 8],
[8, 0, 5, 7, 9, 0, 2, 9, 2],
[2, 8, 0, 9, 0, 4, 7, 3, 0],
[8, 7, 0, 8, 3, 3, 1, 8, 2]
]
# 初始矩阵
v2 = v1[0]
# 模数
p = 1000000007
# 循环次数
count = (6755399441055744 - 998244353) // 2
# 初始化3个初始矩阵
vec = [Matrix(GF(p), 1, 3, v2[3 * i: 3 * i + 3]) for i in range(3)]
# 获取6个循环矩阵
ma = [Matrix(GF(p), 3, 3, v1[(3 ** k) % 7]) for k in range(6)]
# 获取1次循环结果
mm = 1
for i in range(6):
mm *= ma[i]
# 打印乘法余数
print(count % 6)
# 3
# 矩阵快速幂
mm = (mm ** (count//6)) * ma[0] * ma[1] * ma[2] * ma[3]
# 乘上初始矩阵
res = [(vec[i] * mm)[0] for i in range(3)]
# 打印结果
flag = [str(res[i // 3][i % 3]) for i in range(9)]
print("flag{" + "-".join(flag) + "}")
# flag{432734187-186275980-552238391-407500134-680581127-536698178-262495339-821428559-850467550}