ASIS 2022 - Mariana
This is the solution of the challenge “Mariana” given during the ASIS CTF 2022. It consisted in solving 40 discrete logarithm fixed points to solve the challenge. The range check allows to solve the equation with the Chinese remainder theorem with a negative value.
Mariana works in the areas of cryptography and security. But some flaws exists in her work!
nc 220.127.116.11 32066
The script is asking 40 times for a discrete logarithm fixed point:
$$g^x = x \mod p$$
With $p$ being from 32 to 1280 bit long and $x$ being less than $p$. For the latest steps a solution involving the computation of a discrete logartihm will not be feasible. The title would indicate to look at the work of Mariana Levin et. al about discrete logarithm fixed point. However the paper proves that the solution exists but without any construction method. However in the paper there is a note saying: “Note that if x is not restricted to the interval [1, p − 1] it is easy to find fixed points. In our challenge, $x$ is limited to $p-1$ but in the code there is not limit to have a negative value.
The idea is the following, we are looking for a value of $x$ such that:
$$x \equiv 1 \mod p-1$$
$$x \equiv g \mod p$$
If so, we have the correct relation: $g^x = x \mod p$ and we must have $x < p$. The chinese remainder theorem (CRT) would give us a positive solution for the previous system modulo $p(p-1)$. It would be rejected by the server. But if we substract $p(p-1)$ to the result of the CRT it would give a negative value still correct.
The final script to automatized the 40 answers is the following:
Which outputs the flag at the end: