概要
9/24(日)の夜、暇だったのでvsCTFに1時間ちょいくらい出て、1問だけCryptoの問題を解いたのでそのWriteupをここに書きました。マイナー(たぶん)なCTFかつ問題が簡単めなので需要は少なそうですが、Writeupを書く練習だと思って書きました。
Redundancy
以下のファイルが与えられる。flagを求めよ。
chall1.py
from flag import flag
from Crypto.Util.number import getPrime as gP
e1, e2 = 5*2, 5*3
assert len(flag) < 16
flag = "Wow good job the flag is (omg hype hype): vsctf{"+flag+"}"
p = gP(1024)
q = gP(1024)
n = p * q
m = int.from_bytes(flag.encode(), 'big')
c1 = pow(m, e1, n)
c2 = pow(m, e2, n)
print(f"n = {n}")
print(f"c1 = {c1}")
print(f"c2 = {c2}")
output.txt
n = 17017748438705066485980265610504973941689507158214048907934864053951824889071064601073910857498716466379300399394556852943447842816066237762975759146067603346932655815765634166764048084180474131701931383171349451845316534710526574012912735473043515230467907689465656893004952933482461926380363467891367371320920210649076831336026531060035987624376755145919230635976854094060401025222767306359467726378382365555864913880755980365664883663551789406674211837707988941852191026959073337595157795634757323135639457679829852893808412935293002447739900499953490408700913079007749683585557520473906185642328582577705062027631
c1 = 9003062544361468960014218470636404669173735044866342965869660382166263123283806177716541318605500035571883237116335008322263825288011535307210534022613104692306853206661705792651423740907471425532463013873903464958932506542067750598093825475707515378835734567383026995274504596249534287698334255122015294261751214389359548871918811764608535909122754450577618713535336693131845790212493936556686306004719501205711258082359280474173467230238314287036337126459732454648594184069081357024594728733999140381651217417997443994617467740923081974477194695681963791649774704734532274162532760702494593072786469541911070488784
c2 = 2546072448640808612556238065690407010381885201320761372614998667179031247594621466783076820338223816545993779457675793555900878984022886823043416655251600929530018123073858500887780064339665319391244085462799327306580227414809334236098388514789401395708999589289970455742049539846184453090569082144704220108709060216465897683931008575383253420528012257869329475086084346328436404376300397163706384908585243637028839505661432353166021577388901987667955042566919645080401328362001267759995517247132976744463557149680150697522052163536029888394019138507753598600096770531185804183946347241540134230811866880904134661137
特徴は、同一の平文mが異なる公開鍵eで暗号化されていることです。このことから、Common Modulus Attackを用いることができます。
Common Modulus Attack
$ c_1 = m^{e_1} \mod n$, $ c_2 = m^{e_2} \mod n $とする。
このとき、$ a = \gcd(e_1, e_2) $とすると、$ m^a \mod n$を高速に計算できる。
$ \gcd(e_1, e_2) = 1 $であることも多いので、そのまま$m$を求められる問題も多々あります。
具体的には以下のように計算します。
まず、$ e_1s_1 + e_2s_2 = \gcd(e_1, e_2) = a$となる整数$s_1, s_2$を拡張ユークリッドの互除法で求めます。
次に、
\begin{align}
c_1^{s_1}c_2^{s_2}&=(m^{e_1})^{s_1}(m^{e_2})^{s_2}\\
&= m^{e_1s_1+e_2s_2}\\
&= m^a
\end{align}
を計算することで$m^a \mod n$が出ます。
今回は、$\gcd(e_1, e_2)=5$であるため、$m^5 \mod n$が計算できます。
import gmpy2
from Crypto.Util.number import *
n = 17017748438705066485980265610504973941689507158214048907934864053951824889071064601073910857498716466379300399394556852943447842816066237762975759146067603346932655815765634166764048084180474131701931383171349451845316534710526574012912735473043515230467907689465656893004952933482461926380363467891367371320920210649076831336026531060035987624376755145919230635976854094060401025222767306359467726378382365555864913880755980365664883663551789406674211837707988941852191026959073337595157795634757323135639457679829852893808412935293002447739900499953490408700913079007749683585557520473906185642328582577705062027631
c1 = 9003062544361468960014218470636404669173735044866342965869660382166263123283806177716541318605500035571883237116335008322263825288011535307210534022613104692306853206661705792651423740907471425532463013873903464958932506542067750598093825475707515378835734567383026995274504596249534287698334255122015294261751214389359548871918811764608535909122754450577618713535336693131845790212493936556686306004719501205711258082359280474173467230238314287036337126459732454648594184069081357024594728733999140381651217417997443994617467740923081974477194695681963791649774704734532274162532760702494593072786469541911070488784
c2 = 2546072448640808612556238065690407010381885201320761372614998667179031247594621466783076820338223816545993779457675793555900878984022886823043416655251600929530018123073858500887780064339665319391244085462799327306580227414809334236098388514789401395708999589289970455742049539846184453090569082144704220108709060216465897683931008575383253420528012257869329475086084346328436404376300397163706384908585243637028839505661432353166021577388901987667955042566919645080401328362001267759995517247132976744463557149680150697522052163536029888394019138507753598600096770531185804183946347241540134230811866880904134661137
e1 = 10
e2 = 15
def extgcd(a, b):
if b == 0:
x = 1
y = 0
return a, x, y
d, y, x = extgcd(b, a%b)
y -= a//b * x
return d, x, y
d, s1, s2 = extgcd(e1, e2)
m5 = (pow(c1, s1, n)*pow(c2, s2, n))%n
さて、$m^5$の指数5は非常に小さいため、Low Public Exponent Attackが可能に思えますが、もともとの$m$が非常に大きく、したがって$m^5 \gg n$となるため、$m^5 \mod n$から$m$を求めることが難しいです。
そこで、$m$の値の大部分が分かっていることに着目します。
$m$のうち既知の部分を$m_{known}$、未知の部分を$x$とすると、方程式
$$
(m_{known} + x)^5 - m^5 \equiv 0 \mod n
$$
が成り立ちます。
xは16bit未満であることが保証されているので、これに対してCoppersmith's Methodで小さい$x$を求めることで、flagを計算できます。このとき、$m_{known}$の計算時、何ビットシフトさせるかに注意。
さっきのコードと合わせ、最終的なコードは以下。
import gmpy2
from Crypto.Util.number import *
n = 17017748438705066485980265610504973941689507158214048907934864053951824889071064601073910857498716466379300399394556852943447842816066237762975759146067603346932655815765634166764048084180474131701931383171349451845316534710526574012912735473043515230467907689465656893004952933482461926380363467891367371320920210649076831336026531060035987624376755145919230635976854094060401025222767306359467726378382365555864913880755980365664883663551789406674211837707988941852191026959073337595157795634757323135639457679829852893808412935293002447739900499953490408700913079007749683585557520473906185642328582577705062027631
c1 = 9003062544361468960014218470636404669173735044866342965869660382166263123283806177716541318605500035571883237116335008322263825288011535307210534022613104692306853206661705792651423740907471425532463013873903464958932506542067750598093825475707515378835734567383026995274504596249534287698334255122015294261751214389359548871918811764608535909122754450577618713535336693131845790212493936556686306004719501205711258082359280474173467230238314287036337126459732454648594184069081357024594728733999140381651217417997443994617467740923081974477194695681963791649774704734532274162532760702494593072786469541911070488784
c2 = 2546072448640808612556238065690407010381885201320761372614998667179031247594621466783076820338223816545993779457675793555900878984022886823043416655251600929530018123073858500887780064339665319391244085462799327306580227414809334236098388514789401395708999589289970455742049539846184453090569082144704220108709060216465897683931008575383253420528012257869329475086084346328436404376300397163706384908585243637028839505661432353166021577388901987667955042566919645080401328362001267759995517247132976744463557149680150697522052163536029888394019138507753598600096770531185804183946347241540134230811866880904134661137
e1 = 10
e2 = 15
def extgcd(a, b):
if b == 0:
x = 1
y = 0
return a, x, y
d, y, x = extgcd(b, a%b)
y -= a//b * x
return d, x, y
d, s1, s2 = extgcd(e1, e2)
m5 = (pow(c1, s1, n)*pow(c2, s2, n))%n
msg = bytes_to_long(b"Wow good job the flag is (omg hype hype): vsctf{")
for flag_len in range(1, 16):
m_known = (msg << (flag_len+1)*8) + ord("}")
P.<x> = PolynomialRing(Zmod(n))
f = (m_known + x*(1<<8)) **5 - m5
ans = f.monic().small_roots(X=2^(flag_len*8))
if len(ans) > 0:
print("vsctf{", end="")
print(long_to_bytes(int(ans[0])).decode(), end="")
print("}")