redpwnCTF 2021 -blecc(Crypto)

In this Crypto challenge have been given a text file with the following contents:

p = 17459102747413984477
a = 2
b = 3
G = (15579091807671783999, 4313814846862507155)
Q = (8859996588597792495, 2628834476186361781)
d = ???
Can you help me find `d`?
Decode it as a string and wrap in flag format.

According to the title of the challenge, I found that it is a Elliptic Curves Cryptography(ECC) problem. It seemed relatively difficult for me since I didn’t know anything about elliptic curves.

First of all, I glimpsed the text file and after a quick bit of Googling about finding the private key in ECC, I found out that this is a Discrete Log problem because we intend to find the integer d that satisfies: Q=d.G . We have both points Q and G. so, we now need to find d.

Secondly, I found out in my research that there are possible attacks on elliptic curves but it involves that certain conditions are met. For example, if the prime p from the elliptic curve equation is equal to the order of the curve, the curve is said to be anomalous and the computing of discrete log is feasible easily.

After a day trying about how I can get d by attacking the Elliptic Curve Discrete Logarithm Problem, I came across a paper and an example PohIig-Hellman method. So the idea is to calculate the discrete logarithm by factoring the order of the point p and then, computing the “partial” discrete logs modulo each factor of the order of the point and then, join them with the Chinese Remainder Theorem(CRT) to get the solution to the original problem. Beside this, I got familiar with SageMath (a free open-source mathematics software system) which implemented many algorithms and can be downloaded here. So by using Sage, I started to build get d with following script:

sage: p = 17459102747413984477
....: a = 2
....: b = 3
....: G = (15579091807671783999, 4313814846862507155)
....: Q = (8859996588597792495, 2628834476186361781)
....: EC = EllipticCurve(GF(p), [a, b])
....: G = EC(15579091807671783999, 4313814846862507155)
....: Q = EC(8859996588597792495, 2628834476186361781)
....: order = EC.order()
....: # factors from factordb.com
....: factors=[[2,1],[5,1],[11,1],[22303,1],[36209,1],  [196539307,1]]
....: mods = []
....: NUMs = []
....: tmp = 1
....: for factor in factors:
....:     factor, cnt_factor = factor
....:     pe = factor**cnt_factor
....:     Pi = (order // pe) * G
....:     Qi = (order // pe) * Q
....:     zi = Pi.discrete_log(Qi)
....:     NUMs.append(zi)
....:     mods.append(pe)
....:     tmp *= pe
....: print(CRT(NUMs, mods))

This prints out our following number :)

7868191182322623331

After decoding to string:

flag{m1n1_3cc}