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