How hard are discrete logarithms problems in Z_n? Try to solve the given DLP.
The file contains a discrete logarithm problem:
x = bytes_to_long(flag)
g = 685780528648223163108441
n = 12588567055208488159342105634949357220607702491616160304212767442540158416811459761519218454720193189
y = pow(g, x, n)
y = 9136134187598897896238293762558529068838567704462064643828064439262538588237880419716728404254970025We should find x and use long_to_bytes to convert it into a string.
We have:
To find x, we should use Discrete Logarithm. By using factorization tools (Like Alperton) we found that n is not prime. Actually:
We need a prime modulus to solve DLP trivially, but our modulus is not prime here. We could use two approaches here. The first approach is to calculate the remainder of y when divided by each prime factor; Then, solve DLP for each of the prime factors and use the Chinese remainder theorem to combine the results and find the answer.
But our solution is much more straightforward :))
Our solution is to use online tools :)) We used Alperton website to solve the DLP problem. It solves it even for composite numbers. We just need to input g as Base, y as Power, and n as Modulus in this site, and after some time, it gives us the general result of this problem:
By evaluating the expression above for k=0 and using this simple python script, we can quickly get the flag:
from Crypto.Util.number import *
print(long_to_bytes(1936424274652643265366177146994482280350488968204318138649641400181832241265975677))The flag is:
ASIS{D!5Cre73_L09_iN_Zn_I5_3aSy?!}