# TP Advanced crypto - Elliptic curves

## Notations

$\mathcal O$ is the point to the infinity

## Answers

**1.**
Implemented as `fp_inverse` in `ecc.py`. It uses the builtin modular exponentiation of python.

**2.**
Implemented as `EllipticCurve.is_on_curve` in `ecc.py`.

**3.**

Implemented as `EllipticCurve.double_point` in `ecc.py`.

**4.**

Implemented as `EllipticCurve.add_point` in `ecc.py`.

**5.**

Implemented as `EllipticCurve.scalar_mul` in `ecc.py`.

**6.**

This is implemented in a separate file, `test_dh.py` .

**7.** The method `EllipticCurve.is_on_curve` tells us that $P = (x,y)$ is indeed on the curve _secp256k1_

**8.** Thanks to our method `EllipticCurve.scalar_mul`, we find that $oP = \mathcal O$

**9.** We use `sage` to verify if $o$ is a prime number

> o = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
> o.is_prime()
True

We could also have used a simple primality test such as Fermat's.

**10.** As $oP = \mathcal{O}$, the order of $P$ has to divide $o$. However, $o$ is prime, so the order of $P$ is $o$.

**11.** Already what we did for the previous question

## Tests

We use the curve defined by the (short) Weierstrass equation $Y^2 = X^3 + 3$ over $\mathbb{F}_7$ and the point $P = (2,2)$.

You can find all the tests, implemented using `assert`, in the file `ecc.py`