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