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