CTFZone 2024-she's the real one • Swizzer's Sound

chall.py

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]))

python

先来看下输出：

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))

python

题目其实是在实数域上的一条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：

solve.py

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))

python

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

不懂，感觉很玄学（