【crypto】IERAE CTF 2025 公式 Writeup
本記事では2025年6月21日～22日に開催された、IERAE CTF 2025のcrypto問題の解法を解説します。
- Baby MSD (warmup)
- MSD (easy)
- trunc (medium)
- Cipher Brothers (medium)
- Secure Bike (hard)
- Secure Bike Revenge (hard)
- Cubic Math (hard)
他のジャンルの解説は以下の記事をご覧ください:
Baby MSD (warmup)
作問者: hugeh0ge
正解チーム数: 149
概要
特殊な数当てゲームです。
具体的には、サーバーは秘密の数 secret を生成し、ユーザーは法となる整数Mを入力します。サーバーはsecret % Mの最上位桁の数字を記録します。
これを2000回繰り返した後、1から9のうち、最も記録された数字が何かを、ユーザーは答える必要があります。
生成される数や入力できる数には制約があるため、詳しくは以下の実際のコードを参照してください。
def stage():
digit_counts = [0 for i in range(10)]
for i in range(2000):
secret = randint(10 ** 60, 10 ** 100)
M = int(input("Enter mod: "))
if M < 10 ** 30:
print("Too small!")
exit(1)
msd = str(secret % M)[0]
digit_counts[int(msd)] += 1
choice = int(input("Which number (1~9) appeared the most? : "))
for i in range(10):
if digit_counts[choice] < digit_counts[i]:
print("Failed :(")
exit(1)
print("OK")
def main():
for i in range(100):
print("==== Stage {} ====\n".format(i+1))
stage()
print("You did it!")
with open("flag.txt", "r") as f:
print(f.read())解法
結論から言うと、Mとして、2 * 10 ** 30を設定するとよいです。
この時、Mで割った余りとしてありえる数をすべて考えた時、最上位の桁が1であるものは、以下の合計です。
10 ** 30から2 * 10 ** 30 - 1の10 ** 30個10 ** 29から2 * 10 ** 29 - 1の10 ** 29個- …
- 10 から 19 の 10個
- 1
つまり、111...1 （1が31個並んだ数）個あります。
これに対して、余りとしてありえる数すべての総数は、2 * 10 ** 30 であるため、半数以上の余りにおいて、最上位の桁は1となります。
secretは十分大きな範囲から、一様ランダムに選ばれているため、その余りも一様ランダムに決定されると考えてよく、50%以上の確率で最上位の桁は1となると分かります。
なお、これをサーバーに送信する際、典型的にはTCP通信のプログラムを書くことになりますが、サーバー出力を逐次的に受信するべきではありません。
参加者の方の中には、pwntoolsなどのライブラリによって、以下のようなプログラムを書いた人が見られました。
from pwn import *
p = remote('localhost', 12343)
for i in range(100):
print(i)
for j in range(2000):
p.recvuntil('Enter mod: ')
p.sendline(str(2 * 10 ** 30))
p.recvuntil('Which number (1~9) appeared the most? : ')
p.sendline('1')
print(p.recv(1024))
print(p.recv(1024))
print(p.recv(1024))実行している内容自体はまったく間違っていませんが、20万回出力を受信するため、ローカルホストでも実行時間が非常にかかってしまいます。実際のサーバーとの通信では、これに更にインターネットを経由したデータの送受信がかかってくるため、ほぼ間違いなく5分間のタイムアウトに引っかかってしまいます。
そのため、2重ループ内部のrecvuntilを削除し、ステージごとでまとめて出力を受け取ったり、そもそも一切出力を受け取らず、入力だけを送りきった後ですべての出力を取り出したりといった対処が必要です。このうち、もっとも簡単な方法は、以下のようにnetcatへのパイプをうまく使うものでしょう。
$ cat solve.py
for i in range(100):
for j in range(2000):
print(2 * 10 ** 30)
print(1)
$ python solve.py | nc localhost 12343
==== Stage 1 ====
Enter mod: Enter mod: ...
...
You did it!
IERAE{dummy flag for test}MSD (easy)
作問者: hugeh0ge
正解チーム数: 108
概要
Baby MSD と同様に、サーバーは 10 ** 60から10 ** 100 までの範囲から一様ランダムに選んだ秘密数 secret を生成し、M (≥10 ** 30) を 2000 回入力させ、その都度 secret % M の最上位桁を記録します。最後に最も頻出した桁を当てるStageを 100 回連続でクリアするとフラグを獲得できます。
from sys import exit
from random import randint
def stage():
digit_counts = [0 for i in range(10)]
secret = randint(10 ** 60, 10 ** 100)
for i in range(2000):
M = int(input("Enter mod: "))
if M < 10 ** 30:
print("Too small!")
exit(1)
msd = str(secret % M)[0]
digit_counts[int(msd)] += 1
choice = int(input("Which number (1~9) appeared the most? : "))
for i in range(10):
if digit_counts[choice] < digit_counts[i]:
print("Failed :(")
exit(1)
print("OK")
def main():
for i in range(100):
print("==== Stage {} ====\n".format(i+1))
stage()
print("You did it!")
with open("flag.txt", "r") as f:
print(f.read())
if __name__ == '__main__':
main()解法
Benford の法則に従うと、多くの自然数集合における最上位桁は 1 が最も高い確率で出現します。したがって、毎回異なる大きな M を送って余りの分布を自然数集合に近づけ、最終的に 1 を回答することで高確率に成功します。
import socket
import random
import sys
HOST, PORT = "localhost", 18374
LOW, HIGH = 10**30, 10**31
CHUNK = 4096
def build_stage_payload() -> bytes:
mods = [str(random.randrange(LOW, HIGH)) for _ in range(2000)]
return ("\n".join(mods) + "\n1\n").encode()
def recv_until_verdict(sock: socket.socket) -> tuple[str, bytes]:
buf = bytearray()
while True:
chunk = sock.recv(CHUNK)
buf.extend(chunk)
if b"OK\n" in buf:
idx = buf.find(b"OK\n") + 3
return "OK", bytes(buf[idx:])
def main() -> None:
sock = socket.create_connection((HOST, PORT))
sock.setsockopt(socket.IPPROTO_TCP, socket.TCP_NODELAY, 1)
try:
trailing = b""
for stage in range(1, 101):
sock.sendall(build_stage_payload())
verdict, trailing = recv_until_verdict(sock)
print(f"[Stage {stage:3d}] {verdict}")
if trailing:
sys.stdout.buffer.write(trailing)
while (chunk := sock.recv(CHUNK)):
sys.stdout.buffer.write(chunk)
finally:
sock.close()
if __name__ == "__main__":
main()高速化のため以下の方式を採用しています
- build_stage_payload
1Stage分のペイロード（M 2000個分）を生成し、一括送信 - recv_until_verdict
sock.recv(4096)で チャンクを読み取り、'OK'を検出したら即returnする
trunc (medium)
作問者: gyoza_beer
正解チーム数: 41
概要
本問題はTruncated LWEによる暗号化を行います。
格子ベースの暗号方式では、公開鍵として $\mathbb Z/q\mathbb Z$ 上の大きな行列 $A$ を用いますが、この行列のサイズは数百～数千にもなり鍵配布の負担が大きくなります。そこで、各要素の下位 $c$ ビットを落とすことで、鍵サイズを $\tfrac{c}{\log_{2}q}$ 縮小できます。
$$\mathrm{Trunc}_{c}(A_{i,j}) = A_{i,j} - (A_{i,j}\bmod{2^{c}})$$
Truncated LWEでの公開鍵生成
- ランダム行列 $U \in \mathbb Z_q^{m\times n}$ を生成し、下位 $c$ ビットを切り捨てて公開鍵 $A = \mathrm{Trunc}_c(U)$ を作成します。
- 秘密鍵 $s$ と誤差ベクトル $e$ を生成し、$A$ および以下で定まるベクトル $b$ を公開します。 $$
b = A\,s + e \pmod q
$$
from sage.all import *
import secrets
q = 2**20
n = 512
m = 4 * n
c = 8
with open("flag.txt", "rb") as f:
FLAG = f.read().strip()
def trunc_matrix(M, c):
F = M.base_ring()
modulus = 2**c
return matrix(F, M.nrows(), M.ncols(), [F(Integer(x) - (Integer(x) % modulus)) for x in M.list()])
def keygen():
U = random_matrix(Integers(q), m, n)
A = trunc_matrix(U, c)
s = vector(Zmod(q), [secrets.randbelow(q) for _ in range(n)])
e = vector(Zmod(q), [ZZ(secrets.randbelow(400)) for _ in range(m)])
return A, A * s + e
def encrypt_bit(x, A, b):
S = [i for i in range(A.nrows()) if secrets.randbits(1)]
if len(S) == 0:
S = [secrets.randbelow(A.nrows())]
a_sum = sum([A[i] for i in S])
b_sum = sum([b[i] for i in S])
encoded_bit = (x * (q // 2)) % q
return (a_sum, (encoded_bit + b_sum) % q)
def encrypt_message(message, A, b):
bits = []
for byte in message:
for i in range(8):
bits.append((byte >> i) & 1)
ciphertext = [encrypt_bit(bit, A, b) for bit in bits]
return ciphertext
def main():
A, b = keygen()
flag_ciphertext = encrypt_message(FLAG, A, b)
print("q =", q)
print("n =", n)
print("m =", m)
print("c =", c)
print("A =", [list(A[i]) for i in range(A.nrows())])
print("b =", list(b))
print("flag_ciphertext =", flag_ciphertext)
if __name__ == "__main__":
main()解法
今回の問題では $q = 2^{20}$ となっています。
この時、$A$ の各成分は $2^c$ の倍数なので、$b$ の各成分 $b_i$ を $2^c$ で割った余りを考えることで誤差 $e_i$ の値を一意に特定できる場合があります。
- $0 \le e_i \le 143$ , $256 \le e_i < 400$ のとき $$
e_i \;=\; b_i \bmod 2^c
\quad\text{or}\quad
e_i \;=\; (b_i \bmod 2^c) + 2^c
$$ - $144 \le e_i < 256$ のとき $$
e_i \;=\; b_i \bmod 2^c
$$
このようにして「一意に定まる」$e_i$ を十分に集めることで、秘密鍵 $s$ を復元できます。
from sage.all import *
error_bound = 400
def solve_extract_error(A, b, q, c):
modulus = 2**c
reduced_modulus = q // modulus
buff = error_bound - modulus
filtered_rows = []
filtered_b = []
for i in range(m):
b_i = int(b[i])
b_i_mod = b_i % modulus
if buff < b_i_mod < modulus:
A_row_mod = [(int(A[i, j]) // modulus) % reduced_modulus for j in range(A.ncols())]
b_i_corr = (((b_i - b_i_mod) % q) // modulus) % reduced_modulus
filtered_rows.append(A_row_mod)
filtered_b.append(b_i_corr)
X_good = matrix(Integers(reduced_modulus), filtered_rows)
B_good = vector(Integers(reduced_modulus), filtered_b)
s_candidate = X_good.solve_right(B_good)
return vector(Zmod(q), [int(s_candidate[i]) for i in range(len(s_candidate))])
def decrypt(ciphertext, s):
bits = []
center = (q + 1) // 2
for ct in ciphertext:
a, b_val = ct
a = vector(ZZ, list(a))
diff = int((b_val - a.dot_product(s)) % q)
if abs(diff - center) < min(diff, q - diff):
bits.append(1)
else:
bits.append(0)
plaintext_bytes = []
for i in range(0, len(bits), 8):
byte = sum(bits[i+j] << j for j in range(8))
plaintext_bytes.append(byte)
return bytes(plaintext_bytes)
def main():
with open("output.txt", "r") as f:
data = f.read()
exec(data, globals())
flag_ciphertext = globals().get("flag_ciphertext")
A_data = globals().get("A")
b_data = globals().get("b")
A = matrix(Integers(q), A_data)
b = vector(Integers(q), b_data)
s_extract = solve_extract_error(A, b, q, c)
decrypted_flag_extract = decrypt(flag_ciphertext, s_extract)
print("Decrypted flag:", decrypted_flag_extract)
if __name__ == "__main__":
main()Cipher Brothers (medium)
作問者: mitsu
正解チーム数: 24
最終更新: 2025/06/21 22:29（素数生成を高速化）
概要
server.pyを確認すると、ElGamal暗号による暗号文を出力していることがわかります。また暗号化される平文は、フラグ % 入力した数値であることもわかります。
# server.py
def key_generation(nbits=256):
while True:
q = getPrime(nbits - 1)
p = 2 * q + 1
if isPrime(p):
break
g = primitive_root(p)
x = getRandomRange(0, p)
h = pow(g, x, p)
return (p, g, h)
def enc(m, p, g, h):
r = getRandomRange(0, p)
c1 = pow(g, r, p)
c2 = (m * pow(h, r, p)) % p
return (c1, c2)
p, g, h = key_generation()
m = bytes_to_long(FLAG)
red = int(input())
c1, c2 = enc(m % red, p, g, h)
print("p:", p)
print("g:", g)
print("h:", h)
print("c1:", c1)
print("c2:", c2)解法
ElGamal暗号は、暗号文から元の平文がpでの平方剰余か否かを判別することができます。
まず$\left(\frac{h}{p}\right) = 1$ の場合を考えます。
このとき、$\left(\frac{h^r}{p}\right) = 1$ です。そのため$\left(\frac{c_2}{p}\right) = \left(\frac{m}{p}\right)$となります。
次に $\left(\frac{h}{p}\right) = -1$ の場合を考えます。
$g$ が原始根であることから、$\left(\frac{c_1}{p}\right) = 1$ のとき $r$ が偶数であることがわかります。よってこのとき $\left(\frac{h^r}{p}\right) = 1$となり、$\left(\frac{c_2}{p}\right) = \left(\frac{m}{p}\right)$となります。
$\left( \frac{c_1}{p}\right) = -1$のとき、$r$は奇数です。そのため$\left(\frac{h^r}{p}\right) = -1$となり、$\left(\frac{m}{p}\right) = -\left(\frac{c_2}{p}\right)$
この手法を用いることで、問題サーバに $r$ を送信した時の暗号文から $m \bmod r$ が $p$ において平方剰余か否かを判定することができます。
$r$ をうまくとることで、平方剰余か否かの情報から $m \bmod r$ を復元することができるので、最終的に $m$ を復元することができます。
複数回接続し試行を行うことでソルバを回す時間が長くなることが予想されます。そのためフラグを計算する途中経過を確認できることや、途中でソルバが止まっても再開できるよう、想定解法は $m$ の各ビットを特定するものとなっています。
そのため $r$ を $2^k$ の形でとって $m$ を復元していきます。
$m$ の復元方法ですが、例えば今判明している $m$ が 0b01 だとします。サーバが暗号化に使用した $p$ によっては、0b001が平方剰余かつ0b101が平方剰余とならない場合があります。 そのような $p$ であれば、$r = 2^3$ として $\left(\frac{m \bmod r}{p}\right)$を計算することで $m \bmod r$ が 0b001 なのか 0b101 なのか判別することができます。
この試行を $r$ を大きくしながら行うことで、最終的に $m$ が得られます。
以下のソルバを十数分回すことによりフラグが得られます。
# solve.py
from ptrlib import *
from Crypto.Util.number import *
import math
def kronecker(x, p):
if math.gcd(x, p) != 1:
return 0
if pow(x, (p - 1) // 2, p) == 1:
return 1
return -1
def app(red):
# s = Process(["python3", "server.py"])
s = Socket("localhost", 12349)
s.sendline(str(red).encode("utf-8"))
p = eval(s.recvline().split()[1])
g = eval(s.recvline().split()[1])
h = eval(s.recvline().split()[1])
c1 = eval(s.recvline().split()[1])
c2 = eval(s.recvline().split()[1])
s.interactive()
s.close()
return p, g, h, c1, c2
def is_m_qr(c1, c2, p, g, h):
if kronecker(h, p) == 1:
if kronecker(c2, p) == 1:
return 1
else:
return -1
if kronecker(c1, p) == 1:
# r is even
# -> h^r is qr
if kronecker(c2, p) == 1:
return 1
else:
return -1
# r is odd
# -> h^r is nqr
if kronecker(c2, p) == 1:
return -1
else:
return 1
def enc(m, p, g, h):
r = randint(0, p - 1)
c1 = pow(g, r, p)
c2 = (m * pow(h, r, p)) % p
return (c1, c2)
red = 256
m = b'01111101'
while True:
red <<= 1
while True:
p, g, h, c1, c2 = app(red)
k1 = kronecker(int(b'0' + m, 2), p)
k2 = kronecker(int(b'1' + m, 2), p)
if k1 != k2:
break
is_qr = is_m_qr(c1, c2, p, g, h)
if k1 == is_qr:
m = b'0' + m
else:
m = b'1' + m
s = long_to_bytes(int(m, 2))
print(m)
print(s)
if b"IERAE{" in s:
breakSecure Bike (hard)
作問者: chocorusk
正解チーム数: 8
概要
量子耐性を持つ鍵カプセル化方式（Key Encapsulation Mechanism、略してKEM）の一つであるBIKE (Bit Flipping Key Encapsulation) に関する問題です。一般にKEMとは、鍵を安全に共有するための仕組みであり、以下の3つのアルゴリズムから成ります。
- 鍵生成: 公開鍵と秘密鍵の組を生成する
- 鍵カプセル化: 公開鍵を入力に取り、共有鍵と対応する暗号文の組を出力する。秘密鍵なしに暗号文から共有鍵を求めることは困難である
- デカプセル化: 秘密鍵および暗号文を入力に取り、共有鍵を出力する
本問題では、BIKEのWebサイトで公開されているBIKEのリファレンス実装にパッチを当てたものが使われています。最初にBIKEの鍵生成が実行され、公開鍵が与えられます。次に、鍵カプセル化が実行され、結果の暗号文および「ヒント」が与えられます。その後、好きな暗号文を入力して、それをデカプセル化した共有鍵を用いてフラグを暗号化したもの（デカプセル化に失敗した場合は decapsulation error）を取得することが何回でもできます。
import os
import random
from ctypes import cdll, c_buffer
from Crypto.Cipher import AES
with open("flag.txt", "rb") as f:
FLAG = f.read()
libbike = cdll.LoadLibrary('./libbike.so')
libbike.randombytes_init(os.urandom(48), None, 256)
n = 12323
d = 71
t = 134
R_BYTES = (n+7)//8
M_BYTES = 256//8
SS_BYTES = 256//8
N0 = 2
pk_size = R_BYTES
sk_size = R_BYTES * N0 + M_BYTES + M_BYTES
ct_size = R_BYTES + M_BYTES
ss_size = SS_BYTES
e_size = R_BYTES * N0
pk = c_buffer(pk_size)
sk = c_buffer(sk_size)
libbike.crypto_kem_keypair(pk, sk)
print("public key:", bytes(pk).hex())
ct = c_buffer(ct_size)
k_enc = c_buffer(ss_size)
e0 = c_buffer(R_BYTES)
libbike.crypto_kem_enc(ct, k_enc, e0, pk)
print("ciphertext:", bytes(ct).hex())
e0_bin = "".join('{:08b}'.format(v)[::-1] for v in bytes(e0))[:n]
hint = [i for i in range(n) if e0_bin[i] == "1"] + random.sample([i for i in range(n) if e0_bin[i] == "0"], t - e0_bin.count("1"))
random.shuffle(hint)
e0_hint = "".join([e0_bin[i] for i in hint])
hint = hint[:16] + [(hint[i] + int(e0_hint[i-16:i], 2)) % n for i in range(16, len(hint))]
print("hint:", hint)
while True:
ct_input = bytes.fromhex(input("ciphertext: "))
assert len(ct_input) == ct_size
k_dec = c_buffer(ss_size)
res = libbike.crypto_kem_dec(k_dec, ct_input, sk)
if res != 0:
print("decapsulation error")
continue
ss = bytes(k_dec)
cipher = AES.new(key=ss, mode=AES.MODE_CTR)
encrypted_flag = cipher.encrypt(FLAG)
print("encrypted flag:", (cipher.nonce + encrypted_flag).hex())解法
出題ミスにより、BIKEの性質を全く必要としない自明な解法が存在しました。
まず、与えられる公開鍵を用いて鍵カプセル化をローカルで実行します。結果の暗号文を $c$、共有鍵を $K$ とします。サーバーから与えられる暗号文およびヒントは無視します。そして、$c$ をサーバーに入力し、フラグの暗号文を取得します。共有鍵 $K$ を用いればフラグを復号できます。
Revenge問のAttachmentを展開するためのフラグ: IERAE{ff1fc8667f8e9d3f20a21ca07f61ca0abbee3b7e836c63995f6a70f5985f7c93}
Secure Bike Revenge (hard)
作問者: chocorusk
正解チーム数: 2
概要
本問題を理解するにはBIKEのアルゴリズムについて把握する必要があるため、最初にその概要を説明します。
BIKEは符号ベースの耐量子計算機暗号の一つです。BIKEの鍵生成、鍵カプセル化、デカプセル化のアルゴリズムは概ね以下の通りです。ここで、$n$, $d$, $t$ はパラメータで、本問題では $n=12323$, $d=71$, $t=134$（NISTレベル1相当のパラメータ）です。また、$R=\mathbb{F}_{2}[X]/(X^n-1)$ とします。
鍵生成
- $h_{0}, h_{1}\in R$ を、係数が1の項がそれぞれちょうど $d$ 個であるようにランダムに選ぶ。秘密鍵は $(h_{0}, h_{1})$ である。
- $h=h_{1}h_{0}^{-1}$ を計算する。公開鍵は $h$ である。
- 256bitの文字列 $m$ をランダムに選ぶ。
- $(e_{0}, e_{1})=H(m)$ を計算する。ここで、$H$ はハッシュ関数であって、$e_{0}, e_{1}\in R$ の係数が1の項が合わせて $t$ 個であるようなものである。
- $c_{0}=e_{0}+e_{1}h$, $c_{1}=m\oplus L(e_{0}, e_{1})$ を計算する。ここで $\oplus$ はXORを表し、$L$ はハッシュ関数である。暗号文は $c=(c_{0}, c_{1})$ である。
- $K=K(m, c)$ を計算する。ここで $K(m, c)$ はハッシュ関数である。共有鍵は $K$ である。
- $c_{0}h_{0}$ にQC-MDPC符号の復号アルゴリズム（Bit Flipping Algorithm）を適用し、$(e_{0}, e_{1})$ を得る。
- $m=c_{1}\oplus L(e_{0}, e_{1})$ を計算する。
- $(e_{0}, e_{1})=H(m)$ が成り立つことをチェックして、正しければ $K=K(m, c)$ を計算して出力する。
さて、本問題の概要を説明します。Revenge前の問題と同様、BIKEのリファレンス実装に以下のパッチを当てたものが使われています。
diff -u -r Reference_Implementation/FromNIST/rng.c Reference_Implementation_patched/FromNIST/rng.c
--- Reference_Implementation/FromNIST/rng.c 2024-10-10 16:22:14.000000000 +0900
+++ Reference_Implementation_patched/FromNIST/rng.c 2025-06-04 14:54:22.870084199 +0900
@@ -135,7 +135,7 @@
EVP_CIPHER_CTX_free(ctx);
}
-void
+extern "C" void
randombytes_init(unsigned char *entropy_input,
unsigned char *personalization_string,
int security_strength)
diff -u -r Reference_Implementation/FromNIST/rng.h Reference_Implementation_patched/FromNIST/rng.h
--- Reference_Implementation/FromNIST/rng.h 2024-10-10 16:22:14.000000000 +0900
+++ Reference_Implementation_patched/FromNIST/rng.h 2025-06-04 14:54:28.469718862 +0900
@@ -44,7 +44,7 @@
int
seedexpander(AES_XOF_struct *ctx, unsigned char *x, unsigned long xlen);
-void
+extern "C" void
randombytes_init(unsigned char *entropy_input,
unsigned char *personalization_string,
int security_strength);
diff -u -r Reference_Implementation/kem.c Reference_Implementation_patched/kem.c
--- Reference_Implementation/kem.c 2024-10-10 16:22:14.000000000 +0900
+++ Reference_Implementation_patched/kem.c 2025-06-04 14:54:10.243935982 +0900
@@ -146,7 +146,7 @@
//The three APIs below (keypair, enc, dec) are defined by NIST:
//In addition there are two KAT versions of this API as defined.
////////////////////////////////////////////////////////////////
-int crypto_kem_keypair(OUT unsigned char *pk, OUT unsigned char *sk)
+extern "C" int crypto_kem_keypair(OUT unsigned char *pk, OUT unsigned char *sk)
{
//Convert to these implementation types
sk_t* l_sk = (sk_t*)sk;
@@ -203,8 +203,9 @@
//Encapsulate - pk is the public key,
// ct is a key encapsulation message (ciphertext),
// ss is the shared secret.
-int crypto_kem_enc(OUT unsigned char *ct,
+extern "C" int crypto_kem_enc(OUT unsigned char *ct,
OUT unsigned char *ss,
+ OUT unsigned char *e0_leak,
IN const unsigned char *pk)
{
DMSG(" Enter crypto_kem_enc.\n");
@@ -244,6 +245,8 @@
functionH(e, m, mu);
ntl_split_polynomial(e0, e1, e);
+ memcpy(e0_leak, e0, R_SIZE);
+
// ct = (c0, c1) = (e0 + e1*h, L(e0, e1) \XOR m)
ntl_mod_mul(l_ct->val0, e1, l_pk->val);
ntl_add(l_ct->val0, l_ct->val0, e0);
@@ -266,7 +269,7 @@
//Decapsulate - ct is a key encapsulation message (ciphertext),
// sk is the private key,
// ss is the shared secret
-int crypto_kem_dec(OUT unsigned char *ss,
+extern "C" int crypto_kem_dec(OUT unsigned char *ss,
IN const unsigned char *ct,
IN const unsigned char *sk)
{
@@ -314,7 +317,7 @@
// Step 2. decoding:
DMSG(" Decoding.\n");
- rc = BF_decoder(e_tmp1, syndrome.raw, h0_compact, h1_compact);
+ res = (status_t)BF_decoder(e_tmp1, syndrome.raw, h0_compact, h1_compact); CHECK_STATUS(res);
convertBinaryToByte(e_prime, e_tmp1, 2*R_BITS);
diff -u -r Reference_Implementation/kem.h Reference_Implementation_patched/kem.h
--- Reference_Implementation/kem.h 2024-10-10 16:22:14.000000000 +0900
+++ Reference_Implementation_patched/kem.h 2025-06-04 14:54:17.228066041 +0900
@@ -73,19 +73,20 @@
////////////////////////////////////////////////////////////////
//Keygenerate - pk is the public key,
// sk is the private key,
-int crypto_kem_keypair(OUT unsigned char *pk, OUT unsigned char *sk);
+extern "C" int crypto_kem_keypair(OUT unsigned char *pk, OUT unsigned char *sk);
//Encapsulate - pk is the public key,
// ct is a key encapsulation message (ciphertext),
// ss is the shared secret.
-int crypto_kem_enc(OUT unsigned char *ct,
+extern "C" int crypto_kem_enc(OUT unsigned char *ct,
OUT unsigned char *ss,
+ OUT unsigned char *e0_leak,
IN const unsigned char *pk);
//Decapsulate - ct is a key encapsulation message (ciphertext),
// sk is the private key,
// ss is the shared secret
-int crypto_kem_dec(OUT unsigned char *ss,
+extern "C" int crypto_kem_dec(OUT unsigned char *ss,
IN const unsigned char *ct,
IN const unsigned char *sk);パッチの主要な内容は次の2点です。
- 鍵カプセル化の際に $e_{0}$ の値を返す。ただし、実際にはサーバーは $e_{0}$ を「暗号化」し、
hintとして出力する。 - デカプセル化の際に符号の復号アルゴリズムの成否を返す。正確には、$c_{0}h_{0}=e_{0}h_{0}+e_{1}h_{1}$ が成り立つように復号されたかどうかを返す。
最初にBIKEの鍵生成が実行され、公開鍵 $h$ が与えられます。次に、鍵カプセル化が実行され、暗号文 $c=(c_{0}, c_{1})$ および、$e_{0}$ から作られた hint が与えられます。また、共有鍵 $K$ を用いてフラグを暗号化したものも与えられます。その後、好きな暗号文を入力してデカプセル化の成否を取得することが何回でもできます。Revenge前の問題と異なり、フラグの暗号文は与えられません。
import os
import random
from ctypes import cdll, c_buffer
from Crypto.Cipher import AES
with open("flag.txt", "rb") as f:
FLAG = f.read()
libbike = cdll.LoadLibrary('./libbike.so')
libbike.randombytes_init(os.urandom(48), None, 256)
n = 12323
d = 71
t = 134
R_BYTES = (n+7)//8
M_BYTES = 256//8
SS_BYTES = 256//8
N0 = 2
pk_size = R_BYTES
sk_size = R_BYTES * N0 + M_BYTES + M_BYTES
ct_size = R_BYTES + M_BYTES
ss_size = SS_BYTES
e_size = R_BYTES * N0
pk = c_buffer(pk_size)
sk = c_buffer(sk_size)
libbike.crypto_kem_keypair(pk, sk)
print("public key:", bytes(pk).hex())
ct = c_buffer(ct_size)
k_enc = c_buffer(ss_size)
e0 = c_buffer(R_BYTES)
libbike.crypto_kem_enc(ct, k_enc, e0, pk)
print("ciphertext:", bytes(ct).hex())
cipher = AES.new(key=bytes(k_enc), mode=AES.MODE_CTR)
encrypted_flag = cipher.encrypt(FLAG)
print("encrypted flag:", (cipher.nonce + encrypted_flag).hex())
e0_bin = "".join('{:08b}'.format(v)[::-1] for v in bytes(e0))[:n]
hint = [i for i in range(n) if e0_bin[i] == "1"] + random.sample([i for i in range(n) if e0_bin[i] == "0"], t - e0_bin.count("1"))
random.shuffle(hint)
e0_hint = "".join([e0_bin[i] for i in hint])
hint = hint[:16] + [(hint[i] + int(e0_hint[i-16:i], 2)) % n for i in range(16, len(hint))]
print("hint:", hint)
while True:
ct_input = bytes.fromhex(input("ciphertext: "))
assert len(ct_input) == ct_size
k_dec = c_buffer(ss_size)
res = libbike.crypto_kem_dec(k_dec, ct_input, sk)
if res == 0:
print("decapsulation succeed")
else:
print("decapsulation failed")
continue解法
$e_{0}$ が求まれば、$e_{1}=(c_{0}-e_{0})h^{-1}$, $m=c_{1}\oplus L(e_{0}, e_{1})$, $K=K(m, c)$ の順に計算することで、フラグの暗号化に用いられている鍵 $K$ が求まります。よって、$e_{0}$ を求めることが目標です。リスト hint を先頭から順に見て、「$i$ ($0\leq i< n$) が与えられたときに、$e_{0}$ の $x^{i}$ の係数を求める」という問題を $t=134$ 回解けば、$e_{0}$ が求まります。
さて、本問題では暗号文を入力して符号の復号アルゴリズムの成否を得ることができます。符号の復号アルゴリズムが失敗するのはどのような暗号文を入力した場合でしょうか。
BIKEで用いられている符号の復号アルゴリズムはBit Flipping Algorithmと呼ばれるもので、BIKE Specification Documentの§2.3 Decoderに記載されています。本問題を解くうえでBit Flipping Algorithmの詳細は必要なく、アルゴリズムが「ヒューリスティック的」であることのみが重要です。この性質により、復号が失敗する可能性が常に存在します。正しく作成された暗号文の場合は、エラーの数（すなわち $(e_{0}, e_{1})$ の係数が1の項の個数）は $t=134$ 個と十分小さいため、復号失敗確率は無視できるほど小さいです。しかし、エラーの数が増えると、復号失敗確率が上がることが推測できます。
$t$ を134から増やしながら、暗号文の生成および復号を試してみましょう。すると、$t$ が170くらいまでは復号失敗確率はほぼ0ですが、そこから $t$ を1増やすごとに復号失敗確率が上がっていき、$t$ が190くらいになると復号失敗確率がほぼ1になる、という傾向がつかめます。
この結果から、次のような解法が考えられます。$c_{0}$ の $i$ ビット目およびランダムな47箇所のビットを反転させた暗号文 $c_{0}'$ を作成します。$e_{0}$ の対応するビットを反転させたものを $e_{0}'$ とすると、$c_{0}'=e_{0}'+e_{1}h$ であることから、$c_{0}'$ は $(e_{0}', e_{1})$ に対応する暗号文とみなせます。このとき、$e_{0}$ の $x^{i}$ の係数が0ならば $c_{0}'$ のエラーの数は182、1ならばエラーの数は180となります。よって、$e_{0}$ の $x^{i}$ の係数が0の場合のほうが、1の場合より $c_{0}'$ の復号失敗確率が高くなります。$i$ ビット目以外の反転箇所を変えた $c_{0}'$ をいくつかサーバーに入力して復号失敗回数を数えることで、$e_{0}$ の $x^{i}$ の係数を特定できます。
from ptrlib import *
from ctypes import cdll, c_buffer
from Crypto.Cipher import AES
libbike = cdll.LoadLibrary('./libbike-solve.so')
n = 12323
d = 71
t = 134
R_BYTES = (n+7)//8
M_BYTES = 256//8
SS_BYTES = 256//8
N0 = 2
pk_size = R_BYTES
sk_size = R_BYTES * N0 + M_BYTES + M_BYTES
ct_size = R_BYTES + M_BYTES
ss_size = SS_BYTES
e_size = R_BYTES*N0
PR.<x> = PolynomialRing(GF(2))
def bytes_to_poly(b):
f = 0
for i in range(len(b)):
for j in range(8):
if 8*i+j<n and (b[i]>>j)&1:
f += x^(8*i+j)
return f
def poly_to_bytes(f):
coeffs = f.list()
b = [0]*R_BYTES
for i in range(len(coeffs)):
if coeffs[i]==1:
b[i//8] ^^= (1<<(i%8))
return bytes(b)
def poly_to_bits(f):
coeffs = f.list()
b = [0]*n
for i in range(len(coeffs)):
if coeffs[i]==1:
b[i]=1
return bytes(b)
def inverse(f):
T = PR.quotient(x^n-1)
return PR(lift(T(1)/T(f)))
sock = Socket("nc localhost 12350")
h = bytes.fromhex(sock.recvlineafter("public key: ").strip().decode())
h_inv = inverse(bytes_to_poly(h))
c = bytes.fromhex(sock.recvlineafter("ciphertext: ").strip().decode())
c = list(c)
enc_flag = bytes.fromhex(sock.recvlineafter("encrypted flag: ").strip().decode())
nonce, enc_flag = enc_flag[:8], enc_flag[8:]
hint = eval(sock.recvlineafter("hint: ").strip().decode())
b = 16
t_threshold = 181
e_hint = ""
e0 = 0
cnts = []
results = [[] for _ in range(2)]
NUM_TRY = 256
for k in range(len(hint)):
i = hint[k]
if k>=b:
i = (i-int(e_hint[k-b:k], 2))%n
cnt = 0
sock.recvuntil("ciphertext: ")
for _ in range(NUM_TRY):
flips = random.sample(range(n), t_threshold-t) + [i]
for j in flips:
c[j//8] ^^= (1<<(j%8))
sock.sendline(bytes(c).hex())
for j in flips:
c[j//8] ^^= (1<<(j%8))
for _ in range(NUM_TRY):
res = sock.recvline()
if b"fail" not in res:
cnt += 1
print(k, i, cnt, e_hint)
cnts.append(cnt)
if k>=b:
if abs(cnt-ave0) < abs(cnt-ave1):
e_hint += "0"
results[0].append(cnt)
ave0 = sum(results[0])/len(results[0])
else:
e_hint += "1"
e0 += x^i
results[1].append(cnt)
ave1 = sum(results[1])/len(results[1])
if k==b-1:
cnts_sort = sorted(cnts)
ds = [cnts_sort[j+1]-cnts_sort[j] for j in range(len(cnts)-1)]
m = ds.index(max(ds))
results[0], results[1] = cnts_sort[:m+1], cnts_sort[m+1:]
ave0, ave1 = sum(results[0])/len(results[0]), sum(results[1])/len(results[1])
for j in range(b):
if abs(cnts[j]-ave0) < abs(cnts[j]-ave1):
e_hint += "0"
else:
e_hint += "1"
e0 += x^hint[j]
print(e0)
e1 = (bytes_to_poly(c)+e0)*h_inv%(x^n-1)
print(e1)
e = poly_to_bits(e0) + poly_to_bits(e1)
ss = c_buffer(int(ss_size))
res = libbike.crypto_kem_dec_from_e(ss, bytes(c), e)
cipher = AES.new(key=bytes(ss), mode=AES.MODE_CTR, nonce=nonce)
flag = cipher.decrypt(enc_flag)
print(flag)最後、$(e_{0}, e_{1})$ から鍵 $K$ を求めるパートは、crypto_kem_dec の実装を改造するのが楽です。
diff -u -r Reference_Implementation/kem.c Reference_Implementation_patched/kem.c
--- Reference_Implementation/kem.c 2024-10-10 16:22:14.000000000 +0900
+++ Reference_Implementation_patched/kem.c 2025-06-04 16:03:14.331615954 +0900
@@ -353,3 +353,55 @@
return res;
}
+extern "C" int crypto_kem_dec_from_e(OUT unsigned char *ss,
+ IN const unsigned char *ct,
+ IN const unsigned char *e)
+{
+ DMSG(" Enter crypto_kem_dec.\n");
+ status_t res = SUCCESS;
+
+ // convert to this implementation types
+ const ct_t* l_ct = (ct_t*)ct;
+ ss_t* l_ss = (ss_t*)ss;
+
+ int failed = 0;
+
+ // for NIST DRBG_CTR
+ double_seed_t seeds = {0};
+
+ uint8_t e_recomputed[N_SIZE] = {0};
+
+ uint8_t Le0e1[ELL_SIZE + 2*R_SIZE] = {0};
+ uint8_t m_prime[ELL_SIZE] = {0};
+
+ uint32_t h0_compact[DV] = {0};
+ uint32_t h1_compact[DV] = {0};
+
+ uint8_t e_prime[N_SIZE] = {0};
+ uint8_t e_twoprime[R_BITS*2] = {0};
+
+ uint8_t e_tmp1[R_BITS*2] = {0};
+ uint8_t e_tmp2[N_SIZE] = {0};
+
+ uint8_t e0rand[R_SIZE] = {0};
+ uint8_t e1rand[R_SIZE] = {0};
+
+ int rc;
+
+ convertBinaryToByte(e_prime, e, 2*R_BITS);
+
+ // Step 3. compute L(e0 || e1)
+ functionL(Le0e1, e_prime);
+
+ // Step 4. retrieve m' = c1 \xor L(e0 || e1)
+ for(uint32_t i = 0; i < ELL_SIZE; i++)
+ {
+ m_prime[i] = l_ct->val1[i] ^ Le0e1[i];
+ }
+
+ functionK(l_ss->raw, m_prime, l_ct->val0, l_ct->val1);
+
+ DMSG(" Exit crypto_kem_dec.\n");
+ return res;
+}
+
diff -u -r Reference_Implementation/kem.h Reference_Implementation_patched/kem.h
--- Reference_Implementation/kem.h 2024-10-10 16:22:14.000000000 +0900
+++ Reference_Implementation_patched/kem.h 2025-06-04 16:04:44.233553615 +0900
@@ -89,6 +89,9 @@
IN const unsigned char *ct,
IN const unsigned char *sk);
+extern "C" int crypto_kem_dec_from_e(OUT unsigned char *ss,
+ IN const unsigned char *ct,
+ IN const unsigned char *e);
#endif //__KEM_H_INCLUDED__Cubic Math (hard)
作問者: chocorusk
正解チーム数: 0
概要
最初に256bitの整数 $secret$ がランダムに生成され、$secret$ に続く10個の素数のリスト primes が計算されます。3次多項式 $f(x)=x^{3}+ax+b$ をサーバーに入力すると、primes に属す素数 $p$ のうち $f(x)$ が $\mathbb{F}_{p}$ 上既約なものに対する $p-secret$ のリストを取得できます。クエリ数の上限は50回です。$secret$ を当てることができればフラグが得られます。
with open("flag.txt", "r") as f:
FLAG = f.read()
secret = randrange(2**256)
primes = []
p = secret
while len(primes) < 10:
p = next_prime(p)
primes.append(p)
for _ in range(50):
a, b = map(int, input("a, b = ").split(","))
if a == secret:
print(FLAG)
exit()
if not (-2**31 <= a < 2**31 and -2**31 <= b < 2**31):
exit(1)
res = []
for p in primes:
R.<x> = PolynomialRing(GF(p))
if (x^3+a*x+b).is_irreducible():
res.append(p-secret)
print(res)解法
まず、ランダムな3次多項式を数回入力した結果の和集合を取ることで、primes に属すすべての素数 $p$ に対する $p-secret$ を取得できます。
入力できる多項式が3次ではなく2次であれば、問題は簡単です。素数 $q$ に対し、$x^2-q$ が $\mathbb{F}_{p}$ 上既約であることと、$q$ が$\bmod{p}$ で平方非剰余であることは同値です。平方剰余の相互法則により、$q$ が$\bmod{p}$ で平方剰余かどうかは $p\bmod{q}$ で決まります。よって、小さい素数 $q$ について $x^2-q$ をクエリすれば、primes に属す各 $p$ について $p\bmod{q}$ の候補が半分程度に絞られます。このことから $secret\bmod{q}$ がほぼ確定し、中国剰余定理により $secret$ が復元できます。
3次以上の多項式の場合、2次の場合とは異なり、一般には既約性の条件をある $n$ を用いて $p\bmod{n}$ で書くことはできません。しかし、多項式に対応する $\mathbb{Q}$ 上の体の拡大がアーベル拡大である場合に限り、既約性の条件を $p\bmod{n}$ で書くことができることが知られています。これは、類体論という代数的整数論の理論の帰結です。
小さい素数 $q$ に対し、既約性の条件が $p\bmod{q}$ で書けるような3次多項式を実際に構築するには、円分体から考えるのが楽です。$\zeta_{q}$ を1の原始 $q$ 乗根とすると、拡大 $\mathbb{Q}(\zeta_{q})/\mathbb{Q}$ における素数 $p$ の分解法則は $p\bmod{q}$ で書けることが知られています。よって、$q\equiv 1\pmod{3}$ のとき、$\mathbb{Q}(\zeta_{q})$ の3次の部分体 $K$ を取ると、$K/\mathbb{Q}$ における素数 $p$ の分解法則も $p\bmod{q}$ で書けることがわかります。$K$ に対応する3次多項式は、既約性の条件が $p\bmod{q}$ で書けます。
本問題に興味を持たれた方は、ぜひ類体論について勉強してみてください。Primes of the Form x2+ny2: Fermat, Class Field Theory, and Complex Multiplication は、素数 $p$ が $x^{2}+ny^{2}$ の形で表せる条件を $p\bmod{m}$ で書けるか、という問題から始めて類体論を解説している本で、特におすすめです。
from ptrlib import *
sock = Socket("nc localhost 12347")
def del2(f):
R.<x> = PolynomialRing(ZZ)
coeffs = f.list()
c1 = 9*coeffs[1]-3*coeffs[2]^2
c0 = 27*coeffs[0]-coeffs[2]^3-coeffs[2]*(9*coeffs[1]-3*coeffs[2]^2)
return c1, c0
cnt = 0
res_all = set()
while len(res_all)<10:
a, b = randrange(2**31), randrange(2**31)
sock.sendlineafter("a, b = ", str(a)+","+str(b))
res = eval(sock.recvline())
res_all |= set(res)
cnt += 1
print(res_all)
qs = []
rs = []
qs2 = []
rs2 = []
for q in range(7, 600, 3):
if not is_prime(q):
continue
if cnt>=49:
break
K = CyclotomicField(q)
k = K.subfields(3)[0][0]
assert k.conductor()==q
print(q)
f = k.polynomial()
a, b = del2(f)
print(a, b)
sock.sendlineafter("a, b = ", str(a)+","+str(b))
res = eval(sock.recvline())
cnt += 1
irrs = []
for i in range(1, q):
qi = -1
for j in range(i, 10**9, q):
if is_prime(j):
qi = j
break
R.<x> = PolynomialRing(GF(qi))
if R(f).is_irreducible():
irrs.append(i)
kouho = []
for i in range(q):
dame = False
for r in res_all:
if (r+i)%q==0:
dame=True
break
if r in res:
if not ((r+i)%q in irrs):
dame=True
break
else:
if (r+i)%q in irrs:
dame=True
break
if not dame:
kouho.append(i)
print(kouho)
if len(kouho)==1:
qs.append(q)
rs.append(kouho[0])
elif len(kouho)==2:
qs2.append(q)
rs2.append(kouho)
if len(qs2)>10:
qs2 = qs2[-10:]
rs2 = rs2[-10:]
assert prod(qs+qs2) >= 2**256
for i in range(2**len(qs2)):
rs2_ = []
for j in range(len(qs2)):
rs2_.append(rs2[j][(i>>j)&1])
secret = CRT_list(rs+rs2_, qs+qs2)
diffs = set()
p = secret
while len(diffs) < 10:
p = next_prime(p)
diffs.add(p-secret)
if res_all == diffs:
print(secret)
break
sock.sendlineafter("a, b = ", str(secret)+",0")
sock.interactive()
