## Elliptic Curves

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

Toggle
5 pts

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

Y2 = X3 + 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: Y2 = X3 + a X + b

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

4a3 + 27 b2 ≠ 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.

You must be logged in to submit your flag.

#### Starter

Toggle
• Point Negation
10 pts

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: Y2 = X3 + a X + b `, which satisfy the following conditions: `a,b ∈ Fp` and `4a3 + 27 b2 ≠ 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 ∈ Fp satisfying: y2 = x3 + 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(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: Y2 = X3 + 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.

You must be logged in to submit your flag.

30 pts · 1243 Solves

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 = (x1, y1) and Q = (x2, y2).
(d) If x1 = x2 and y1 = −y2, then P + Q = O.
(e) Otherwise:
(e1) if P ≠ Q: λ = (y2 - y1) / (x2 - x1)
(e2) if P = Q: λ = (3x12 + a) / 2y1
(f) x3 = λ2 − x1 − x2,     y3 = λ(x1 −x3) − y1
(g) P + Q = (x3, y3)

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: Y2 = X3 + 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(Fp)`

You must be logged in to submit your flag.

• Scalar Multiplication
35 pts · 1194 Solves

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(Fp) 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: Y2 = X3 + 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(Fp)`.

You must be logged in to submit your flag.

• Curves and Logs
40 pts · 1128 Solves

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(Fp)` seems to be be a hard problem to undo, with the most efficient algorithm running at `p1/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 `nA` and calculates `QA = nAG`

Bob generates a secret random integer `nB` and calculates `QB = nBG`

Alice sends Bob `QA`, and Bob sends Alice `QB`. Due to the hardness of ECDLP, an onlooker Eve is unable to calculate `nA/B` in reasonable time.

Alice then calculates `nAQB`, and Bob calculates `nBQA`.

Due to the associativity of scalar multiplication, `S = nAQB = nBQA`.

Alice and Bob can use `S` as their shared secret.

Using the curve, prime and generator:

E: Y2 = X3 + 497 X + 1768, p: 9739, G: (1804,5368)

Calculate the shared secret after Alice sends you `QA = (815, 3190)`, with your secret integer `nB = 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.

• Efficient Exchange
50 pts · 1014 Solves

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 `y2`.

Using the curve, prime and generator:

E: Y2 = X3 + 497 X + 1768, p: 9739, G: (1804,5368)

Calculate the shared secret after Alice sends you `q_x = 4726`, with your secret integer `nB = 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.

#### Parameter Choice

Toggle
• Smooth Criminal
60 pts · 663 Solves

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.

• Exceptional Curves
100 pts · 446 Solves

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.

• Micro Transmissions
120 pts · 301 Solves

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.

• Elliptic Nodes
150 pts · 312 Solves

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.

• Moving Problems
150 pts · 319 Solves

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.

• Real Curve Crypto
200 pts · 26 Solves

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.

#### Signatures

Toggle
• Curveball
100 pts · 391 Solves

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

Connect at `nc socket.cryptohack.org 13382`

Challenge files:
- 13382.py

You must be logged in to submit your flag.

• ProSign 3
100 pts · 332 Solves

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

Connect at `nc socket.cryptohack.org 13381`

Challenge files:
- 13381.py

You must be logged in to submit your flag.

• No Random, No Bias
120 pts · 182 Solves

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.

#### Edwards Curves

Toggle
• Edwards Goes Degenerate
100 pts · 185 Solves

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.

#### Side Channels

Toggle
40 pts · 313 Solves

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 l-bit integer k = Σ 2i ki where kl-1 = 1
Output: [k]P in E(Fp)

1. Set (R0, R1) to (P, P)
2. for i = l - 2 down to 0 do
3.   If ki = 0 then
4.      Set (R0, R1) to (R0, R0 + R1)
5.   Else:
6.      Set (R0, R1) to (R0 + R1, R1)
7. Return R0

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: Y2 = X3 + 486662X2 + X, p: 2255 - 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: `By2 = x3 + Ax2 + 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(Fp) with P != Q
Output: R = (P + Q) in E(Fp)

α = (y2 - y1) / (x2 - x1 )
x3 = Bα2 - A - x1 - x2
y3 = α(x1 - x3) - y1

Doubling formula for Montgomery Curve (Affine)

Input: P in E(Fp)
Output: R = P in E(Fp)

α = (3x21 + 2Ax1 + 1) / (2By1)
x3 = Bα2 - A - 2x1
y3 = α(x1 - x3) - y1

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.

• Double and Broken
50 pts · 171 Solves

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.

### Level Up You are now level Current level