The use of elliptic curves for public-key cryptography was first suggested in 1985. After resisting decades of attacks, they started to see widespread use from around 2005, providing several benefits over previous public-key cryptosystems such as RSA.
Smaller EC keys offer greater strength, with a 256-bit EC key having the same security level as a 3072-bit RSA key. Furthermore, several operations using those keys (including signing) can be more efficient both time- and memory-wise. Finally, since ECC is more complex than RSA, it has the welcome effect of encouraging developers to make use of trusted libraries rather than rolling their own.
These challenges aim to give you an intuition for the trapdoor function behind ECC; dip your toes into the mathematical structure underlying it; and have you breaking popular schemes like ECDSA.
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. 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
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 = nP
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} ≠ 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 F_{p}
. 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 F_{p}
.
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.
You must be logged in to submit your flag.
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 F_{p}
.
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 ∈ F_{p}
and 4a^{3} + 27 b^{2} ≠ 0
. However, we no longer think of the elliptic curve as a geometric object, but rather a set of points defined by
E(F_{p}) = {(x,y) : x,y ∈ F_{p} satisfying: y^{2} = x^{3} + a x + b} ∪ 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(F_{p})
, the addition law will generate another point in E(F_{p})
.
For all the challenges in the starter set, we will be working with the elliptic curve
E: Y^{2} = X^{3} + 497 X + 1768, p: 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 work correctly with negative numbers.
Resources:
- The Animated Elliptic Curve: Visualizing Elliptic Curve Cryptography
You must be logged in to submit your flag.
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 ≠ Q: λ = (y_{2} - y_{1}) / (x_{2} - x_{1})
(e2) if P = Q: λ = (3x_{1}^{2} + a) / 2y_{1}
(f) x_{3} = λ^{2} − x_{1} − x_{2}, y_{3} = λ(x_{1} −x_{3}) − y_{1}
(g) P + Q = (x_{3}, y_{3})
We are working with a finite field, so the above calculations should be done mod p
, and we do not "divide" by an integer, we instead multiply by the modular inverse of a number. e.g. 1 / 5 = 9 mod 11
.
We will work with the following elliptic curve, and prime:
E: Y^{2} = X^{3} + 497 X + 1768, p: 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(F_{p})
You must be logged in to submit your flag.
Scalar multiplication of two points is defined by repeated addition: 3P = 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 of point P by n
Input: P in E(F_{p}) and an integer n > 0
1. Set Q = P and R = O.
2. Loop while n > 0.
3. If n ≡ 1 mod 2, set R = R + Q.
4. Set Q = 2 Q and n = ⌊n/2⌋.
5. If n > 0, continue with loop at Step 2.
6. Return the point R, which equals nP.
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, p: 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(F_{p})
.
You must be logged in to submit your flag.
The Elliptic Curve Discrete Logarithm Problem (ECDLP) is the problem of finding an integer n
such that Q = nP
.
Like we encountered with the discrete logarithm problem, scalar multiplication of a point in E(F_{p})
seems to be be a hard problem to undo, with the most efficient algorithm running at p^{1/2}
time.
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 create a secret others can't replicate.
Alice and Bob agree on a curve E
, a prime p
and a generator point G
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.
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, p: 9739, 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 decimal 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
You must be logged in to submit your flag.
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 ≡ 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, p: 9739, G: (1804,5368)
Calculate the shared secret after Alice sends you q_x = 4726
, with your secret integer n_{B} = 6534
.
Use the decrypt.py
file to decode the flag{'iv': 'cd9da9f1c60925922377ea952afc212c', 'encrypted_flag': 'febcbe3a3414a730b125931dccf912d2239f3e969c4334d95ed0ec86f6449ad8'}
You can specifiy 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
You must be logged in to submit your flag.
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
You must be logged in to submit your flag.
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
You must be logged in to submit your flag.
Been fine tuning my bit lengths to ensure my data packages and calculation times are super efficient.
Challenge files:
- source.sage
- output.txt
You must be logged in to submit your flag.
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
You must be logged in to submit your flag.
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
You must be logged in to submit your flag.
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
You must be logged in to submit your flag.
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
You must be logged in to submit your flag.
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
You must be logged in to submit your flag.
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(F_{p}).
Montgomery’s binary algorithm in the group E(F_{p})
Input: P in E(F_{p}) and an l-bit integer k = Σ 2^{i} k_{i} where k_{l-1} = 1
Output: [k]P in E(F_{p})
1. Set (R_{0}, R_{1}) to (P, [2]P)
2. for i = l - 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, and prime:
E: Y^{2} = X^{3} + 486662X^{2} + X, p: 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: 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, Q in E(F_{p}) with P != Q
Output: R = (P + Q) in E(F_{p})
α = (y_{2} - y_{1}) / (x_{2} - x_{1} )
x_{3} = Bα^{2} - A - x_{1} - x_{2}
y_{3} = α(x_{1} - x_{3}) - y_{1}
Doubling formula for Montgomery Curve (Affine)
Input: P in E(F_{p})
Output: R = [2]P in E(F_{p})
α = (3x^{2}_{1} + 2Ax_{1} + 1) / (2By_{1})
x_{3} = Bα^{2} - A - 2x_{1}
y_{3} = α(x_{1} - x_{3}) - y_{1}
Note that all operations are performed mod 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
.
You must be logged in to submit your flag.
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
You must be logged in to submit your flag.
You are now level Current level