osu!gaming CTF 2025 Writeup (crypto)
先日参加したosu!gaming CTF 2025のcrypto分野の解説記事です。
crypto分野については全ての問題を解くことができました。
目次
- rot727 (648 solves)
- beyond-wood (392 solves)
- xnor-xnor-xnor (348 solves)
- pls-nominate (224 solves)
- linear-feedback (142 solves)
- ssss (128 solves)
- please-nominate (72 solves)
- ssss+ (34 solves)
rot727 (648 solves)
問題の概要
この問題では、暗号文 aeg{at_imuf_nussqd_zgynqd_paqezf_yqmz_yadq_eqogdq} が与えられます。問題文には「i rotated my flag 727 times! that’s super secure right」とあり、シーザー暗号（ROT暗号）が使用されていることが示唆されます。
解法のアプローチ
FLAGの形式が osu{...} であることから、暗号文の先頭 aeg が平文 osu に対応します。各文字のシフト量を計算すると：
- \(a\) (0) → \(o\) (14): \(+14\) シフト
- \(e\) (4) → \(s\) (18): \(+14\) シフト
- \(g\) (6) → \(u\) (20): \(+14\) シフト
であるため、\(+14\) シフトを適用することで復号できます。
ソルバーは以下です。
ciphertext = "aeg{at_imuf_nussqd_zgynqd_paqezf_yqmz_yadq_eqogdq}"
def caesar_shift(text, key):
result = ""
for char in text:
if 'a' <= char and char <= 'z':
result += chr((ord(char) - ord('a') + key) % 26 + ord('a'))
else:
result += char
return result
FLAG = caesar_shift(ciphertext, 14)
print(FLAG)beyond-wood (392 solves)
問題の概要
この問題では、元画像 flag.png に対して次の2つの操作を施した output.png が与えられます：
- XOR暗号化: 各画素に対して、短い鍵でチャンネルごとにXOR
- 座標シャッフル: アフィン変換によるピクセル座標の置換
座標変換は次の式で定義されます：
$$i’ \equiv a + mi \pmod{w}, \quad j’ \equiv b + mj \pmod{h}$$
ここで、\(a=2134266\)、\(b=4501511\)、\(m=727\) であり、\(w\) と \(h\) はそれぞれ画像の幅と高さです。この変換は可逆です。
問題文は「spinning white floating glowing man in forest」であり、白く輝く対象が含まれることが示唆されています。元画像を復元することが目標です。
実際のコードは以下です。
from PIL import Image
import random
FLAG = Image.open("flag.png")
width, height = FLAG.size
key = [random.randrange(0, 256) for _ in range(width+height+3)]
out = FLAG.copy()
for i in range(width):
for j in range(height):
pixel = FLAG.getpixel((i, j))
pixel = tuple(x ^ k for x, k in zip(pixel, key))
newi, newj = (2134266 + i * 727) % width, (4501511 + j * 727) % height
out.putpixel((newi, newj), pixel)
out.save("output.png")解法のアプローチ
1.最頻値からの鍵推定
座標シャッフルは画素値のヒストグラムを変化させないため、暗号化後の画像でも各チャンネルの画素値分布は保存されます。問題文から白色のピクセルが多く含まれることが分かるため、各チャンネルの最頻値 \(y_c^*\) を求めます。
平文側の最頻値が 255（白）であると仮定すると、鍵は次のように求まります：
$$k_c = y_c^* \oplus 255$$
2.XOR暗号の解除
推定した鍵 \(\mathbf{k} = (k_R, k_G, k_B)\) を用いて、各画素ベクトル \(\mathbf{p}’\) に対して次の操作を行います：
$$\mathbf{p}” = \mathbf{p}’ \oplus \mathbf{k}$$
XOR演算と座標置換は可換であるため、この操作は座標を戻す前後のどちらで行っても結果は同じです。
3.座標変換の逆写像
元の座標を復元するため、変換式の逆変換を計算します。\(\gcd(m,w)=\gcd(m,h)=1\) の条件下で、\(m\) の逆元を各法について求めます：
$$m_w^{-1} \equiv m^{-1} \pmod{w}, \quad m_h^{-1} \equiv m^{-1} \pmod{h}$$
逆変換は次のようになります：
$$i \equiv m_w^{-1}(i’ – a) \pmod{w}, \quad j \equiv m_h^{-1}(j’ – b) \pmod{h}$$
各画素を元の座標 \((i, j)\) に配置することで、元画像 flag.png が復元されます。
ソルバーは以下です。
from PIL import Image
import numpy as np
from sympy import mod_inverse
a, b, m = 2134266, 4501511, 727
img = Image.open("output.png").convert("RGB")
arr = np.array(img)
h, w, _ = arr.shape
# 最頻値から鍵を推定（白=255を仮定）
key = [int(np.bincount(arr[..., i].ravel()).argmax()) ^ 255 for i in range(3)]
arr ^= np.array(key, dtype=np.uint8).reshape(1, 1, 3)
# 座標逆変換
inv_w = int(mod_inverse(m, w))
inv_h = int(mod_inverse(m, h))
a %= w
b %= h
out = np.zeros_like(arr)
for i in range(w):
for j in range(h):
ii = (inv_w * (i - a)) % w
jj = (inv_h * (j - b)) % h
out[jj, ii] = arr[j, i]
Image.fromarray(out).save("recovered_flag.png")
xnor-xnor-xnor (348 solves)
問題の概要
この問題では、FLAGを4バイトの鍵とビット単位でXNOR暗号化した結果が与えられます。暗号化は次の形で実行されます：
$$\text{enc} = \mathrm{XNOR}(\mathrm{XNOR}(\mathrm{XNOR}(\text{flag}, \text{key}), \text{key}), \text{key})$$
ここで、鍵は os.urandom(4) で生成された4バイトを繰り返したものです。XNORの定義 \(\mathrm{XNOR}(a,b) = \neg(a \oplus b)\) を用いると、暗号文は次の関係を持ちます：
$$c = \neg(p \oplus k)$$
同じ鍵とのXNORを奇数回適用しても1回と等価であるため、実質的には1回のXNOR演算となります。この性質から、鍵が分かれば \(p = \neg c \oplus k\) により即座に復号できます。4バイトの周期的な鍵を求め、FLAGを復元することが目標です。
実際のコードは以下です。
import os
flag = open("flag.txt", "rb").read()
def xnor_gate(a, b):
if a == 0 and b == 0:
return 1
elif a == 0 and b == 1:
return 0
elif a == 1 and b == 0:
return 0
else:
return 1
def str_to_bits(s):
bits = []
for x in s:
bits += [(x >> i) & 1 for i in range(8)][::-1]
return bits
def bits_to_str(bits):
return bytes([sum(x * 2 ** j for j, x in enumerate(bits[i:i+8][::-1])) for i in range(0, len(bits), 8)])
def xnor(pt_bits, key_bits):
return [xnor_gate(pt_bit, key_bit) for pt_bit, key_bit in zip(pt_bits, key_bits)]
key = os.urandom(4) * (1 + len(flag) // 4)
key_bits = str_to_bits(key)
flag_bits = str_to_bits(flag)
enc_flag = xnor(xnor(xnor(flag_bits, key_bits), key_bits), key_bits)
print(bits_to_str(enc_flag).hex())
# 7e5fa0f2731fb9b9671fb1d62254b6e5645fe4ff2273b8f04e4ee6e5215ae6ed6c解法のアプローチ
1. XNOR演算の簡略化
3回のXNOR適用は、同じ鍵を使う限り1回と等価です。これは次のように確認できます：
$$\mathrm{XNOR}(\mathrm{XNOR}(p,k),k) = \neg(\neg(p\oplus k)\oplus k) = p\oplus k\oplus k = p$$
したがって奇数回（3回）の適用は \(\mathrm{XNOR}(p,k) = \neg(p\oplus k)\) と単純化され、復号式は次のようになります：
$$p = \neg c \oplus k$$
2. 周期構造を利用した鍵の絞り込み
鍵は4バイト周期で繰り返されるため、各位置 \(r \in \{0,1,2,3\}\) について同じ鍵バイト \(k_r\) が使用されます。暗号文の各バイト \(c[i]\) に対して、\(i \bmod 4 = r\) となるインデックスは全て同じ鍵バイト \(k_r\) で処理されています。
復号式 \(p[i] = \neg c[i] \oplus k_r\) において、平文が可読なASCII文字（英大小文字、数字、_、{、} など）に限定されると仮定すると、各バイト位置 \(r\) について許容される鍵値 \(k_r\) の範囲が大きく制約されます。
3. フォーマット制約による鍵の特定
FLAGは osu{...} の形式を持つため、先頭4バイトが osu{、末尾が } という制約があります。各合同類 \(i \bmod 4 = r\) に属する全ての暗号文バイトについて、\(\neg c[i] \oplus k_r\) が許容文字集合に入るような \(k_r\) を求めます。
特に、先頭の osu{ と末尾の } の位置から得られる制約を用いることで、4バイトの鍵 \((k_0, k_1, k_2, k_3)\) を一意に決定できます。
4. FLAGの取得
求めた4バイト鍵を繰り返して平文長と同じキー列を作成し、\(\text{flag} = \neg c \oplus \text{key}\) により復号します。得られた平文が正しいFLAGとなります。
ソルバーは以下です。
CT_HEX = "7e5fa0f2731fb9b9671fb1d62254b6e5645fe4ff2273b8f04e4ee6e5215ae6ed6c"
PREFIX = b"osu{"
c = bytes.fromhex(CT_HEX)
nc = bytes((~b) & 0xFF for b in c)
k4 = bytes(nc[i] ^ PREFIX[i] for i in range(4))
p = bytes(nc[i] ^ k4[i % 4] for i in range(len(c)))
print(p.decode())pls-nominate (224 solves)
問題の概要
この問題では、公開指数 \(e=5\) を使用する5つの異なるRSA暗号系が与えられます。同一の平文 \(m\)（既知のプレフィックスと未知のFLAGを連結したもの）を、各暗号系で暗号化した結果が提供されます。
各RSA法は約2048ビットの2つの素数の積 \(n_i = p_i q_i\) \((i=1,\dots,5)\) として生成され、暗号文は次の形で与えられます：
$$c_i \equiv m^5 \pmod{n_i}$$
出力には5個の法 ns、対応する暗号文 cs、そしてFLAGの長さ len(FLAG) が含まれており、これらからFLAGを復元することが目標です。
実際のコードは以下です。
from Crypto.Util.number import *
FLAG = open("flag.txt", "rb").read()
message = bytes_to_long(
b"hello there can you pls nominate my map https://osu.ppy.sh/beatmapsets/2436259 :steamhappy: i can bribe you with a flag if you do: " + FLAG
)
ns = [getPrime(727) * getPrime(727) for _ in range(5)]
e = 5
print(len(FLAG))
print(ns)
print([pow(message, e, n) for n in ns])解法のアプローチ
1. 中国剰余定理による合同式の統合
5つの合同式を統合するため、中国剰余定理を適用します。各法 \(n_i\) は互いに素です。積 \(N = \prod_{i=1}^5 n_i\) に対して、次を満たす一意の解 \(M \in [0, N)\) を求めます：
$$M \equiv c_i \pmod{n_i} \quad (i=1,\dots,5)$$
この構成により、\(M \equiv m^5 \pmod{N}\) が成立します。
2. 整数域での5乗根の計算
平文のサイズ制約から \(m^5 < N\) が成立します。各法が約2048ビットであれば積 \(N\) は約10240ビットとなり、平文が数百バイト程度なら容易にこの条件を満たします。
この条件下では、合同式 \(M \equiv m^5 \pmod{N}\) は整数の等式 \(M = m^5\) を意味するため、整数5乗根を計算することで平文を復元できます：
$$m = \sqrt[5]{M}$$
3. FLAGの抽出
復元した整数 \(m\) をバイト列に変換し、平文の構造が「既知プレフィックス + FLAG」であることから、末尾の len(FLAG) バイトを切り出すことでFLAGを取得できます。
ソルバーは以下です。
from sympy.ntheory.modular import crt
from sympy import integer_nthroot
PREFIX = (b"hello there can you pls nominate my map https://osu.ppy.sh/beatmapsets/2436259 "
b":steamhappy: i can bribe you with a flag if you do: ")
flag_len = 51
ns = [
250595396282063209494575040924347535718377683482891600245762578107828862102674761114596255712438613333084596184792828788407383247558654559454089469986479081755983932855108019303831103066796233258382489582930536579371270189763162153515702860564938568045151352777820047894231299381399970139347989102071591624967158663442340607621438098266100701196825065519485094630829410736139969891010792546625692049625954656831699035171996469050264653519,
274193894251894220756361545934981580561716587343502325614560502213231097664469582415896327192024233714369720707686115433619798180404789138894067772483823865845960858748702597162370083356345247341014451005796413454404641015516131648586490172413946109076519615677569833823093216546284937656690546486895353267404868698676199564604463636499575466246860736708986174600028222786416474243294353345680209117811499529853520907091701228114817603341,
250799342406461286072464998395337312450245201655027007410237718631499754452822255347456526289099898965321822671514782488741429427305776533799167428860480805487315744950556177330105418061977431001775317350105402223927656557524000999352457757910475375628290615583082601813818635461940350546377443417651889260364946457646723831198413138381669914264256219982213937975414376723125047495586971424241557485231775101178049132539231505246677535311,
424944038623958440933855665649910939213053530859402286143675513220496021786445337272966523453996205752202713497414819150875478398393046433188515528170856189163826639434032436582059667688688880862276540443913407720932133045261989787061306952765245738545030903458101323357019464537917143233906507656465350475977450213990615572573474700619979502153864626401863294100140176446546365233603532530624614938982882757207592863414287369042546971519,
190902360498923981884467164531021372209737709612751157876047387113070619788864781987406983172298076877277648095765822757629049183301893699559004938030166520411955041284763767367633388446007417241478444104664237424445213634253699407015432110027972438018815169650491766550691229860103594060212173628624522421052861949630723039778975476515078589820738377723637869903050748150998629965678848786824733474968760721078438148119740362699143145661
]
cs = [
123451724931477698812069511077458860459906769716993869507604368750013627155203649026878565706523272034474865506508962044958969096479439140090681403538412644329412752922637248582028201974150208943081418296518937380419465322558643434318990712657710219963788075009287648875763482189708828745866942138140694074154628539909488581608681566648945293332282252866416448399029058170554552880389525160322280616124297247776106117085199571903380300602,
25521272212086093871680233376409740841684880441320606653986457586214228433726846827063346040622596803682405351090250464809787622301562945715858274147064371839443966925136930647541454865892780911461753966896009773200289476756676124794087249400266226027218836477923252144492106017794796924100502787481309583584738175138358520327875032255246435556182629496953900460417813322557030951101538854106453327597012091626682332420269075467900021711,
185794248348100154380171644978622218400518238250460812348815837123659842567285820889770059992960889881347901994420631735102166283167843240900863871790624347481898956733174665116495731603736544724548220276282583347110470600528846477853732162784786525839648496719341390265839130761362980916014963941737879183454424512265005367317359376039242988696224018798645014519276397488302687294083964113652155465518932071360150626192713920598188877877,
253586754830185402755129821208401339617813079433078480306550244166018490731187464131167959996920120199131859308803805312785667542198282217092146066559207637833505962392131719788571007971893923218099583927291388588829681723690416962688366275898952085934742953047229390090702589945168823704791405472122768397486450092804662113840124827388352338015003693741233274505595280978468538153880244070082267537407664878646371738748713917087874183934,
179921278884389482689970386454786826216817164768869732618011304299464646110222440114625532548731013316437178194666578920837571688939194292542951671294588526331670811293769249832666220726222224721812635640949602967313922271367769076173808739323285134139353621782784562334885703861549547716097420971226456620806331145247840335617343331077891979324239020388123429770254863290698575175653976557893390825861821917810477967554648397683909903482
]
# 1) CRTで M (mod N) を得る
M, N = crt(ns, cs)
# 2) A = bytes_to_long(PREFIX) * 256**flag_len
B = 1 << (8 * flag_len)
A = int.from_bytes(PREFIX, "big") * B
# 3) m^5 = M + kN なので、k ≈ round((A^5 - M)/N) を求める
k = ((A**5 - M) + N//2) // N
# 4) (M + kN) の 5 乗根が m
m, exact = integer_nthroot(M + k * N, 5)
mb = int(m).to_bytes((m.bit_length() + 7) // 8, "big")
flag = mb[-flag_len:]
print(flag.decode())linear-feedback (142 solves)
問題の概要
この問題では、長さ21と29の2本のLFSRの出力をXNOR結合した観測列が与えられます。具体的には、各時刻 \(t\) での出力が
$$\text{output} = \mathrm{XNOR}(L1[t], L2[t]) = 1 \oplus L1[t] \oplus L2[t]$$
として計算され、先頭72ビットの観測列 bits が公開されます。
FLAGは、2つの初期状態 \(k_1 \in \{0,1\}^{21}\)、\(k_2 \in \{0,1\}^{29}\) から生成されるキーストリームで暗号化されています。キーストリームは \(\mathrm{SHA256}(\text{str}(k_1) | \text{str}(k_2))\) の32バイトを2回繰り返したものです。これらの初期状態を復元し、FLAGを復号することが目標です。
なお、L2のタップ列は [5,3,5,5,9,9,7] として与えられていますが、GF(2)では偶数回出現する要素が相殺されるため、実効的なタップ位置は \(\{3, 5, 7\}\) となります。
実際のコードは以下です。
from secrets import randbits
from math import floor
from hashlib import sha256
class LFSR:
def __init__(self, key, taps, format):
self.key = key
self.taps = taps
self.state = list(map(int, list(format.format(key))))
def _clock(self):
ob = self.state[0]
self.state = self.state[1:] + [sum([self.state[t] for t in self.taps]) % 2]
return ob
def xnor_gate(a, b):
if a == 0 and b == 0:
return 1
elif a == 0 and b == 1:
return 0
elif a == 1 and b == 0:
return 0
else:
return 1
key1 = randbits(21)
key2 = randbits(29)
L1 = LFSR(key1, [2, 4, 5, 1, 7, 9, 8], "{:021b}")
L2 = LFSR(key2, [5, 3, 5, 5, 9, 9, 7], "{:029b}")
bits = [xnor_gate(L1._clock(), L2._clock()) for _ in range(floor(72.7))]
print(bits)
FLAG = open("flag.txt", "rb").read()
keystream = sha256((str(key1) + str(key2)).encode()).digest() * 2
print(bytes([b1 ^ b2 for b1, b2 in zip(FLAG, keystream)]).hex())解法のアプローチ
1. 観測列からXOR列への変換
XNOR の定義から、
$$s_t = L1[t] \oplus L2[t] = 1 \oplus \text{bits}[t]$$
が成立します。この関係により、公開された観測列から2本のLFSR出力のXOR列を直接計算できます。
2. 片側の総当たりによる候補生成
21ビット側の初期状態 \(k_1\) を \(2^{\,21}\) 通り全探索します。各候補について、L1を72ステップ実行し、出力列 \({o_t^{(1)}}_{t=0}^{71}\) を生成します。
この出力列と前ステップで得た \(s_t\) を用いて、L2の出力列候補を次のように合成します：
$$o_t^{(2)} = o_t^{(1)} \oplus s_t$$
これは「もし \(k_1\) が正しければ、真のL2出力列と一致する」という性質を持ちます。
3. 線形漸化式による早期棄却
長さ29、実効タップ \(\{3, 5, 7\}\) のLFSR出力列は、次の線形漸化式を満たします：
$$o_t^{(2)} = o_{t-29+3}^{(2)} \oplus o_{t-29+5}^{(2)} \oplus o_{t-29+7}^{(2)} \quad (t \geq 29)$$
各 \(k_1\) 候補について、\(t=29\) から順次この関係式をチェックし、1箇所でも矛盾が生じた時点でその候補を棄却します。ランダムな列はこの線形制約を満たさないため、大部分の誤った候補は早期に除外されます。
4. 初期状態の復元
線形漸化式の検証を全て通過した候補については、合成した (o_t^{(2)}) の先頭29ビットがL2の初期状態そのものとなります：
$$k_2 = \text{MSB→LSBの順で } o_{0..28}^{(2)} \text{ を整数化}$$
これにより、\((k_1, k_2)\) の組が一意に決定されます。
5. 復号とFLAGの取得
復元した初期状態からキーストリームを生成します：
$$\text{KS} = \big(\mathrm{SHA256}(\text{str}(k_1) | \text{str}(k_2))\big) \text{ を2回繰り返し}$$
暗号文とこのキーストリームをXORすることで、平文FLAGが得られます。
ソルバーは以下です。
from hashlib import sha256
TAPS1 = [2,4,5,1,7,9,8]
def lfsr_clock(state, taps):
ob = state[0]
new = sum(state[t] for t in taps) & 1
state[:] = state[1:] + [new]
return ob
def try_key1(key1, s):
state = list(map(int, f"{key1:021b}"))
o2 = []
for t in range(len(s)):
o2.append(lfsr_clock(state, TAPS1) ^ s[t])
if t >= 29:
if o2[t] != (o2[t - 26] ^ o2[t - 24] ^ o2[t - 22]):
return None
k2 = int("".join(map(str, o2[:29])), 2)
return k2
bits = [0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0]
ct_hex = "9f7f799ec2fb64e743d8ed06ca6be98e24724c9ca48e21013c8baefe83b5a304af3f7ad6c4cc64fa4380e854e8"
s = [1 ^ b for b in bits[:72]]
ct = bytes.fromhex(ct_hex if len(ct_hex) % 2 == 0 else "0" + ct_hex)
for k1 in range(1 << 21):
k2 = try_key1(k1, s)
if k2 is None:
continue
ks = sha256((str(k1)+str(k2)).encode()).digest() * 2
pt = bytes(c ^ ks[i] for i,c in enumerate(ct))
try:
print(pt.decode())
break
except:
continuessss (128 solves)
問題の概要
素数 \(p=2^{\,255}-19\) 上で定義された次数14の多項式
$$f(x)=\sum_{i=0}^{14} c_i x^i \pmod p$$
を持つサーバーがあり、任意の \(x\in{1,\dots,p-1}\) に対する \(f(x)\) の値を最大14回まで問い合わせることができます。
ここでポイントとなるのは、係数列が線形合同法（LCG）により生成されていることです。具体的には、\(c_0=\texttt{SECRET}\) として、\(c_i\equiv ac_{i-1}+b \pmod p\) \((i=1,\dots,14)\) という関係があります（\((a,b)\) は非公開）。この制約を利用して \(\texttt{SECRET}\) を求めることが目標です。
実際のコードは以下です。
from Crypto.Util.number import *
import random
p = 2**255 - 19
k = 15
SECRET = random.randrange(0, p)
def lcg(x, a, b, p):
return (a * x + b) % p
a = random.randrange(0, p)
b = random.randrange(0, p)
poly = [SECRET]
while len(poly) != k: poly.append(lcg(poly[-1], a, b, p))
def evaluate_poly(f, x):
return sum(c * pow(x, i, p) for i, c in enumerate(f)) % p
print("welcome to ssss", flush=True)
for _ in range(k - 1):
x = int(input())
assert 0 < x < p, "no cheating!"
print(evaluate_poly(poly, x), flush=True)
if int(input("secret? ")) == SECRET:
FLAG = open("flag.txt").read()
print(FLAG, flush=True)解法の戦略
1. 再帰構造を利用した変形
LCGの差分関係 \(c_i – ac_{i-1} \equiv b \pmod p\) に着目します。多項式 \(f(x)\) に \((1-ax)\) を掛けると、係数の再帰構造がうまく相殺されます：
$$\begin{array}{rcl}
(1-ax)f(x) & = & \sum_{i=0}^{14} c_i x^i – a\sum_{i=0}^{14} c_i x^{i+1} \\
& = & c_0 + \sum_{i=1}^{14}(c_i – a c_{i-1}) x^i – a c_{14} \,x^{15} \\
& \equiv & c_0 + b \sum_{i=1}^{14} x^i – a c_{14} \,x^{15}\ (\mathrm{mod}\ p)
\end{array}$$
結果として、次の関係式を得ます：
$$(1-ax)y \equiv c_0 + bS(x) – ac_{14} \,x^{15} \pmod p$$
2. 連立方程式への帰着
上の式を整理すると、\(y = c_0 + bS(x) + a(xy) – (ac_{14}\,)x^{15}\) という形になります。これは未知数 \((c_0, b, a, d)\)（ただし \(d=ac_{14}\)）についての一次方程式として見ることができます。
3. 効率的な求解
異なる4つの \(x\) を選んで問い合わせを行い、4本の方程式を得ます。これらから係数行列 \(A\in\mathrm{GF}(p)^{4\times 4}\) と右辺ベクトル \(\mathbf{y}\) を構成し、
$$A\mathbf{u}=\mathbf{y}$$
を有限体 \(\mathrm{GF}(p)\) 上で解きます。解ベクトルの第1成分が求める \(\texttt{SECRET}\) となります。
ソルバーは以下です。
from itertools import combinations
from sympy import Matrix
from pwn import process
p = 2**255 - 19
f = lambda x: (14 if x % p == 1 else (x * (pow(x, 14, p) - 1) * pow(x - 1, p - 2, p)) % p)
io = process(["python", "server.py"])
io.recvuntil(b"welcome to ssss\n")
X = [2, 3, 5, 7] + [1] * 10
xs, ys = [], []
for x in X:
io.sendline(str(x).encode())
y = int(io.recvline().strip())
xs.append(x)
ys.append(y)
A = Matrix([[1, f(xs[i]), (xs[i] * ys[i]) % p, (-pow(xs[i], 15, p)) % p] for i in range(4)])
b = Matrix([ys[i] % p for i in range(4)])
secret = ((A.inv_mod(p) * b) % p)[0]
io.sendlineafter(b"secret? ", str(secret).encode())
print(io.recvall().decode())please-nominate (72 solves)
問題の概要
この問題では、公開指数 \(e=3\) を使用する3つの異なるRSA暗号系 \((n_1,n_2,n_3)\) が与えられています。各平文は、既知の接頭辞 \(P_i\) と共通の未知147バイト文字列（FLAG）を連結した形になっています：
$$m_i = P_i \,||\, \text{FLAG}$$
暗号文 \(c_i \equiv m_i^3 \pmod{n_i}\) と各法 \(n_i\)（約1454ビット、727ビット素数2個の積）、そして接頭辞 \(P_i\) が与えられており、これらから共通のFLAGを復元することが目標です。
実際のコードは以下です。
from Crypto.Util.number import *
FLAG = open("flag.txt").read()
BNS = ["Plus4j", "Mattay", "Dailycore"]
print(len(FLAG))
for BN in BNS:
print("message for", BN)
message = bytes_to_long(
(f"hi there {BN}, " + FLAG).encode()
)
n = getPrime(727) * getPrime(727)
e = 3
print(n)
print(pow(message, e, n))解法のアプローチ
1. 文字列連結を数値として扱う
まず、文字列の連結を256進整数として解釈します。平文を \(m_i = k_i + X\) の形で表現すると、\(k_i = \text{int}(P_i) \cdot 256^{\,\,147}\) が既知の接頭辞部分、\(X = \text{int}(\text{FLAG})\) が求めたい未知の部分となります。これにより、次の合同式が得られます：
$$(X+k_i)^3 \equiv c_i \pmod{n_i}$$
2. 中国剰余定理を活用した多項式の構成
3つの合同式を統合するため、積 \(N=n_1n_2n_3\) に対してCRTの直交べき等元を利用します：
$$\lambda_i \equiv N_i \cdot N_i^{-1} \pmod{n_i} , \quad N_i = \frac{N}{n_i}$$
これらの性質（\(\lambda_i \equiv 1 \pmod{n_i},\ \lambda_i \equiv 0 \pmod{n_j}\ (j \ne i)\)）を使うと、3つの合同式を合成して単一のモニック三次多項式を得ることができます：
$$F(X) = X^3 + AX^2 + BX + C \equiv 0 \pmod{N}$$
ここで重要なのは、CRTの一意性により \(\sum_{i=1}^3 \lambda_i \equiv 1 \pmod{N}\) となるため、自然にモニック（最高次係数が1）になることです。
係数は次のように計算されます：
$$\begin{aligned}
A &= 3\sum_{i=1}^3 \lambda_i k_i \\
B &= 3\sum_{i=1}^3 \lambda_i k_i^2 \\
C &= \sum_{i=1}^3 \lambda_i(k_i^3 – c_i)
\end{aligned}$$
3. Coppersmith法で小さな根を見つける
FLAGのサイズが \(|X| < 256^{\,\,147} = 2^{1176}\) である一方、\(N^{1/3} \approx 2^{1454}\) となることから、\(256^{\,\,147} < N^{1/3}\) が成立します。これは単変数Coppersmithの定理の条件（次数 \(d=3\) のモニック多項式に対して \(|X| < N^{1/d}\,\,\)）を満たしているため、効率的に根を求めることができます。
4. FLAGの復元と検証
得られた根 \(X\) を147バイトの文字列に変換することでFLAGを取得できます。
ソルバーは以下です。
from sage.all import Zmod, PolynomialRing, crt
BNS = ["Plus4j", "Mattay", "Dailycore"]
SHIFT = 8 * 147 # FLAG は 147 バイト
E = 3
ns = [
398846569478640111212929905737126219425846611917845064245986310899352455531776606361272505433849914145167344554995030812644189047710542954339906669786929747875597103059283954786345252202913509966200329213618547501451752329008531151228646387182403280019664272348231587940227470159846477386295856419407431569159867135365878913551268186765163877676657618137090681937329865631964114691373454627873900294385351135992352798790940857277941472243,
263921537800979838796221921202623647462415714721726394821753160972868778052085367522658133754602607941536627474441882978361116817475949497489399939969612509386335591643019109294105788234910211931439396509289221190345347268312099449152342020093136914687793357372601654532872673983206837150636881928382445566331068237688851345596537893940860402116702078271640048006152159670916299390559068168682951764623558492401318864545619303656361575039,
244031565800210621970295548144726813179733488382314342571474949081381534498271587584918252306707810369627816196681952536809552862200098862267362735277533022204353497254323228274491354364582967316701126783750290886096960998524414107270804949357307485711415647006606381700355291677615735646360495158637105102935658791364633128882874894799509049190571860852436246528522948513282608143921733438326627413507376148669722384969604597622237576689,
]
cs = [
158222951303542921410153264594688628146576794503998427093311713650774531277430572380170172031191979123500854263417781975728851277579707820383487572964731381023292312261571110891911863884482902461410218286288183400964045679561296043109527250114073394295486982996930960424139332989226106162113091535475425207610140495532136130360540296097313129598880764160739736823532823136291009499982471028009894097569348660440830784543668141509385395632,
166535918659821916010028099769670832129351247306732465032191446110439632420210106966178779555368253320514619095691319433325610616798380002564235371548166904170934635615481900225094067835806190805967329346507481446735982286060193425107057243896658750175391024795867108700750688771820192759373880324263838550825384190714299697136118712791588291627904942573970568726142296145821435413605295796704576678263679112272532276173497584694652201371,
132630164676661516893599967289982601955380588903536428955472887691456873565355730161547637935630009622741758822400797894281114572338413548852823840995609427904180355965179631480101131212344121270312182355342132383562008365671754190667582150820337165104642347684925014217687937383396003151315200366708307846959894632317624125785370063052712288658901699972320248281442796056361927746314341729204052997736037101265782906021307934740092047950,
]
# 既知プレフィックス k_i = int(P_i) << (8*147)
ks = [(int.from_bytes(f"hi there {bn}, ".encode(), "big") << SHIFT) for bn in BNS]
N = ns[0] * ns[1] * ns[2]
# F(X) = X^3 + A X^2 + B X + C (mod N) を CRT で構成
A = crt([(3 * k) % n for k, n in zip(ks, ns)], ns)
B = crt([(3 * pow(k, 2, n)) % n for k, n in zip(ks, ns)], ns)
C = crt([((pow(k, 3, n) - c) % n) for k, n, c in zip(ks, ns, cs)], ns)
R = PolynomialRing(Zmod(N), "x"); x = R.gen()
f = x**E + A * x**(E - 1) + B * x + C
# Coppersmith
XBound = 1 << SHIFT
roots = f.small_roots(X=XBound, beta=1/3, epsilon=1/64)
x0 = int(roots[0])
FLAG = x0.to_bytes(147, "big")
print(FLAG)ssss+ (34 solves)
問題の概要
ssssと同様の設定ですが、より難しい制約があります。係数列が256ビットの別の素数 \(pp\) 上のLCGで生成されており、\(c_0=\texttt{SECRET}\)、\(c_{i+1}\equiv ac_i+b \pmod{pp}\) という関係があります（\((pp,a,b)\) は非公開）。サーバーの応答は常に \(\bmod p\) で返されるため、係数の真の値を直接知ることはできません。\(\texttt{SECRET}\in[0,p)\) を求めることが目標です。
実際のコードは以下です。
from Crypto.Util.number import *
import random
p = 2**255 - 19
k = 15
SECRET = random.randrange(0, p)
def lcg(x, a, b, p):
return (a * x + b) % p
pp = getPrime(256)
a = random.randrange(0, pp)
b = random.randrange(0, pp)
poly = [SECRET]
while len(poly) != k: poly.append(lcg(poly[-1], a, b, pp))
def evaluate_poly(f, x):
return sum(c * pow(x, i, p) for i, c in enumerate(f)) % p
print("welcome to ssss", flush=True)
for _ in range(k - 1):
x = int(input())
assert 0 < x < p, "no cheating!"
print(evaluate_poly(poly, x), flush=True)
if int(input("secret? ")) == SECRET:
FLAG = open("flag.txt").read()
print(FLAG, flush=True)解法の流れ
1. DFTを使った奇数係数の抽出
\(12\mid(p-1)\) という性質から、\(\mathbb{F}_p^*\) に位数12の元 \(\omega\) が存在します。\(t^{12}\neq1\) を満たす適当な \(t\) を選び、\(x_j=\omega^j t\ (j=0,\dots,11)\) で問い合わせを行います。
逆離散フーリエ変換により
$$S_i(t)=\frac{1}{12}\sum_{j=0}^{11} f(\omega^j t)\omega^{-ij}$$
を計算すると、\(\omega\) の周期性により次の性質が得られます：
$$S_i(t)=\sum_{m\ge0} c_{i+12m} \,t^{i+12m}$$
多項式の次数が14であることから、\(i\in\{3,5,7,9,11\}\) では単項になり、\(c_i\equiv S_i(t)t^{-i}\pmod p\) として係数を直接求めることができます。
2. パリティ分離による残りの係数の取得
\(x=\pm1\) での値の差を利用すると、
$$\frac{f(1)-f(-1)}{2}\equiv \sum_{\text{odd }i} c_i \pmod p$$
から奇数係数の総和が得られます。既に求めた係数を差し引くことで \(c_1+c_{13}\pmod p\) を得ます。
さらに、\(S_1(t)=c_1 t + c_{13} \,t^{13}\) と \(t^{12}\neq1\) の条件を活用して、連立方程式を解くことで \(c_1\) と \(c_{13}\) を個別に求めることができます。
3. 持ち上げと(\gcd)による(pp)の復元
各奇数係数について、\(\bmod p\) での値から \(\bmod pp\) での真の値は2通りの可能性があります（\(pp < 2p\) であることがほぼ確実なため）。7個の奇数係数について \(2^7=128\) 通りの候補を考えます。
奇数添字の係数間には次の二次漸化式が成立します：
$$c_{2i+3} \equiv a^2 c_{2i+1} + b(a+1) \pmod{pp}$$
この関係から導かれる条件式 \(D_i := d_{i+1}d_{i-1} – d_i^2 \equiv 0 \pmod{pp}\) を利用し、各候補について \(\gcd(D_1, D_2, D_3, D_4)\) の最大素因数を求めることで、正しい \(pp\) を特定できます。
4. パラメータの復元とSECRETの計算
奇数添字列から \((A,B)\) を求め、Tonelli-Shanks法で \(\sqrt{A}\) を計算して \(a\) を得ます。その後、
$$c_0\equiv (c_1-b)a^{-1}\pmod{pp}$$
により \(c_0\) を計算し、\(0\le c_0<p\) の制約を満たす値が求める \(\texttt{SECRET}\) となります。
ソルバーは以下です。
from pwn import process
from sympy import sqrt_mod, factorint, isprime
from math import gcd
import random
p = 2**255 - 19
io = process(["python", "server.py"])
io.recvuntil(b"welcome to ssss\n")
def root12(p):
while True:
g = random.randrange(2, p - 1)
w = pow(g, (p - 1) // 12, p)
if pow(w, 12, p) == 1 and all(pow(w, d, p) != 1 for d in (1, 2, 3, 4, 5, 6)):
return w
def ask(x):
io.sendline(str(x).encode())
return int(io.recvline().strip())
w = root12(p)
t = 2
while pow(t,12,p)==1:
t += 1
# 12点: x_j = w^j * t
xs = [(pow(w, j, p) * t) % p for j in range(12)]
ys = [ask(x) for x in xs]
# x = ±1
f1 = ask(1)
f2 = ask(p - 1)
# 逆DFT: S_i(t) = (1/12) * Σ f(w^j t) w^{-ij}
inv12 = pow(12, -1, p)
wp = [pow(w, i, p) for i in range(12)]
S = [(inv12 * sum(ys[j] * wp[(12 - (i * j) % 12) % 12] % p for j in range(12))) % p for i in range(12)]
odds_single = {i: S[i] * pow(pow(t, i, p), -1, p) % p for i in (3, 5, 7, 9, 11)}
# 奇数係数和から c1+c13
sodd = (f1 - f2) * pow(2, -1, p) % p
s13 = (sodd - sum(odds_single[i] for i in (3, 5, 7, 9, 11))) % p
# S1 = c1*t + c13*t^13, かつ c1+c13 = s13
t13 = pow(t,13,p)
den = (t - t13) % p
c1 = (S[1] - s13 * t13) * pow(den, -1, p) % p
c13 = (s13 - c1) % p
odds_modp = [c1, odds_single[3], odds_single[5], odds_single[7], odds_single[9], odds_single[11], c13]
# 2通りの持ち上げ (+0 か +p) 全探索 → gcdから pp を抽出
best_bitlen, best_G, best_y = 0, None, None
for mask in range(1 << 7):
y = [odds_modp[i] + (((mask>>i) & 1) * p) for i in range(7)]
d = [y[i + 1] - y[i] for i in range(6)]
Ds = [d[i + 1] * d[i - 1] - d[i] * d[i] for i in range(1, 5)]
G = 0
for D in Ds:
G = gcd(G, abs(D))
if G and G.bit_length() > best_bitlen:
best_bitlen, best_G, best_y = G.bit_length(), G, y
pp = best_G if isprime(best_G) else max(factorint(best_G).keys())
y = best_y
d = [(y[i + 1] - y[i]) % pp for i in range(6)]
i0 = next(i for i in range(5) if d[i] % pp)
A = (d[i0 + 1] * pow(d[i0], -1, pp)) % pp
B = (y[i0 + 1] - A*y[i0]) % pp
# a^2 = A の平方根
for a in sqrt_mod(A, pp, all_roots=True):
if (a + 1) % pp == 0:
continue
b = (B * pow((a + 1) % pp, -1, pp)) % pp
c0 = ((y[0] - b) * pow(a, -1, pp)) % pp # c1 = a*c0 + b
if c0 < p:
io.recvuntil(b"secret? ")
io.sendline(str(int(c0)).encode())
print(io.recvall().decode())
