RaRCTF 2021 | unrandompad

#rarctf2021

from random import getrandbits
from Crypto.Util.number import getPrime, long_to_bytes, bytes_to_long

def keygen():  # normal rsa key generation
    primes = []
    e = 3
    for _ in range(2):
        while True:
            p = getPrime(1024)
            if (p - 1) % 3:
                break
        primes.append(p)
    return e, primes[0] * primes[1]

def pad(m, n):  # pkcs#1 v1.5
    ms = long_to_bytes(m)
    ns = long_to_bytes(n)
    if len(ms) >= len(ns) - 11:
        return -1
    padlength = len(ns) - len(ms) - 3
    ps = long_to_bytes(getrandbits(padlength * 8)).rjust(padlength, b"\x00")
    return int.from_bytes(b"\x00\x02" + ps + b"\x00" + ms, "big")

def encrypt(m, e, n):  # standard rsa
    res = pad(m, n)
    if res != -1:
        print(f"c: {pow(m, e, n)}")
    else:
        print("error :(", "message too long")

menu = """
[1] enc()
[2] enc(flag)
[3] quit
"""[1:]

e, n = keygen()
print(f"e: {e}")
print(f"n: {n}")
while True:
    try:
        print(menu)
        opt = input("opt: ")
        if opt == "1":
            encrypt(int(input("msg: ")), e, n)
        elif opt == "2":
            encrypt(bytes_to_long(open("/challenge/flag.txt", "rb").read()), e, n)
        elif opt == "3":
            print("bye")
            exit(0)
        else:
            print("idk")
    except Exception as e:
        print("error :(", e)

RSA padding とみせかけてpaddingついてない/ e=3 なので Hastad Broadcast Attack やるだけ

import gmpy2
c = 477106988788868259080048070061157377947342381104552881832140870019802188665655266083939954191053582609243376323308058266582919923374430371950128501500114929001581090805265581252812922393650888609115158904059820288577834348042144880801242804971228803172133158972220537633474902495622235867657684192048158377462055017796326316473710440916920658441397661249796795127220520022061292733298980168652464775165170358585765978141419577305021234492257467497262648233170150044101871214880141431173978014996655535972914242149347917825200871150028796658815403725522342560098571097377402384885226006359750513180168953852489069273
n = 26046604517609955113372258713510883495587875802805078701405869916296191589455500586809577482207503976034811539835465809567757181828328736162175523173004807850803602290836175542430562234684553034631154280095039201445998532236230579578840262238352001003584827429932026310306445316688747565275275145744638575644373292569893724596291319617337892543562456711796919731456877123837213953488110625958118950781420567567455669573239542047363935058194146131484936330118671601337475576534907915764095286372309556736081071548428560079497167778316357756717765230503775860128977898291474989868381183706492827089429390581424430318017

while True:
    m, ok = gmpy2.iroot(c, 3)
    if ok:
        print(m)
        quit()
    c += n