TSJ CTF 2022 - babyRSA

TL;DR

$n = pq$ に対して $\mathbb Z/n\mathbb Z$ 上の楕円曲線 $y^2 = x^3+px+q$ が定義され、 $x$ 座標がフラグとなる点を65537倍した点が与えられる
$p$ を法とした合同方程式を解くCoppersmith's Attackを利用して $q$ を求めて $n$ を素因数分解する
この楕円曲線の位数は法を $p,q$ とした曲線の位数の積となることからこれを計算して $e$ の逆数を計算し、元の点を復元してフラグを得る

Prerequisite

法の未知の約数を法としたCoppersmith's Attack
$\mathbb Z/n\mathbb Z$ ( $n$ は合成数)上の楕円曲線における位数

Writeup

次のスクリプトとその実行結果が与えられる。

from Crypto.Util.number import *
import os

proof.arithmetic(False)  # to make sage faster

flag = b"TSJ{not_real_flag}"

p = getPrime(1024)
q = getPrime(512)
n = p * q
e = 65537
E = EllipticCurve(Zmod(n), [p, q])

while True:
    x = ZZ(bytes_to_long(flag + os.urandom(192 - len(flag))))
    try:
        yp = ZZ(E.change_ring(GF(p)).lift_x(x).xy()[1])
        yq = ZZ(E.change_ring(GF(q)).lift_x(x).xy()[1])
        y = crt([yp, yq], [p, q])
        break
    except:
        pass

C = e * E(x, y)
print(n)
print(C.xy())

2素数 $p,q$ とその積 $n=pq$ に対して、楕円曲線 $y^2 = x^3 + px + q$ が $\mathbb Z/n\mathbb Z$ 上で定義されている。ここで、 $p$ は1024bitだが、 $q$ は512bitと大きさにバラつきがある。

この楕円曲線上の点で、フラグ(にパディングを施した値)が $x$ 座標となる点が用意され、それを $e=65537$ 倍した点 $C$ が与えられる。

まずは $p,q$ を求める事を考える。これが出来れば $\mathbb F_p$ 上の楕円曲線 $y^2 = x^3+px+q$ と $\mathbb F_q$ 上の楕円曲線 $y^2 = x^3+px+q$ を求めることが出来、この積が $\mathbb Z/n\mathbb Z$ 上での楕円曲線の位数となるから、 $e$ の逆数を求めてフラグが $x$ 座標である点を求めることが出来る。

$C = (C_x,C_y)$ とすると、 $C_y^2 \equiv C_x^3 + C_xp + q \equiv C_x^3 + q \mod p$ が成り立つ。 $q \ll p$ であるから、合同方程式 $x+C_x^3-C_y^2 \equiv 0 \mod p$ をCoppersmith's Attackを使って解くことで $q$ が得られることが期待出来る。SageMathに実装されているCoppersmith's Attack(small_roots()メソッド)ではパラメータbetaを調整することで、 $n$ の約数である値(ここでは $p,q$ )を法とした合同方程式も解くことが出来るのでこれを利用する。

beta=0.65, epsilon=1/20で解けたのでこれで $q$ が求まり、ついでに $p = n/q$ も求まったことになる。よって後はそれぞれを法として楕円曲線 $y^2 = x^3 + px + q$ の位数を求めてその積を計算し、それを法とした下での $e$ の逆数 $d$ を求める。

この $d$ によって $dC = edG = G$ が求まるのでフラグを入手出来る。ここで問題作成時にフラグを $x$ 座標に埋め込んだ点を $G$ とおいた。

Code

from Crypto.Util.number import long_to_bytes


n = 1084688440161525456565761297723021343753253859795834242323030221791996428064155741632924019882056914573754134213933081812831553364457966850480783858044755351020146309359045120079375683828540222710035876926280456195986410270835982861232693029200103036191096111928833090012465092747472907628385292492824489792241681880212163064150211815610372913101079146216940331740232522884290993565482822803814551730856710106385508489039042473394392081462669609250933566332939789
C = (1079311510414830031139310538989364057627185699077021276018232243092942690870213059161389825534830969580365943449482350229248945906866520819967957236255440270989833744079711900768144840591483525815244585394421988274792758875782239418100536145352175259508289748680619234207733291893262219468921233103016818320457126934347062355978211746913204921678806713434052571635091703300179193823668800062505275903102987517403501907477305095029634601150501028521316347448735695, 950119069222078086234887613499964523979451201727533569872219684563725731563439980545934017421736344519710579407356386725248959120187745206708940002584577645674737496282710258024067317510208074379116954056479277393224317887065763453906737739693144134777069382325155341867799398498938089764441925428778931400322389280512595265528512337796182736811112959040864126090875929813217718688941914085732678521954674134000433727451972397192521253852342394169735042490836886)
Cx, Cy = C

PR.<x> = PolynomialRing(Zmod(n))
f = x + Cx^3 - Cy^2
roots = f.small_roots(beta=0.65, epsilon=1/20)

q = int(roots[0])
assert n % q == 0
p = n // q

curve_p = EllipticCurve(GF(p), [p,q])
curve_q = EllipticCurve(GF(q), [p,q])
curve = EllipticCurve(Zmod(n), [p,q])
C = curve(C)

order = curve_p.order() * curve_q.order()
inv_e = inverse_mod(65537, order)
_C = inv_e * C
flag = _C.xy()[0]

print(long_to_bytes(flag))

Flag

TSJ{i_don't_know_how_to_come_up_with_a_good_flag_sorry}

Resources

My-CTF-Challenges/TSJ CTF 2022/babyRSA at master · maple3142/My-CTF-Challenges: 問題リポジトリ