https://nsucrypto.nsu.ru/archive/2021/round/2/task/4/#data
The main idea of the exercise: Find the secret key $k$, having access to the $Enc(x, d) = Enc(x^d \bmod n), n = 1060105447831$.
I will assume $0 < k < n.$
$Enc$ is a normal hash, it returns the same output as its corresponding input.
I want to find a collision such that $hash(k, 1) = hash(x, d)$, this would mean that I found $k = x^d \bmod n.$
My first idea was to search for the generator of the cyclic group of $Z_{1060105447831}$, but I found out that 2 and 3 and nothing in the first 20000 numbers worked. I would use the generator to check for collisions for $k$. I know $2^{40} > n$. It would also help to use the generator for computing the discrete logarithm and find the value of k faster. I want to test it but it feels like the problem was made with manual checking in mind.
A birthday attack doesn't work for a 128-bit hash if I want a good probability and efficiency.
I also tried to get the hash value of small values Enc(2,1), Enc(3,1) ... Enc(10, 1) to see if the hash has any hidden relation between its outputs.
Additionally, $\phi(n)$ has a nice factorization of small numbers.
I will add any new important details.
What values should be chosen to help find k? Do they matter? Generators aren't useful, I can't apply any faster algorithms for modular exponentiation because all I get is a 128-bit string. All I can do is check if a number or the power of a number has an encoding equal to that of the secret number $k$
