## 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).## 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).