前言

前段时间感觉忙的要死，最近终于算是有了一点空余时间，正好刚打完的 HICTF2024 有一点有意思的点子，正好记录一下

共四题

  • strhash
  • poly
  • supercomputer
  • potter

解出来前三题

strhash

gen.c

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
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

uint64_t str_hash(char *s, uint64_t mod) {
    uint64_t res = 0x114514;
    for(; *s; s++) {
        res *= 233;
        res += *s;
        res %= mod;
    }
    return res;
}

int main(void) {
    char *flag = getenv("FLAG");

    for(int x=0; x<=100; x++) {
        uint64_t mod = rand();
        printf("%lu %lu\n", mod, str_hash(flag, mod));
    }

    return 0;
}

res.txt

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
1804289383 1190008377
846930886 9501214
1681692777 742357966
1714636915 444438409
1957747793 134431161
424238335 402721979
719885386 270112044
1649760492 1155227242
596516649 476308501
1189641421 1026995005
1025202362 369524526
1350490027 115768525
783368690 128781574
1102520059 794945957
2044897763 525021698
1967513926 1202472002
1365180540 718629814
1540383426 1527890008
304089172 219173622
1303455736 72850430
35005211 32895570
521595368 324916694
294702567 183761521
1726956429 992055442
336465782 47459012
861021530 394191254
278722862 76296070
233665123 202549164
2145174067 1745191260
468703135 11282359
1101513929 1092941761
1801979802 393444958
1315634022 855060862
635723058 557940082
1369133069 416017631
1125898167 426745258
1059961393 866659529
2089018456 101422542
628175011 274383911
1656478042 158353442
1131176229 778866802
1653377373 1576568200
859484421 731620102
1914544919 120626132
608413784 169934934
756898537 58946343
1734575198 273830734
1973594324 1866382218
149798315 84760904
2038664370 1847515654
1129566413 157937244
184803526 150496144
412776091 336475073
1424268980 129480814
1911759956 1720023158
749241873 353186023
137806862 88508746
42999170 1638164
982906996 513000390
135497281 79014386
511702305 389240449
2084420925 1708688029
1937477084 490818622
1827336327 314296213
572660336 310139630
1159126505 1081657949
805750846 738718898
1632621729 651390559
1100661313 65789714
1433925857 933378653
1141616124 216772582
84353895 17465494
939819582 69317806
2001100545 946538374
1998898814 1321902102
1548233367 150257914
610515434 529740294
1585990364 1061756098
1374344043 1144447075
760313750 410706104
1477171087 966325917
356426808 330752134
945117276 566296666
1889947178 58695214
1780695788 1583317062
709393584 615812830
491705403 466490056
1918502651 697630426
752392754 542594364
1474612399 47749896
2053999932 198147682
1264095060 943869214
1411549676 437802578
1843993368 883507846
943947739 53460922
1984210012 591589678
855636226 423196126
1749698586 1315862194
1469348094 971172988
1956297539 729119640
1036140795 184356454

记得之前做过一道哈希的密码题，当时似乎是用双向搜索给爆出来的，这次显然不一样

学长讲了才看出来（（

将 hash 用多项式表示 \[ hash(s) = \text{0x114514} \cdot 233^{n} + s_0 \cdot 233^{n-1} + s_1 \cdot 233^{n-2} + \cdots + s_{n-1}\cdot233^0 \pmod {M_i} \] 这样就能看出来，是个 CRT 问题

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
from sympy.ntheory.modular import crt
mod = [
    1804289383, 846930886, 1681692777, 1714636915, 1957747793, 424238335,
    719885386, 1649760492, 596516649, 1189641421, 1025202362, 1350490027,
    783368690, 1102520059, 2044897763, 1967513926, 1365180540, 1540383426,
    304089172, 1303455736, 35005211, 521595368, 294702567, 1726956429,
    336465782, 861021530, 278722862, 233665123, 2145174067, 468703135,
    1101513929, 1801979802, 1315634022, 635723058, 1369133069, 1125898167,
    1059961393, 2089018456, 628175011, 1656478042, 1131176229, 1653377373,
    859484421, 1914544919, 608413784, 756898537, 1734575198, 1973594324,
    149798315, 2038664370, 1129566413, 184803526, 412776091, 1424268980,
    1911759956, 749241873, 137806862, 42999170, 982906996, 135497281,
    511702305, 2084420925, 1937477084, 1827336327, 572660336, 1159126505,
    805750846, 1632621729, 1100661313, 1433925857, 1141616124, 84353895,
    939819582, 2001100545, 1998898814, 1548233367, 610515434, 1585990364,
    1374344043, 760313750, 1477171087, 356426808, 945117276, 1889947178,
    1780695788, 709393584, 491705403, 1918502651, 752392754, 1474612399,
    2053999932, 1264095060, 1411549676, 1843993368, 943947739, 1984210012,
    855636226, 1749698586, 1469348094, 1956297539, 1036140795
]
hash = [
    1190008377, 9501214, 742357966, 444438409, 134431161, 402721979,
    270112044, 1155227242, 476308501, 1026995005, 369524526, 115768525,
    128781574, 794945957, 525021698, 1202472002, 718629814, 1527890008,
    219173622, 72850430, 32895570, 324916694, 183761521, 992055442,
    47459012, 394191254, 76296070, 202549164, 1745191260, 11282359,
    1092941761, 393444958, 855060862, 557940082, 416017631, 426745258,
    866659529, 101422542, 274383911, 158353442, 778866802, 1576568200,
    731620102, 120626132, 169934934, 58946343, 273830734, 1866382218,
    84760904, 1847515654, 157937244, 150496144, 336475073, 129480814,
    1720023158, 353186023, 88508746, 1638164, 513000390, 79014386,
    389240449, 1708688029, 490818622, 314296213, 310139630, 1081657949,
    738718898, 651390559, 65789714, 933378653, 216772582, 17465494,
    69317806, 946538374, 1321902102, 150257914, 529740294, 1061756098,
    1144447075, 410706104, 966325917, 330752134, 566296666, 58695214,
    1583317062, 615812830, 466490056, 697630426, 542594364, 47749896,
    198147682, 943869214, 437802578, 883507846, 53460922, 591589678,
    423196126, 1315862194, 971172988, 729119640, 184356454
]

assert len(mod) == len(hash)
res, Mod = crt(mod, hash)

print(res)
res -= 0x114514 * 233 ** 42

flag = b''

for i in range(41):
    c = res % (233)
    res //= 233
    flag += bytes([c])

print(flag)
print(flag[::-1])

# 3038904180309451889298837328685449386951729223201782575312887178624194103003153917723896684610138843289854
# b'}07b7f151caf3-62a9-fe34-76e7-6a4baacc{gal'
# b'lag{ccaab4a6-7e67-43ef-9a26-3fac151f7b70}'

poly

题目附件

gen.py

1
2
3
4
5
from secret import flag
from functools import reduce

print(list(map(lambda x: reduce(lambda t, y: t * x + y, flag.encode()), range(len(flag)))))

out.txt

1
2
[125, 2996, 452635961261861, 5640012588785953252742, 663780389523502221593026277, 5845169438213803974237048659360, 9887686914794970408229246877837261, 5337690699007613492950100661443838386, 1246816454677070240427082753828238163437, 153460164802093351535746693021820792205932, 11388634061367409705082975835211766201321045, 561110174338870387179778825126282853603302526, 19707795929255451006208863819787576643829770261, 520881194974728297519631110000138317264353793432, 10805092812709807233540502091207064827348602091837, 181889014548692631324457891650518586246753508973930, 2552507382661657536880498041728210235325197081880541, 30526683751460091693383854169085501144119622770115236, 316865109417499484669699487403444039480141224348233477, 2898653848895952221370426792142177095594525094522186742, 23673843301340973009664515191259831073817022946431821765, 174539049232138773732842515032017313916154669096708343056, 1172733551080318790000994789603513594241654018460818966061, 7240523617671723109603340026802418603641003659017975484322, 41374103585680599659105199547442215866047005195866840568397, 220199857217101214349082389841043173220339718159981048158300, 1097626867177210522501108725164094179734775217327646541376821, 5149764870836833092990530866127123407661712365054932690325486, 22841615951981693536493860837124386678939843016655243827081717, 96157610067108350424366847753813154389844296991097936198764552, 385562422203859626216008093491644153104891734674128504106992285, 1477221645609927756179115371650629543504813846434947526324458586, 5423633936317940537039114323538499637949438626254731152203731261, 19132290548239069397038234653722740430029897400022438133844971412, 64999757417753858733496171026572335062387390211817558640690377957, 213142909661667580939007866138222724809887474172878584374436922470, 675944013875172159995957069622450735032975415629563730466165480101, 2076951592374410038709677191998396913746258932819180055450081131136, 6193688888445369259889561497114942414360276754293622820640778134157, 17953715518690549873845638320302721807364019714363222114478505961362, 50659931725962874327370012361788145918161221262881139309840223762605, 139334089414772808841572383856822545223058318039478733568743937623116]

仔细分析 map , reduce 和 lambda，可以得到关系： \[ \mathbf{M} = \begin{bmatrix} 0 & \cdots & 0 & 0 & 1\\ 1^{n-1} & \cdots & 1^{2} & 1^{1} & 1\\ 2^{n-1} & \cdots & 2^{2} & 2^{1} & 1\\ \vdots & \ddots & \vdots & \vdots & \vdots\\ (n-1)^{n-1} & \cdots & (n-1)^{2} & (n-1)^{1} & 1 \end{bmatrix}_{n \times n} \] \[ \mathbf{M} \mathbf{u} = \mathbf{v} \]

其中 \(\mathbf{M}\) 为系数矩阵，\(\mathbf{u}\) 为编码的 flag，\(\mathbf{v}\) 为输出的密文，很容易写出解题脚本：

1
2
3
4
5
6
7
8
9
10
11
12
M = matrix(42)
for i in range(42):
    for j in range(42):
        M[i, 41-j] = i ^ j

assert M[0, -1] == 1 # 0^0=1 in Sagemath

v = vector([125, 2996, ...])
u = M^-1 * v
flag = bytes(u)
print(flag)
# b'flag{b67eb341-1e2d-4964-bb19-3ae28679871f}'

不过，比赛期间并非是这样出的

当时想到 sage 可以用 CAS 计算，那为何不试试让他直接解方程组呢？

于是有了下面的脚本，都不需要手撕原来的 map , reduce 和 lambda

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from functools import reduce

u = var([f"x{i}" for i in range(42)])
v = vector([125, 2996, ...])

equ = vector(list(map(lambda x: reduce(lambda t, y: t * x + y, u), range(42)))) - vector(v)
res = solve([*equ], *u)
assert len(res) == 1
print(res)
# [[x0 == 102, x1 == 108, x2 == 97, x3 == 103, x4 == 123, x5 == 98, x6 == 54, x7 == 55, x8 == 101, x9 == 98, x10 == 51, x11 == 52, x12 == 49, x13 == 45, x14 == 49, x15 == 101, x16 == 50, x17 == 100, x18 == 45, x19 == 52, x20 == 57, x21 == 54, x22 == 52, x23 == 45, x24 == 98, x25 == 98, x26 == 49, x27 == 57, x28 == 45, x29 == 51, x30 == 97, x31 == 101, x32 == 50, x33 == 56, x34 == 54, x35 == 55, x36 == 57, x37 == 56, x38 == 55, x39 == 49, x40 == 102, x41 == 125]]

flag = bytes([res[0][i].right() for i in range(42)])
print(flag)
# b'flag{b67eb341-1e2d-4964-bb19-3ae28679871f}'

虽然直接列线性方程组难度不高，但是这个很有趣，并且直接启发我做出了下一题

supercomputer

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
def f(x):
    x ^= ((x >> 11) & 0xb114514bb114514b)
    x ^= ((x << 13) & 0x114514cc114514cc)
    x ^= ((x << 17) & 0xaa191981aa191981)
    x ^= ((x >> 19) & 0xb1919810b1919810)
    x ^= ((x << 23) & 0x114514cd114514cd)
    x ^= ((x >> 29) & 0xb114514ab114514a)
    x ^= ((x << 31) & 0x114514cb114514cb)
    x ^= ((x << 37) & 0xaa19198caa19198c)
    x ^= ((x >> 41) & 0xb191981db191981d)
    x ^= ((x << 43) & 0x114514ce114514ce)
    return x

def calc(n):
    x = 0x1122334455667788
    for _ in range(n):
        x = f(x)
    return x

assert calc(1) == 0xaa732acf4eb6a79d
assert calc(10) == 0x28262ecbd673b7d7
assert calc(100) == 0x23a6b8be477b7c3
assert calc(1000) == 0x93737600f66aa785
assert calc(100000) == 0x8a762387c4e3aed8
assert calc(1000000) == 0x1267270a756bf7df
assert calc(10000000) == 0x39377648f4e367d7
assert calc(100000000) == 0x82232f8777773e8a
assert calc(1000000000) == 0x8762b83d6faa783
assert calc(10000000000) == 0x27237cdd6726788
assert calc(100000000000) == 0x97f6b44e7fe66de
assert calc(1000000000000) == 0x88723b8666ff27ca
assert calc(10000000000000) == 0x8a32670ee5ef6ec0
assert calc(100000000000000) == 0x993b3b4265ea6edb
assert calc(1000000000000000) == 0x8b732ec065e7e795

print('flag{%s}' % hex(calc(10000000000000000)))


这就纯纯算法题（？

一开始把已知的一串十六进制改成二进制观察规律，找到了个别 bit 至始至终没有发生改变，但是其他的没有任何思路

然后基于上一题的灵感，想到 f(x) 不就是函数式编程中所谓的纯函数吗？

那么我们可以把这个 函数 方法 f(x) 改写为等效的 函数 映射 \(f: ULL \to ULL\)

即一个在 64bit 的非负整数 (unsigned long long) 域内的映射

那么只要找到这个改写方法，这样就可以从数学角度研究该 函数 映射 的可结合性

我的方法是将这个 64bit 的 ULL 拆成 64 个 PolynomialRing(Zmod(2))

1
2
3
Bool.<x0,x1,x2,x3,x4,x5,x6,x7,x8,x9,x10,x11,x12,x13,x14,x15,x16,x17,x18,x19,x20,x21,x22,x23,x24,x25,x26,x27,x28,x29,x30,x31,x32,x33,x34,x35,x36,x37,x38,x39,x40,x41,x42,x43,x44,x45,x46,x47,x48,x49,x50,x51,x52,x53,x54,x55,x56,x57,x58,x59,x60,x61,x62,x63> = PolynomialRing(Zmod(2))
X = [x0,x1,x2,x3,x4,x5,x6,x7,x8,x9,x10,x11,x12,x13,x14,x15,x16,x17,x18,x19,x20,x21,x22,x23,x24,x25,x26,x27,x28,x29,x30,x31,x32,x33,x34,x35,x36,x37,x38,x39,x40,x41,x42,x43,x44,x45,x46,x47,x48,x49,x50,x51,x52,x53,x54,x55,x56,x57,x58,x59,x60,x61,x62,x63]

我确实不知道怎么直接申请多项式环上的 64 个变量了，丑点就丑点吧（逃

拆开后很方便位移

我们约定 x0 表示最低位，x63 表示最高位

那么例如 \(6_{10}\) 就可以写作 [x0, x1, x2, x3, x4, x5, x6, x7, ...] = [0, 1, 1, 0, 0, 0, 0, 0, ...]

1
2
3
4
5
6
7
def hex2bin(a):
    return list(map(int, list(bin(a+(1<<64))[3:])))[::-1]
	# 人话: 输入 ULL 加上 (1<<64) 用于占位，bin() 后取每个字符 int() 的结果存入数组

def bin2hex(a):
    return hex(int( ''.join(list(map(str, a)))[::-1] ,2))
	# 人话: 列表中每个元素 str() 后拼接起来，倒个序再转成 int，最后输出 hex

数学左移 \(a\) 位就是这个数组向 后/右 移动 \(a\) 位， 数学右移 \(a\) 位就是这个数组向 前/左 移动 \(a\) 位

但是由于每次左右移后都有一个按位与逻辑，溢出的位等效于被直接丢弃，而非从另一端循环或扩展数组长度

1
2
3
4
5
def left(x, a):
    return [*[0 for _ in range(a)] , *x[ :(len(x) - a)]]

def right(x, a):
    return [*x[a:] , *[0 for _ in range(a)]]

实现按位与逻辑和按位或逻辑，也就是转成 \(\mathbb{F}_2[x_0, x_1, \cdots, x_{63}]\) 下的 \(+\) 和 \(\times\)

底层全部交给 sage 的 CAS 系统，非常舒适

1
2
3
4
5
6
7
8
9
10
11
12
def and_(x, a):
    x = deepcopy(x)
    a_ = hex2bin(a)
    for i in range(len(x)):
        x[i] *= a_[i]
    return x

def xor_(x , y):
    x = deepcopy(x)
    for i in range(len(x)):
        x[i] += y[i]
    return x

然后就可以组合函数以实现 f() 和 calc()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from copy import deepcopy

def f(x):
    x = deepcopy(x)
    x = xor_(x, and_(right(x, 11) , 0xb114514bb114514b))
    x = xor_(x, and_(left(x, 13) , 0x114514cc114514cc))
    x = xor_(x, and_(left(x, 17) , 0xaa191981aa191981))
    x = xor_(x, and_(right(x, 19) , 0xb1919810b1919810))
    x = xor_(x, and_(left(x, 23) , 0x114514cd114514cd))
    x = xor_(x, and_(right(x, 29) , 0xb114514ab114514a))
    x = xor_(x, and_(left(x, 31) , 0x114514cb114514cb))
    x = xor_(x, and_(left(x, 37) , 0xaa19198caa19198c))
    x = xor_(x, and_(right(x, 41) , 0xb191981db191981d))
    x = xor_(x, and_(left(x, 43) , 0x114514ce114514ce))
    return x

F = f(X)

def calc(x, n):
    x = deepcopy(x)
    for i in range(n):
        x = f(x)
    return x

上面 X 是所有元的向量，也可以是一个恒等函数

F = f(X) 是进行一次 \(f\) 的映射

简单测验不难发现并证明： \[ (f^a \circ f^b)(\mathbf{x}) = f^b (f^a(\mathbf{x})) = f^{b+a}(\mathbf{x}) = f^{a+b}(\mathbf{x}) = f^a (f^b(\mathbf{x})) = (f^b \circ f^a)(\mathbf{x}) \] 即纯函数 \(f^n\) 是可结合的

然后借用了快速幂的思想，也是尝试利用可结合性来优化，将复杂度由 \(O(n)\) 降低至 \(O(\log n)\)

1
2
3
4
5
6
7
8
9
10
11
12
def compose(x, y):
    return [x[i](y) for i in range(len(x))]

def quick_calc(F, n):
    F = deepcopy(F)
    result = deepcopy(X)
    while n > 0:
        if n & 1 == 1:
            result = compose(result, F)
        F = compose(F, F)
        n >>= 1
    return result

剩下就可以通过

1
2
def compute(F, a):
    return bin2hex(compose(F, hex2bin(a)))

来带值计算

综上，整理脚本如下：

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
# 将 unsigned long long 数转化为 $\mathbb{F}_2[x_0, x_1, \cdots, x_{63}]$
from copy import deepcopy

Bool.<x0,x1,x2,x3,x4,x5,x6,x7,x8,x9,x10,x11,x12,x13,x14,x15,x16,x17,x18,x19,x20,x21,x22,x23,x24,x25,x26,x27,x28,x29,x30,x31,x32,x33,x34,x35,x36,x37,x38,x39,x40,x41,x42,x43,x44,x45,x46,x47,x48,x49,x50,x51,x52,x53,x54,x55,x56,x57,x58,x59,x60,x61,x62,x63> = PolynomialRing(Zmod(2))
X = [x0,x1,x2,x3,x4,x5,x6,x7,x8,x9,x10,x11,x12,x13,x14,x15,x16,x17,x18,x19,x20,x21,x22,x23,x24,x25,x26,x27,x28,x29,x30,x31,x32,x33,x34,x35,x36,x37,x38,x39,x40,x41,x42,x43,x44,x45,x46,x47,x48,x49,x50,x51,x52,x53,x54,x55,x56,x57,x58,x59,x60,x61,x62,x63]


def hex2bin(a):
    return list(map(int, list(bin(a+(1<<64))[3:])))[::-1]
	# 人话: 输入 ULL 加上 (1<<64) 用于占位，bin() 后取每个字符 int() 的结果存入数组

def bin2hex(a):
    return hex(int( ''.join(list(map(str, a)))[::-1] ,2))
	# 人话: 列表中每个元素 str() 后拼接起来，倒个序再转成 int，最后输出 hex

# 数学左移 <-> 数组右移 + 溢出
def left(x, a):
    return [*[0 for _ in range(a)] , *x[ :(len(x) - a)]]

# 数学右移 <-> 数组左移 + 溢出
def right(x, a):
    return [*x[a:] , *[0 for _ in range(a)]]

# 逻辑与 <-> 域乘
def and_(x, a):
    x = deepcopy(x)
    a_ = hex2bin(a)
    for i in range(len(x)):
        x[i] *= a_[i]
    return x

# 逻辑异或 <-> 域加
def xor_(x , y):
    x = deepcopy(x)
    for i in range(len(x)):
        x[i] += y[i]
    return x


def f(x):
    x = deepcopy(x)
    x = xor_(x, and_(right(x, 11) , 0xb114514bb114514b))
    x = xor_(x, and_(left(x, 13) , 0x114514cc114514cc))
    x = xor_(x, and_(left(x, 17) , 0xaa191981aa191981))
    x = xor_(x, and_(right(x, 19) , 0xb1919810b1919810))
    x = xor_(x, and_(left(x, 23) , 0x114514cd114514cd))
    x = xor_(x, and_(right(x, 29) , 0xb114514ab114514a))
    x = xor_(x, and_(left(x, 31) , 0x114514cb114514cb))
    x = xor_(x, and_(left(x, 37) , 0xaa19198caa19198c))
    x = xor_(x, and_(right(x, 41) , 0xb191981db191981d))
    x = xor_(x, and_(left(x, 43) , 0x114514ce114514ce))
    return x


def calc(x, n):
    x = deepcopy(x)
    for i in range(n):
        x = f(x)
    return x

# 函数的复合
def compose(x, y):
    return [x[i](y) for i in range(len(x))]

# 类似快速幂，O(n) -> O(log n)
def quick_calc(F, n):
    F = deepcopy(F)
    result = deepcopy(X)
    while n > 0:
        if n & 1 == 1:
            result = compose(result, F)
        F = compose(F, F)
        n >>= 1
    return result

def compute(F, a):
    return bin2hex(compose(F, hex2bin(a)))


F = f(X)
result = compute(quick_calc(F, 10000000000000000), 0x1122334455667788)
flag = f"flag{{{result}}}"
print(flag)
# flag{0xa8276600c7e3b6d9}

后记

前段时间网鼎杯半决赛，当时打算晚上就整理一下的，结果各种事一直拖了这么久（（

接下来几周要好好整理博客了

__END__