## Elliptic Curve

### Challenge

> Are all elliptic curves smooth and projective?
>
> ```
> nc 76.74.178.201 9531
> ```

### Solution

The hard part of this challenge was dealing with boring bugs when sending data to the server while resolving the proof of work. One you connected to the server and passed the proof of work, we were given the prompt

```
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+ hi! There are three integer points such that (x, y), (x+1, y), and +
+ (x+2, y) lies on the elliptic curve E. You are given one of them!! +
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
| One of such points is: P = (68363894779467582714652102427890913001389987838216664654831170787294073636806, 48221249755015813573951848125928690100802610633961853882377560135375755871325)
| Send the 37362287180362244417594168824436870719110262096489675495103813883375162938303 * P :
```

So the question is, given a single point $P$, together with the knowledge of the placement of three points, can we uniquely determine the curve?

If we assume the curve is over some finite field with prime characteristic, and that as standard this challenge uses a curve of Weierstrass form, we know we are looking for curves of the form

$$
y^2 = x^3 + Ax + B \mod p
$$

and from the knowledge of the three points we have

$$
x^3 + Ax + B = (x+ 1)^3 + A(x+1) + B = (x + 2)^3 + A(x + 2) + B \mod p
$$

We can then write down

$$
x^3 + Ax = (x+ 1)^3 + A(x+1), \quad \Rightarrow \quad A = -1 -3x - 3x^2
$$

and

$$
x^3 + Ax = (x+ 2)^3 + A(x+2), \quad \Rightarrow \quad A = -4 -6x - 3x^2
$$

as all three points are on the same curve, we have that

$$
3x^2 + 3x + 1 = 3x^2 +6x +4, \quad \Rightarrow \quad x = -1
$$

and from the above we have $x = -1 \Rightarrow A = -1$. The only thing left to do is to find $B$, which we can see is recovered from the general form of the curve.

$$
y^2 = (-1)^3 + (-1)^2 + B, \quad \Rightarrow \quad B = y^2
$$

Now we have recovered the inital point, we see that the triple of points we will be given is $(-1, y)$, $(0, y)$ and $(1,y)$. The last two of these points would be trivial to spot and we can see this isn't what the server is sending us. We can then know for certain that the given point

```
(68363894779467582714652102427890913001389987838216664654831170787294073636806, 48221249755015813573951848125928690100802610633961853882377560135375755871325)
```

is the point $(x_0, y_0) = (-1, y)$ . We can now recover the characteristic from

$$
-1 \equiv x_0 \mod p, \quad \Rightarrow \quad p = x_0 + 1
$$

and we can quickly check that

```python
sage: x0 = 68363894779467582714652102427890913001389987838216664654831170787294073636806
sage: p = x0 + 1
sage: print(p.is_prime())
True
```

With everything now understood, we can take the point given by the server, together with the given scale factor, computer the scalar multiplication and send the new point back to the server

### Implmentation

```python
import os
os.environ["PWNLIB_NOTERM"] = "True"

import hashlib
import string
import random
from pwn import *

IP = "76.74.178.201"
PORT = 9531
r = remote(IP, PORT, level="debug")
POW = r.recvline().decode().split()
x_len = int(POW[-1])
suffix = POW[-5]
hash_type = POW[-7].split('(')[0]

"""
The server asks for a random length string, hashed with a random hash
function such that the last 3 bytes of the hash match a given prefix.
"""
while True:
X = ''.join(random.choices(string.ascii_letters + string.digits, k=x_len))
h = getattr(hashlib, hash_type)(X.encode()).hexdigest()
if h.endswith(suffix):
print(h)
break

r.sendline(X)

header = r.recvuntil(b'One of such points')

points = r.recvline().split(b'P = (')[-1]
points = points.split(b', ')
px = Integer(points[0])
py = Integer(points[-1][:-2])

scale_data = r.recvline().split(b' ')
scale = Integer(scale_data[3])

p = px + 1
assert p.is_prime()
a = -1
b = (py^2 - px^3 - a*px) % p
E = EllipticCurve(GF(p), [a,b])
P = E(px,py)

Q = P*scale

"""
For some reason sending str(Q.xy()) to the server caused an error, so I
just switched to interactive and sent it myself. I'm sure it's a dumb
formatting bug, but with the annoying POW to deal with, I can't be bothered
to figure it out...
"""
# r.sendline(str(Q.xy()))
print(Q.xy())
r.interactive()
```

#### Flag

`ASIS{4n_Ellip71c_curve_iZ_A_pl4Ne_al9ebr4iC_cUrv3}`

Original writeup (https://jack4818.github.io/ASIS-Quals-2020/#elliptic-curve).