はじめに
2023/12/23（土）- 2023/12/24（日）の2日間でSECCON CTF 2023の決勝戦が開催されました。 チーム southball 1 の4人で参加して国内3位でした🎉 思った以上の結果が出せて嬉しいです。
SECCON本戦に出場していました
— Laika (@ki4l_) December 24, 2023
チームsouthballで国内3位でした！ pic.twitter.com/CNyPbsQ2le
チームメイトのwriteup
- Ciffelia: https://blog.ciffelia.com/article/seccon2023-finals
- southball: https://github.com/southball/ctf-writeups/tree/main/SECCON-CTF-2023-Final
[Crypto] DLP 4.0
1import os
2import secrets
3import signal
4
5FLAG = os.getenv("FLAG", "FAKEFLAG{THIS_IS_FAKE}")
6
7
8if __name__ == "__main__":
9 signal.alarm(333)
10 p = int(input("What's your favorite 333-bit p: "))
11 if not is_prime(p) or p.bit_length() != 333:
12 print("Invalid p")
13 exit()
14 order = p**2 - 1
15 x = secrets.randbelow(order)
16 Q = QuaternionAlgebra(Zmod(p), -1, -1)
17 g = Q.random_element()
18 h = g**x
19 print(f"{g = }")
20 print(f"{h = }")
21 _x = int(input("Guess x: "))
22 if g**_x == h:
23 print(FLAG)
24 else:
25 print("NO FLAG")
問題は至ってシンプル。
- 333bitの素数$p$をサーバーへ送信する。
- サーバー側で適当な$g \in \mathbb{H}_p$が選択される。
- $g, g^x$が与えられるので、$x$を求める。
離散対数問題で、こちらが$p$を自由に決められる状況なので、Pohlig-Hellmanを真っ先に試しました。
素数生成
一番典型的なPohlig-Hellmanではorder = p-1であることが多いですが、 今回はorder = p**2 - 1なので素数生成を少し工夫する必要があります。
はじめは$p-1$, $p+1$ともにsmoothな$p$を探すスクリプトを回していたのですが、待ち時間でいろいろ実験した結果、そこそこ早くて体感50%くらいの確率で成功する素数生成方法にたどり着きました。
ビット数が333bitになるように$m$個の乱数$r_i$を用いて、以下のように$p$を定めます。
$$
p = \left( \prod_{i=1}^{m}{r_i}^2 \right) + 1
$$
この$p$でPohlig-Hellmanをすればそこそこの確率で解が出てきます。
よくわかっていないので別の問題をupsolveしたら深掘りしてみます。
余談ですが、 生成した$p$を投げてsageのdiscrete_logに投げようとすると、Cへの変換でoverflowする旨の面倒そうなエラーと遭遇しました… 仕方がないので、bsgsの実装をコピペしてきて少しいじったものを使いつつ、自前でPohlig-Hellmanを書きました。
1from copy import copy
2import random
3
4from Crypto.Util.number import isPrime
5
6from toyotama import *
7
8load('dlog.sage') # fixed bsgs
9
10def pohlig_hellman(g, y, p):
11 remain = []
12 moduli = []
13 order = p**2-1
14 fct = list(factor(p**2-1))
15 for ii, (p, e) in enumerate(fct):
16 q = p**e
17 print(f'{ii}/{len(fct)} {q = }')
18 assert g**order == 1
19 try:
20 x = bsgs(g**(order//q), y**(order//q), (0, q-1))
21 except ValueError as ee:
22 print('error', ee, ii, p**e)
23 exit()
24 remain.append(x)
25 moduli.append(q)
26 ans = crt(remain, moduli)
27 ans = crt(remain, moduli)
28 return ans
29
30
31def gen_prime(bits: int = 333) -> int:
32 while True:
33 p = 1
34 while p.bit_length() < bits:
35 p *= random.getrandbits(37//2) ** 2
36 p |= 1
37 if p.bit_length() == bits and isPrime(p):
38 return p
39
40_r = Socket("nc host.docker.internal 8888")
41p = int(gen_prime())
42_r.sendlineafter(": ", p)
43
44Q = QuaternionAlgebra(Zmod(p), -1, -1)
45i, j, k = Q.gens()
46
47g = _r.recvline().decode().strip().split('=')[-1].split(' + ')
48g = int(g[0]) + int(g[1][:-2])*i + int(g[2][:-2])*j + int(g[3][:-2])*k
49
50h = _r.recvline().decode().strip().split('=')[-1].split(' + ')
51h = int(h[0]) + int(h[1][:-2])*i + int(h[2][:-2])*j + int(h[3][:-2])*k
52
53x = int(pohlig_hellman(g, h, p))
54assert g**x == h
55_r.sendlineafter(": ", x)
56_r.recvline()
SECCON{Yay! You've got a 333-bit useful prime for CTF! <333}
[Crypto] KEX 4.0
1import os
2from hashlib import sha256
3from secrets import randbelow
4
5from Crypto.Cipher import AES
6from Crypto.Util.number import long_to_bytes
7
8
9FLAG = os.getenvb(b"FLAG", b"FAKEFLAG{THIS_IS_FAKE}")
10
11p = 0xC20C8EDB31BFFA707DC377C2A22BE4492D1F8399FFFD388051EC5E4B68B4598B
12order = p**2 - 1
13Q = QuaternionAlgebra(Zmod(p), -1, -1)
14i, j, k = Q.gens()
15pub_A = (
16 71415146914196662946266805639224515745292845736145778437699059682221311130458
17 + 62701913347890051538907814870965077916111721435130899071333272292377551546304 * i
18 + 60374783698776725786512193196748274323404201992828981498782975421278885827246 * j
19 + 60410367194208847852312272987063897634106232443697621355781061985831882747944 * k
20)
21pub_B = (
22 57454549555647442495706111545554537469908616677114191664810647665039190180615
23 + 8463288093684346104394651092611097313600237307653573145032139257020916133199 * i
24 + 38959331790836590587805534615513493167925052251948090437650728000899924590900 * j
25 + 62208987621778633113508589266272290155044608391260407785963749700479202930623 * k
26)
27
28
29def hash_Q(x):
30 return sha256(
31 long_to_bytes(int(x[0]))
32 + long_to_bytes(int(x[1]))
33 + long_to_bytes(int(x[2]))
34 + long_to_bytes(int(x[3]))
35 ).digest()
36
37
38if __name__ == "__main__":
39 # Alice sends share_A to Bob
40 priv_A = randbelow(order)
41 A = pub_A**priv_A
42 share_A = A**-1 * pub_B * A
43 print(f"{share_A = }")
44 # Bob sends share_B to Alice
45 priv_B = randbelow(order)
46 B = pub_B**priv_B
47 share_B = B**-1 * pub_A * B
48 print(f"{share_B = }")
49 # Alice computes the shared key
50 Ka = A**-1 * share_B**priv_A
51 # Bob computes the shared key
52 Kb = share_A**-priv_B * B
53 assert Ka == Kb
54
55 # Encrypt FLAG with the shared key
56 key = hash_Q(Ka)
57 cipher = AES.new(key, mode=AES.MODE_CTR)
58 nonce = cipher.nonce.hex()
59 enc = cipher.encrypt(FLAG).hex()
60 print(f"{nonce = }")
61 print(f"{enc = }")
鍵交換と四元数。
まずは、ソースコードで示された鍵交換を追ってみます。 Alice由来のパラメータは以下の通り。
- $p_A$
priv_A - $P_A$
pub_A - $a = {P_A}^{p_A}$
A - $S_A = A^{-1} P_B A$
share_A
Bob由来のパラメータは以下の通り。
- $p_B$
priv_B - $P_B$
pub_B - $b = {P_B}^{p_B}$
B - $S_B = B^{-1} P_A B$
share_B
共有鍵の導出
共有鍵$K_A, K_B$は以下のように変形できます。 $$ \begin{aligned} K_A &= a^{-1} S_B^{p_A} &= a^{-1}(b^{-1} P_A b)^{p_A} &= a^{-1}(b^{-1} P_A^{p_A} b) &= a^{-1}b^{-1}ab \end{aligned} $$ $$ \begin{aligned} K_B &= S_A^{-p_B} b &= (a^{-1} P_B a)^{-p_B} b &= (a^{-1} P_B^{-p_B} a)b &= a^{-1} b^{-1} ab \end{aligned} $$ よって$K_A=K_B$となり、確かに鍵交換できていそうです。
四元数の要素ごとに立式
最終的に$a$と$b$が分かれば共有鍵を復元できるので、これらの四元数を未知数として要素ごとに方程式を立ててみます。
$$ \begin{aligned} a &= a_0 + a_1 i + a_2 j + a_3 k \\ S_A &= {S_A}_0 + {S_A}_1 i + {S_A}_2 j + {S_A}_3 k \\ P_B &= {P_B}_0 + {P_B}_1 i + {P_B}_2 j + {P_B}_3 k \\ \end{aligned} $$ とすると、$A S_A = P_B A$より、
$$
\left\{
\begin{aligned}
a_0 {S_A}_0 - a_1 {S_A}_1 - a_2 {S_A}_2 - a_3 {S_A}_3 \equiv {P_B}_0 a_0 - {P_B}_1 a_1 - {P_B}_2 a_2 - {P_B}_3 a_3 \mod p \\
a_0 {S_A}_1 + a_1 {S_A}_0 + a_2 {S_A}_3 - a_3 {S_A}_2 \equiv {P_B}_0 a_1 + {P_B}_1 a_0 + {P_B}_2 a_3 - {P_B}_3 a_2 \mod p \\
a_0 {S_A}_2 - a_1 {S_A}_3 + a_2 {S_A}_0 + a_3 {S_A}_1 \equiv {P_B}_0 a_2 - {P_B}_1 a_3 + {P_B}_2 a_0 + {P_B}_3 a_1 \mod p \\
a_0 {S_A}_3 + a_1 {S_A}_2 - a_2 {S_A}_1 + a_3 {S_A}_0 \equiv {P_B}_0 a_3 + {P_B}_1 a_2 - {P_B}_2 a_1 + {P_B}_3 a_0 \mod p \\
\end{aligned}
\right.
$$
が成り立ちます。
これを I.groebner_basis() に投げると、$[f_0(a_2, a_3), f_1(a_2, a_3), a_2, a_3]$が返されます。
自由度が大きくてまだ値を決定できないので、もう少しがんばります。
制約の追加
自由度を減らしたいので、制約の式を追加したくなります。
いろいろ調べていると、似たような問題を解く際に制約を追加する面白いテク2が紹介されていたのでそれを使いました。
具体的には、$A P_A = P_A A$という制約が追加できます。四元数同士の積は非可換ですが、べき乗の演算をあえて分解すると
$$
AP_A = {P_A}^{p_A} P_A = P_A {P_A}^{p_A} = P_A A
$$
であることから先ほどの関係が成り立ちます。これを要素ごとの関係に書き直すと以下の式になります。
$$
\begin{aligned}
a_0 {P_A}_3 + a_1 {P_A}_2 - a_2 {P_A}_1 + a_3 {P_A}_0 \equiv {P_A}_0 a_3 + {P_A}_1 a_2 - {P_A}_2 a_1 + {P_A}_3 a_0 \mod p \\
\end{aligned}
$$
先ほどの4つの式とあわせて5本の式をまとめて I.groebner_basis() に投げると、$[f_0(a_3), f_1(a_3), f_2(a_3), a_3]$ のような基底が返されます。
$b_0, b_1, b_2, b_3$についても同様にして$[g_0(b_3), g_1(b_3), g_2(b_3), b_3]$ のようになります。
ここからさらに$a_3, b_3$を決定したくなりますが、$a_3, b_3$に適当な値を入れて実験してみると、実は$a_3 \neq 0, b_3 \neq 0$であれば$K_A$は同じ値になります。
$K_A = A^{-1}B^{-1}AB$の各要素に着目して分子分母をそれぞれ${a_3}^2{b_3}^2$で割れば、$K_A$の各要素は$\frac{a_0}{a_3}, \frac{a_1}{a_3}, \frac{a_2}{a_3}, \frac{b_0}{b_3}, \frac{b_1}{b_3}, \frac{b_2}{b_3}$で表現できます。(実験スクリプトと結果を参照)
これらの比はすでに求めたので$K_A$の値が定まります。
- 実験スクリプト
1def mat_to_quat(M):
2 a0 = M[0,0]
3 a1 = M[0,1]
4 a2 = M[0,2]
5 a3 = M[0,3]
6 return a0 + a1*i + a2*j + a3*k
7
8Q.<i,j,k> = QuaternionAlgebra(SR, -1, -1)
9a0, a1, a2, a3 = var('a0 a1 a2 a3')
10b0, b1, b2, b3 = var('b0 b1 b2 b3')
11
12assume(a0, a1, a2, a3, b0, b1, b2, b3, 'real')
13assume(a0, a1, a2, a3, b0, b1, b2, b3, 'integer')
14
15a = a0 + a1*i + a2*j + a3*k
16b = b0 + b1*i + b2*j + b3*k
17
18A = a.matrix()
19B = b.matrix()
20
21K_A = A.inverse()*B.inverse()*A*B
22K_A = K_A.simplify_full()
23K_A = mat_to_quat(K_A)
24
25for ii in range(4):
26 print(K_A[ii].numerator() * a3^(-2) * b3^(-2))
27 print(K_A[ii].denominator() * a3^(-2) * b3^(-2))
- 結果
1# 1
2# numerator
3a0^2/a3^2 - a1^2/a3^2 - a2^2/a3^2 + a0^2*b0^2/(a3^2*b3^2) + a1^2*b0^2/(a3^2*b3^2) + a2^2*b0^2/(a3^2*b3^2) + b0^2/b3^2 + a0^2*b1^2/(a3^2*b3^2) + a1^2*b1^2/(a3^2*b3^2) - a2^2*b1^2/(a3^2*b3^2) - b1^2/b3^2 + 4*a1*a2*b1*b2/(a3^2*b3^2) + a0^2*b2^2/(a3^2*b3^2) - a1^2*b2^2/(a3^2*b3^2) + a2^2*b2^2/(a3^2*b3^2) - b2^2/b3^2 + 4*a1*b1/(a3*b3) + 4*a2*b2/(a3*b3) + 1
4# denominator
5a0^2/a3^2 + a1^2/a3^2 + a2^2/a3^2 + a0^2*b0^2/(a3^2*b3^2) + a1^2*b0^2/(a3^2*b3^2) + a2^2*b0^2/(a3^2*b3^2) + b0^2/b3^2 + a0^2*b1^2/(a3^2*b3^2) + a1^2*b1^2/(a3^2*b3^2) + a2^2*b1^2/(a3^2*b3^2) + b1^2/b3^2 + a0^2*b2^2/(a3^2*b3^2) + a1^2*b2^2/(a3^2*b3^2) + a2^2*b2^2/(a3^2*b3^2) + b2^2/b3^2 + 1
6
7# i
8# numerator
9-2*a0*a1/a3^2 - 2*a2/a3 + 2*a2^2*b0*b1/(a3^2*b3^2) + 2*b0*b1/b3^2 - 2*a1*a2*b0*b2/(a3^2*b3^2) - 2*a0*b0*b2/(a3*b3^2) + 2*a0*a2*b1*b2/(a3^2*b3^2) + 2*a1*b1*b2/(a3*b3^2) - 2*a0*a1*b2^2/(a3^2*b3^2) + 2*a2*b2^2/(a3*b3^2) + 2*a0*a2*b0/(a3^2*b3) - 2*a1*b0/(a3*b3) - 2*a1*a2*b1/(a3^2*b3) + 2*a0*b1/(a3*b3) - 2*a2^2*b2/(a3^2*b3) + 2*b2/b3
10# denominator
11a0^2/a3^2 + a1^2/a3^2 + a2^2/a3^2 + a0^2*b0^2/(a3^2*b3^2) + a1^2*b0^2/(a3^2*b3^2) + a2^2*b0^2/(a3^2*b3^2) + b0^2/b3^2 + a0^2*b1^2/(a3^2*b3^2) + a1^2*b1^2/(a3^2*b3^2) + a2^2*b1^2/(a3^2*b3^2) + b1^2/b3^2 + a0^2*b2^2/(a3^2*b3^2) + a1^2*b2^2/(a3^2*b3^2) + a2^2*b2^2/(a3^2*b3^2) + b2^2/b3^2 + 1
12
13# j
14# numerator
15-2*a0*a2/a3^2 + 2*a1/a3 - 2*a1*a2*b0*b1/(a3^2*b3^2) + 2*a0*b0*b1/(a3*b3^2) - 2*a0*a2*b1^2/(a3^2*b3^2) - 2*a1*b1^2/(a3*b3^2) + 2*a1^2*b0*b2/(a3^2*b3^2) + 2*b0*b2/b3^2 + 2*a0*a1*b1*b2/(a3^2*b3^2) - 2*a2*b1*b2/(a3*b3^2) - 2*a0*a1*b0/(a3^2*b3) - 2*a2*b0/(a3*b3) + 2*a1^2*b1/(a3^2*b3) - 2*b1/b3 + 2*a1*a2*b2/(a3^2*b3) + 2*a0*b2/(a3*b3)
16# denominator
17a0^2/a3^2 + a1^2/a3^2 + a2^2/a3^2 + a0^2*b0^2/(a3^2*b3^2) + a1^2*b0^2/(a3^2*b3^2) + a2^2*b0^2/(a3^2*b3^2) + b0^2/b3^2 + a0^2*b1^2/(a3^2*b3^2) + a1^2*b1^2/(a3^2*b3^2) + a2^2*b1^2/(a3^2*b3^2) + b1^2/b3^2 + a0^2*b2^2/(a3^2*b3^2) + a1^2*b2^2/(a3^2*b3^2) + a2^2*b2^2/(a3^2*b3^2) + b2^2/b3^2 + 1
18
19# k
20# numerator
21-2*a0*a2*b0*b1/(a3^2*b3^2) - 2*a1*b0*b1/(a3*b3^2) + 2*a1*a2*b1^2/(a3^2*b3^2) - 2*a0*b1^2/(a3*b3^2) + 2*a0*a1*b0*b2/(a3^2*b3^2) - 2*a2*b0*b2/(a3*b3^2) - 2*a1^2*b1*b2/(a3^2*b3^2) + 2*a2^2*b1*b2/(a3^2*b3^2) - 2*a1*a2*b2^2/(a3^2*b3^2) - 2*a0*b2^2/(a3*b3^2) + 2*a1^2*b0/(a3^2*b3) + 2*a2^2*b0/(a3^2*b3) + 2*a0*a1*b1/(a3^2*b3) + 2*a2*b1/(a3*b3) + 2*a0*a2*b2/(a3^2*b3) - 2*a1*b2/(a3*b3)
22# denominator
23a0^2/a3^2 + a1^2/a3^2 + a2^2/a3^2 + a0^2*b0^2/(a3^2*b3^2) + a1^2*b0^2/(a3^2*b3^2) + a2^2*b0^2/(a3^2*b3^2) + b0^2/b3^2 + a0^2*b1^2/(a3^2*b3^2) + a1^2*b1^2/(a3^2*b3^2) + a2^2*b1^2/(a3^2*b3^2) + b1^2/b3^2 + a0^2*b2^2/(a3^2*b3^2) + a1^2*b2^2/(a3^2*b3^2) + a2^2*b2^2/(a3^2*b3^2) + b2^2/b3^2 + 1
最終的なsolverは以下の通りです。
1from hashlib import sha256
2from secrets import randbelow
3from Crypto.Util.number import long_to_bytes
4from Crypto.Cipher import AES
5
6p = 0xC20C8EDB31BFFA707DC377C2A22BE4492D1F8399FFFD388051EC5E4B68B4598B
7order = p**2 - 1
8Q = QuaternionAlgebra(Zmod(p), -1, -1)
9i, j, k = Q.gens()
10
11pub_A = (
12 71415146914196662946266805639224515745292845736145778437699059682221311130458
13 + 62701913347890051538907814870965077916111721435130899071333272292377551546304 * i
14 + 60374783698776725786512193196748274323404201992828981498782975421278885827246 * j
15 + 60410367194208847852312272987063897634106232443697621355781061985831882747944 * k
16)
17
18pub_B = (
19 57454549555647442495706111545554537469908616677114191664810647665039190180615
20 + 8463288093684346104394651092611097313600237307653573145032139257020916133199 * i
21 + 38959331790836590587805534615513493167925052251948090437650728000899924590900 * j
22 + 62208987621778633113508589266272290155044608391260407785963749700479202930623 * k
23)
24
25share_A = 57454549555647442495706111545554537469908616677114191664810647665039190180615 + 29676674584636622512615278554619783662266316745243745754583020553342447549066*i + 13738434026348321269316223833101191512670504554293346482813342673413295266974*j + 23943604179074440949144139144245518129342426692024663551007842394683089455212*k
26share_B = 71415146914196662946266805639224515745292845736145778437699059682221311130458 + 65071948237600563018819399020079518439338035815171479183947570522190990857574*i + 52272525531848677372993318721896591307730532037121185733047803928301284987593*j + 68406537373378314867132842983264676792172029888604057526079501977599097329576*k
27
28PA_0, PA_1, PA_2, PA_3 = pub_A.coefficient_tuple()
29PB_0, PB_1, PB_2, PB_3 = pub_B.coefficient_tuple()
30SA_0, SA_1, SA_2, SA_3 = share_A.coefficient_tuple()
31SB_0, SB_1, SB_2, SB_3 = share_B.coefficient_tuple()
32
33# A
34PR.<a_0,a_1,a_2,a_3> = PolynomialRing(Zmod(p))
35
36fs = [0 for _ in range(5)]
37fs[0] += (a_0*SA_0 - a_1*SA_1 - a_2*SA_2 - a_3*SA_3)
38fs[0] -= (PB_0*a_0 - PB_1*a_1 - PB_2*a_2 - PB_3*a_3)
39fs[1] += (a_0*SA_1 + a_1*SA_0 + a_2*SA_3 - a_3*SA_2)
40fs[1] -= (PB_0*a_1 + PB_1*a_0 + PB_2*a_3 - PB_3*a_2)
41fs[2] += (a_0*SA_2 - a_1*SA_3 + a_2*SA_0 + a_3*SA_1)
42fs[2] -= (PB_0*a_2 - PB_1*a_3 + PB_2*a_0 + PB_3*a_1)
43fs[3] += (a_0*SA_3 + a_1*SA_2 - a_2*SA_1 + a_3*SA_0)
44fs[3] -= (PB_0*a_3 + PB_1*a_2 - PB_2*a_1 + PB_3*a_0)
45fs[4] += (a_0*PA_3 + a_1*PA_2 - a_2*PA_1 + a_3*PA_0)
46fs[4] -= (PA_0*a_3 + PA_1*a_2 - PA_2*a_1 + PA_3*a_0)
47
48I = Ideal(fs)
49basis = I.groebner_basis()
50a = [0, 0, 0, 1]
51for ii, ba in enumerate(basis):
52 _, x = ba.coefficients()
53 a[ii] = -a[3]*x
54A = a[0] + a[1]*i + a[2]*j + a[3]*k
55print(A)
56
57
58# B
59PR.<b_0,b_1,b_2,b_3> = PolynomialRing(Zmod(p))
60
61fs = [0 for _ in range(5)]
62fs[0] += (b_0*SB_0 - b_1*SB_1 - b_2*SB_2 - b_3*SB_3)
63fs[0] -= (PA_0*b_0 - PA_1*b_1 - PA_2*b_2 - PA_3*b_3)
64fs[1] += (b_0*SB_1 + b_1*SB_0 + b_2*SB_3 - b_3*SB_2)
65fs[1] -= (PA_0*b_1 + PA_1*b_0 + PA_2*b_3 - PA_3*b_2)
66fs[2] += (b_0*SB_2 - b_1*SB_3 + b_2*SB_0 + b_3*SB_1)
67fs[2] -= (PA_0*b_2 - PA_1*b_3 + PA_2*b_0 + PA_3*b_1)
68fs[3] += (b_0*SB_3 + b_1*SB_2 - b_2*SB_1 + b_3*SB_0)
69fs[3] -= (PA_0*b_3 + PA_1*b_2 - PA_2*b_1 + PA_3*b_0)
70fs[4] += (b_0*PB_3 + b_1*PB_2 - b_2*PB_1 + b_3*PB_0)
71fs[4] -= (PB_0*b_3 + PB_1*b_2 - PB_2*b_1 + PB_3*b_0)
72
73I = Ideal(fs)
74basis = I.groebner_basis()
75b = [0, 0, 0, 1]
76print(basis)
77for ii, ba in enumerate(basis):
78 _, x = ba.coefficients()
79 b[ii] = -b[3]*x
80B = b[0] + b[1]*i + b[2]*j + b[3]*k
81print(B)
82
83def hash_Q(x):
84 return sha256(
85 long_to_bytes(int(x[0]))
86 + long_to_bytes(int(x[1]))
87 + long_to_bytes(int(x[2]))
88 + long_to_bytes(int(x[3]))
89 ).digest()
90
91K_A = A**-1 * B**-1 * A * B
92key = hash_Q(K_A)
93nonce = '6ced0927695bc45e'
94enc = '6a59a899fed260513cd4ad037bb3d8681ae47e4d5c13139aebde981c01f93aac63d6a39c04e4dfa3fd05fa41c1bcda8b39c660aff5673458d5324eac738d1bd0a255'
95cipher = AES.new(key, mode=AES.MODE_CTR, nonce=bytes.fromhex(nonce))
96flag = cipher.decrypt(bytes.fromhex(enc))
97print(flag)
SECCON{Is this a secure cryptosystem if quaternions are not used?}
[Crypto] Paillier 4.0
当日はガチャガチャして n だけ取得した。
$\ell \in \mathbb{Z}$ として、$g = 1+\elln$ とする。 $r \in \mathbb{Z}^{*}_{n^2}$ として、$c = g^mr^n \mod n^2$ となる。 ここで、$c = c_0 + c_1 i + c_2 j + c_3 k$とすると、 $$
[Crypto] muck-a-mac
年末年始でupsolveします🦅
[Crypto] v_v_m_m_v_m_m
年末年始でupsolveします🍆
おわりに
実はオンサイトでCTFするのは初めてでしたが、家でカタカタするのとはまた違う楽しさがありました。運営の皆さんありがとうございました。 最後はsouthballの面々で焼肉を食べに行きました。 賞金で食べる焼肉は最高😋
-
元々予選はsouthball氏1人で突破していたのですが、決勝に1人はつらいとのことでWani HackaseからCaffeine, Ciffelia, Laikaの3名が参戦しました。southball氏もWani Hackaseにjoinしたので完全に🐊です。 「実質 Wani Hackase です」とはそういうことです。 ↩︎
-
XornetさんのWriteup: Crew CTF 2022 - matdlp ↩︎