Ellipse

Platform: cryptohack | Category: Crypto | Type: Challenge | Difficulty: Medium | OS: NA | Author: XESXOR | Date: 2026-06-22 | Status: Solved Techniques: dlp_in_fp_star, pell_conic_to_field_isomorphism, pohlig_hellman, shared_secret_recovery

Summary

Task: a fake 'elliptic curve' Diffie-Hellman where points live on the Pell conic x^2 - Dy^2 = 1 mod p with group law Rx=P.xQ.x+DP.yQ.y, Ry=P.xQ.y+P.yQ.x. Solution: because D=529=23^2 is a perfect square, the conic group is isomorphic to F_p* via the map (x,y) -> u = x + sqrt(D)y; scalar multiplication becomes u^n, so recover Alice's private key by a discrete log of u_A base u_G in F_p (p-1 is smooth -> Pohlig-Hellman), compute the shared secret u_B^{n_a}, invert the map to get x, and AES-CBC decrypt the flag.

Ellipse — cryptohack (Mathematics)

Description

"I overheard my professor talking about ellipse curve cryptography. I tried googling it, but didn't find anything so I implemented it myself."

Files: source.py, output.txt.

The scheme defines a custom group on points satisfying x^2 - D*y^2 == 1 (mod p) with:

 python read-only • copy allowed Copy
def point_addition(P, Q):
    Rx = (P.x*Q.x + D*P.y*Q.y) % p
    Ry = (P.x*Q.y + P.y*Q.x) % p
    return Point(Rx, Ry)

p = 173754216895752892448109692432341061254596347285717132408796456167143559
D = 529
G = Point(29394812077144852405795385333766317269085018265469771684226884125940148,
          94108086667844986046802106544375316173742538919949485639896613738390948)

‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

It runs a Diffie-Hellman: Alice and Bob publish A = n_a·G, B = n_b·G; the shared secret is (n_a·B).x, used as an AES-CBC key (SHA1-derived) over the flag.

Analysis

This is not an elliptic curve — it is the Pell conic x^2 - D y^2 = 1. The given group law is exactly multiplication in the ring Z/p[√D]:

(x1 + y1·√D)(x2 + y2·√D) = (x1·x2 + D·y1·y2) + (x1·y2 + y1·x2)·√D

So each point (x, y) corresponds to the element u = x + y·√D, and point_addition corresponds to multiplication of these elements. Scalar multiplication n·P corresponds to u^n. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

The key observation: D = 529 = 23^2 is a perfect square mod p. Therefore √D = 23 exists in F_p, and the conic "splits": the map

φ(x, y) = x + 23·y  (mod p)

is a group isomorphism from the conic group onto a subgroup of F_p*. (The norm x^2 - D y^2 = (x+√D y)(x-√D y) = 1 means x - 23y = φ(x,y)^{-1}.)

Under φ, the whole ECDLP collapses into an ordinary discrete log in F_p*, which is easy because p - 1 is smooth (all prime factors ~30 bits) → Pohlig-Hellman.

p - 1 = 2 · 671619593 · 710437279 · 988228543 · 813892307 · 739003417
            · 657631441 · 821078411 · 567307171

‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Solution

1. Map G, A, B to F_p*: u = x + 23·y mod p.
2. Recover Alice's private key: n_a = dlog_{u_G}(u_A) (Pohlig-Hellman via sympy.discrete_log).
3. Shared secret element: u_s = u_B^{n_a} mod p.
4. Invert the map: from u_s = x + 23y and x - 23y = u_s^{-1}, get x = (u_s + u_s^{-1})/2 mod p. The shared secret is this x.
5. Derive the AES key sha1(str(x)).digest()[:16] and decrypt the CBC ciphertext.

 python read-only • copy allowed Copy
import sympy
from sympy.ntheory.residue_ntheory import discrete_log
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
from hashlib import sha1
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

p = 173754216895752892448109692432341061254596347285717132408796456167143559
r = 23  # sqrt(D), D = 529
Gx, Gy = (29394812077144852405795385333766317269085018265469771684226884125940148,
          94108086667844986046802106544375316173742538919949485639896613738390948)
Ax, Ay = (155781055760279718382374741001148850818103179141959728567110540865590463,
          73794785561346677848810778233901832813072697504335306937799336126503714)
Bx, By = (171226959585314864221294077932510094779925634276949970785138593200069419,
          54353971839516652938533335476115503436865545966356461292708042305317630)
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

uG, uA, uB = (Gx + r*Gy) % p, (Ax + r*Ay) % p, (Bx + r*By) % p
na = discrete_log(p, uA, uG)              # Pohlig-Hellman; p-1 is smooth
us = pow(uB, na, p)                        # shared secret element
inv = pow(us, -1, p)
x = (us + inv) * pow(2, -1, p) % p         # invert phi -> shared secret x

key = sha1(str(x).encode()).digest()[:16]
iv  = bytes.fromhex('64bc75c8b38017e1397c46f85d4e332b')
ct  = bytes.fromhex('13e4d200708b786d8f7c3bd2dc5de0201f0d7879192e6603d7c5d6b963e1df2943e3ff75f7fda9c30a92171bbbc5acbf')
print(unpad(AES.new(key, AES.MODE_CBC, iv).decrypt(ct), 16))

‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Output:

b'crypto{REDACTED}'

‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍