Imaginary CTF 2021 | lines - crypto-writeup-public

#imaginaryctf2021

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) = }")

ElGamal暗号のような感じだが、暗号化は $s = g^{ab} \mod p$ として $c = m*s \mod p$

$msg$ は既知なので $c_{msg} * msg^{-1} = s \mod p$ として $s$ を求めた後 $flag = c_{flag} * s^{-1} \mod p$ で良い

msg = int.from_bytes(b":roocursion:", "big")
with open("out.txt") as f:
    p = int(f.readline().strip().split(" = ")[1])
    c1 = int(f.readline().strip().split(" = ")[1])
    c2 = int(f.readline().strip().split(" = ")[1])

key = c2 * pow(msg, -1, p) % p
flag = c1 * pow(key, -1, p) % p

print(flag.to_bytes(100, "big"))