Tags: crypto elliptic-curve 


The name of the task leads to the concusion, that it is about elliptic curve cryptography. In fact it is about obtaining $d$, such that $Q = d\times G$
From the task description we know the following values:

$p = 17459102747413984477$

$a = 2$

$b = 3$

$G = (15579091807671783999, 4313814846862507155)$

$Q = (8859996588597792495, 2628834476186361781)$


The elliptic curve over a finite field can be described as follows:

$y^2 = x^3 +ax + b\ mod\ n$

In our case if looks like that: $y^2 = x^3 + 2x + 3\ mod\ 17459102747413984477$

Using SageMath we can build it in the following way:
# Known parameters
p = 17459102747413984477
a, b = 2, 3

# Build an object that describes the ellliptic curve
ec = EllipticCurve(GF(p), [a, b])

# define points
G = ec(15579091807671783999, 4313814846862507155)
Q = ec(8859996588597792495, 2628834476186361781)


As said before we need to find out $d$ such that $Q = d\times G$, that is known as Elliptic Curve Discrete Logarithm Problem (ECDLP).

In this case we'll try to use [Pohlig-Hellman algorithm](https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=&ved=2ahUKEwjxp9rL4t_xAhXDs4sKHR_0AW8QFnoECAIQAA&url=https%3A%2F%2Fwww.researchgate.net%2Ffile.PostFileLoader.html%3Fid%3D5583faed6225ff040e8b458b%26assetKey%3DAS%253A273804985602059%25401442291603545&usg=AOvVaw3x4kWhwsAyL_QGrTe3UqCS) (page 64), because factoring the generator's order produces many (actually not, but it is enough) small primes:
[In] factor(G.order())
[Out] 2 * 5 * 11 * 22303 * 36209 * 196539307


The generic idea of Pohling-Hellman algorithm is to build and solve the following system of congruences:

$d = d_1\ mod\ p_1^{e_1}$

$d = d_2\ mod\ p_2^{e_2}$


$d = d_k\ mod\ p_k^{e_k}$

where $d$ denotes the target value, $e_i$ denotes the exponent of $p_i$, each $d_i$ denotes discrete logarithm of $d$ modulo $p_i$ and can be expressed in the following way:

$d_i=z_0+z_1p_i+z_2p_i^2+...+z_{e_i-1}p_i^{e_i-1}\ mod\ p_i^{e_i}$, where $\forall k: z_k\in [0, p_i -1]$

Now let $G_i=\frac{x}{p_i}G$ and $Q_i=\frac{x}{p_i}Q$, where $x=\prod_{i=1}^{k}{p_i^{e_i}}$.

Using the fact that the order of $G_i$ is $p_i$ we can write the following equation: $Q_i=d\times G_i=z_i\times G_i$. Numbers $z_i$ can be obtained directly by calculating discrete logarithms, because all $p_i$ are relatively small.

The last step is to solve the system of congruences (mentioned above) using Chinese Remainder Theorem.


These operations can be written in SageMath as follows:
primes = [2 , 5 , 11 , 22303 , 36209 , 196539307] # factor(G.order())

dlogs = []
for fac in primes:
t = int(G.order()) // int(fac)
dlog = discrete_log(t*Q, t*G, operation="+")
dlogs += [dlog]

print(crt(dlogs, primes))

Because of small primes this task requires a small amount of time - just a few seconds. It yields the following result: `7868191182322623331`.

This number needs to be translated into hex and then decoded as ascii: `0x6d316e315f336363` => `flag{m1n1_3cc}`