solve.py

from sage.all import *
import subprocess
from Crypto.Util.number import sieve_base
from tqdm import tqdm
from lll_cvp import solve_underconstrained_equations_general

p = 60136177367560631039092956703653203338217286978701852857028839528525260293087
q = (p - 1) // 2
y = 36460313315646730969501498120968068746377445179920045296321232935228480996523
ps = sieve_base[:23]

# for convenience, we force everything into the q-torsion subgroup
y = pow(y, 2, p)
ps = [pow(x, 2, p) for x in ps]

# generate snapshot from
# cado-nfs.py -dlp -ell 30068088683780315519546478351826601669108643489350926428514419764262630146543 target=2 60136177367560631039092956703653203338217286978701852857028839528525260293087
CADONFS_SNAPSHOT = "/tmp/cado.hyo_bv4s/p75.parameters_snapshot.0"


def solve_dlp(t):
    return int(
        subprocess.check_output(
            ["cado-nfs.py", CADONFS_SNAPSHOT, f"target={t}"], stderr=subprocess.DEVNULL
        )
        .strip()
        .decode()
    )


dlps = []
# fmt: off
dlps = [10384063090009066710531334213802121248814539639404940507198226062034802615673, 27881051888857450752556615569210841608617074548319314693597962038206779072226, 27144412581181055656565307680199321652573394819509643498431835656599895706435, 5170493848469001531224310316656767678329397702015390070406118045335790146753, 19757181344648204042557859678468466150906326118085129530975575643868986271259, 29685324688910771166622478038668843393198287948478542902692554029879480090474, 27019630770154370143040197109894398323967131340825925654293951457738366801642, 10235162233767662252777186290914469918387622753197199633544957210947454294965, 21677258589948967493242241707115163087126182017105767130038095254247262376920, 17145114574523123375127106890237510691138833390884642622173486660645678242540, 7568375225590839715113870336065350433712220490716492547966423496770590408865, 28762683945028367515845266715651058900904021100835469590573045706318711602435, 3504613131803844225651558717869089562679113708867435910449441789691549974469, 23495608440620952913938075290317081840991450828968222676335478109818700714168, 7019107810441469583535196089798469845450770130432030172106283805422943924578, 17931194450097515696697987696648775659750787071856096208369465890989082362674, 7423409733466215213976847179772777638707375638644649673258834941577139427810, 29220754588620143187357199154395824285714656335627921830513738765156205656263, 11728700227690004897744543551259798172493807548223178791055046652484647405761, 15128491581810023898131553238827554239116766533019714183090842444917265971115, 17409126547344668348064322739335411121406993183567858640422619854067776724952, 27587863909301677387617924231162224955760773602222481214982577565545538471239, 21157234182011330172360362491734565278766574940778130099700042383610656770485]
# computed using the following code
# fmt: on
for i, p in enumerate(tqdm(ps)):
    if i < len(dlps):
        continue
    dlps.append(solve_dlp(p))
    print(dlps)

dy = solve_dlp(y)
print(dy)  # 26538796780882712233621757626223610680134248177802750559887935637756806753369

xs = PolynomialRing(GF(q), "x", 23).gens()
f = vector(xs) * vector(dlps) - dy
print(f)
bounds = {x: 128 for x in xs}
for _, sol in solve_underconstrained_equations_general(q, [f], bounds):
    print(bytes(sol[:-1]))
    break