Elliptic Curve Cryptography-2
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)
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).
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
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?
