Chujowy CTF 2020 | middle-aged RSA

RSA

from hashlib import sha256
from flag import flag

def encrypt_chunk(N, e, chunk):
    x = int.from_bytes(chunk, 'big')
    y = randint(0, 256^len(chunk))
    return Zmod(N)(x*y)^e

p, q = [random_prime(2^1024) for _ in range(2)]
N = p * q
e = 0x10001
print(N, e)
print(sha256(flag).hexdigest())
print([encrypt_chunk(N, e, flag[i:i+3]) for i in range(0, len(flag), 3)])

RSAで3バイト全探索のmeet-in-the-middle attack

from Crypto.Util.number import *
from ptrlib import *
import string
import json


N = 8253739811954581079883039653942654828989174169644077688004866911334570443238256707000464976374427913064639227592850646081613768794916489709879420823958866972099691720365204482444559053744098284697751099958397641049841044824572077836245068765517608578206286963402252110099502447542876135399013735538782226595080682739972858610074768168965455264004190192539915392931811674915249218168102737221545006205089105812553097584709166808879443187183230873628462738206111021585807086602983532655417491697917674860731538262303204924272897658587479800829311801911720997580159145158561580130445341389419966759054769453825386497329
e = 65537

cs = eval(open("middle_aged_rsa.txt", "r").read().strip().split("\n")[2])

yinvs = set()
X = 256**2
for y in range(1, X):
    if y % 1024 == 0:
        print(f"[+] y:{y}")
    yinvs.add(pow(y, -e, N))


for i, c in enumerate(cs):
    cinv = inverse(c, N)
    for x1 in range(0x20, 0x7f):
        print(f"[+] i:{i}, x:{x1}")
        for x2 in range(0x20, 0x7f):
            for x3 in range(0x20, 0x7f):
                x = x1 * 65536 + x2 * 256 + x3
                yinv = cinv * pow(x, e, N) % N
                if yinv in yinvs:
                    print(f"[!] {x}")