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 function where the message is multiplied (share secret key). So if we have the we will get the message. By analyzing script, I found that reaching to is so difficult by guessing or I should looking for another way to get the value of . Since one of the messages is available with its encrypted value, and then (flag) can be obtained using 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}

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store