Daily AlpacaHack - Fully Padded RSA

2025/12/09

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

問題ソースコード

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

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

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

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))

Writeups