ctf upsolve by kodai Advent Calendar 2025（Day9）

今日はDaily AlpacaHackでLLMと対話して解いた問題をしっかり理解するために、upsolveします。
Cryptoも初心者なのでいろいろ調べながら書きます。ChatGPTと対話しながら書いてます。
おかしなところがあれば教えて下さい。
Yuさんの作問者writeupも参考にさせていただきながら書いてます。
また少し遅れてしまいました。

取り扱った問題

Daily AlpacaHack Fully Padded RSA
Author: Yu212

---

upsolve

コードが与えられます。
これとは別にoutput.txtが与えられており、nとe1, e2が書かれています。

import os
from Crypto.Util.number import *
from math import gcd

flag = os.environ.get("FLAG", "Alpaca{dummy}")
assert len(flag) <= 40

e1 = 65517
e2 = 65577
while True:
    p = getPrime(512)
    q = getPrime(512)
    if gcd((p-1)*(q-1), e1) == gcd((p-1)*(q-1), e2) == 1:
        break
n = p * q

padded_flag = long_to_bytes(n)[:-len(flag)] + flag.encode()
m = bytes_to_long(padded_flag)
assert m < n
c1 = pow(m, e1, n)
c2 = pow(m, e2, n)

print(f"{n = }")
print(f"{c1 = }")
print(f"{c2 = }")

このRSA暗号では同一の平文を同一のnで、異なるeを使って暗号化された暗号文が与えられています。
この実装だと、Common Modulus Attackができてしまうようです。

引用元
https://zenn.dev/anko/articles/ctf-crypto-rsa

あんこさんの記事によると、異なるeで暗号化するとユークリッドの互除法の互除法を用いて、より小さなeの暗号文を作れて解読できてしまうらしいです。

$$
\begin{aligned}
c_1 &= m^{e_1} \ (mod\ N) \\
c_2 &= m^{e_2} \ (mod\ N)
\end{aligned}
$$
$e_1, e_2$ について拡張ユークリッドの互除法を用いて $g = \gcd(e_1, e_2)$ となります。

$$
\begin{aligned}
g = \gcd(e_1, e_2) = s_1 e_1 + s_2 e_2 \\
m^g = m^{s_1 e_1 + s_2 e_2} = c_1^{s_1} c_2^{s_2} \ (mod\ N)
\end{aligned}
$$
$e_1, e_2$が互いに素であるとき、またはgが小さいならばLow Public Exponent Attackを用いてmを求められます。

今回の問題では、e1=65517, e2=65577になっています。
今回はこれらについて拡張ユークリッドの互除法を使っていきます。

$g=gcd(e_1, e_2) = gcd(65517, 65577) = 3 = -1093e_1 + 1092e_2$
$m^g = m^{-1093 e_1 + 1092 e_2} = c_1^{-1093} ・ c_2^{1092} \ (mod\ N)$

今回は$e_1, e_2$が互いに素であるときflagをゲットできますが、今回はg=3なので$m^3$になり、Low Public Exponent Attackを使ってmを特定することができます。

ここでLow Public Exponent Attackについてあんこさんの記事で確認してみます。

$e$が小さいとき、$m^e$ < N となって累乗根を取ればそのまま平文になることがあります。

しかし今回の問題ではmの値がパディングによって大きな値となってしまっているので、そのままmを特定するのは難しそうです。

padded_flag = long_to_bytes(n)[:-len(flag)] + flag.encode()
m = bytes_to_long(padded_flag)

今回のflagの形を見てみます。
long_to_bytes(n) は「n を big-endian の最短バイト列にしたもの」です。
n は 1024bit (512bit の素数 p,q の積) なので、だいたい 128 バイト（= 1024 / 8）
例えば len(flag) = 32 だったとすると、

long_to_bytes(n) = [ B0 B1 B2 ... B(127) ]  (128 bytes)
padded_flag      = [ B0 B1 ... B(95) ] + FLAG(32 bytes)

みたいな感じで、
上位 96 バイトは「n の頭の部分そのまま」
下位 32 バイトだけ FLAG に差し替えという構造になります。
バイト列を整数と見なすときは big-endian なので、
$m = (\text{prefix_int}) \cdot 256^{Lf} + x$と書くことができます。

• prefix_int: prefix_bytesを整数にしたもの
• x: flag_bytesを整数にしたもの
• $0≤x<256^{Lf}$

256 は $2^8$なので、x のビット長はだいたい$8L_f$bitになります。

assert len(flag) <= 40

となっている通り、$L_f <= 40$なので、xの値は高くなっても320bitになります。
nは1024bitです。

これらの情報を整理すると以下のようにまとめることができます。
$c_1^{-1093} ・ c_2^{1092} = M3$とおくと
$M3 ≡ (p * 2^{8L_f} + x)^3$が成り立ちます。
これを関数として定義した場合、
$f(x) = (p * 2^{8L_f} + x)^3 - M3 ∈ Z_n[x]$ となり、
$ f(x) ≡ 0 (mod n)$ を満たす小さい整数xを探すという問題に帰着します。

ここで
$N = n$ は 1024bit であるため、$N \approx 2^{1024}$
また、$f(x)$ の次数は 3（$m^3$ だから）となります。

したがって、
$N^{1/3} \approx 2^{1024/3} \approx 2^{341}$

ここで、$x$ は「フラグの整数」であり、最大でも 320bit（$2^{320}$）になります。

よって、$x$ は $N^{1/3}$ より十分小さい ため、
Coppersmith の求める条件を満たしていることになります。

上記から分かったことをもとにsolverを書きます。SageMathを使いました。

#!/usr/bin/env sage
import re

with open("output.txt", "r") as f:
    text = f.read()

def extract_int(name):
    m = re.search(rf"{name}\s*=\s*(\d+)", text)
    if not m:
        raise ValueError(f"{name} not found in output.txt")
    return Integer(m.group(1))

n  = extract_int("n")
c1 = extract_int("c1")
c2 = extract_int("c2")

print("[+] Loaded parameters")
print("  n  =", n)
print("  c1 =", c1)
print("  c2 =", c2)

e1 = Integer(65517)
e2 = Integer(65577)

g, s, t = xgcd(e1, e2)
print(f"[+] gcd(e1, e2) = {g}")
if g != 3:
    print("[!] Warning: gcd(e1,e2) is not 3, this script assumes it is 3")

def pow_mod_with_neg(base, exp, mod):
    base = Integer(base)
    mod  = Integer(mod)
    if exp >= 0:
        return power_mod(base, exp, mod)
    else:
        inv = inverse_mod(base, mod)
        return power_mod(inv, -exp, mod)

m3 = (pow_mod_with_neg(c1, s, n) * pow_mod_with_neg(c2, t, n)) % n
print("[+] Computed m^3 mod n")

nb_len = (n.nbits() + 7) // 8
n_bytes = int(n).to_bytes(nb_len, "big")

print(f"[+] n has {nb_len} bytes")

ZmodN = Zmod(n)
M3 = ZmodN(m3)

PR = PolynomialRing(ZmodN, "x")
x = PR.gen()

candidates = []

max_flag_len = 40

for Lf in range(1, max_flag_len + 1):
    if Lf >= nb_len:
        continue

    prefix_bytes = n_bytes[:-Lf]
    prefix_int   = Integer(int.from_bytes(prefix_bytes, "big"))

    shift = 8 * Lf
    Xbound = 2 ** shift

    f = (prefix_int * 2**shift + x)^3 - M3

    print(f"[+] Trying flag length = {Lf} (small_roots bound X = 2^{shift})")
    
    roots = f.small_roots(X=Xbound, beta=1/3)

    if not roots:
        continue

    for r in roots:
        xv = int(r)
        fb = xv.to_bytes(Lf, "big", signed=False)

        try:
            txt = fb.decode("utf-8", errors="replace")
        except Exception:
            txt = repr(fb)

        print(f"  [*] Found root for L = {Lf}: {fb}  (as text: {txt})")
        candidates.append((Lf, fb, txt))

print("\n===== Summary of candidates =====")
if not candidates:
    print("No candidates found. Maybe parameters or output.txt are different?")
else:
    for Lf, fb, txt in candidates:
        print(f"[L={Lf}] bytes={fb}  text={txt}")

FLAG : Alpaca{p4dd1n6_mu57_u53_r4nd0m_v41u3s}