https://yu212.hatenablog.com/entry/2025/12/09/000014

Daily AlpacaHackという毎日0時に1題ずつ公開される常設CTFの8日目の問題、「Fully Padded RSA」の作問を担当したので、公式writeupを書きます。当日に解けた方も解けなかった方もぜひ復習に利用していただけると嬉しいです。

初心者向けCTFということで、Crypto分野で最初の一歩として登場するRSAでよく出題される攻撃を題材にしました。一方で複数の攻撃方法を組み合わせたり少しひねったりしたことで、ただ既知の攻撃方法を実装するだけというのは避けて、中級者にも楽しめる難易度にしたつもりです。

alpacahack.com

問題ソースコードは以下の通り。

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の問題においてよく出題される攻撃手法が列挙されている。

zenn.dev

今回の問題に適用できる攻撃がないか調べてみると、以下が該当する。

Common Modulus Attack
同一の平文を同一の $N$ 異なる $e$ で暗号化した暗号文を与えてはいけない

この攻撃を適用すると、より小さな $e$ の暗号文を作ることができる。実際に適用してみよう。
今回の問題では、e1 = 65517, e2 = 65577となっている。これらについて、拡張ユークリッドの互除法を適用する。

実際に計算すると、
$\mathrm{gcd}(e_1, e_2) = 3 = -1093 e_1 + 1092 e_2$ という式が得られる。
これを使って、 $m^g = m^{-1093 e_1 + 1092 e_2} = c_1^{-1093} c_2^{1092} \pmod n$ という形で $m^g$ の値が計算できる。
e1とe2が互いに素だった場合はこれだけで $m^1$ 、つまりフラグが得られるが、今回は最小公倍数 $g$ が3なため、 $m^3$ が得られた。

再度攻撃可能なケースのリストを見てみると、 $m^3$ の値が計算できたことから、以下の状況に合致する。

Low Public Exponent Attack
公開鍵 $e$ が小さすぎてはいけない

これは、 $m^e < n$ という条件を満たす場合に直接 $m^e$ の $e$ 乗根を計算することによって $m$ の値が計算出来てしまうという攻撃だ。しかし、これは今回の問題には直接は適用できない。 $m$ の値がパディングによって大きな値となっているためだ。
パディングはflagの前にnと同じビット列を結合することによって計算されている。これだと $m$ と $n$ は上位bitが完全に一致し、 $m$ が $n$ と非常に近い値になることとなる。実際に手元で $m$ と $n$ の値を計算して出力してみると、 $m$ が $n$ より少し小さい値になっていることがわかる。

n = 0x5080c9faff634e8018c4a6c367b257fad5cb95797a00c663b277af51926b72b41f0aebf8b8d7760842c3b3be9d28da7b50c173deb2017f7c733fa0442ee298a4721311168af7fca9f21d1673d2a64c8948c3e57befad0fff4cb991dedd05f7bf2d9eb3d7803344b6adb5a768bd47b825395c7630f4c3ce665b2dc315665de735
m = 0x5080c9faff634e8018c4a6c367b257fad5cb95797a00c663b277af51926b72b41f0aebf8b8d7760842c3b3be9d28da7b50c173deb2017f7c733fa0442ee298a4721311168af7fca9f21d1673d2a64c8948c3e57befad0fff4cb991dedd05f7bf2d9eb3d7803344b6adb5a768bd47b825395c76416c706163617b64756d6d797d

この $m$ と $n$ の差を $m'$ とすると、 $m = n-m'$ という式が立つ。すると、 $m^3 = (n-m')^3 = -m'^3 \pmod n$ となることから、 $n-m^3 = m'^3$ 、つまり $n-m^3$ が $m'$ の暗号文となることがわかる。
$m'$ はフラグが40byte以下という制約から320bit程度のかなり小さい値となる。 $n$ は1024bitなので、Low Public Exponent Attackが成立する条件である $m^e < n$ を満たす。よって、 $n-m^3$ の3乗根を計算すれば、 $m'$ の値が求まり、そこから $m$ の値も求めることができる。

ソルバの全体は以下の通り。
拡張ユークリッドの互除法は自分で実装してもいいが、SageMathのxgcd関数や、gmpy2のgcdext関数を利用すると簡単に計算できる。
同様に、3乗根を求めるのにはgmpy2のiroot関数を使うと簡単。int(x**(1/3))のような方法だと精度の問題で正しく計算できないので注意。

from Crypto.Util.number import long_to_bytes
from gmpy2 import gcdext, iroot

n = ...
c1 = ...
c2 = ...

g, x, y = gcdext(65517, 65577)
c = pow(c1, x, n) * pow(c2, y, n) % n
m_dash, _ = iroot(n-c, 3)
m = n-m_dash
print(long_to_bytes(m))

LLMと対話して解いた人や、中級者以上の人の中には、この問題をCoppersmith methodというアルゴリズムを使って解いた方もいるかもしれません。実際、今回説明した方法よりも難しいですが、Coppersmith methodを使うことも想定解法の一つでした。実はこの方法では、パディングがlong_to_bytes(n)[:-len(flag)]でなくても、既知の（攻撃者が計算できる）値であれば解くことが出来ます。