Skip to content

NahamCon 2022, Baby RSA Quiz

Cryptography

nilai n, e, ct bisa berbeda, tapi hasil tetap sama

Part 1

soal
n = 136264894803833
e = 65537
ct = 67764901398180

dengan bantuan webite alpertron, diperoleh faktorisasi nilai \(n\)

jawaban
from Crypto.Util.number import inverse

p = 8998813 
q = 15142541
n = p*q
e = 65537
ct = 67764901398180

phi = (p-1)*(q-1)
d = inverse(e, phi)

print(pow(ct, d, n))
print(bytes.fromhex(hex(pow(ct, d, n))[2:]))

Part 2

soal
n = 17925435334771013587505133312134011446454665306214868091426625738043654249842612378335769578853505374390032891305043469561633552835484637362051339282618327861863328779440585015290730732272120220814803393146082919022972321742125754827478629002093519872871126896844333575033296315672275008047278029857137147394445352038087033926481419884176987149176269587567688515370267383832925167970567780250165687458061877719682886965443559610523490229924398623783300021139294199543473933632906825708371890824433970966242607905055173858196908145444852654979292627541037359062687311270588137614930275427855189444098664111302437861137
e = 3
ct = 26480272848384180570411447917437668635135597564435407928130220812155801611065536704781892656033726277516148813916446180796750368332515779970289682282804676030149428215146347671350240386440440048832713595112882403831539777582778645411270433913301224819057222081543727263602678819745693540865806160910293144052079393615890645460901858988883318691997438568705602949652125

disini nilai \(n\) terlalu besar (1024 bit x 1024 bit) sehingga tidak dapat difaktorisasikan, tetapi memiliki kerentanan pada nilai \(e\) yang terlalu kecil (materi)

jawaban
n = 17925435334771013587505133312134011446454665306214868091426625738043654249842612378335769578853505374390032891305043469561633552835484637362051339282618327861863328779440585015290730732272120220814803393146082919022972321742125754827478629002093519872871126896844333575033296315672275008047278029857137147394445352038087033926481419884176987149176269587567688515370267383832925167970567780250165687458061877719682886965443559610523490229924398623783300021139294199543473933632906825708371890824433970966242607905055173858196908145444852654979292627541037359062687311270588137614930275427855189444098664111302437861137
e = 3
ct = 26480272848384180570411447917437668635135597564435407928130220812155801611065536704781892656033726277516148813916446180796750368332515779970289682282804676030149428215146347671350240386440440048832713595112882403831539777582778645411270433913301224819057222081543727263602678819745693540865806160910293144052079393615890645460901858988883318691997438568705602949652125

for j in range(130000000):
    a, b = gmpy2.iroot(ct + j * n, 3)
    if b == 1:
        m = a
        print(m)
        print(bytes.fromhex(hex(m)[2:]))
        break

Part 3

menggunakan cara yang sama seperti part 1

jawaban
n = 78604621794859254377441240758546691212252719196950677920996438809794723269891783763248474720077319283856135748212772766201496834837866985496988310839851402734816862730799141522806959739687508988075088500036281804849197202116396323478001075482571447841421840179024783853406299077136051285194547787251092448717
e = 65537
ct = 64260894456709053708131874606931233303294614435134258773719481625864684029722126297441699761600170345509407555526981816230807117628073227746581833033382845409470027697867835610091416408500724134007900766475301243929728458577316272426023726155915879223756361962204625550239964938010427596649916752055569962850

p = 8865924756891367526548784117109474928099627857597434007513939836088315293719086434197228572399671985200566321179910478312963492609208679794157183762974311
q = 8865924756891367526548784117109474928099627857597434007513939836088315293719086434197228572399671985200566321179910478312963492609208679794157183762975147

phi = (p-1)*(q-1)
d = inverse(e, phi)

print(pow(ct, d, n))
print(bytes.fromhex(hex(pow(ct, d, n))[2:]))