In the file handout.txt, we are given the following parameters for an elliptic curve:
- y^2 = x^3 + A*x + B mod M -- the curve equation
- M -- the modulus of the curve
- A -- a coefficient in the curve equation
- P -- a point on the given curve
- Q -- a second point on the curve
To solve the problem, we will need to solve for the following values:
- B -- a constant in the curve equation
- n -- a number satisfying the equation n*P = Q
We are given the additional information that n < 400000000000000000000000000000 and that the flag will simply be the number n.
We won't be able to make much progress until we solve for B. This isn't too difficult, since we're given all of the other parameters as well as a couple of sample points. By rearranging the equation y^2 = x^3 + A*x + B mod M into the form B = y^2 - x^3 - A*x mod M, we can plug in values from either of the given points and find B.
Now that we have a fully defined elliptic curve, we can represent it in SageMath using the following code:
M = 93556643250795678718734474880013829509320385402690660619699653921022012489089
A = 66001598144012865876674115570268990806314506711104521036747533612798434904785
B = 25255205054024371783896605039267101837972419055969636393425590261926131199030
E = EllipticCurve(Integers(M),[0,0,0,A,B])
P = E.point((56027910981442853390816693056740903416379421186644480759538594137486160388926, 65533262933617146434438829354623658858649726233622196512439589744498050226926))
Q = E.point((79745356646949069441279781387743208137742538544495675881933883371885177103895, 34529309219406689418881493671300037164559702076524725195399995669560101677178))
Now how do we solve for n? First a nifty fact about elliptic curves: Any two points on an elliptic curve can be "added" together to produce a third point on the curve. Repeatedly adding a point with itself is known as "point multiplication," and this is what is implied by the expression n*P. So we just need to figure out how many times we have to add P to itself before we get Q.
Finding how many times a point must be added to itself to obtain a specified second point is known as the Elliptic Curve Discrete Logarithm Problem (ECDLP), and it's really difficult if the elliptic curve is chosen properly. However, there are certain algorithms that can solve the ECDLP efficiently for special types of elliptic curves. One of these algorithms is called the Pohlig-Hellman algorithm. Here's how it works:
- Suppose we're solving the equation n*P = Q where P and Q are points on a elliptic curve
- Since the curve is modular, there are only so many values that n*P can take on before getting wrapped around. Let's call the total number of these values ord(P).
- Using an algorithm called Pollard's Rho, the time it takes to compute the ECDLP will be on the order of sqrt(ord(P))
- Say ord(P) has prime factors p1, p2, ... pn. The Pohlig Hellman algorithm lets us break the big ECDLP into a bunch of smaller ECDLP's with orders of p1, p2, ... pn. The answers to each of these mini-ECDLP's are then combined using the Chinese Remainder Theorem to give us n.
- Since the running time of this algorithm is on the order of sqrt(p1) + sqrt(p2) + ... + sqrt(pn), this is a lot faster if ord(P) can be factored into small primes
So is ord(P) factorable into small primes? Let's ask Sage:
factor(P.order())
2^2 * 3 * 5 * 7 * 137 * 593 * 24337 * 25589 * 3637793 * 5733569 *
106831998530025000830453 * 1975901744727669147699767
Hmmm.... Those last two numbers seem awfully large. Large enough to make the Pohlig Hellman algorithm intractable. So is all hope lost? Maybe not.
What if we just ditched those last two factors? Well, since the Pohlig Hellman algorithm combines the answers to the smaller ECDLP's using Chinese Remainder Theorem, we would still get the right answer in some sense. The problem is that we would get the right answer mod some number, and if that number is too small it doesn't help very much. In this case that number is just the product of all of the factors of ord(P) besides the largest two:
2^2 * 3 * 5 * 7 * 137 * 593 * 24337 * 25589 * 3637793 * 5733569
443208349730265573969192476820
Wait a second, we know that n < 400000000000000000000000000000! This means that
n mod 443208349730265573969192476820 = n, so we can use Pohlig Hellman without the last two factors and get a perfectly correct answer anyway. Here's some Sage code to do that for us:
fac = list(factor(P.order()))
moduli = []
remainders = []
for i in fac[0:-2]:
P0 = P* ZZ(P.order()/i[0])
Q0 = Q*ZZ(P.order()/i[0])
moduli.append(i[0])
remainders.append(discrete_log(Q0,P0, operation = '+'))
crt(remainders,moduli)
This code returns the number 124194987912445918487544544020.
Flag get!