imaginaryctf 2021 - Lines(Crypto)

As you can see in this crypto challenge, we’re faced with a kind of encryption based on Diffie-Hellman key exchange. It’s also attached two file including:

p = 82820875767540480278499859101602250644399117699549694231796720388646919033627
encrypt(flag) = 26128737736971786465707543446495988011066430691718096828312365072463804029545
encrypt(msg) = 15673067813634207159976639166112349879086089811595176161282638541391245739514

and a python file that show how the cryptosystem work:

from Crypto.Util.number import bytes_to_long
import random
flag = bytes_to_long(open(“flag.txt”, “rb”).read())
msg = bytes_to_long(b”:roocursion:”)
p = 82820875767540480278499859101602250644399117699549694231796720388646919033627
g = 2
a = random.randint(0, p)
b = random.randint(0, p)
s = pow(pow(g, a, p), b, p)
def encrypt(msg):
    return (s*msg) % p
print(f”{p = }”)
print(f”{encrypt(flag) = }”)
print(f”{encrypt(msg) = }”)

The most important part of script is encrypt() function where the message is multiplied s (share secret key). So if we have the s we will get the message. By analyzing script, I found that reaching to s is so difficult by guessing a or b(private keys) and I should looking for another way to get the value of s. Since one of the messages is available with its encrypted value, s and then m (flag) can be obtained using modular inverse by following method.

Finally, I used the following script to recover the flag:

from Crypto.Util.number import long_to_bytes
from Crypto.Util.number import bytes_to_long
msg = bytes_to_long(b”:roocursion:”)
p = 82820875767540480278499859101602250644399117699549694231796720388646919033627
Cflag = 26128737736971786465707543446495988011066430691718096828312365072463804029545
Cmsg = 15673067813634207159976639166112349879086089811595176161282638541391245739514
def egcd(a, b):
 if a == 0:
 return (b, 0, 1)
 else:
 g, y, x = egcd(b % a, a)
 return (g, x — (b // a) * y, y)
def modinv(a, m):
 g, x, y = egcd(a, m)
 if g != 1:
 raise Exception(‘modular inverse does not exist’)
 else:
 return x % m
s=(Cmsg*modinv(msg,p))%p
flag=(Cflag*modinv(s,p))%p
print(long_to_bytes(flag))

flag: ictf{m0d_4r1th_ftw_1c963241}