Fully Padded RSA
authored by yu212
eは大きいし、パディングもしてるし、絶対に安全です！
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 = }")
$e_1, e_2$と公開鍵が2つあり、$c_1,c_2$と暗号文が2つ公開されています。
これは、Common Modulus Attackが使えます。
(参考: https://zenn.dev/anko/articles/ctf-crypto-rsa)
\displaylines{c_1 = m^{e_1} \pmod n\\ c_2 = m^{e_2} \pmod n}
とありますが、ここで、$e_1, e_2$について拡張ユークリッド互除法を用いると
g = gcd(e_1, e_2) = ue_1+ve_2
となり、
m^g = m^{ue_1+ve_2} = c_1^uc_2^v \pmod n
と表すことができます。もし、$e_1, e_2$が互いに素のときか$g$が小さい場合、Low Public Exponent Attack($m^e < N$のとき、$e$乗根を取ってあげることでmが求まる攻撃)を用いることでmを求めることができます。
ということで実際にやってみましょう。
gcd(e_1,e_2) = -1013e_1+1092e_2 = 3
よって、$g=3$なので、$m^3$が取得できました。しかし、今回のmは以下の処理をしています。
padded_flag = long_to_bytes(n)[:-len(flag)] + flag.encode()
これにより、$m$の値は大きいことがわかり、$m^3 > N$となってしまいます。
解法
先ほどのパディングの処理を考えてみましょう。
これは、nのバイト列のうち下位len(flag)バイトをflagをエンコードしたバイト列の置き換えています。
$l=len(flag)$とすると、flagをエンコードしたバイト列を
\mathrm{enc(flag)} = (f_0, f_1, \dots, f_{l-1})
と表せます。
そして、nのバイト列は
\text{bytes(n)} = (n_0, n_1, \dots, n_{k-1})
となり、今回のパディング処理からpadded_flagは
\text{enc(flag)} = (n_0, n_1, \dots, n_{k-l-1}, f_0, f_1, \dots, f_{l-1})
となります。
今回のflagは40未満であることがわかっているため、以下のように考えられます。
\text{enc}(\text{flag}) = (n_0, n_1, \dots, n_{k-l-1},
\underbrace{f_0, f_1, \dots, f_{l-1})}_{\leq40\ \text{bytes}}
よって、このenc(flag)を抜き出し、3乗根を計算することで、差分が求まり、それをnから引いていけば解けます。
実際、nとpadded_flagの差を$m'$とすると、求めたい平文$m$は
m = n-m'
と書けます。このとき
m^3 \equiv (n-m')^3 equiv -m'^3 \pmod n
となるため、$m^3 \pmod n$を$m_3$とおくと
m'^3 \equiv -m_3 \equiv n-m_3 \pmod n
さらに、$m'^3 < n$が成立するため
m'^3 = n - m_3
が成立します。以上より、$m'^3$の3乗根を計算して$m'$を求め、$m = n - m'$とすることで平文を復元できます。
これを実装すると以下になります。
from sympy import *
from Crypto.Util.number import long_to_bytes
n = 91102717210596990388603678426683097953697889897819753293818443119019220403217013812232251320814152567699322671590559119510246139859891156830672838769529887961956970370968572962306584295059185945752892892100975462391203805852473243296747559459800718013816237662990504689724747628304890125129146326331097856907
c1 = 84316690833236468829386139306045298111202426584048821548102362931269993141514516100633466389955824290011995159677864206138653174440904170622039293036862729884826231898868928186453091113165643576890891297150845933751243965934735328928976655465009980896153972226679588496970771925581698573227941539852081781874
c2 = 74682069306151159606579889187354529286195652598555930926994495384029865435810129236911316774977007932641783161876484392995815937986886903514990618178943843429073696833993271982336114314882872652681858748846455760309012235191324385691614015531641062111894149446939460102878320469041435024347449132388644171970
def modexp(base, exp, mod):
if exp >= 0:
return pow(base, exp, mod)
base_inv = invert(base, mod)
return pow(base_inv, -exp, mod)
e1 = 65517
e2 = 65577
g = gcd(e1, e2)
assert g == 3
e1p = e1 // g
e2p = e2 // g
u, v, g2 = gcdex(e1p, e2p)
u = int(u)
v = int(v)
assert g2 == 1
m1 = modexp(c1, u, n)
m2 = modexp(c2, v, n)
m3 = (m1 * m2) % n
t3 = n - m3
t, exact = integer_nthroot(t3, 3)
m = n - t
flag = long_to_bytes(m)
## 綺麗にするため書く
prefix = b"Alpaca{"
start = flag.rfind(prefix)
end = flag.find(b"}", start)
print(flag[start:end + 1].decode("utf-8"))
Flag: Alpaca{p4dd1n6_mu57_u53_r4nd0m_v41u3s}
解法2
未知のflagを整数$x$として考えてみましょう。
すると、$m$は
m(x) = \text{Prefix} ・256^{L} + x
と表せます。ただし、$L \leq 40$です。
これを用いて、多項式
f(x) = m(x)^3 - m_3 \equiv 0 \pmod n
を立て、Coppersmithで解けばフラグが出てきます。
今回cusoを使いました。
from sympy import gcd, gcdex, invert
from Crypto.Util.number import long_to_bytes, bytes_to_long
from sage.all import *
import cuso
n = 91102717210596990388603678426683097953697889897819753293818443119019220403217013812232251320814152567699322671590559119510246139859891156830672838769529887961956970370968572962306584295059185945752892892100975462391203805852473243296747559459800718013816237662990504689724747628304890125129146326331097856907
c1 = 84316690833236468829386139306045298111202426584048821548102362931269993141514516100633466389955824290011995159677864206138653174440904170622039293036862729884826231898868928186453091113165643576890891297150845933751243965934735328928976655465009980896153972226679588496970771925581698573227941539852081781874
c2 = 74682069306151159606579889187354529286195652598555930926994495384029865435810129236911316774977007932641783161876484392995815937986886903514990618178943843429073696833993271982336114314882872652681858748846455760309012235191324385691614015531641062111894149446939460102878320469041435024347449132388644171970
len_flag = 40
def modexp(base, exp, mod):
if exp >= 0:
return pow(base, exp, mod)
base_inv = invert(base, mod)
return pow(base_inv, -exp, mod)
e1 = 65517
e2 = 65577
g = gcd(e1, e2)
assert g == 3
e1p = e1 // g
e2p = e2 // g
u, v, g2 = gcdex(e1p, e2p)
u = int(u)
v = int(v)
assert g2 == 1
m1 = modexp(c1, u, n)
m2 = modexp(c2, v, n)
m3 = (m1 * m2) % n
n_bytes = long_to_bytes(n)
prefix_bytes = n_bytes[:-len_flag]
Prefix = bytes_to_long(prefix_bytes)
x = var('x')
m_poly = Prefix * (1 << (8 * len_flag)) + x
f = m_poly**3 - int(m3)
relations = [f]
bounds = {
x: (0, 1 << (8 * len_flag))
}
roots = cuso.find_small_roots(
relations,
bounds,
modulus=n,
)
assert len(roots) > 0
root = roots[0]
x_val = int(root[x])
print(f"flag:{long_to_bytes(x_val).decode()} ")