srdnlen CTF 2022 | one flag padding

#srdnlen_CTF_2022

#!/usr/bin/env python3

import random
import string
from Crypto.Util.number import getPrime, bytes_to_long


def flag_padding(flag):
    s = string.ascii_lowercase + string.ascii_uppercase + string.digits
    for i in range(random.randint(5, 10)):
        flag = random.choice(s) + flag + random.choice(s)
    return flag


def message_padding(message, flag):
    return message + flag


flag = open("flag.txt", "r").read()
flag = flag_padding(flag)
p = getPrime(512)
q = getPrime(512)
n = p*q
e = 7

encrypted_flag = pow(bytes_to_long(flag.encode()), e, n)
print("This is the flag: ", encrypted_flag)
print("Give any message you want, I will pad it with my special flag and encrypt it")
msg = input("> ")
if len(msg) < 10:
    print("Message to small, you are not gonna trick me")
    exit()
final_msg = message_padding(msg, flag)
ct = pow(bytes_to_long(final_msg.encode()), e, n)

print("Here is your ciphertext")
print("e: ", e)
print("n: ", n)
print("enc_message: ", ct)

フラグにランダムなパディングを加えた後、こちらの指定した文字列をprefixとして指定してもう一度暗号化させてくれる。二つの平文の間に線形に表せる関係があるので、フラグとパディングの長さを全探索しながらFranklin-Reiter Related Message Attackをやれば良い（今思うとフラグの長さ + パディングの長さで一重ループで全探索すれば良いな）

from ptrlib import Socket



sock = Socket("nc oneflagpadding.challs.srdnlen.it 15006")
c1 = int(sock.recvlineafter("flag: "))


padstr = "x" * 10
pad = int(padstr.encode().hex(), 16)
sock.sendlineafter("> ", padstr)

e = int(sock.recvlineafter("e: "))
n = int(sock.recvlineafter("n: "))
c2 = int(sock.recvlineafter("message: "))

PR.<m> = PolynomialRing(Zmod(n))

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a.monic()

for flen in range(2, 100):
    for i in range(5, 11):
        f1 = m**e - c1
        f2 = (m + pad*(2**(8*i*2 + 8*flen)) ) **e - c2

        try:
            g = gcd(f1, f2)
            if g == 1:
                continue
            m = -g.constant_coefficient()
            print(bytes.fromhex(hex(m)[2:]))
        except:
            pass