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
  • Background Reading
    5 pts · 3665 Solves

    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



    diagram of ECC addition



    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 · 2915 Solves

    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.

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

    You must be logged in to submit your flag.


  • Point Addition
    30 pts · 2557 Solves · 15 Solutions

    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 · 2432 Solves · 11 Solutions

    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 · 2318 Solves · 8 Solutions

    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 to 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 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

    You must be logged in to submit your flag.


  • Efficient Exchange
    50 pts · 2097 Solves · 11 Solutions

    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

Signatures

Toggle

Edwards Curves

Toggle
  • Edwards Goes Degenerate
    100 pts · 351 Solves · 2 Solutions

    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
  • Montgomery's Ladder
    40 pts · 859 Solves · 10 Solutions

    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, [2]P)
    2. for i = l - 2 down to 0 do
    3.   If ki = 0 then
    4.      Set (R0, R1) to ([2]R0, R0 + R1)
    5.   Else:
    6.      Set (R0, R1) to (R0 + R1, [2]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 = [2]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 · 390 Solves · 4 Solutions

    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

level up icon

You are now level Current level