Ellipse

cryptohack

Task: a fake 'elliptic curve' Diffie-Hellman where points live on the Pell conic x^2 - D*y^2 = 1 mod p with group law Rx=P.x*Q.x+D*P.y*Q.y, Ry=P.x*Q.y+P.y*Q.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.