Crypto: WeakEr (RSA e=3, no padding)

Challenge Description

I really hope you paid attention to the slides

Attachments

chal.py

from Crypto.Util.number import getPrime, bytes_to_long

p = getPrime(4096)
q = getPrime(4096)
n = p * q
e = 3

with open("flag.txt", 'r') as f:
    flag = f.read()

m = bytes_to_long(flag.encode())
c = pow(m, e, n)

with open("output.txt", "w") as f:
    f.write(f"n = {n}\n")
    f.write(f"e = {e}\n")
    f.write(f"c = {c}\n")

output.txt

n = 626636467174812132624753452494486959968972903857184775465482545243177755850814922108487826900492083855534184067161590140062503898083806619801177101115148217785108119810982867066104515821531303186156298223107285555824033608840668013132755135302035514068912017318277127847389145223943098252062799783042521738561609864161041729593145188996569456495642550258938200094079862831320244131814535621542190951264052328546737591271113597831887604889604911726110210327271363183114195324443395345315603646519861332327877764789455091149153174460623976958474154423281927339896711716830325834393297883532581726433978121453773751770542420647112195175674144360587876543034833715769851841856236293032972179523812475198582663158195078947196631195942651582838116218779451268655196811725652800362297091078185767104548625030566859586617558185927389517052818099003822898712884664118851303027074599878349443815740540327090646025711739833906267925512150419628749433736438398684254781821247460865507511905839492104735701768111543689484140852218135836206872804579325395444441696949121624034313241095774780506737452857467620322672545784369742189147253361628304765297103557036053284649590592114880762502276728824066298300121581521710809328857981012118477107790579066112082735280105950053064047836113626334076360795848746333907836597690009816319319961798374740491076906742914440962560909452527255744669758839942820477410751614718308112740772795132208638386915981801643663841576173509850796746210054141926767664160624094595363742979694986031399742674859444126354346830725215317374350097085883222116198352845280429020037678156162087409235523572978940437938375137903427270878232926690132402658069930828062853200920457751717510427569655058641077231840842778499847975840365113752241516403173936911096418244927299656298846709220305236992889514265341151518456480317567960492446442652164181508459882397951179873569770077973326865258563345546276311095208751950043460786625907629800185299396481765004700659585707590803881495478469764445006812883312143872420868524642288676686655342250510414878522337107449407166215191346381450973712726097430695319028146343650089849490469546811970284604151437166884894287415108573909629444185247691094701765207397245763953872672075535614074320382335361177433650510261258632651759373258936490862831608333167972841916063008505416089049013686731647557871494026245929435915859622834373471541514459190142247009117176627981740089197882651796265405626542305933483660313992150762263
e = 3
c = 4084895669255322768054668654772507329626361292690240488444510899238981094810024350311979210761453631620589432321206738873539185174926172053474810198052023452359091965274036172185765622512115832150787248079064748304714679876173527606535730815155774279040452709

Approach

This is the well known low exponent attack on RSA. With $e=3$, and $m$ small enough such that $m^3 < n$, then modular reduction never triggers and we simply have

So we can directly take the integer cube root of $c$ to get $m$, then read $m$ as bytes to get the flag. No factoring, no private key.

Python solve script

from Crypto.Util.number import long_to_bytes, inverse
from gmpy2 import iroot

with open("output.txt") as f:
    lines = f.readlines()
    n = int(lines[0].split("=")[1].strip())
    e = int(lines[1].split("=")[1].strip())
    c = int(lines[2].split("=")[1].strip())

flag, exact = iroot(c, e) # in this case e=3, so this is integer cube root

print(long_to_bytes(flag).decode('utf-8'))

Result:

RISC{y0u_d1dnt_3v3n_n33d_t0_f4ct0r!}