Marginally More Spooky ECC

Now marginally more spooky!

intercept.txt

problem.sage

We are given intercept.txt and problem.sage, which are some data the challenge script.

Description

This implements an elliptic curve key distribution algorithm, and the curve has quite a interesting property, E_order = N. This allows us to use the smart attack.

Smart attack

The main idea about this is to lift the curve from mod N to mod N^2, and ECC multiplication becomes an additive group. More detail is in the paper about smart attack here

Derivation of Hensel lifting

Here is just a short derivation of Hensel lifting for this particular case.

Let $f (y) = y^{2} - k$ where $k$ is given by $x^{3} + a x + b$ . Let’s say we found a root of $f (y) (\mod p)$ , then we can find a root, with $s = y (\mod p)$ and $f (s) = 0 (\mod p^{2})$ .

Since $y^{2} - k = 0 (\mod N), y^{2} - k = r N (\mod N^{2})$

$f (y + a N) = y^{2} - k + 2 y a N = (r + 2 y a) N = 0 (\mod N^{2})$

Since we just need to find $a$ , we get $r + 2 y a = 0 (\mod N)$ and $a = - \frac{r}{2 y} = - \frac{y^{2} - j}{2 y N} (\mod N)$ .

The division of $N$ is well defined since $y^{2} - k = 0 (\mod N)$ .

Flag: hsctf{Y_does_4lice_have_such_weird_cuRV3s?}