The Elliptic Curve Discrete Logarithm Problem (ECDLP) is the problem of finding an integer $n$ such that $Q = [n]P$.

Like we encountered with the discrete logarithm problem, scalar multiplication of a point in $E(\Fp)$ seems to be be a hard problem to undo, with the most efficient algorithm running at $q^{1/2}$ time when $P$ generates a subgroup of size $q$.

This makes it a great candidate for a trapdoor function.

Alice and Bob are talking and they want to create a shared secret so they can start encrypting their messages with some symmetric cryptographic protocol Alice and Bob don't trust their connection, so they need a way to create a secret others can't replicate.

To start thing off, Alice and Bob agree on a curve $E$, a prime $p$ and a generator point $G$ which generates a subgroup $H = \langle G \rangle$ of prime order $q$

In elliptic curve cryptography, it is important that the order of $G$ is prime. Constructing secure curves is complicated and it is recommended to use a preconstructed curve where a client is given the curve, the prime and the generator to use.

The Elliptic Curve Diffie-Hellman Key Exchange goes as follows:

• Alice generates a secret random integer $n_A$ and calculates $Q_A = [n_A]G$
• Bob generates a secret random integer $n_B$ and calculates $Q_B = [n_B]G$
• Alice sends Bob $Q_A$, and Bob sends Alice $Q_B$. Due to the hardness of ECDLP, an onlooker Eve is unable to calculate $n_{A/B}$ in reasonable time.
• Alice then calculates $[n_A]Q_B$, and Bob calculates $[n_B]Q_A$.
• Due to the associativity of scalar multiplication, $S = [n_A]Q_B = [n_B]Q_A$.
• Alice and Bob can use $S$ as their shared secret.


Using the curve, prime and generator:

$E: Y^{2} = X^{3} + 497 X + 1768 \mod 9739, \quad G: (1804,5368)$

Calculate the shared secret after Alice sends you $Q_A = (815, 3190)$, with your secret integer $n_B = 1829$.

Generate a key by calculating the SHA1 hash of the $x$ coordinate (take the integer representation of the coordinate and cast it to a string). The flag is the hexdigest you find.

This curve is not cryptographically secure!! We've picked a small prime for these starter challenges to keep everything fast while you learn. Cryptographically secure curves have primes of bit size ≈ 256