Swizzer's euphonium
2024 SekaiCTF Crypto Writeup
Swizzer
  2024-08-29 16:41:24   2024-08-29 16:41:24    2.4k 字  13 分钟  

包含3道简单题，另外几个还在尝试复现。

赛中没看マスタースパーク实在是亏麻了，赛后多看了几眼才发现压根不需要攻击CSIDH本身QQ

以及，Neobeo我一直是你的粉丝啊（

Some Trick

task

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
import random
from secrets import randbelow, randbits
from flag import FLAG

CIPHER_SUITE = randbelow(2**256)
print(f"oPUN_SASS_SASS_l version 4.0.{CIPHER_SUITE}")
random.seed(CIPHER_SUITE)

GSIZE = 8209
GNUM = 79

LIM = GSIZE**GNUM


def gen(n):
    p, i = [0] * n, 0
    for j in random.sample(range(1, n), n - 1):
        p[i], i = j, j
    return tuple(p)


def gexp(g, e):
    res = tuple(g)
    while e:
        if e & 1:
            res = tuple(res[i] for i in g)
        e >>= 1
        g = tuple(g[i] for i in g)
    return res



def enc(k, m, G):
    if not G:
        return m
    mod = len(G[0])
    return gexp(G[0], k % mod)[m % mod] + enc(k // mod, m // mod, G[1:]) * mod


def inverse(perm):
    res = list(perm)
    for i, v in enumerate(perm):
        res[v] = i
    return res


G = [gen(GSIZE) for i in range(GNUM)]


FLAG = int.from_bytes(FLAG, 'big')
left_pad = randbits(randbelow(LIM.bit_length() - FLAG.bit_length()))
FLAG = (FLAG << left_pad.bit_length()) + left_pad
FLAG = (randbits(randbelow(LIM.bit_length() - FLAG.bit_length()))
        << FLAG.bit_length()) + FLAG

bob_key = randbelow(LIM)
bob_encr = enc(FLAG, bob_key, G)
print("bob says", bob_encr)
alice_key = randbelow(LIM)
alice_encr = enc(bob_encr, alice_key, G)
print("alice says", alice_encr)
bob_decr = enc(alice_encr, bob_key, [inverse(i) for i in G])
print("bob says", bob_decr)

在置换群上实作的一个类似Diffie-Hellman的加密，但是random seed给了你所以加密用的置换是可以求得的。enc函数的递归可以看作是一个mod进制展开式，先爆破拿到bob_key之后就可以逐位爆破flag了。

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
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
def base_expan(n, m):
    expan = []
    while n!=0:
        expan.append(n%m)
        n = n//m
    return expan

def inverse(perm):
    res = list(perm)
    for i, v in enumerate(perm):
        res[v] = i
    return res

def gexp(g, e):
    res = tuple(g)
    while e:
        if e & 1:
            res = tuple(res[i] for i in g)
        e >>= 1
        g = tuple(g[i] for i in g)
    return res


G = 
Ginv = [inverse(i) for i in G]
GSIZE = 8209
bob_decr = 
alice_encr = 
bob_encr = 
x = base_expan(alice_encr, GSIZE)
y = base_expan(bob_decr, GSIZE)
i = 0
bob_key = []

# try to find bobkey
for g in Ginv:
    if i >= len(x):
        tmp = gexp(g,0)
    else:
        tmp = gexp(g, x[i])
    for t in range(len(tmp)):
        if tmp[t] == y[i]:
            bob_key.append(t)
            break
    i += 1
bob_key_re = bob_key[::-1]
print(bob_key_re)
bobkey = 0
for i in range(len(bob_key_re)):
    bobkey *= GSIZE
    bobkey += bob_key_re[i]
print(bobkey)
print(bobkey<GSIZE**79)
from tqdm import trange
flag = []
bobkey_expan = base_expan(bobkey, GSIZE)
bob_encr_expan = base_expan(bob_encr, GSIZE)
print(bob_encr_expan,bobkey_expan)
count = 0

# crack flag "bit by bit"
for g in G:
    for i in trange(GSIZE):
        if count>= len(bobkey_expan):
            if(gexp(g,i)[0]==(bob_encr_expan[count])):
                flag.append(i)
                break
        else:
            if(gexp(g,i)[bobkey_expan[count]]==(bob_encr_expan[count])):
                flag.append(i)
                break
    count += 1
from Crypto.Util.number import long_to_bytes
flag_int = 0
flag_re = flag[::-1]
print(flag_re)
for i in range(len(flag_re)):
    flag_int *= GSIZE
    flag_int += flag_re[i]
print(flag_int)

# remove the padding
for i in range(flag_int.bit_length()):
    tmp = long_to_bytes(flag>>i)
    if b'{' in tmp:
        print(tmp)

はやぶさ

task

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from falcon import falcon
from flag import flag

def main():
    sk = falcon.SecretKey(64)
    pk = falcon.PublicKey(sk)
    print(pk)
    print(sk)
    print(sk.sign(b"Can you break me").hex())
    your_sig = bytes.fromhex(input("what is your sig? >"))


    if pk.verify(b"Can you break me", your_sig):
        print("well done!!")
        print(flag)
        exit()

    print("Broken your wing T_T")


main()

up.sh

1
2
3
4
5
6
7
8
9
git clone https://github.com/tprest/falcon.py.git

mv falcon.py falcon

echo "import os
import sys

sys.path.append(os.path.dirname(__file__))
" > ./falcon/__init__.py

读一下falcon的代码后知道这是个NTRU签名系统，私钥是多项式f、g、F、G，公钥是多项式h，所在的环是

所以就是商环上的NTRU签名伪造，拿格子直接打就行，但是coding就比较麻烦...

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
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
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
import falcon
from ntrugen import *
import encoding
# from timeout_decorator import timeout
import copy

HEAD_LEN = 1
SALT_LEN = 40
SEED_LEN = 56

def Babai_closest_vector(B, target):
    # Babai's Nearest Plane algorithm
    M = B.BKZ(block_size=20)
    G = M.gram_schmidt()[0]
    small = target
    for _ in range(1):
        for i in reversed(range(M.nrows())):
            c = ((small * G[i]) / (G[i] * G[i])).round()
            small -= M[i] * c
    return target - small

def get_fgFG(mat):
    lll = mat.BKZ()
    print(lll)

    cands = []
        
    for cand in lll:
        print(cand)
        f = cand[:blocksize]
        g = cand[blocksize:]

        if gs_norm(f, g, q) > (1.17 ** 2) * q:
            continue
        f_ntt = ntt(f)
        if any((elem == 0) for elem in f_ntt):
            continue
        try:
            F, G = ntru_solve(f, g)
            F = [int(coef) for coef in F]
            G = [int(coef) for coef in G]
            cands.append([f, g, F, G])
        # If the NTRU equation cannot be solved, a ValueError is raised
        # In this case, we start again
        except ValueError:
            continue

    return cands

def solve(h):
    n = int(64)
    sk = falcon.SecretKey(n)
    pk = falcon.PublicKey(sk)
    q = 12 * 1024 + 1
    salt = b"a"*SALT_LEN
    H = pk.hash_to_point(b"Can you break me", salt)
    K = int(sqrt(q))

    blocksize = len(h)

    one = matrix.identity(blocksize)
    qblock = q * one

    hblock = matrix(blocksize, blocksize)
    rh = list(reversed(h))
    for i in range(blocksize):
        for j in range(blocksize):
            hblock[i,j] = rh[(j-i) % blocksize]

    for j in range(blocksize-1):
        for i in range(j+1):
            hblock[i,j] = -1 * hblock[i,j]


    Hblock = matrix.circulant(H).transpose()
    zero = matrix(blocksize, blocksize)
    Kblock = K * one

    mat = block_matrix([
        [one, hblock],
        [zero,qblock]
    ])

    HH = copy.deepcopy(H)
    for i in range(blocksize):
        index = ((blocksize-1)*2 - i) % blocksize
        print(index)
        HH[i] = H[((blocksize-1)*2 - i) % blocksize]
    target = vector([0] * blocksize + HH)
    print("target:", target)
    res = Babai_closest_vector(mat, target)
    print("res:", res)
    print("hblock")
    print(hblock)
    print("hoge:", vector(GF(q), res[:blocksize]) * hblock)
    s1 = list(reversed(res[:blocksize]))
    print(sk.myverify(b"Can you break me", salt, list(reversed(res[:blocksize]))))
    print("--------------------------------------------------")
    s = sk.mysign(b"Can you break me", salt)
    sk.myverify(b"Can you break me", salt, s[1])
    print(s)
    print(res)

    logn = {
        2: 1,
        4: 2,
        8: 3,
        16: 4,
        32: 5,
        64: 6,
        128: 7,
        256: 8,
        512: 9,
        1024: 10
    }
    Params = {
        # FalconParam(2, 2)
        2: {
            "n": 2,
            "sigma": 144.81253976308423,
            "sigmin": 1.1165085072329104,
            "sig_bound": 101498,
            "sig_bytelen": 44,
        },
        # FalconParam(4, 2)
        4: {
            "n": 4,
            "sigma": 146.83798833523608,
            "sigmin": 1.1321247692325274,
            "sig_bound": 208714,
            "sig_bytelen": 47,
        },
        # FalconParam(8, 2)
        8: {
            "n": 8,
            "sigma": 148.83587593064718,
            "sigmin": 1.147528535373367,
            "sig_bound": 428865,
            "sig_bytelen": 52,
        },
        # FalconParam(16, 4)
        16: {
            "n": 16,
            "sigma": 151.78340713845503,
            "sigmin": 1.170254078853483,
            "sig_bound": 892039,
            "sig_bytelen": 63,
        },
        # FalconParam(32, 8)
        32: {
            "n": 32,
            "sigma": 154.6747794602761,
            "sigmin": 1.1925466358390344,
            "sig_bound": 1852696,
            "sig_bytelen": 82,
        },
        # FalconParam(64, 16)
        64: {
            "n": 64,
            "sigma": 157.51308555044122,
            "sigmin": 1.2144300507766141,
            "sig_bound": 3842630,
            "sig_bytelen": 122,
        },
        # FalconParam(128, 32)
        128: {
            "n": 128,
            "sigma": 160.30114421975344,
            "sigmin": 1.235926056771981,
            "sig_bound": 7959734,
            "sig_bytelen": 200,
        },
        # FalconParam(256, 64)
        256: {
            "n": 256,
            "sigma": 163.04153322607107,
            "sigmin": 1.2570545284063217,
            "sig_bound": 16468416,
            "sig_bytelen": 356,
        },
        # FalconParam(512, 128)
        512: {
            "n": 512,
            "sigma": 165.7366171829776,
            "sigmin": 1.2778336969128337,
            "sig_bound": 34034726,
            "sig_bytelen": 666,
        },
        # FalconParam(1024, 256)
        1024: {
            "n": 1024,
            "sigma": 168.38857144654395,
            "sigmin": 1.298280334344292,
            "sig_bound": 70265242,
            "sig_bytelen": 1280,
        },
    }

    from encoding import compress

    int_header = 0x30 + logn[n]
    header = int(int_header).to_bytes(1, "little")
    enc_s = compress(s1, Params[n]['sig_bytelen'] - HEAD_LEN - SALT_LEN)
    s = header + salt + enc_s 
    return s

from pwn import remote
io = remote("hayabusa.chals.sekai.team", int(1337), ssl=True)
print(io.recvline())
print(io.recvline())
h = io.recvline()
print(io.recvuntil('what is your sig? >'))

h = eval(h.split(b'=')[1])
print(h)

n = int(64)
sk = falcon.SecretKey(n)
pk = falcon.PublicKey(sk)
print(h)
s = solve(h)
print(sk.verify(b"Can you break me", s))
io.sendline(s.hex())
io.interactive()

*マスタースパーク

task

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
from Crypto.Util.number import *
import os
from timeout_decorator import timeout, TimeoutError

load("GA.sage")

FLAG = os.getenv("FLAG")
secret = getPrime(256)
choice = set()


@timeout(60)
def T_T(p, primes, secret):

    assert isPrime(p)
    assert len(primes) > 3

    Fp = GF(p)
    Fp2.<j> =  GF(p ^ 2, modulus=x ^ 2 + 1)
    ls = len(factor(p + 1)) - 2

    m = ceil((sqrt(p) ** (1 / ls) - 1) / 2)
    alice_priv = [randrange(-m, m + 1) for _ in range(len(primes))]
    bob_priv = [randrange(-m, m + 1) for _ in range(len(primes))]
    EC = montgomery(Fp2, 0)
    P = EC.gens()[0]
    k = 1
    alice_pub, Q = group_action(p, primes, Fp, Fp2, 0, alice_priv, k * P)
    share_bob, Q = group_action(p, primes, Fp, Fp2, alice_pub, bob_priv, secret * Q)
    bob_pub, P = group_action(p, primes, Fp, Fp2, 0, bob_priv, P)
    share_alice, P = group_action(p, primes, Fp, Fp2, bob_pub, alice_priv, P)
    return P, Q


def check(p):
    assert isPrime(p)
    assert p.bit_length() <= 96
    assert ((p + 1) // 4) % 2 == 1
    prime_list = []
    cnt = 0

    for p, i in factor((p + 1) // 4):
        assert not p in choice
        if i > 1:
            cnt += 1
            choice.add(p)
            assert int(p).bit_length() <= 32
        else:
            prime_list.append(p)
            choice.add(p)

    assert all([int(p).bit_length() <= 16 for p in prime_list])
    assert cnt == 1

    return prime_list


def main():
    while True:
        try:
            p = int(input("input your prime number or secret > "))
            if int(p).bit_length() == 256:
                if p == secret:
                    print(FLAG)
                    exit()
                print("not flag T_T")
            else:
                prime_list = check(p)
                P, Q = T_T(p, prime_list, secret)
                print(P.xy())
                print(Q.xy())
        except:
            print("T_T")
            exit()
main()

GA.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
40
41
from random import randint

# I received advice from Mitsu to write this program. I appreciate it very much

def montgomery(Fp2, A):
    return EllipticCurve(Fp2, [0, A, 0, 1, 0])

def to_montgomery(Fp, Fp2, E, G):
    Ep = E.change_ring(Fp).short_weierstrass_model()
    a, b = Ep.a4(), Ep.a6()
    P.<x> = PolynomialRing(Fp)
    r = (x^3 + a*x + b).roots()[0][0]
    s = sqrt(3 * r^2 + a)
    if not is_square(s):
        s = -s
    A = 3 * r / s
    phi = E.isomorphism_to(EllipticCurve(Fp2, [0, A, 0, 1, 0]))
    return Fp(A), phi(G)

def group_action(p, primes, Fp, Fp2, pub, priv, G):
    E = montgomery(Fp2, pub)
    es = priv[:]
    while any(es):
        x = Fp.random_element()
        P = E.lift_x(x)
        s = 1 if P[1] in Fp else -1
        S = [i for i, e in enumerate(es) if sign(e) == s and e != 0]
        k = prod([primes[i] for i in S])
        Q = ((p + 1) // k) * P
        
        for i in S:
            R = (k // primes[i]) * Q
            if R.is_zero():
                continue
            phi = E.isogeny(R)
            E = phi.codomain()
            Q, G = phi(Q), phi(G)
            es[i] -= s
            k //= primes[i]
    return to_montgomery(Fp, Fp2, E, G)

基于CSIDH的题目，会对传入的素数检查是否等于secret，是则输出flag，否则在通过额外的一些检查后生成超奇异椭圆曲线，接着在上面CSIDH。

虽然我对CSIDH一窍不通，但是题目把映射后的点也输出了：

P = EC.gens()[0] # 把这里的P记作G

那么返回给我们的其实是

所以有

一个ECDLP而已。

题目的二次曲线的阶是拿我们构造的(p+1)//4的素因子组成的，所以只需要控制p光滑之后就能求解ECDLP，最后crt起来就行。

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
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
# Sage
from Crypto.Util.number import *
import os
from pwn import remote, subprocess



load("GA.sage")
# PoW抄了鸡块师傅的写法，感谢ta的代码让手动挡变成自动挡
# 侵删
def runcmd(command):
    ret = subprocess.run(command,shell=True,stdout=subprocess.PIPE,stderr=subprocess.PIPE,encoding="utf-8")
    if ret.returncode == 0:
        print("success:",ret)
        return ret.stdout.strip()
    else:
        print("error:",ret)

io = remote(*'master-spark.chals.sekai.team 1337'.split(), ssl=True)
io.recvuntil(b'proof of work: ')
cmd = io.recvline().strip().decode()
res = runcmd(cmd)
io.sendlineafter(b'solution: ', res.encode())



def chal(p):
    print(">p", p)
    io.recvuntil(b"input your prime number or secret > ")
    io.sendline(str(p).encode())
    P= io.recvline().strip()
    Q= io.recvline().strip()
    return P, Q

import random
memo = set()
def make_prime():
    primes = []
    for i in range(2**7+256):
        if isPrime(i) and (i not in memo):
            primes.append(i)

    print(len(primes))
    for i in range(100000):
        p = 4
        l = random.sample(primes, 5)
        for pp in l:
            p *= pp
        r = random.sample(l, 1)[0]
        p *= r * r
        if isPrime(int(p-1)) and (p // 4) % 2 == 1:
            for ll in l:
                memo.add(ll)
            print("l:", l)
            return int(p-1)

def make_primes():
    res = []
    for i in range(10):
        res.append(make_prime())
    return res

def solve1(p):
    Fp = GF(p)
    Fp2.<j> =  GF(p ^ 2, modulus=x ^ 2 + 1)
    P, Q = chal(p)
    P = eval(P)
    Q = eval(Q)
    A = -(P[0]^3 - P[1]^2 + P[0])/P[0]^2
    EC = montgomery(Fp2, A) # order: (p+1)^2
    P = EC(P)
    Q = EC(Q)
    print(P)
    print(P.discrete_log(Q))
    return P.discrete_log(Q), P.order()

def check1(num):
    print(">p", p)
    return False

vals = []
mods = []
primes = make_primes()
for p in primes:
    print("==================================================", p, "==================================================")
    val, m = solve1(int(p))
    vals.append(val)
    mods.append(m)
    if lcm(mods) > 2**256:
        break

print(vals)
print(mods)
print(lcm(mods))
import copy

length = len(mods)


for mask in range(2**length):
    vals2 = copy.deepcopy(vals)
    for j in range(length):
        if ((mask >> j) & 1) == 1:
            vals2[j] = -vals2[j]
    try:
        cand = int(crt(vals2, mods))
        if cand.bit_length() == 256:
            print("check:", cand)
            io.sendline(str(cand).encode())
            print(io.recvline())
            print(io.recvline())
            print(io.recvline())

    except:
        pass
2024 SekaiCTF Crypto Writeup
da2307c.html
作者
Swizzer
发布于
2024-08-29 16:41
许可
  1. Some Trick
  2. はやぶさ
  3. *マスタースパーク
© 2022 - 2025    Swizzer
由 Hexo 驱动 & 主题 Keep
访客数 访问量
  1. Some Trick
  2. はやぶさ
  3. *マスタースパーク