2024 CTFZone-she's the real one-Writeup

CTFZone好难好难...肝了一天也只不过拿下这一道题。

task

from functools import namedtuple
from sage.all import *
from secret import flag

assert len(flag) == 33

Point = namedtuple("Point", ["x", "y"])
R = RealField(prec=800)
inf = Point(R(0), R(1))


def lift_x(x):
    return Point(x, sqrt(x**3 - R(3) * x - R(2)))


def add(P, Q):
    if P.x == Q.x and P.y != Q.y:
        return inf
    elif P.y == Q.y:
        raise ValueError("Points have to differ!")
    elif P == inf:
        return Q
    elif Q == inf:
        return P

    lambda_ = (P.y - Q.y) / (P.x - Q.x)

    xr = lambda_**2 - P.x - Q.x
    yr = lambda_ * (Q.x - xr) - Q.y
    return Point(xr, yr)


def double(P):
    if P == inf:
        return P

    lambda_ = (R(3) * P.x**2 - R(3)) / (R(2) * P.y)

    xr = lambda_**2 - 2 * P.x
    yr = lambda_ * (P.x - xr) - P.y
    return Point(xr, yr)


def multiply_by_scalar(P, n: int):
    if n == 0 or P == inf:
        return inf
    elif n < 0:
        return multiply_by_scalar(Point(-P.x, P.y), -n)

    R0, R1 = P, double(P)
    for b in bin(n)[3:]:
        if b == "0":
            R0, R1 = double(R0), add(R0, R1)
        else:
            R0, R1 = add(R0, R1), double(R1)
    return R0


P = lift_x(R(5.0) + R.random_element())
s = int.from_bytes(flag, 'big')
Q = multiply_by_scalar(P, s)
with open("output.dump", 'wb') as f:
    f.write(dumps([P, Q]))

先来看下输出：

output.dump

# sage
from functools import namedtuple
Point = namedtuple("Point", ["x", "y"])
P, Q = loads(open("output.dump", "rb").read())
P, Q
# (Point(x=4.85057122750390330433014774845690325940033540110422764146149706704984961847838462175367562988623210644689151060385830985493965537584825006903699918005698470402542767276523398111510174025601811323527600859249876547306988688344166390608748190, y=9.87789077496982192809140902261474042136361328873826618292731494933661532935267994217820007421649597601541657151434891797385177282719442155927874875209661909760176717387846469008534007174587603568767109138181793952471643100734778684208975367), Point(x=14.6291715870227010270603447705099642062932549788679450534625902324668696595989549084153588377210135662551306850345710441061288798249363739503554577196027351649478485916115558430512623160495597643113114945568549632790168083747304533148749256, y=-55.5422400477503792524895176160494754137265713945942105661081051205424768891166215797738467415408445726009305745975391949619787546987772117912621958687123922494608661071102641576350850861266231818560288901594219333219685647260080309129676830))

题目其实是在实数域上的一条singular curve上的ECDLP。我们知道singular curve只会是cusp(三重根)或node(二重根)。对于本题而言，曲线其实是\(y^{2}=x^{3}-3x-2=(x+1)^{2}(x-2)\)，是node(二重根)，所以有个homomorphism可以把ECDLP转化到DLP：

\[\phi: E\left(\mathbb{R}\right) \rightarrow K^{\times}(x, y) \mapsto \frac{y+\sqrt{\alpha-\beta}(x-\alpha)}{y-\sqrt{\alpha-\beta}(x-\alpha)},\alpha=-1,\beta=2\]

这题中\(\mathbb{K}=\mathbb{C}\)，sagemath没有可以直接解决其上的DLP的函数。记\(\phi(P)^{m}=\phi(Q)\),则\(m = \frac{ln(\phi(Q))}{ln(\phi(P))}\)。不过因为复对数函数是多值函数，所以实际的m对应的分子/分母上是要加上\(2k\pi\)的，因此没办法直接从这个式子计算得到m。

不过总之我们有\(ln(\phi(Q))-mln(\phi(P))+k\pi=0\)，所以还是可以考虑LLL求解。这里反而困扰了我一段时间，因为赛场上最初构造的格乘上的系数太大，出不来flag：

from sage.all import *
R = RealField(prec=800)

alpha = -1
beta = 2
def hom(x,y):
    div = y+sqrt(alpha-beta)*(x-alpha)
    todiv = y-sqrt(alpha-beta)*(x-alpha)
    return div/todiv

P = (R(4.85057122750390330433014774845690325940033540110422764146149706704984961847838462175367562988623210644689151060385830985493965537584825006903699918005698470402542767276523398111510174025601811323527600859249876547306988688344166390608748190), R(9.87789077496982192809140902261474042136361328873826618292731494933661532935267994217820007421649597601541657151434891797385177282719442155927874875209661909760176717387846469008534007174587603568767109138181793952471643100734778684208975367))
Q = (R(14.6291715870227010270603447705099642062932549788679450534625902324668696595989549084153588377210135662551306850345710441061288798249363739503554577196027351649478485916115558430512623160495597643113114945568549632790168083747304533148749256), R(-55.5422400477503792524895176160494754137265713945942105661081051205424768891166215797738467415408445726009305745975391949619787546987772117912621958687123922494608661071102641576350850861266231818560288901594219333219685647260080309129676830))
print(ln(hom(P[0],P[1]).n(800)))
print(ln(hom(Q[0],Q[1]).n(800)))

"""
stage 2
"""
from Crypto.Util.number import long_to_bytes

lnA = 1.5963399904427224116173827067870805565590340871250159532480571882126644527245944378708607087469070702562689993080725487929823685075110225872715830601783644029979376992010083200663415416743039753924899188724496117733386312004922854550327233
lnB = -0.90701142842631779866989635451465989740748171137396031502748236138314098068314071068047683347370914363484552270097028805338972038604958239411917951278259144793574361613789650347897002759119665062755502665641658407547473699916261636571633561


R = RealField(prec=800)
pi = R(pi)


Ge = Matrix(QQ,[[2^528,0,2^528*lnB],[0,1,-2^528*lnA],[0,0,2^528*2*pi]])
ans = int(abs(Ge.LLL()[-1][1]))
print(long_to_bytes(ans))

最初格子里的\(2^{528}\)取的是\(2^{2048}\)，一直出不来；最后把系数调小到\(2^{528}\)反而就有了...

不懂，感觉很玄学（