Maple Brsa

Maple-brsaaby

Setelah sekian lama tidak update blog yang berdebu ini author kembali, ingin update biar blog nya rame :p, kali ini author ingin membahas CTF Maple, yaitu soal cyptography brsa.

Setelah sekian lama keluar dari zona nyaman forensic author belajar beberapa kategori, seperti rev, crypto dan tipis tipis pentotsky. kali ini author ingin menjelaskan penyelesain terhadap chall brsa, dengan semudah mungkin karena author merasakan belajar enksripsi mtk ini, :uu dengan semangat elite, skill sulit :p

enc.py 

from Crypto.Util.number import getPrime, bytes_to_long
from secret import FLAG

msg = bytes_to_long(FLAG)
p = getPrime(512)
q = getPrime(512)
N = p*q
e = 0x10001
enc = pow(msg, e, N)
hint = p**4 - q**3

print(f"{N = }")
print(f"{e = }")
print(f"{enc = }")
print(f"{hint = }")

'''
N = 134049493752540418773065530143076126635445393203564220282068096099004424462500237164471467694656029850418188898633676218589793310992660499303428013844428562884017060683631593831476483842609871002334562252352992475614866865974358629573630911411844296034168928705543095499675521713617474013653359243644060206273
e = 65537
enc = 110102068225857249266317472106969433365215711224747391469423595211113736904624336819727052620230568210114877696850912188601083627767033947343144894754967713943008865252845680364312307500261885582194931443807130970738278351511194280306132200450370953028936210150584164591049215506801271155664701637982648648103
hint = 20172108941900018394284473561352944005622395962339433571299361593905788672168045532232800087202397752219344139121724243795336720758440190310585711170413893436453612554118877290447992615675653923905848685604450760355869000618609981902108252359560311702189784994512308860998406787788757988995958832480986292341328962694760728098818022660328680140765730787944534645101122046301434298592063643437213380371824613660631584008711686240103416385845390125711005079231226631612790119628517438076962856020578250598417110996970171029663545716229258911304933901864735285384197017662727621049720992964441567484821110407612560423282
'''

Dari enskripsi diatas sebenarnya nilai nilai enksripsi yang dilakukan adalah sebuah basic rsa dimana yang membedakan adalah point berikut

Refrensi https://en.wikipedia.org/wiki/RSA_(cryptosystem)

  • N yang digunakan adalah Big N atau N besar yang mana faktor dari sebuah nilai N besar pasti nya memiliki nilai besar yang cukup kompleks, sesuai refrensi berikut rsa
  • Selanjutnya digunakan generate secara random dengan nilai 512 bits, nilai p dan q tidak bisa ditebak karena dengan menggunakan function pada getPrime yang membuat nilai di generate dengan 512 bits. rsa
  • lalu dilakukan pow(msg,en) yaitu == msg ** e % n
  • lalu diakhir pembuat soal melakukan nilai hint dengan p**4 - q**3, pada proses ini lah yang membuat soal menjadi vuln yang bisa diselesaikan oleh author

Penyelesaian

Berdasarkan dari refrensi wikipedia berikut nilai nilai yang di butuhkan untuk menyelasaikan suatu enskripsi pada rsa

rsa

  • Pertama tama harus di faktorkan nilai dari sebuah N, karena umumnya n terbentuk dari p * q, maka pasti nya ada pembentuk kedua variabel dalam pembetukan nilai N, namun dengan menggunakan kakulator factor online untuk mempermudah author, tapi masih tidak di temukan hasil dari p dan q, https://www.alpertron.com.ar/ECM.HTM
  • Setelah mengamati lebih dalam karena tidak bisa menggunan kalkulator online untuk factor, ternyata nilai p dan q bisa dicari dengan dua cara, sebagai gambar berikut
  • Author prefer menggunakan rumus 1, karena untuk hanya menyari p dan q dengan menggunakan eliminasi, namun kalau diitung secara manual tentu akan memakan waktu dan cenderung tidak tepat, dari sini author memanfaakan sebuah libray pada python yang digunakan untuk mencari nilai suatu persamaan
solver = Solver()
p = Int('p')
q = Int('q')
solver.add(p**4 - q**3 == hint)
solver.add(p*q == N)
solver.add(p>1)
solver.add(q>1)

solver.check()
print(solver.model())

Sehingga didapatkan nilai p dan q, kemudian tinggal gunakan saja kerumus untuk penyelasaian pada refrensi wikipedia diatas, sehingga menjadi seperit berikut

from Crypto.Util.number import *
from z3 import *

N = 134049493752540418773065530143076126635445393203564220282068096099004424462500237164471467694656029850418188898633676218589793310992660499303428013844428562884017060683631593831476483842609871002334562252352992475614866865974358629573630911411844296034168928705543095499675521713617474013653359243644060206273
e = 65537
enc = 110102068225857249266317472106969433365215711224747391469423595211113736904624336819727052620230568210114877696850912188601083627767033947343144894754967713943008865252845680364312307500261885582194931443807130970738278351511194280306132200450370953028936210150584164591049215506801271155664701637982648648103
hint = 20172108941900018394284473561352944005622395962339433571299361593905788672168045532232800087202397752219344139121724243795336720758440190310585711170413893436453612554118877290447992615675653923905848685604450760355869000618609981902108252359560311702189784994512308860998406787788757988995958832480986292341328962694760728098818022660328680140765730787944534645101122046301434298592063643437213380371824613660631584008711686240103416385845390125711005079231226631612790119628517438076962856020578250598417110996970171029663545716229258911304933901864735285384197017662727621049720992964441567484821110407612560423282
#hint = p**4 - q**3

'''
solver = Solver()
p = Int('p')
q = Int('q')
solver.add(p**4 - q**3 == hint)
solver.add(p*q == N)
solver.add(p>1)
solver.add(q>1)

solver.check()
print(solver.model())
'''

q = 11248052945492193606877386307812298309646455365482356576580845624056836046347518805927852646289457003475918197991787867864250859819603651806169306473552239
p = 11917573148183173444338385104784582231114229409447057112131253050235068806316496452352116287542988361044359262597423159386263430710183647113674868056755407

phi = (p-1) * (q-1)
d = inverse(e,phi)
m = long_to_bytes(pow(enc,d,N))
print(m)

flag