KalmarCTF 2026 RBG+ Writeup — 和で隠された RSA を交互和と多項式 GCD で割る

概要

KalmarCTF 2026 の Crypto 問題「RBG+」（106pts）。RSA と LCG（線形合同法）を組み合わせた問題で、フラグ m が RSA で暗号化され、指数 e が LCG で更新されていく。厄介なのは、出力が「2つの暗号文の和」 として与えられる点だ。2項が足し合わさって個別の m^e mod N に分離できないため、そのままでは RSA の構造が使えない（値は各項 mod N の整数和で、和は N を超えうる。この整数性は後の議論を楽にするが、攻撃の本質は「和で隠されている」ことにある）。

この「和」をどう剥がすかが核心になる。

問題の構造

N = getPrime(371) * getPrime(371)  # 約742-bit RSA modulus（371bit素数2つの積、本インスタンスは742bit）
e = getRandomRange(731, N)
print(f"{N, e = }")                # N と初期指数 e_0 は出力の1行目で公開される
lcg = lambda s: (s * 3 + 1337) % N

for i in range(13):
    print(pow(m, e, N) + pow(m, e:=lcg(e), N))

つまり N と初期指数 e_0 は公開値（出力の1行目）で、以降 13 行が和 c_i として与えられる。秘密はフラグ m だけだ。

整理すると、

c_i = m^{e_i} + m^{e_{i+1}}（和の形。各項は mod N だが、和は N を超えうる整数）
e_{i+1} = (3 · e_i + 1337) mod N（LCG による指数更新）
13 個のデータポイントに対し、未知の値 a_j = m^{e_j} mod N は 14 個

未知が1個多いが、LCG の構造が拘束条件を与えてくれる。

解法

Step 1: 交互和で `a_j` を `a_0` の線形関数にする

c_i = a_i + a_{i+1} なので、交互和を取ると隣接項が打ち消し合う。

S_k = Σ_{i=0}^{k} (-1)^i · c_i = a_0 + (-1)^k · a_{k+1}

ここで c_i は N を超える整数なので、この式は mod N ではなく正確な整数として成立する。したがって、

k が偶数: a_{k+1} = S_k − a_0
k が奇数: a_{k+1} = a_0 − S_k

つまり 全ての a_j が a_0 の1次式 で書ける。未知は実質 a_0 の1個だけになった。

Step 2: LCG の「wrap」回数を数える

e_{i+1} = (3 · e_i + 1337) mod N の mod は、実際の指数差にオフセットを生む。

e_{i+1} − 3 · e_i = 1337 − wraps[i] · N

wraps[i] は 3 · e_i + 1337 が N を何回跨いだか。e_i < N なので 3 · e_i + 1337 < 3N + 1337、理論上は 0〜3 の値を取り得る（このインスタンスの実データでは 0, 1, 2 のみだった）。同じ wrap 値を持つ連続ペア (i, i+1)（wraps[i] = wraps[i+1]）では、指数の定数項が揃う：

e_{i+1} = 3·e_i   + (1337 − wraps[i]·N)
e_{i+2} = 3·e_{i+1} + (1337 − wraps[i]·N)   ← 定数項が i と同じ

この2式から定数項を消すと、

4·e_{i+1} = e_{i+2} + 3·e_i

指数をそのまま a = m^e に持ち上げれば、

a_{i+1}^4 = a_{i+2} · a_i^3   (mod N)

が得られる（a_i が mod N で可逆なら比の形 a_{i+1}/a_i^3 = a_{i+2}/a_{i+1}^3 とも書けるが、この交差乗算形は可逆性を要求せず、より厳密）。

Step 3: 多項式 GCD で `a_0` を一意に決める

Step 1 で全ての a_j は a_0 の1次式だった。それを Step 2 の等式に代入すると、a_0 についての 4次多項式 になる（最高次の係数がキャンセルして実質3次）。

同じ wrap 値を持つ連続ペアが複数あれば、それぞれから多項式を作れる。それらの 多項式 GCD を mod N で計算する。ただし合成数 N 上の多項式環は体ではないため、GCD が素直に1次まで落ちるとは限らない。mod p と mod q で別々の共通根を拾うと、CRT で混ざった 偽の1次因子 が出ることがある（実際このデータでは、2本の3次多項式の GCD がそのまま真の a_0 を与えず、偽根が出る）。対処は2通り：GCD の割り算途中で先頭係数と N の GCD が 1 でなくなれば N の因数が得られる（bonus。mod p / mod q で個別に解いて CRT）。因数が出ない場合は、得られた候補根で全 c_i を再構成して検証し、真の a_0 を選ぶ。

# wraps = [2, 0, 2, 0, 0, 1, 0, 1, 2, 0, 0, 1, 0]
# 同じ wrap を持つ連続ペア: (3,4) と (9,10)
# → 2 本の3次多項式が得られる
# GCD → 候補の1次因子（合成数環では偽根もあり得る）
# → 全 c_i の再構成で検証し、真の a_0 を確定

Step 4: 拡張ユークリッドで `m` を復元

a_0 = m^{e_0} mod N と、比 a_1 / a_0^3 = m^{1337 − wraps[0]·N} mod N が手に入る（以降、m は N と互いに素、すなわち可逆と仮定する。RSA のフラグでは実質確実に成り立つ）。ここで

gcd(e_0, 1337 − wraps[0]·N) = 1

が成り立てば（このインスタンスでは成立を確認済み。ランダムな e_0 に対して構造的に常に保証されるわけではないが、成り立つ場合）、拡張ユークリッドで s · e_0 + t · (1337 − wraps[0]·N) = 1 を満たす s, t を求め、

m = a_0^s · ratio^t   mod N

として平文（フラグ）を復元できる。

多項式 GCD mod 合成数 N の実装

N が合成数なので、SageMath や SymPy の標準 GCD はそのまま使えない（体ではないため逆元が常に存在するとは限らない）。ユークリッド互除法を手で実装する。割り算の途中で先頭係数と N の GCD が 1 でなくなったら、それは N の因数を掘り当てたということで、ボーナスとして factorization が得られることもある。

def poly_divmod_N(p1, p2, N):
    p1 = list(p1)
    while len(p1) >= len(p2):
        if p1[0] == 0:
            p1.pop(0); continue
        g = math.gcd(p2[0], N)
        if g != 1 and g != N:
            return "FACTOR", g        # N の因数を発見（ボーナス）
        inv = pow(p2[0], -1, N)
        coeff = (p1[0] * inv) % N
        for j in range(len(p2)):
            p1[j] = (p1[j] - coeff * p2[j]) % N
        p1.pop(0)
    return p1

これは要点を抜き出した断片で、実運用では入力を正規化済みと仮定している：係数は mod N に落とし、先頭ゼロを除去し、除数 p2 の先頭係数が 0 (mod N) でない（＝gcd(p2[0], N) == N にならない）ことを呼び出し側で保証する。ゼロ多項式や g == N の縮退ケースは別途弾く必要がある。

kalmar{GCD_is_handy_like_always}

キーインサイト

出力が「和」の形でも、交互和で隣接項を打ち消せば a_j を a_0 の線形関数に開ける。出力が整数和（各項 mod N・和は N 超え）なので交互和は厳密な整数関係になるが、後段は結局 mod N で扱うため、仮に各出力が mod N に畳まれていても線形化自体は mod N で成立する。要点は「和を線形に開けること」で、mod の有無は本質ではない。
LCG の wrap 回数が同じペアでは指数比が等しくなり、a 同士に多項式等式が立つ。LCG の決定性が拘束条件に化ける。
合成数 N 上の多項式 GCD は手実装が要る。体上と違い「2本あれば必ず1次まで落ちる」わけではなく、CRT 由来の偽根が出たり、割り算の途中で N の因数が転がり出たりする（後者は bonus）。得られた候補根は全 c_i の再構成で検証して真の a_0 を選ぶ。
gcd(e_0, 1337 − wraps[0]·N) = 1 が成り立つおかげで、拡張ユークリッドで指数を打ち消して直接 m を取り出せる。フラグの GCD_is_handy はまさにこの問題の骨子そのものだった。

概要