HICTF2024_Crypto_部分题解

前言#

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

共四题

strhash
poly
supercomputer
potter

解出来前三题

strhash#

gen.c

1
#include <stdio.h>
2
#include <stdlib.h>
3
#include <stdint.h>
4

5
uint64_t str_hash(char *s, uint64_t mod) {
6
    uint64_t res = 0x114514;
7
    for(; *s; s++) {
8
        res *= 233;
9
        res += *s;
10
        res %= mod;
11
    }
12
    return res;
13
}
14

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

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

23
    return 0;
24
}

res.txt

1
1804289383 1190008377
2
846930886 9501214
3
1681692777 742357966
4
1714636915 444438409
5
1957747793 134431161
6
424238335 402721979
7
719885386 270112044
8
1649760492 1155227242
9
596516649 476308501
10
1189641421 1026995005
11
1025202362 369524526
12
1350490027 115768525
13
783368690 128781574
14
1102520059 794945957
15
2044897763 525021698
16
1967513926 1202472002
17
1365180540 718629814
18
1540383426 1527890008
19
304089172 219173622
20
1303455736 72850430
21
35005211 32895570
22
521595368 324916694
23
294702567 183761521
24
1726956429 992055442
25
336465782 47459012
26
861021530 394191254
27
278722862 76296070
28
233665123 202549164
29
2145174067 1745191260
30
468703135 11282359
31
1101513929 1092941761
32
1801979802 393444958
33
1315634022 855060862
34
635723058 557940082
35
1369133069 416017631
36
1125898167 426745258
37
1059961393 866659529
38
2089018456 101422542
39
628175011 274383911
40
1656478042 158353442
41
1131176229 778866802
42
1653377373 1576568200
43
859484421 731620102
44
1914544919 120626132
45
608413784 169934934
46
756898537 58946343
47
1734575198 273830734
48
1973594324 1866382218
49
149798315 84760904
50
2038664370 1847515654
51
1129566413 157937244
52
184803526 150496144
53
412776091 336475073
54
1424268980 129480814
55
1911759956 1720023158
56
749241873 353186023
57
137806862 88508746
58
42999170 1638164
59
982906996 513000390
60
135497281 79014386
61
511702305 389240449
62
2084420925 1708688029
63
1937477084 490818622
64
1827336327 314296213
65
572660336 310139630
66
1159126505 1081657949
67
805750846 738718898
68
1632621729 651390559
69
1100661313 65789714
70
1433925857 933378653
71
1141616124 216772582
72
84353895 17465494
73
939819582 69317806
74
2001100545 946538374
75
1998898814 1321902102
76
1548233367 150257914
77
610515434 529740294
78
1585990364 1061756098
79
1374344043 1144447075
80
760313750 410706104
81
1477171087 966325917
82
356426808 330752134
83
945117276 566296666
84
1889947178 58695214
85
1780695788 1583317062
86
709393584 615812830
87
491705403 466490056
88
1918502651 697630426
89
752392754 542594364
90
1474612399 47749896
91
2053999932 198147682
92
1264095060 943869214
93
1411549676 437802578
94
1843993368 883507846
95
943947739 53460922
96
1984210012 591589678
97
855636226 423196126
98
1749698586 1315862194
99
1469348094 971172988
100
1956297539 729119640
101
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
from sympy.ntheory.modular import crt
2
mod = [
3
    1804289383, 846930886, 1681692777, 1714636915, 1957747793, 424238335,
4
    719885386, 1649760492, 596516649, 1189641421, 1025202362, 1350490027,
5
    783368690, 1102520059, 2044897763, 1967513926, 1365180540, 1540383426,
6
    304089172, 1303455736, 35005211, 521595368, 294702567, 1726956429,
7
    336465782, 861021530, 278722862, 233665123, 2145174067, 468703135,
8
    1101513929, 1801979802, 1315634022, 635723058, 1369133069, 1125898167,
9
    1059961393, 2089018456, 628175011, 1656478042, 1131176229, 1653377373,
10
    859484421, 1914544919, 608413784, 756898537, 1734575198, 1973594324,
11
    149798315, 2038664370, 1129566413, 184803526, 412776091, 1424268980,
12
    1911759956, 749241873, 137806862, 42999170, 982906996, 135497281,
13
    511702305, 2084420925, 1937477084, 1827336327, 572660336, 1159126505,
14
    805750846, 1632621729, 1100661313, 1433925857, 1141616124, 84353895,
15
    939819582, 2001100545, 1998898814, 1548233367, 610515434, 1585990364,
16
    1374344043, 760313750, 1477171087, 356426808, 945117276, 1889947178,
17
    1780695788, 709393584, 491705403, 1918502651, 752392754, 1474612399,
18
    2053999932, 1264095060, 1411549676, 1843993368, 943947739, 1984210012,
19
    855636226, 1749698586, 1469348094, 1956297539, 1036140795
20
]
21
hash = [
22
    1190008377, 9501214, 742357966, 444438409, 134431161, 402721979,
23
    270112044, 1155227242, 476308501, 1026995005, 369524526, 115768525,
24
    128781574, 794945957, 525021698, 1202472002, 718629814, 1527890008,
25
    219173622, 72850430, 32895570, 324916694, 183761521, 992055442,
26
    47459012, 394191254, 76296070, 202549164, 1745191260, 11282359,
27
    1092941761, 393444958, 855060862, 557940082, 416017631, 426745258,
28
    866659529, 101422542, 274383911, 158353442, 778866802, 1576568200,
29
    731620102, 120626132, 169934934, 58946343, 273830734, 1866382218,
30
    84760904, 1847515654, 157937244, 150496144, 336475073, 129480814,
31
    1720023158, 353186023, 88508746, 1638164, 513000390, 79014386,
32
    389240449, 1708688029, 490818622, 314296213, 310139630, 1081657949,
33
    738718898, 651390559, 65789714, 933378653, 216772582, 17465494,
34
    69317806, 946538374, 1321902102, 150257914, 529740294, 1061756098,
35
    1144447075, 410706104, 966325917, 330752134, 566296666, 58695214,
36
    1583317062, 615812830, 466490056, 697630426, 542594364, 47749896,
37
    198147682, 943869214, 437802578, 883507846, 53460922, 591589678,
38
    423196126, 1315862194, 971172988, 729119640, 184356454
39
]
40

41
assert len(mod) == len(hash)
42
res, Mod = crt(mod, hash)
43

44
print(res)
45
res -= 0x114514 * 233 ** 42
46

47
flag = b''
48

49
for i in range(41):
50
    c = res % (233)
51
    res //= 233
52
    flag += bytes([c])
53

54
print(flag)
55
print(flag[::-1])
56

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

poly#

题目附件

gen.py

1
from secret import flag
2
from functools import reduce
3

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

out.txt

1
[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
M = matrix(42)
2
for i in range(42):
3
    for j in range(42):
4
        M[i, 41-j] = i ^ j
5

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

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

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

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

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

1
from functools import reduce
2

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

6
equ = vector(list(map(lambda x: reduce(lambda t, y: t * x + y, u), range(42)))) - vector(v)
7
res = solve([*equ], *u)
8
assert len(res) == 1
9
print(res)
10
# [[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]]
11

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

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

supercomputer#

1
def f(x):
2
    x ^= ((x >> 11) & 0xb114514bb114514b)
3
    x ^= ((x << 13) & 0x114514cc114514cc)
4
    x ^= ((x << 17) & 0xaa191981aa191981)
5
    x ^= ((x >> 19) & 0xb1919810b1919810)
6
    x ^= ((x << 23) & 0x114514cd114514cd)
7
    x ^= ((x >> 29) & 0xb114514ab114514a)
8
    x ^= ((x << 31) & 0x114514cb114514cb)
9
    x ^= ((x << 37) & 0xaa19198caa19198c)
10
    x ^= ((x >> 41) & 0xb191981db191981d)
11
    x ^= ((x << 43) & 0x114514ce114514ce)
12
    return x
13

14
def calc(n):
15
    x = 0x1122334455667788
16
    for _ in range(n):
17
        x = f(x)
18
    return x
19

20
assert calc(1) == 0xaa732acf4eb6a79d
21
assert calc(10) == 0x28262ecbd673b7d7
22
assert calc(100) == 0x23a6b8be477b7c3
23
assert calc(1000) == 0x93737600f66aa785
24
assert calc(100000) == 0x8a762387c4e3aed8
25
assert calc(1000000) == 0x1267270a756bf7df
26
assert calc(10000000) == 0x39377648f4e367d7
27
assert calc(100000000) == 0x82232f8777773e8a
28
assert calc(1000000000) == 0x8762b83d6faa783
29
assert calc(10000000000) == 0x27237cdd6726788
30
assert calc(100000000000) == 0x97f6b44e7fe66de
31
assert calc(1000000000000) == 0x88723b8666ff27ca
32
assert calc(10000000000000) == 0x8a32670ee5ef6ec0
33
assert calc(100000000000000) == 0x993b3b4265ea6edb
34
assert calc(1000000000000000) == 0x8b732ec065e7e795
35

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

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

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

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

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

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

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

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

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

8
def xor_(x , y):
9
    x = deepcopy(x)
10
    for i in range(len(x)):
11
        x[i] += y[i]
12
    return x

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

1
from copy import deepcopy
2

3
def f(x):
4
    x = deepcopy(x)
5
    x = xor_(x, and_(right(x, 11) , 0xb114514bb114514b))
6
    x = xor_(x, and_(left(x, 13) , 0x114514cc114514cc))
7
    x = xor_(x, and_(left(x, 17) , 0xaa191981aa191981))
8
    x = xor_(x, and_(right(x, 19) , 0xb1919810b1919810))
9
    x = xor_(x, and_(left(x, 23) , 0x114514cd114514cd))
10
    x = xor_(x, and_(right(x, 29) , 0xb114514ab114514a))
11
    x = xor_(x, and_(left(x, 31) , 0x114514cb114514cb))
12
    x = xor_(x, and_(left(x, 37) , 0xaa19198caa19198c))
13
    x = xor_(x, and_(right(x, 41) , 0xb191981db191981d))
14
    x = xor_(x, and_(left(x, 43) , 0x114514ce114514ce))
15
    return x
16

17
F = f(X)
18

19
def calc(x, n):
20
    x = deepcopy(x)
21
    for i in range(n):
22
        x = f(x)
23
    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
def compose(x, y):
2
    return [x[i](y) for i in range(len(x))]
3

4
def quick_calc(F, n):
5
    F = deepcopy(F)
6
    result = deepcopy(X)
7
    while n > 0:
8
        if n & 1 == 1:
9
            result = compose(result, F)
10
        F = compose(F, F)
11
        n >>= 1
12
    return result

剩下就可以通过

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

来带值计算

综上，整理脚本如下：

1
# 将 unsigned long long 数转化为 $\mathbb{F}_2[x_0, x_1, \cdots, x_{63}]$
2
from copy import deepcopy
3

4
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))
5
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]
6

7

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

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

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

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

24
# 逻辑与 <-> 域乘
25
def and_(x, a):
26
    x = deepcopy(x)
27
    a_ = hex2bin(a)
28
    for i in range(len(x)):
29
        x[i] *= a_[i]
30
    return x
31

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

39

40
def f(x):
41
    x = deepcopy(x)
42
    x = xor_(x, and_(right(x, 11) , 0xb114514bb114514b))
43
    x = xor_(x, and_(left(x, 13) , 0x114514cc114514cc))
44
    x = xor_(x, and_(left(x, 17) , 0xaa191981aa191981))
45
    x = xor_(x, and_(right(x, 19) , 0xb1919810b1919810))
46
    x = xor_(x, and_(left(x, 23) , 0x114514cd114514cd))
47
    x = xor_(x, and_(right(x, 29) , 0xb114514ab114514a))
48
    x = xor_(x, and_(left(x, 31) , 0x114514cb114514cb))
49
    x = xor_(x, and_(left(x, 37) , 0xaa19198caa19198c))
50
    x = xor_(x, and_(right(x, 41) , 0xb191981db191981d))
51
    x = xor_(x, and_(left(x, 43) , 0x114514ce114514ce))
52
    return x
53

54

55
def calc(x, n):
56
    x = deepcopy(x)
57
    for i in range(n):
58
        x = f(x)
59
    return x
60

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

65
# 类似快速幂，O(n) -> O(log n)
66
def quick_calc(F, n):
67
    F = deepcopy(F)
68
    result = deepcopy(X)
69
    while n > 0:
70
        if n & 1 == 1:
71
            result = compose(result, F)
72
        F = compose(F, F)
73
        n >>= 1
74
    return result
75

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

79

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

后记#

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

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

音乐

HICTF2024_Crypto_部分题解

前言#

strhash#

poly#

supercomputer#

后记#

评论区

文章目录