Related (crypto)

706B
chal.py
Open
4KB
out.txt
Open

The encryption code is as follows:

import random
from flag import FLAG
from Crypto.Util.number import getPrime, bytes_to_long, long_to_bytes

p = getPrime(1024)
q = getPrime(1024)
n = p * q
e = 0x101

def pad(flag):
    m = bytes_to_long(flag)
    a = random.randint(2, n)
    b = random.randint(2, n)
    return (a, b), a*m+b

def encrypt(flag):
    padded_variables, padded_message = pad(flag)
    encrypted = pow(padded_message, e, n)
    return padded_variables, encrypted

variables, ct1 = encrypt(FLAG)
a1 = variables[0]
b1 = variables[1]

variables, ct2 = encrypt(FLAG)
a2 = variables[0]
b2 = variables[1]

print(f"{n = }")
print(f"{a1 = }")
print(f"{b1 = }")
print(f"{ct1 = }")
print(f"{a2 = }")
print(f"{b2 = }")
print(f"{ct2 = }")

Essentially, RSA encryption is used to encrypt the flag twice. However, each time we pad the flag by multiplying it with a and adding it to b, both of which are random. We are given n, and both the a, b and ct values.

As the challenge name suggests, this is a Franklin Reiter Related Message Attack. As long as a linear relationship can be drawn between the two messages (which is true here), this attack can be used. My solve script is given below:

Last updated