(October 25, 2022, 09:12 AM)xiorat89 Wrote: Solution for crypto (Python3.8+, requires PyCryptodome)
from Crypto.Util.number import long_to_bytes
FNAME="data.txt"
with open(FNAME, "r") as f:
lines = f.read().split("
")
p = int(lines[0].split(" ")[-1])
g = int(lines[1].split(" ")[-1])
h = int(lines[2].split(" ")[-1])
c1, c2 = lines[3].split(" = (")[-1].split(", ")
c1 = int(c1)
c2 = int(c2[:-1])
print("
[*]Loaded values from " + FNAME)
# c1 = (g * y) % p
# c1, g, p are given
# First we need to find the modular multiplicative inverse of y
# https://www.delftstack.com/howto/python/mod-inverse-python/
g_inv = pow(g, p-2, p)
solved_y = g_inv * c1 % p
print("
[*]Solved y=%d" % solved_y)
# Next we can solve for s since all values are given:
# s = h ^ y % p
solved_s = pow(h, solved_y, p)
print("
[*]Solved for s=%d" % solved_s)
# Finally we can solve for m since using the same modular mult. inverse
# technique as before:
# c2 = (m * s) % p
s_inv = pow(solved_s, p-2, p)
solved_m = s_inv * c2 % p
print("
[*]Solved for m=%d" % solved_m)
print("[+] long_to_bytes(m) =", long_to_bytes(solved_m))
thanks
