May Contain Hackers 2022 - Squaring Off
This is the solution of the challenge “Squaring Off” given during the MCH CTF. It consisted in solving a discrete logarithm of in the multiplicative groups of a the square of a prime.
Description
Details
Points: 300
Category: Crypto
Validations: 5
Solution
The problem was simple, we had to solve the discrete logarithm of $2^{flag} \mod n$. We could quickly figure out that $n$ is a square of a prime number.
|
|
It means that the order of the multiplicative group is $\varphi(n) = p(p-1)$. The first idea was to compute the Pohlig-Hellman algorithm to recover the flag:
|
|
However, $p$ and the largest factor of $p-1$ were too big, the computation was not finishing. Then we figure out that there is an isomorhism between the cyclic group:
$$H = { x \in (\mathbb{Z}/p^2\mathbb{Z})^*, x^{p-1} = 1 \mod p}$$
to the additive group $\mathbb{Z}/p\mathbb{Z}$ exactly as in the Okamoto–Uchiyama cryptosystem. This isomorphism is $L(x) = \frac{x-1}{p}$ and gives directly the discrete logarithm in the subgroup of order $p$. However, this was not enougth to recover the flag.
Thus, we run the Pohlig-Hellman algorithm on the remaining factors except $p$ and the second bigger one. The we reconstruct the flag modulus $n$ divided by the missing prime number and it was sufficient to recover the flag completely:
|
|
Here it the full solution.