2025.4.26ACTF

2025.4.26ACTF

是 2025.4.26ACTF 哒！

难难难。跑了4个小时的脚本说无解…
总之就是我自己爆0了。

easy_log

E@sy L0g

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
from Crypto.Util.number import long_to_bytes, bytes_to_long, isPrime
from os import urandom
from random import randint
from collections import namedtuple
from signal import alarm

Point = namedtuple("Point", "x y")
O = "Origin"

def point_addition(P, Q, n):
	if P == O:
		return Q
	if Q == O:
		return P
	x = (P.x * Q.y + P.y * Q.x - P.x * Q.x) % n
	y = (P.x * Q.x + P.y * Q.y) % n
	return Point(x, y)
	
def double_and_add(k, P, n):
	Q = P
	R = O
	while(k > 0):
		if k & 1:
			R = point_addition(R, Q, n)
		k >>= 1
		Q = point_addition(Q, Q, n)
	return R

with open("flag.txt", "rb") as f:
	flag = f.read()

assert len(flag) == 50
flag = urandom(randint(38, 48)) + flag
flag = flag + urandom(118 - len(flag))

flag1, flag2 = bytes_to_long(flag[:68]), bytes_to_long(flag[68:])

n = 0x231d5fa471913e79facfd95e9b874e2d499def420e0914fab5c9f87e71c2418d1194066bd8376aa8f02ef35c1926f73a46477cd4a88beae89ba575bb3e1b04271426c6706356dd8cd9aa742d7ad0343f8939bfd2110d45122929d29dc022da26551e1ed7000
G1 = Point(0xf22b9343408c5857048a19150c8fb9fd44c25d7f6decabc10bf46a2250a128f0df15adc7b82c70c0acaf855c0e898b141c9c94ba8aef8b67ea298c6d9fd870ea70e1c4f8a1b595d15373dc6db25a4ecddf626a64f47beba5538b7f733e4aa0c4f1fd4c291d, 0x8d3264514b7fdbce97fbaedb33120c7889a1af59691a1947c2c7061347c091b0950ca36efaa704514004a988b9b87b24f5cebf2d1c7bef44ff172519e1a62eb62cde234c94bd0ab39375d7ddb42e044090c8db46d3f965ef7e4753bc41dac3b8b3ae0cdb57)
G2 = Point(0x81919777837d3e5065c6f7f6801fe29544180be9db2137f075f53ebb3307f917183c6fc9cdfc5d75977f7, 0xd1a586d6848caa3a5436a86d903516d83808ce2fa49c5fb3f183ecb855e961c7e816a7ba8f588ef947f19)

f1 = double_and_add(flag1, G1, n)

print(f1)

alarm(30)

if flag1 != int(input()):
	exit()

p = int(input())

assert isPrime(p) and p.bit_length() == 400

f2 = double_and_add(flag2, G2, p)

print(f2)

题目让我们求2个在自定义曲线上的DLP。
NaCl是把这个问题转化为了矩阵上的问题，我们构造如下矩阵：
$$M_G=
\begin{bmatrix}
G.y-G.x,Q.x \
Q.x, Q.y
\end{bmatrix} \mod n$$
所有点加就被转换为了矩阵的乘法，倍乘就是矩阵的次方。
这个问题就转化为了矩阵的DLP了。
之后看他做的比较痛苦，我也不是很懂，但这个思路感觉还是不错的，记录一下。
然后就是照着小鸡块的博客的复现了。
easy_log
2个思路：

  1. 手写一个pohlig hellman+bsgs的ECDLP求解
  2. 可以通过曲线上的点来求出这条曲线（点可以通过点加和倍乘来得到，然后解个方程得到系数就好了，但再往后我就看不懂了…）

第一个思路：
先讲一下bsgs（baby-step giant-step）吧，这次遇到了，正好浅浅的学一下
对于一个离散对数问题（DLP）:
$a^x \equiv b\ (mod p)$
我们可以令$x=A\lceil \sqrt{p} \rceil + B$
那么等式就可以化为:
$a^{A\lceil \sqrt{p} \rceil}\equiv b^{-B}\ (mod p)$
那么我们只需要枚举A的值，从0到$\sqrt{p}$然后存入哈希表，再枚举B的值，从0到$\sqrt{p}$，每次枚举的时候查找表中是否有值和$b^{-B}$相同的值，有则取出对应的A，把$A\lceil \sqrt{p} \rceil + B$返回即可，可以在$O(\sqrt{p})$的时间复杂度下完成。
下面是这题中小鸡块写的bsgs:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def bsgs(G, kG, p, order):
    t = int(sqrt(order))+2
    dic = {}

    tG = double_and_add(t, G, p)
    atG = Point(0, 1)
    for a in range(t):
        dic[atG] = a
        atG = point_addition(atG, tG, p)
    
    bG = kG
    _G = double_and_add((-1) % order, G, p)
    for b in range(t):
        if(bG in dic.keys()):
            return t*dic[bG] + b
        bG = point_addition(bG, _G, p)

其中参数里的order是G的阶，而不是所在的群的阶。
然后再是pohlig hellman
值得一提的是，这里我们在应用pohlig hellman的时候，是需要分解一下这个群的order的。
即对于一个在$p * q$上的群，其中p,q都是质数，我们需要分解$(p-1) * (q-1)$，然后把整个群投影到阶更小的群中去（阶会比p-1,q-1更小），再用bsgs求解然后crt。在投影到阶更小的群后，bsgs里传入这个群的阶就可以了。

在其它情况下，如果我们的运算是在sagemath上有定义的，比如加减乘除，椭圆曲线的点加和点乘，我们可以直接使用sagemath内置的discrete_log函数来求解离散对数，这时我们就不需要分解order了，直接在discrete_log里传入ord=order即可，discrete_log函数会自动选择pohlig hellman来分解order求解（AI说的，但确实是不需要分解order，但在阶太大的情况下还是要考虑pohlig hellman+discrete_log，即先初步分解一下order，比如在前面那种情况下可以分解成p-1和q-1来传入）

回到题目中，至于投影的操作，比如整个群的阶是order，而你需要把这个群投影到阶为ord1的群上，那么对于点G，计算double_and_add(order//ord1,G,n)，这个点就是投影后的点了，kG也是一样的。
但是这题pohlig hellman还是不够，还是太慢了，所以我们需要再套一层，也就是小鸡块wp中的dlp函数:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def dlp(G, kG):
    ps = []
    ord_p = []
    for p, exp in primes[2:3]:
        ps.append(p-1)
        ord_p.append(pohlig_hellman(G, kG, p, p-1))
    for p, exp in primes[3:4]:
        ps.append(p^2-1)
        ord_p.append(pohlig_hellman(G, kG, p, p^2-1))
    for p, exp in primes[4:5]:
        ps.append(p^2-1)
        ord_p.append(pohlig_hellman(G, kG, p, p^2-1))
        ps.append(p)
        ord_p.append(lift_to_pk(p, G, kG))
    for p, exp in primes[6:]:
        ps.append(p-1)
        ord_p.append(pohlig_hellman(G, kG, p, p-1))
    return crt(ord_p, ps), ps

这里我去问了小鸡块，勉强搞懂了部分代码。
题目中的点加和点乘可以看作是二阶矩阵的运算，前面也有提到，所以我们可以把这个求自定义曲线的DLP转化成求二阶矩阵的DLP。
在模p上的矩阵，它的阶是$p*(p-1)*(p^2-1)$，也就是说我们可以把这个二阶矩阵投影到阶更小的子群上去求解，比如说阶为$p-1$，$p^2-1$的子群，而点的运算和这个二阶矩阵矩阵的运算是一样的，所以直接用点的运算即可，前面讲的也就不需要更改了。
个人感觉这个思路和pohlig hellman是很像的，整个思路就变成了：对一个阶很大的二阶矩阵矩阵构成的群，先把它投影到阶较小的子群上求解，在这个求解过程中再投影一次，投影到阶更小的子群上。
在实际的过程中，只需要最后一次投影即可，子群的子群还是子群，所以只需要在最后投影就好了，第一次就做了投影的话可能就是多此一举了，甚至可能会出现错误了。
而dlp函数中有的时候用的是$p-1$，有的时候是$p^2-1$，是这些子群有的阶是$p-1$，有的是$p^2-1$，实际测一下即可。
还有一点，我们可以注意到n的分解中有一个$p^3$，小鸡块在处理这个因子的时候特意加入了另一组解，这种是把$p^3$拆成了$p$和$p^2$，其中p用正常的pohlig hellman来解，$p^2$的求解用的是p-adic，但这个我还不是很懂，只知道这个也能用来求解离散对数，并且我遇到的都是用来求解$p^x$的，这题中x=2正好可以用。但实际原理我是不太懂的。
小鸡块的dlp这块的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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
def lift_to_pk(p, G, kG):
    order_p = p^2 - 1

    QPP = Qp(p)
    P_Qp = Point(QPP(G[0] % p^2), QPP(G[1] % p^2))
    Q_Qp = Point(QPP(kG[0] % p^2), QPP(kG[1] % p^2))

    nP_Qp = double_and_add_Qp(order_p, P_Qp)
    nQ_Qp = double_and_add_Qp(order_p, Q_Qp)

    secret_p =  ZZ((-nQ_Qp[0]/nQ_Qp[1]) / (-nP_Qp[0]/nP_Qp[1]))
    return secret_p % p

def bsgs(G, kG, p, order):
    t = int(sqrt(order))+2
    dic = {}

    tG = double_and_add(t, G, p)
    atG = Point(0, 1)
    for a in range(t):
        dic[atG] = a
        atG = point_addition(atG, tG, p)
    
    bG = kG
    _G = double_and_add((-1) % order, G, p)
    for b in range(t):
        if(bG in dic.keys()):
            return t*dic[bG] + b
        bG = point_addition(bG, _G, p)
        
def pohlig_hellman(G, kG, p, order):
    facs = list(factor(order))
    qs = []
    ord_q = []
    for q, exp in facs:
        qs.append(q^exp)
        ord_q.append(bsgs(double_and_add(order//(q^exp), G, p), double_and_add(order//(q^exp), kG, p), p, q^exp))
    return crt(ord_q, qs)

def dlp(G, kG):
    ps = []
    ord_p = []
    for p, exp in primes[2:3]:
        ps.append(p-1)
        ord_p.append(pohlig_hellman(G, kG, p, p-1))
    for p, exp in primes[3:4]:
        ps.append(p^2-1)
        ord_p.append(pohlig_hellman(G, kG, p, p^2-1))
    for p, exp in primes[4:5]:
        ps.append(p^2-1)
        ord_p.append(pohlig_hellman(G, kG, p, p^2-1))
        ps.append(p)
        ord_p.append(lift_to_pk(p, G, kG))
    for p, exp in primes[6:]:
        ps.append(p-1)
        ord_p.append(pohlig_hellman(G, kG, p, p-1))
    return crt(ord_p, ps), ps

或者可以这么理解第一个思路:
这实际上就是一种矩阵的dlp，我之前见过的矩阵的dlp的用矩阵的行列式来代替矩阵，这样就是把矩阵的dlp转化成了普通的dlp。
但第一个思路里，我们就是直接通过手写一个bsgs去求矩阵的dlp。
在模质数p上的矩阵的阶是$p*(p-1)*(p^2-1)$，所以可以分别用pohlig hellman求一下子群的dlp。

第二个思路就不讲了，我也还没去试过。

AAALLL

Let’s welcome AAA’s LLL master!

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
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from random import choice, sample
from secret import flag
from hashlib import md5

def sample_ternery_poly(Q):
    return Q([choice([-1, 0, 1]) for _ in range(Q.degree())])

n = 450
p = 3774877201
t = n//2

P.<x> = PolynomialRing(GF(p))
g = x^n+1
roots = [i[0] for i in g.roots()]

subset = sample(roots, t)

Q.<x> = P.quotient(x^n+1)
f = sample_ternery_poly(Q)
f_lift = f.lift()
values = [f_lift(i) for i in subset]

print(f"subset: {subset}")
print(f"values: {values}")

key = md5(str(f.list()).encode()).digest()
aes = AES.new(key = key, mode = AES.MODE_ECB)
print(f"ct: {aes.encrypt(pad(flag, 16))}")

'''
subset: [1040018022, 3719840057, 2086762603, 3065369513, 3179320758, 891114580, 966265556, 664146925, 1232096603, 1449704729, 2810118429, 2891821810, 698162894, 3070228878, 3114653287, 2793650430, 2941920517, 1811454265, 325024118, 1860481904, 555392385, 2818572232, 3719972491, 981226771, 1777524396, 2717373523, 3694549306, 91210020, 1397236365, 2806262125, 1966653548, 1369610707, 3545263790, 595556443, 1601356313, 2865921937, 2795518764, 1690002428, 3501122295, 2078440315, 1222414863, 1997352805, 271758023, 3348936352, 1800648013, 410072905, 3378691273, 185134810, 1281817316, 821730517, 2855781188, 3353349707, 273754906, 1187616168, 569728457, 401428606, 3671298095, 149603298, 2300569286, 1057503678, 1915386614, 2716934671, 2005635066, 389589525, 2691165686, 586877133, 2874838, 660954102, 3258633701, 1083711515, 1785913794, 3410290851, 1914395297, 2544074509, 3076714307, 2169463229, 2654223166, 3648299978, 3188000068, 1130206965, 875184747, 2549126013, 3602874619, 80327895, 983400559, 2423201604, 3384400899, 654136379, 1835112234, 3302809337, 3388376496, 364586350, 3219484816, 52162306, 3488542302, 2843511894, 638341256, 427235375, 757491483, 3364804296, 172002582, 3112473265, 2746078509, 2118542465, 421527494, 3017385718, 3683667181, 3536621837, 3113923099, 1989065494, 1769242135, 1541932517, 1963422936, 2341204092, 3306256995, 186750428, 1381468653, 1288011784, 229613411, 839241230, 425544589, 2345390466, 2552462338, 286334899, 2984993503, 3741109364, 103579106, 138703348, 2369990075, 2377640836, 1279106009, 2542780598, 1653097443, 3373448595, 2405266494, 3385287676, 289622793, 2376573706, 3096235437, 1971476669, 3449853083, 3565565810, 762810383, 272826480, 516243500, 1710511548, 3233762177, 2013126070, 224313638, 1884110819, 3141861971, 2014729696, 1572103482, 2232944684, 2644670236, 1350302342, 3589742391, 2106163918, 1077036824, 3527373372, 2474464298, 971863088, 1219963894, 3349332612, 1474307915, 905651245, 2666266327, 2192845472, 2748042118, 1489782942, 1300412903, 126577223, 545427793, 360417066, 704648323, 3562938536, 908955264, 1108610874, 247503829, 2379959160, 1059927520, 2869225956, 2202773719, 1498564318, 2032958616, 3485254408, 1091224495, 3287849020, 780873181, 3410363615, 1398303495, 2426564739, 487028181, 1230802692, 139226346, 789883698, 2557862280, 2994004020, 3205148744, 2914199937, 1803400532, 2738281702, 883055391, 1761751131, 1220550272, 1947825121, 3543565567, 1939764967, 2986882625, 798323428, 1120654035, 3722714895, 3679983602, 364513586, 1760147505, 472067864, 2393408548, 2239781327, 799334306, 3497260623, 2769084221, 860677264, 990410164, 3772002363, 2883762621]
values: [712538976, 1225537965, 2633482204, 1245652635, 2529155164, 1672980719, 3024410928, 1535384351, 2252244320, 672919726, 2976916118, 3089453551, 2512277279, 2431400831, 1129198075, 3441247454, 610984549, 2043949242, 3306515233, 2759625250, 2459507335, 2885552592, 3226187015, 983312810, 1815610133, 871259259, 3651562935, 570267317, 2548725905, 70380481, 685470168, 1925389996, 2466124957, 1512923993, 2603725653, 409457162, 859041441, 3193931087, 786021320, 2481319115, 2379423262, 1972220678, 251474531, 448830331, 3189297419, 845468707, 3014186402, 1476144624, 1412175603, 464556671, 1251535251, 2252149066, 3501165225, 1173484383, 1168113959, 2547845342, 3132683037, 182880838, 3236782773, 637440805, 1077834200, 910992912, 1281164705, 763525563, 1025793488, 3031918542, 2457090411, 159146268, 3252417067, 1695150089, 1863899429, 2660689081, 647461624, 3736679821, 2034134877, 973654854, 1545264273, 692989149, 769387639, 2024000598, 2916906076, 1996631367, 2889527392, 527082343, 3319918691, 3629378248, 685639382, 2659312228, 472574946, 1237496521, 434512296, 3649895972, 3500730074, 1092276151, 1513927060, 1179642291, 474879861, 1132457849, 3072787035, 1536862618, 3131879287, 1635514910, 2467715064, 2377496874, 2888951190, 3697148067, 1885811970, 1037114846, 2862197847, 2248493059, 829223452, 17390497, 1063920331, 2504310664, 2269937803, 667770896, 1855657371, 323906741, 2972650844, 3620395133, 2613325861, 2508686438, 2143229100, 977352912, 3380653143, 2367018411, 1665354812, 2473914413, 3531805346, 2023595772, 1909192693, 844059686, 2233570033, 1997039839, 3558799006, 2872633369, 1949018254, 3159312415, 3021409934, 2505867881, 2357897866, 3436059930, 1496867815, 594001374, 3433203342, 2396280741, 2696363547, 1775021594, 434891096, 862244228, 1372573410, 3003385341, 3051290794, 493688483, 2143128679, 394087901, 3668481745, 1085467544, 2438896216, 1782052147, 2415529482, 149721114, 1539904401, 1902915995, 1929333694, 1759980967, 2106193398, 3670877657, 2736025727, 3133082490, 182590224, 1099952929, 3522052498, 2206338880, 1925988633, 3440533747, 25471854, 325651518, 72348028, 3178620735, 3335468600, 818634602, 2932340363, 1163855672, 2453716531, 373827915, 2373018915, 2231504345, 2975884007, 3636085022, 2354093635, 2696203979, 799834661, 2412088324, 1446875965, 3299868618, 302142905, 1957341475, 1522953201, 1257060525, 3769499753, 1591149900, 295691418, 3249943297, 1280379656, 1164820140, 115871117, 219831260, 2505969457, 2618672354, 2781617927, 2886486193, 1648555579, 1265576372, 1720183485, 2424145699, 2772052592, 2399827477, 626825210, 2422432913, 322266950, 2157976175, 2208875362, 2216568965, 3223085486]
ct: b'"\xf2Y\xf0\x15\xc5x\x94\xb9E\xbd\xd3\xa7\xb1\xad\x00\xa2D*+\x87BQ_20\x87\xa2\nP\xfc\xce\x0eW\xaf\xd8-.\xb5\xfai\xf1\xf6*\xben^\xd5'
'''

题目我不是很能看懂，大致意思就是构造了一个多项式，最高次是$x^{449}$，多项式的系数是从$-1,0,1$中随机抽取的，然后用一个值带入这个多项式并给出结果，总共生成了$n/2$组数据，subset是带入的值的列表，values的结果的列表。然后要求我们解出这个$-1,0,1$序列。
一开始就感觉这个和背包问题很像，然后事实证明在数据量比较小的情况下，比如n=100,背包确实能解。但这题数据量明显特别大，即使用了flatter加速也要好几个小时才能跑完，并且随着数据量的增大，背包也很难求出我们所需要的解。
后来问了下小鸡块，他是把背包构造的矩阵进行了拆解，然后使得数据量减小了，也就更容易解出来了。
在背包问题中我们有系数向量s，$s * A=b$，其中A是由求s用的$450 * 450$的单位矩阵和255个规约组成的，这样的格明显会特别大，所以小鸡块对s和A进行了拆分，可以让A的构造变小很多，也就是降维。
我们把s按左右拆成$s_1$和$s_2$，A则对应的按上下拆成$A_1$和$A_2$，我们仍然有$s_1 \cdot A_1 + s_2 \cdot A_2 = \mathbf{b}$，然后移项化简得出:
$s_1 * A_1 * A_2^{-1}+s_2=b * A_2^{-1}$
所以我们可以构造格
$$
\begin{pmatrix}
1 & 0 & -A_1A_2^{-1} \
0 & 1 & \mathbf{b}A_2^{-1} \
0 & 0 & p
\end{pmatrix}
\to
(s_1, 1, \mathbf{k})
\begin{pmatrix}
1 & 0 & -A_1A_2^{-1} \
0 & 1 & \mathbf{b}A_2^{-1} \
0 & 0 & p
\end{pmatrix}
= (s_1, 1, s_2)
$$
这样我们构造的格就会小很多了，求解也就更容易了。
感觉这样的构造会很有用，以后格过大的时候可以参考一下来降维。
构造完就是直接flatter加速，然后拿出$s_1$和$s_2$组成s就是我们要求的了。
小鸡块的exp

顺带提一下arch上安装flatter(目前还是电脑小白，只会这个喵)
直接

1
paru -S flatter-git

就可以了
然后要用就

1
2
3
4
5
from subprocess import check_output
def flatter(M):
    z = "[[" + "]\n[".join(" ".join(map(str, row)) for row in M) + "]]"
    ret = check_output(["flatter"], input=z.encode())
    return matrix(M.nrows(), M.ncols(), map(int, findall(b"-?\\d+", ret)))

以及我发现传入flatter的矩阵如果是在QQ上的就会报错，ZZ上的就不会，很神奇。

OhMyTetration

Welcome to my Lottery Center!

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
from Crypto.Util.number import bytes_to_long
from secret import LotteryCenter, FLAG
import signal

def handler1(signum, frame):
    raise TimeoutError("You took too long to make a decision. The boss is not patient.")
def handler2(signum, frame):
    e = '''
Before I can react, a heavy hand clamps onto my shoulder. The boss's face is dark with rage. "What the hell did you do?!"
I stammer, "I just thought the numbers could be luckier..."
"OUT!" he roars, dragging me toward the door. "And don't come back unless you've got the money to replace this thing!"
'''
    raise TimeoutError(e)

x = bytes_to_long(FLAG)
assert x.bit_length() <= 512

descrption = """
You step into the Lottery Center, the bell above the door rings softly as you enter. The air is stale, with an old fan humming above. The walls are lined with lottery posters and flashing numbers. At the counter, a middle-aged man in a dark suit is busy sorting through some papers, unaware of your presence.

The atmosphere is quiet and slightly unsettling. You glance around the room — a corner has an old lottery machine, still occasionally making a "clicking" noise. There's a poster on the wall showing today's lucky numbers, but they seem somewhat blurry.
"""

print(descrption)

lotteryCenter = LotteryCenter()

menu = """
You're left with a few choices:
1. Talk to the Boss.
2. Pick Your Lucky Number.
3. Choose Your Bet Size.
4. Look Around.
"""

signal.signal(signal.SIGALRM, handler1)
signal.alarm(600)

while 1:
    print(menu)
    choice = input("What do you do? ")
    if choice == "1":
        # Choose my favourite number.
        print(f"You approach the counter. The boss looks up briefly, then says in a low voice, \"Today's lucky number is {lotteryCenter.P}. Trust it, it will bring good luck.\"")
    elif choice == "2":
        g = int(input("You decide to pick your own lucky number: "))
        if lotteryCenter.defineG(g):
            print("You successfully pick your lucky number.")
        else:
            print("You can't pick that number.")
    elif choice == "3":
        if lotteryCenter.g==None:
            print("You should pick your lucky number first.")
        else:
            times = int(input("You decide to pick your bet size: "))
            assert times>0
            ticket = lotteryCenter.tetration(times, x)
            # Calculate the tetration g^g^...^g(times)^x.
            # For example, P=23, g=3, tetration(3, 2) = 3^(3^(3^2)) % 23 = 12.
            print(f"You take the ticket with the number {ticket} from the machine, feeling a slight chill in the air. The boss looks at you for a moment longer, his expression unreadable. Then, with a slow smile, he finally speaks, his voice low but clear:")
            print("\"Good luck... I hope today is your lucky day.\"")
            break
    elif choice == "4":
        print("The boss seems distracted — perhaps counting cash or sorting through stacks of old receipts, his back turned just enough. Seizing the moment, I slip around to the back of the lottery machine, my fingers hovering over the controls. A quiet smirk tugs at my lips as I mutter under my breath ...")
        lotteryCenter.P = int(input("I don't think the boss's lucky number is lucky enough: "))
        assert lotteryCenter.P>1
        x = int(input("\"Yes!\" I whisper, overriding the preset algorithm with my own: "))
        g = int(input("You decide to pick your own lucky number: "))
        times = int(input("You decide to pick your bet size: "))
        assert times>0
        signal.signal(signal.SIGALRM, handler2)
        signal.alarm(10)
        try:
            if lotteryCenter.defineG(g):
                ticket = lotteryCenter.tetration(times, x)
                print(f"You take the ticket with the number {ticket} from the machine secretly.")
            else:
                print("Oops! The lottery machine whirs weakly as I finish tampering with its settings — then suddenly, the screen flickers violently before dying with a pathetic click. A thin wisp of smoke curls from the vents.")
        except TimeoutError as e:
            print(e)
        finally:
            signal.alarm(0)
        break
    else:
        print("Nothing here.")

print("\nYou exit the Lottery Center, the door closing softly behind you. The bell rings once more, leaving you standing outside, holding the ticket — unsure if you've just stepped into a stroke of luck... or something else entirely.")

你可以指定t和g，靶机会计算
$$
f(t, g) = g^{g^{g^{\dots(\text{共} t \text{个} g)^{x}}}} \mod p
$$
并返回
实际测一下可以发现有些p，p-1是很光滑的，所以我们可以使用pohlig hellman，同样也是手写一个bsgs。
只不过这次我们要解的方程是$g^{g^x} \equiv f\ (mod p)$，

To Be Continue…

crypto > ACTF
#crypto #矩阵DLP #bsgs #pohlig hellman #flatter
2025.4.26ACTF
https://bddye.github.io/2025/05/11/2025-4-26ACTF/
作者
蹦跶的鱼儿
发布于
2025年5月11日
许可协议