Elliptic Curve Cryptography (ECC) is an asymmetric cryptographic protocol that, like RSA and Diffie-Hellman (DH), relies on a trapdoor function. To recap: trapdoor functions allow a client to keep data secret by performing a mathematical operation which is computationally easy to do, but currently understood to be very expensive to undo.

For RSA, the trapdoor function relies on the hardness of factoring large numbers. For Diffie-Hellman, the trapdoor relies on the hardness of the discrete log problem in a finite field. For both RSA and DH, the operations that run through the veins of the protocol are familiar to us. Multiplying numbers and taking powers of numbers are things we are taught to do in school. ECC stands out, because the group operation in ECC won't pop up in your life unless you are looking for it.

This discussion here will not be total, and those who are really looking to understand ECC, I recommend these notes Elliptic Curve notes by Ben Lynn, and the textbook "An Introduction to Mathematical Cryptography", Jeffrey Hoffstein, Jill Pipher, Joseph H. Silverman.

Let's start thinking about ECC by looking at what we mean by an elliptic curve. We will be studying Weierstrass equations, which are of the form

$E : Y^{2} = X^{3} + a X + b$

Elliptic curves have an amazing feature: we can define an operator that we will call "point addition". This operator takes two points on some curve and produces a third point on the curve. Taking the set of points on an elliptic curve, point addition defines an Abelian group operation.

There's a lot of text here. Let's motivate this! We can understand scalar multiplication of a point as the repeated point addition of the same point. $Q = [2]P = P + P$. It turns out that scalar multiplication is a trapdoor function! ECC relies on the hardness of finding the $n$ such that $Q = [n]P$ given $Q$ and $P$.

So how do we understand point addition?

Geometrically, we can understand point addition $P + Q$ like so. Take an elliptic curve and mark the two points $P, Q$ along the curve with their $x,y$ coordinates. Draw a straight line that passes through both points. Now continue the line until it intersects your curve a third time. Mark this new intersection $R$. Finally, take $R$ and reflect it along the $y$ direction to produce $R' = R(x,-y)$. The result of the point addition is $P + Q = R'$

What if we want to add two of the same point together: $P + P$? We can't draw a unique line through one point, but we can pick a unique line by calculating the tangent line to the curve at the point. Calculate the tangent line at the point $P$. Continue the line until it intersects with the curve at point $R$. Reflect this point as before: $P + P = R' = R(x,-y)$.

What happens if there is no third intersection? Sometimes you will pick two points $P, Q$ and the line will not touch the curve again. In this case we say that the line intersects with the point ($O$) which is a single point located at the end of every vertical line at infinity. As such, point addition for an elliptic curve is defined in 2D space, with an additional point located at infinity.

Included below is a diagram as a visual aid to these different cases

The point $O$ acts as the identity operator of the group: $P + O = P$ and $P + (-P) = O$.

This brings us to the point of defining an elliptic curve.

Definition: An elliptic curve $E$ is the set of solutions to a Weierstrass equation

$E: Y^{2} = X^{3} + a X + b$

together with a point at infinity $O$. The constants $a,b$ must satisfy the relationship

$4a^{3} + 27 b^{2} \neq 0$

to ensure there are no singularities on the curve.

Formally, let E be an elliptic curve, point addition has the following properties

(a) $P + O = O + P = P$
(b) $P + (−P) = O$
(c) $(P + Q) + R = P + (Q + R)$
(d) $P + Q = Q + P$

In ECC, we study elliptic curves over a finite field $\Fp$. This means we look at the curve modulo the characteristic $p$ and an elliptic curve will no longer be a curve, but a collection of points whose $x,y$ coordinates are integers in $\Fp$.

The following starter challenges will take you through the calculations for ECC and get you used to the basic operations that ECC is built upon, have fun!

Property (d) shows that point addition is commutative. The flag is the name we give groups with a commutative operation.

In the background section, we covered the basics of how we can view point addition over an elliptic curve as being an abelian group operation. In this geometric picture we allowed the coordinates on the curve to be any real number.

To apply elliptic curves in a cryptographic setting, we study elliptic curves which have coordinates in a finite field $\Fp$.

We will still be considering elliptic curves of the form $E: Y^{2} = X^{3} + a X + b $, which satisfy the following conditions: $a,b \in \Fp$ and $4a^{3} + 27 b^{2} \neq 0$. However, we no longer think of the elliptic curve as a geometric object, but rather a set of points defined by

$E(\Fp) = \{(x,y) : x,y \in \Fp \textrm{ satisfying } y^{2} = x^{3} + a x + b \} \cup O$

Note: Everything we covered in the background still holds. The identity of the group is the point at infinity: $O$, and the addition law is unchanged. Given two points in $E(\Fp)$, the addition law will generate another point in $E(\Fp)$.

For all the challenges in the starter set, we will be working with the elliptic curve

$E: Y^{2} = X^{3} + 497 X + 1768 \mod 9739$

Using the above curve, and the point $P(8045,6936)$, find the point $Q(x,y)$ such that $P + Q = O$.

Remember, we're working in a finite field now, so you'll need to correctly handle negative numbers.

Resources:
  - The Animated Elliptic Curve: Visualizing Elliptic Curve Cryptography

While working with elliptic curve cryptography, we will need to add points together. In the background challenges, we did this geometrically by finding a line that passed through two points, finding the third intersection and then reflecting along the $y$-axis.

It turns out that there is an efficient algorithm for calculating the point addition law for an elliptic curve.

Taken from "An Introduction to Mathematical Cryptography", Jeffrey Hoffstein, Jill Pipher, Joseph H. Silverman, the following algorithm will calculate the addition of two points on an elliptic curve

Algorithm for the addition of two points: $P + Q$

(a) If $P = O$, then $P + Q = Q$.
(b) Otherwise, if $Q = O$, then $P + Q = P$.
(c) Otherwise, write $P = (x_{1}, y_{1})$ and $Q = (x_{2}, y_{2})$.
(d) If $x_{1} = x_{2}$ and $y_{1} = −y_{2}$, then $P + Q = O$.
(e) Otherwise:
  (e1) if $P \neq Q$: $\lambda = (y_{2} - y_{1}) / (x_{2} - x_{1})$
  (e2) if $P = Q$: $\lambda = (3x_{1}^2 + a) / 2y_{1}$
(f) $x_{3} = λ^2 − x_{1} − x_{2}$
(h) $y_{3} = λ(x_{1} −x_{3}) − y_{1}$
(i) $P + Q = (x_{3}, y_{3})$


We are working with a finite field, so the above calculations should be done modulo $p$, and we do not "divide" by an integer, we instead multiply by the modular inverse of a number. e.g. $5^{-1} \equiv 9 \mod 11$.

We will work with the following elliptic curve, and prime:

$E: Y^{2} = X^{3} + 497 X + 1768 \mod 9739$

You can test your algorithm by asserting: $X + Y = (1024, 4440)$ and $X + X = (7284, 2107)$ for $X = (5274, 2841)$ and $Y = (8669, 740)$.

Using the above curve, and the points $P = (493, 5564), Q = (1539, 4742), R = (4403,5202)$, find the point $S(x,y) = P + P + Q + R$ by implementing the above algorithm.

After calculating $S$, substitute the coordinates into the curve. Assert that the point $S$ is in $E(\Fp)$

Scalar multiplication of two points is defined by repeated addition: $[3]P = P + P + P$.

In the next few challenges, we will use scalar multiplication to create a shared secret over an insecure channel similarly to the Diffie-Hellman challenges.

Taken from "An Introduction to Mathematical Cryptography", Jeffrey Hoffstein, Jill Pipher, Joseph H. Silverman, the following algorithm will efficently calculate scalar multiplication of a point on an elliptic curve

Double and Add algorithm for the scalar multiplication

Input: $P \in E(\Fp)$ and an integer $n > 0$
Output: $Q = [n]P \in E(\Fp)$

1. Set $Q = P$ and $R = O$.
2. Loop while n > 0.
  3. If $n \equiv 1 \mod 2$, set $R = R + Q$.
  4. Set $Q = [2] Q$ and $n = \lfloor n/2 \rfloor$.
  5. If $n > 0$, continue with loop at Step 2.
6. Return the point $R$, which equals $[n]P$.


This is not the most efficient algorithm, there are many interesting ways to improve this calculation up, but this will be sufficient for our work.

We will work with the following elliptic curve, and prime:

$E: Y^2 = X^3 + 497 X + 1768 \mod 9739$

You can test your algorithm by asserting: $[1337] X = (1089, 6931)$ for $X = (5323, 5438)$.

Using the above curve, and the points $P = (2339, 2213)$, find the point $Q(x,y) = [7863] P$ by implementing the above algorithm.

After calculating $Q$, substitute the coordinates into the curve. Assert that the point $Q$ is in $E(\Fp)$.

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

Alice and Bob are looking at the Elliptic Curve Discrete Logarithm Problem and thinking about the data they send.

They want to try and keep their data transfer as efficient as possible and realise that sending both the $x$ and $y$ coordinate of their public key isn't necessary.

As long as Alice and Bob agree on the curve parameters, there are only ever two possible values of $y$ for a given $x$.

In fact, given either of the values of $y$ permissible from the value $x$ they receive, the $x$ coordinate of their shared secret will be the same.

For these challenges, we have used a prime $p \equiv 3 \mod 4$, which will help you find $y$ from $y^{2}$.

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 $x(Q_A) = 4726$, with your secret integer $n_B = 6534$.

Use the decrypt.py file to decode the flag

{'iv': 'cd9da9f1c60925922377ea952afc212c', 'encrypted_flag': 'febcbe3a3414a730b125931dccf912d2239f3e969c4334d95ed0ec86f6449ad8'}

You can specify which of the two possible values your public $y$ coordinate has taken by sending only one bit. Try and think about how you could do this. How are the two $y$ values related to each other?

Challenge files:
  - decrypt.py

Spent my morning reading up on ECC and now I'm ready to start encrypting my messages. Sent a flag to Bob today, but you'll never read it.

Challenge files:
  - source.py
  - output.txt

Learning from my mistakes... This time I've ensured my curve is of prime order. This flag will be safe forever.

Challenge files:
  - source.sage
  - output.txt

Been fine tuning my bit lengths to ensure my data packages and calculation times are super efficient.

Challenge files:
  - source.sage
  - output.txt

I've included an extra layer of security by picking my own curve parameters a,b and keeping them secret.

Challenge files:
  - output.txt
  - source.py

I've learnt that when life gives you lemons, if you look at things the right way they taste just like pairs.

Challenge files:
  - source.sage
  - output.txt

I implemented the scalar multiplication from another challenge. It is secure enough, so you will never guess my private key!

You are allowed to send *two* base points, and I give you *two minutes* to prove me wrong.

Connect at socket.cryptohack.org 13416

Challenge files:
  - 13416.py


Challenge contributed by Aloof

For this last one, I chose a very secure elliptic curve. Finally, my private key is safe.

You are allowed to send *one* base point, and you have *30 seconds* to find my private key.

Connect at socket.cryptohack.org 13417

Challenge files:
  - 13417.py


Challenge contributed by Aloof

During an internal audit, you find a custom service performing ECDH key exchange to establish secure communications with clients. Can you exploit it?

Depending on the speed of your computer, the solution may take a while to calculate.

Connect at socket.cryptohack.org 13419

Challenge files:
  - 13419.py


Challenge contributed by $in

For more security, I made some changes on the curve parameters! This time, I am sure my private key cannot be found.

You are allowed to send one base point, and you have one minute to find my private key.

Connect at socket.cryptohack.org 13418

Challenge files:
  - 13418.py


Challenge contributed by Aloof

When developing a secure crypto system, the most important rule is to keep it real.

Challenge files:
  - output.txt
  - source.py


Challenge contributed by jschnei

Should ECDSA be avoided for better digestive health?

Play at https://web.cryptohack.org/digestive

Here's my secure search engine, which will only search for hosts it has in its trusted certificate cache.

Connect at socket.cryptohack.org 13382

Challenge files:
  - 13382.py

This is my secure timestamp signing server. Only if you can produce a signature for "unlock" can you learn more.

Connect at socket.cryptohack.org 13381

Challenge files:
  - 13381.py

Relying on randomness is bad with a bad entropy source, so I got rid of it and changed to a better signature generation method.

Challenge files:
  - source.py
  - output.txt


Challenge contributed by aloof

I heard elliptic curves in Edwards form have nice and efficient point addition formulas that work with any points.

Challenge files:
  - source.py
  - output.txt


Challenge contributed by aloof

This category is filled with insecure implementations of elliptic curve cryptography. Picking bad curves leads to broken protocols and fun puzzles, but private keys can be extracted from devices even when the curves picked are safe!

One technique to learn private information is through side channel analysis. At a high level, a system performing operations with a secret can leak information about the secret through data such as the time taken, or work done by the circuit.

Timing attacks against ECDSA signing can leak information about the nonce, which together with sophisticated attacks like LadderLeak can be lethal for the protocol. To protect against this, a lot of work has been done to make scalar multiplication of points on an elliptic curve to run in constant time.

A key component of constant time algorithms for scalar multiplication for points on elliptic curves are based on Montgomery's Ladder. In this challenge, the aim is to implement the most basic version of this: Montgomery’s binary algorithm in the group $E(\Fp)$.

Montgomery’s binary algorithm in the group $E(\Fp)$

Input: $P \in E(\Fp)$ and an n-bit integer $k = \sum 2^i k_i$ where $k_{n-1} = 1$
Output: $[k]P \in E(\Fp)$

1. Set $(R_0, R_1)$ to $(P, [2]P)$
2. for i = n - 2 down to 0 do
3.   If $k_i = 0$ then
4.      Set $(R_0, R_1)$ to $([2]R_0, R_0 + R_1)$
5.   Else:
6.      Set $(R_0, R_1)$ to $(R_0 + R_1, [2]R_1)$
7. Return $R_0$


At a high level, notice that regardless of the bit of k, we perform both a doubling and an addition operation for each step. Compare this to the double and add algorithm we gave in the starter challenges. There are a couple obvious problems within here still: the number of steps taken leaks the bit length of k and there's an if statement, which could leak data on the bit structure of k due to branching. For the interested learner, we recommend improving your algorithm to match Alg. 8 in this resource: Montgomery curves and their arithmetic.

We will work with the following elliptic curve:

$E: Y^{2} = X^{3} + 486662 X^{2} + X \mod 2^{255} - 19 $

Using the above curve, and the generator point with G.x = 9, find the $x$-coordinate (decimal representation) of point Q = [0x1337c0decafe] G by implementing the above algorithm.

This curve is in Montgomery form, rather than Weierstrass like many of the curves in these challenges. Although this curve can be mapped to Weierstrass form and old doubling and addition formula can be reused, we recommend working directly with the formula for Montgomery curves: $ E : By^{2} = x^{3} + Ax^{2} + x$. To encourage this, we give the addition and doubling formulas for the curve in affine coordinates. Please see Montgomery curves and the Montgomery ladder for a beautiful and fast set of formula in projective coordinates.

Addition formula for Montgomery Curve (Affine)

Input: $P_1, P_2 \in E(\Fp)$ with $P \neq Q$
Output: $P_3 = (P_1 + P_2) \in E(\Fp)$

$(x_1, y_1), (x_2, y_2) = P_1, P_2$
$\alpha = (y_{2} - y_{1}) / (x_{2} - x_{1} )$
$x_{3} = B \alpha^{2} - A - x_{1} - x_{2}$
$y_{3} = \alpha (x_{1} - x_{3}) - y_{1}$

Doubling formula for Montgomery Curve (Affine)

Input: $P \in E(\Fp)$
Output: $R = [2]P \in E(\Fp)$

$\alpha = (3x^{2}_{1} + 2Ax_{1} + 1) / (2By_{1})$
$x_{3} = B\alpha^{2} - A - 2x_{1}$
$y_{3} = \alpha(x_{1} - x_{3}) - y_{1}$

Note that all operations are performed modulo $p$.

For a general overview of Montgomery's ladder, we recommend: Montgomery curves and the Montgomery ladder. For a clean algorithm to implement, we recommend Alg. 4 LADDER in Montgomery curves and their arithmetic together with Alg. 1 xADD and Alg. 2 xDBL.

We've managed to get power readings from scalar multiplication on the Secp256k1 curve. Can you recover the private key from the data dump from 50 repeated multiplications?

Challenge files:
  - source_snippet.py
  - collected_data.txt