LoginSignup
0

vsCTF Redundancy Writeup

Posted at

概要

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("}")

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0