糖醋小鸡块的blog
0%

2025-ACTF-wp-crypto

发表于 更新于 分类于 Valine：

和rec鏖战到半夜终于做出了ckks，算是锦上添花，恭喜NK拿到冠军！

image-20250427221056551

easy_log

题目

题目描述：

1
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)

题目给出了一套曲线点加和倍乘运算法则，在此基础上给出：

  • 一个作为模数的合数$n$
  • 两个起始点$G_1, G_2$

之后题目大概可以分为两个任务：

  1. 靶机在$Z_n$下计算$f_1 \cdot G_1$并给出，要求30s内计算出$f_1$并发回给靶机
  2. 输入一个400bit的素数$p$，靶机在$Z_p$下计算$f_2 \cdot G_2$并给出

思路

可以看出这题就是要解决题目给定曲线上的ECDLP，而一般要根据点加和倍乘运算法则，先找出对应的曲线方程，然后找对应映射，题目才会更清晰一点。

然而实际上这题并不需要这样，首先上factordb可以查到$n$的分解：

1
2
3
n = 0x231d5fa471913e79facfd95e9b874e2d499def420e0914fab5c9f87e71c2418d1194066bd8376aa8f02ef35c1926f73a46477cd4a88beae89ba575bb3e1b04271426c6706356dd8cd9aa742d7ad0343f8939bfd2110d45122929d29dc022da26551e1ed7000
primes = [(2, 12), (5, 4), (15271784978279, 1), (10714146599832792643, 1), (222696442740376752383, 3), (899889935029682511225429150065010811552017719005924136271659166808024139, 1), (899889935029682511225429150065010811552017719005924136271659168643090431, 1)]
assert n == prod([i[0]^i[1] for i in primes])

由于题目提供了点加和倍乘运算，这使得我们可以在$n$的任意一个素因子$p$下自行计算点乘，而这个操作的意义在于我们可以手动试一下题目点群的阶，测试出点群的阶基本是$p-1$或$p^2-1$。

进一步检查所有$p-1$的因子，会发现光滑的因子很多，这说明可以直接利用题目的点加和倍乘手写一个pohlig hellman+bsgs的ECDLP求解即可。由于第一部分求解的$f_1$是544bit的数量级，而光滑因子乘积就有520bit出头，并且由于有一个$p^3$因子的存在，还可以用p-adic求出$p$下的dlp，所以比特数完全够了。

第二部分就更简单，构造一个$p-1$光滑的不行的$p$发过去，再本地再运行一次pohlig hellman+bsgs就能得到$f_2$。

exp

(最后交给rec手动交互去了，还有个hashcash的pow要过)

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
from Crypto.Util.number import long_to_bytes, bytes_to_long, isPrime
from collections import namedtuple

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

def point_addition_Qp(P, Q):
	if P == O:
		return Q
	if Q == O:
		return P
	x = (P.x * Q.y + P.y * Q.x - P.x * Q.x)
	y = (P.x * Q.x + P.y * Q.y)
	return Point(x, y)

def double_and_add_Qp(k, P):
	Q = P
	R = O
	while(k > 0):
		if k & 1:
			R = point_addition_Qp(R, Q)
		k >>= 1
		Q = point_addition_Qp(Q, Q,)
	return R

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
1
2
3
4
5
6
7
8
from Crypto.Util.number import *

n = 0x231d5fa471913e79facfd95e9b874e2d499def420e0914fab5c9f87e71c2418d1194066bd8376aa8f02ef35c1926f73a46477cd4a88beae89ba575bb3e1b04271426c6706356dd8cd9aa742d7ad0343f8939bfd2110d45122929d29dc022da26551e1ed7000
primes = [(2, 12), (5, 4), (15271784978279, 1), (10714146599832792643, 1), (222696442740376752383, 3), (899889935029682511225429150065010811552017719005924136271659166808024139, 1), (899889935029682511225429150065010811552017719005924136271659168643090431, 1)]
assert n == prod([i[0]^i[1] for i in primes])

G1 = Point(0xf22b9343408c5857048a19150c8fb9fd44c25d7f6decabc10bf46a2250a128f0df15adc7b82c70c0acaf855c0e898b141c9c94ba8aef8b67ea298c6d9fd870ea70e1c4f8a1b595d15373dc6db25a4ecddf626a64f47beba5538b7f733e4aa0c4f1fd4c291d, 0x8d3264514b7fdbce97fbaedb33120c7889a1af59691a1947c2c7061347c091b0950ca36efaa704514004a988b9b87b24f5cebf2d1c7bef44ff172519e1a62eb62cde234c94bd0ab39375d7ddb42e044090c8db46d3f965ef7e4753bc41dac3b8b3ae0cdb57)
G2 = Point(0x81919777837d3e5065c6f7f6801fe29544180be9db2137f075f53ebb3307f917183c6fc9cdfc5d75977f7, 0xd1a586d6848caa3a5436a86d903516d83808ce2fa49c5fb3f183ecb855e961c7e816a7ba8f588ef947f19)
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
1
2
3
4
5
k = getrandbits(540)
kG1 = double_and_add(k, G1, n)
kk, ps = dlp(G1, kG1)

print(k % prod(ps) == kk)
1
ACTF{OL#m9Lpg8D1$<R3&e=10g@1N%F^nQ02pKjgZo0Oo!$Mp}

其他

虽然题目用不上曲线方程，但比赛中当然还是要靠方程清晰一下思路，这里正好分享一个比较通用的曲线方程插值法。

假设我们拥有足够多的曲线上点(这可以通过题目给的点加和倍乘做到)，那么可以假设曲线方程为下列向量的内积：

其中$\mathbf{a}$就是曲线方程每个单项的未知系数组成的向量，因此实际上一个点对就可以提供一个向量方程，搜集足够的单项式向量之后解方程解出$\mathbf{a}$即可。

对于题目来说，可以对$G_2$的倍点应用插值，就可以发现他所在的方程是在$\mathbb{Z}$上成立的$x^2+xy-y^2+1 = 0$，这是一个圆锥曲线，所以不手写ECDLP的话可以去搜下这个圆锥曲线对应点群的映射。



OhMyTetration

题目

题目描述：

1
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.")

简单来说，题目将flag转化为小于等于512bit的大整数$x$，之后随机发送给你一个素数$p$，可以选择一个数字$g$和一个次数$t$发回给靶机，然后靶机计算：

要求从这个值计算出$x$得到flag，并且有一些没有明确说的额外条件：

  • $p$并不是完全随机的素数，而是从给定的八个值里随便选的(反复重连测试了一下)
  • 发送的$g$需要通过$defineG$函数的check，具体要求不详，但是极慢

思路

首先，多次测试可以得出以下几个额外结论：

  • 有几个$p$满足$p-1=2q$，且$q-1$很光滑，基本是32bit的因子
  • $g$是素数似乎基本能通过$defineG$函数的check

所以可以类似数信杯的这道DDLLPP，发送$t=2$以及$Z_q$乘法群中的低阶因子作为$g$，然后在已知$f(t, g)$和$g$的情况下bsgs求解$f(t, g) = g^{g^x}$中的子群意义下的$x$并crt起来即可。

exp

$defineG$函数的check实在太慢，接近十分钟才能check一次，有时候直接超时断掉，所以我和rec只能手动开好几个窗口来一个个接下来数据再bsgs，最后手动crt，所以我最后写的相当乱，就贴个rec的exp好了TT：

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
from Crypto.Util.number import *
from pwn import *
from tqdm import tqdm, trange
from math import sqrt, prod

def fuzz():
    p = 7
    x = 233
    for g in range(100):
        io = remote(*"1.95.137.123 9999".split())
        io.sendlineafter(b'What do you do? ', b'4')
        io.sendlineafter(b"I don't think the boss's lucky number is lucky enough: ", str(p).encode())
        io.sendlineafter(b"with my own: ", str(x).encode())
        io.sendlineafter(b"own lucky number: ", str(g).encode())
        io.sendlineafter(b'your bet size: ', b'1')
        print(g, 'Oops' not in io.recvline().decode())
        io.close()
    exit()
# fuzz()

p = 1502305675703953507826564356364207463785905265358954425050832597353379827611347779894929874274487297076504174110953417469304402049079223143080164648064147459
q = (p - 1) // 2
qs = [(2, 12), (2449952539, 1), (2580715139, 1), (2792523953, 1), (2945474351, 1), (2996317717, 1), (3172879987, 1), (3229817321, 1), (3272969519, 1), (3435471803, 1), (3606091481, 1), (3613773421, 1), (3696075863, 1), (3706535681, 1), (3729911617, 1), (3912962413, 1), (3919762169, 1)]
assert q == prod(qi**i for qi, i in qs) + 1
qs = qs[1:]

def bsgs(g, h, p, q, qi):
    '''
    y = g^(g^x mod q) mod p
    let: x = a*m + b
    g^(g^(a*m)) = g^(g^(x-b)) = g^(g^x*g^(-b)) = (g^(g^x))^(g^(-b))
    '''
    m = int(sqrt(qi)) + 3
    dic = dict()
    for a in trange(m + 1):
        dic[pow(g, 2*pow(g, a*m, q), p)] = a
    for b in trange(m + 1):
        t = pow(h, 2*pow(g, -b, q), p)
        if t in dic:
            return dic[t]*m + b
    return None

# qi = qs[1][0]
# g = pow(2, (q-1)//qi, q)
# x = randint(0, qi-1)
# print(x)
# h = pow(g, pow(g, x, q), p)
# x = bsgs(g, h, p, q, qi)
# print(x)

nums = list()
g = 2
# for qi, _ in tqdm(qs[0:4]):
# for qi, _ in tqdm(qs[4:8]):
# for qi, _ in tqdm(qs[8:12]):
for qi, _ in tqdm(qs[4:8][::-1]):
    times = 2
    gi = pow(g, (q-1)//qi, q)

    while True:
        io = remote(*"1.95.137.123 9999".split())
        # context.log_level = 'debug'

        io.sendlineafter(b'What do you do? ', b'1')
        io.recvuntil(b"Today's lucky number is ")
        P = int(io.recvuntil(b'.')[:-1].decode())
        if P == p:
            break
        io.close()

    while True:
        gi = pow(gi, randint(1, qi-1), q)
        if isPrime(gi):
            io.sendlineafter(b'What do you do? ', b'2')
            io.sendlineafter(b"You decide to pick your own lucky number: ", str(gi).encode())
            if 'successfully' in io.recvline().decode():
                break

    io.sendlineafter(b'What do you do? ', b'3')
    io.sendlineafter(b"You decide to pick your bet size: ", str(times).encode())
    io.recvuntil(b'You take the ticket with the number ')
    # number = int(io.recvuntil(b'.')[:-1].decode())
    number = int((io.recvuntil(b'.')[:-1].split(b" from the machine")[0]).decode())
    nums.append((gi, number))
    print(f"{qi = }\n{gi = }\n{number = }")
    try:
        xi = bsgs(gi, number, p, q, qi)
        print(f"{xi = }")
    except:
        continue

    io.close()
print(f"{nums = }")
1
#Lucky won't help you but wisdom can! ACTF{0oooooh_My_T3tr@ti0n!}



AAALLL

题目

题目描述：

1
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'
'''

题目给出一个$Q = \frac{Z_p[x]}{x^{450}+1}$下的-1，0，1三值多项式$f(x)$，并随机抽取$Z_p$下$x^{450}+1=0$的其中225个根$g_i$，给出所有$(g_i,f(g_i))$，要求还原出三值多项式$f(x)$，从而解AES得到flag。

思路

不妨记$f(x)$的系数向量为$\mathbf{s}$，由拉格朗日插值的矩阵方程，225个点值可列出一个矩阵方程$\mathbf{s}_{1\times 450}A_{450\times 225} = \mathbf{b}_{1\times 225}$，并且可以拆成$\mathbf{s}_1A_1 + \mathbf{s}_2A_2 = \mathbf{b}$，最终可移项化简为$\mathbf{s}_1A_1A_2^{-1} + \mathbf{s}_2 = \mathbf{b}A_2^{-1}$。利用$\mathbf{s}$为短向量的特点，可以构造格：

如果将约束全部取上，则该格的维数为451维，并且由于模数较大、向量极短，可以少取很多组约束并flatter求解。经测试取140组约束即可在几分钟内可以规约出$\mathbf{s}_1$，代入求解$\mathbf{s}_2$即可拼起来得到$f(x)$。

exp

1
2
3
4
5
6
7
8
from re import findall
from subprocess import check_output

def flatter(M):
    # compile https://github.com/keeganryan/flatter and put it in $PATH
    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)))
1
2
3
4
5
6
7
8
9
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from hashlib import md5

n = 450
p = 3774877201
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'
1
2
3
4
5
6
7
A = []
for i in range(n//2):
    A.append([pow(subset[i], j, p) for j in range(n)])
A = Matrix(Zmod(p), A).T
A1, A2 = A[:n//2], A[n//2:]
A1_inv = A1^(-1)
b = vector(Zmod(p), values)
1
2
3
4
5
6
7
nums = 140
L = block_matrix(ZZ, [
    [1, 0, -(A2*A1_inv)[:, :nums]],
    [0, 1, Matrix(ZZ, (b*A1_inv)[:nums])],
    [0, 0, p]
])
print(L.dimensions())
1
2
L = flatter(L)
print(L[0])
1
2
3
4
5
6
7
8
9
10
res = L[0]
s2 = vector(Zmod(p), res[:n//2])
s1 = s2*-(A2*A1_inv) + b*A1_inv
s = []
for i in s1:
    if(i != 0 and i != 1):
        s.append(-1)
    else:
        s.append(int(i))
s += [i for i in res[:n//2]]
1
2
3
4
5
P.<x> = PolynomialRing(GF(p))
Q.<x> = P.quotient(x^n+1)
g = x^n+1
f = Q(s)
print([f.lift()(subset[i]) for i in range(n//2)] == values)
1
2
3
4
5
6
7
8
from Crypto.Cipher import AES
from hashlib import md5

key = md5(str(f.list()).encode()).digest()
aes = AES.new(key = key, mode = AES.MODE_ECB)
print(aes.decrypt(ct))

#ACTF{Pat141_V4nd3rrrrrm0000nd333_Pr000bl333m}

其他

但是这很显然是个非预期，原因有以下几个：

  • 一般来说，flatter似乎不太适用于这种-1、0、1的很小数量级的规约，只是这题模数大了一些，导致flatter比较适用

    要不是题目叫LLL估计真不会往flatter想，这种比较精确的一般都要BKZ

  • 题目给的不是随随便便的点值，而是$x^{450}+1=0$的根

赛后和@rec、@hashhash、@yolbby讨论了一下，其中第二个条件相当关键，factor一下$x^{450}+1$，可以发现它拥有一些结构较特殊的因式：

1
[x^2 + 1, x^6 + 1, x^10 + 1, x^18 + 1, x^30 + 1, x^50 + 1, x^90 + 1, x^150 + 1, x^450 + 1]

由于在$Z_p$下，$x^{450}+1$拥有全部450个根$g_i$，这代表着他可以在$F_p$下展开成：

而对于上面那些因式，比如$x^{150}+1$，这代表着$x^{150}+1$也可以写成其中某150个$(x-g_i)$的乘积，而对于这150个特殊的$g_i$来说，由于$g^{150}=-1$，因此其对应的范德蒙德矩阵行向量会出现正负号交替的循环，而此时则可以把对应的行向量三折叠，而系数向量$\mathbf{s}$的每个分量也就对应变成了$s_i - s_{i+150} + s_{i+300}$的形式，这就实现了降维。

而降维的意义在于，$s_i - s_{i+150} + s_{i+300}$这样的分量依然在$Z_p$下显得很小，所以可以规约出这样的所有三项和，这相当于在原来的$\mathbf{s}_{1\times 450}A_{450\times 225} = \mathbf{b}_{1\times 225}$这225个方程基础上，多出了150个新的方程，虽然一部分会是线性相关的，但是依然会有一部分多出来的线性无关的，这就可以让最后的格维数有所降低。

同理，对于$x^{90} + 1$，可以规约出所有五项和，这也可以多出一些方程，在有这些方程的基础上，$\mathbf{s}$的解空间维数就会下降很多，最后规约一个一百三四十维的矩阵即可。



tinyCKKS

题目

题目描述：

1
EE and ZZ. Isn’t it easy?

题目：

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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
import random
import re
import os
load("ckks.sage")

flag = os.getenv('FLAG')

def recv_poly():
    pattern = r"^(.*?) over Z\[X\]/\(X\^(\d+)\+1\) modulo (\d+)$"

    poly = input("")
    match = re.match(pattern, poly)
    if match:
        poly_str, N_str, q_str = match.groups()
        N = int(N_str)
        q = int(q_str)
        return polynomial(q, N, poly_str)
    else:
        raise TypeError("Input is not a valid polynomial")

def send_ct(ct):
    print(ct)

def recv_ct():
    a = recv_poly()
    b = recv_poly()

    return Ciphertext(a, b)

def send_key(key):
    for i in range(len(key)):
        send_ct(key[i])

def main():
    print("Welcome to ACTF 2025!")
    print("Here is a tiny implementation of CKKS scheme.")
    print("You can test by running module_test.sage.")
    print("Now let's start the challenge.")

    N = 1024
    p = 947819
    B = 2
    L = 4

    r = 10
    precision = 4

    debug = False

    ckks = tinyCKKS(N, p, B, L, debug)

    for _ in range(7):
        plain = [round(np.random.uniform(0, r), precision) for _ in range(N)]
        pt = ckks.encode(plain)
        ct = ckks.encrypt(pt)
        target_pt = pt

        send_ct(ct)

        c = int(input("Please give me c: "))

        if c == 1:
            ccc = int(input("Please choose operations you want to perform: "))
            assert 0 <= ccc <= 4

            if ccc == 1:
                print("Addition")
                plain1 = [round(np.random.uniform(0, r), precision) for _ in range(N)]
                pt1 = ckks.encode(plain1)
                ct1 = ckks.encrypt(pt1)
                send_ct(ct1)
                target_pt += pt1
            if ccc == 2:
                print("Multiplication")
                plain1 = [round(np.random.uniform(0, r), precision) for _ in range(N)]
                pt1 = ckks.encode(plain1)
                ct1 = ckks.encrypt(pt1)
                send_ct(ct1)
                print("relin_key: ")
                send_key(ckks.relin_key)
                target_pt *= pt1
                target_pt //= ckks.delta
            if ccc == 3:
                print("Key Switching")
                new_sk = sample_ternery_poly(ckks.Q)
                ksk = ckks.gen_ksk(new_sk)
                send_key(ksk)
                target_pt = pt
            if ccc == 4:
                print("Galois")
                t = int(input("Please choose galois parameter:")) % (2 * ckks.N)
                assert t % 2 == 1
                galois_key = ckks.gen_galois_key(t)
                send_key(galois_key)
                target_pt = target_pt.mapping(t)

            print("Please give me ct: ")
            ct = recv_ct()

            if ccc == 3:
                pt_decrypt = ckks.decrypt(ct, new_sk)
            else:
                pt_decrypt = ckks.decrypt(ct)

            new_plain = ckks.decode(pt_decrypt)
            target_plain = ckks.decode(target_pt)
            assert all([abs(target_plain[i] - new_plain[i]) <= 0.5 for i in range(ckks.N)])

            print("new_plain: ", new_plain)

            if ccc == 2:
                ckks.reset()
        elif c == 2:
            print("Here you are: ")
            origin_plain = ckks.decode(target_pt)
            print(origin_plain)
        elif c == 3:
            print("Do you know?")
            your_plain = recv_poly()
            if your_plain == target_pt:
                print(flag)
        else:
            print("Bye...")
            break
    

if __name__ == "__main__":
    main()

这个题目本身文件比较多，所以我也不太能很简洁的描述清楚题目内容，还是要仔细读下他的所有内容才行。这里就直接进做法。

思路

审计代码，发现源码的distribution.sage部分存在一定漏洞：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from random import getrandbits
from secrets import randbelow
import numpy as np

load("poly.sage")

def sample_gaussian_poly(Q):
    q = Q.base_ring().cardinality()
    N = Q.degree()
    return polynomial(q, N, Q([getrandbits(4) for _ in range(Q.degree()//2)] + [-getrandbits(4) for _ in range(Q.degree()//2)]))

def sample_uniform_poly(Q):
    q = Q.base_ring().cardinality()
    N = Q.degree()
    return polynomial(q, N, Q([np.random.choice([-1, 1]) * randbelow(int(q//2)) for _ in range(Q.degree())]))

def sample_ternery_poly(Q):
    q = Q.base_ring().cardinality()
    N = Q.degree()
    return polynomial(q, N, Q([np.random.choice([-1, 0, 1]) for _ in range(Q.degree())]))

这里比较突兀的地方在于高斯采样多项式的系数分布：

  • 用了random库的getrandbits
  • 前一半低次项系数为正，后一半高次项系数为负，并且没有shuffle
  • 无论是后面的均匀分布多项式系数采样，还是-1,0,1三值多项式系数采样，都没有再使用random库的其他任何函数

那么合理猜测这里的高斯采样是用来进行MT预测的，而主要是生成噪声e的时候会使用高斯采样，因此题目应该是想要想出办法泄露e并解出私钥，并向后继续预测e，从而得到我们需要发回的明文多项式。

但是赛中并没有看出哪里能泄露出e，甚至看不出哪里可以泄露e的任何分量的任何bit(因为不管怎么泄露，够19937bit就有机会)，所以没有在这方面继续下去。

而突破点依然在于MT，经过本地测试发现均匀分布的采样里有1024次np.random.choice([-1, 1])的采样，而经测试，这个采样实际上可以等价于MT意义下的getrandbits(1)，由此可以构建出一个解题思路：

  1. 第一次交互，输入c=1，之后输入ccc=3或ccc=4，在生成ksk或galois_key时，会连续生成100个sample_uniform_poly采样的多项式a
  2. 从a的各项系数是否小于int(q//2)，可以判断出choice究竟选了-1还是1，这等价于获得了1bit的MT的信息。100个a相当于提供了102400=100*1024bit的信息，远大于19937，所以完全足够
  3. 凑够19937个bit，从而获取numpy.random的初始624个state，从而可以向后预测。这一步可用102400bit中剩余的bit验证是否求解正确
  4. 第二次交互产生plain时，采用的依然是numpy内的函数plain = [round(np.random.uniform(0, r), precision) for _ in range(N)]，因此可以直接预测该明文对应的编码多项式，发送给靶机即获得flag。

exp

1
2
3
4
5
import random
import re
import os
load("ckks.sage")
load("poly.sage")
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
def strpoly_to_poly(poly):
    pattern = r"^(.*?) over Z\[X\]/\(X\^(\d+)\+1\) modulo (\d+)$"
    match = re.match(pattern, poly)
    poly_str, N_str, q_str = match.groups()
    N = int(N_str)
    q = int(q_str)
    return polynomial(q, N, poly_str)

def convert_ct_to_strpoly(line):
    ct = (line.strip().decode()[4:]).split(",")
    a, b = ct[0][1:], ct[1][:-1]
    return a, b

def poly_str_to_coeffs(poly_str):
    poly_str = poly_str.split(' over ')[0]  # 去掉 over 后面
    poly_str = poly_str.replace(' ', '')    # 去掉空格

    # 切出所有项
    terms = re.findall(r'[+-]?\d+\*X\^\d+|[+-]?\d+\*X|[+-]?\d+', poly_str)

    max_degree = 1023
    coeffs = [0] * (max_degree + 1)

    for term in terms:
        if '*X^' in term:  # a*X^b
            coef_str, exp_str = term.split('*X^')
            coef = int(coef_str)
            exp = int(exp_str)
        elif '*X' in term:  # a*X
            coef_str = term.replace('*X', '')
            coef = int(coef_str)
            exp = 1
        else:  # 常数
            coef = int(term)
            exp = 0

        coeffs[exp] = coef

    return coeffs
1
print(L.rank())
1
2
def decision(coeffs, q):
    return [1 if i < q // 2 else 0 for i in coeffs]
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
from pwn import *
from tqdm import *

context.log_level = "critical"

sh = remote("118.178.193.68", 9999)
#sh = process(["sage", "main.sage"])
sh.recvuntil(b"Now let's start the challenge.\n")
a, b = convert_ct_to_strpoly(sh.recvline())

p = 947819
q = p^5
t = 100
lines = []
c = []
for i in range(1):
    sh.sendline(b"1")
    sh.recvuntil(b"Please choose operations you want to perform: ")
    sh.sendline(b"4")
    sh.recvuntil(b"Please choose galois parameter:")
    sh.sendline(b"1")

    for j in range(t):
        lines.append(sh.recvline())
    for l in lines:
        c.append(convert_ct_to_strpoly(l))
    lines = []

    sh.recvuntil(b"Please give me ct: ")
    sh.sendline(a.encode())
    sh.sendline(b.encode())
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
a_bit = []
for i in c:
    a_bit += decision(poly_str_to_coeffs(i[0]), q)
R = vector(GF(2), a_bit[:19937])
res = (KK_inv * R).list()
res = [res[0]] + [0]*31 + res[1:]

init = "".join(list(map(str, res)))
state = []
for i in range(624):
    state.append(int(init[32*i:32*i+32],2))

RNG1 = np.random
RNG1.set_state(('MT19937', np.array(state), 623, 0, 0.0))

aa_bit = [RNG1.choice([0, 1]) for i in range(1024*100)]
print(aa_bit == a_bit)
1
2
3
4
5
6
7
8
9
10
11
12
13
plain = [round(np.random.uniform(0, 10), 4) for _ in range(1024)]
plain_poly = [round(plain[i] * p) for i in range(len(plain))]
poly = polynomial(q, 1024, plain_poly)

sh.recvuntil(b"Please give me c: ")
sh.sendline(b"3")
sh.sendline(str(poly).encode())
print(sh.recvline())
print(sh.recvline())
print(sh.recvline())


#ACTF{CcccckKkKkKkkKKsSSsS_CP4_s3cur1ty_14_1mp0rt4nt}

其他

但很显然这是个非预期，因为numpy之前是真没想过也能打MT，上一次这么震惊还是在@hashhash出的N1CTF的Matrix被sagemath的MT非预期掉XD。