Cryptosystem
Dalam tantangan ini, diberikan sebuah skrip Python yang mengenkripsi sebuah flag menggunakan algoritma RSA. Namun, hanya diberikan nilai ciphertext (c) dan modulus (n) tanpa mengetahui nilai faktor primanya (p dan q). Tujuan saya adalah menemukan private key (d) untuk mendekripsi ciphertext dan mendapatkan flag.
Category: Crypto || Level: EASY
📌Analisis
Diberikan skrip berikut:
from Crypto.Util.number import *
from flag import FLAG
def primo(n):
n += 2 if n & 1 else 1
while not isPrime(n):
n += 2
return n
p = getPrime(1024)
q = primo(p)
n = p * q
e = 0x10001
d = inverse(e, (p-1) * (q-1))
c = pow(bytes_to_long(FLAG.encode()), e, n)
Dari kode di atas, dapat memahami bahwa:
p adalah bilangan prima 1024-bit yang dipilih secara acak.
q adalah bilangan prima berikutnya setelah (menggunakan fungsi primo(p)).
n = p × q adalah modulus yang digunakan dalam enkripsi RSA.
e adalah eksponen publik.
d adalah eksponen privat yang dihitung sebagai invers modular dari terhadap totient.
Ciphertext (c) adalah hasil enkripsi dari flag.
Diberikan hanya nilai n dan c, sehingga perlu mencari p dan q untuk menghitung d dan mendekripsi pesan.
📌Solusi
Karena q adalah bilangan prima setelah p, saya bisa merekonstruksi faktor-faktor n dengan cara berikut:
Menghitung perkiraan p menggunakan akar kuadrat dari n.
Menggunakan fungsi prevprime() dari library sympy untuk mencari bilangan prima sebelum hasil akar tersebut.
Menggunakan nextprime(p) untuk mencari q, karena saya tahu bahwa q adalah bilangan prima setelah p.
Memverifikasi p × q = n apakah untuk memastikan bahwa faktorisasi saya benar.
Setelah mendapatkan p dan q, saya menghitung Euler's Totient Function ϕ(n)=(p-1) × (q-1). Kemudian, saya menghitung eksponen privat d sebagai: d = e⁻¹ mod ϕ(n)
Setelah mendapatkan d, saya bisa mendekripsi ciphertext c dengan rumus: m=c^d mod n. Kemudian, hasilnya dikonversi kembali menjadi teks asli.
📌Implementasi Code
Berikut adalah script Python yang saya gunakan untuk menyelesaikan tantangan ini:
import gmpy2
from sympy import prevprime, nextprime
from Crypto.Util.number import long_to_bytes, inverse
n = 15956250162063169819282947443743274370048643274416742655348817823973383829364700573954709256391245826513107784713930378963551647706777479778285473302665664446406061485616884195924631582130633137574953293367927991283669562895956699807156958071540818023122362163066253240925121801013767660074748021238790391454429710804497432783852601549399523002968004989537717283440868312648042676103745061431799927120153523260328285953425136675794192604406865878795209326998767174918642599709728617452705492122243853548109914399185369813289827342294084203933615645390728890698153490318636544474714700796569746488209438597446475170891
c = 3591116664311986976882299385598135447435246460706500887241769555088416359682787844532414943573794993699976035504884662834956846849863199643104254423886040489307177240200877443325036469020737734735252009890203860703565467027494906178455257487560902599823364571072627673274663460167258994444999732164163413069705603918912918029341906731249618390560631294516460072060282096338188363218018310558256333502075481132593474784272529318141983016684762611853350058135420177436511646593703541994904632405891675848987355444490338162636360806437862679321612136147437578799696630631933277767263530526354532898655937702383789647510
e = 0x10001 # 65537
# Cari p menggunakan akar kuadrat dari n
approx_p = gmpy2.isqrt(n)
# Cari p sebagai bilangan prime sebelumnya
p = prevprime(approx_p)
# Hitung q sebagai bilangan prima setelah p
q = nextprime(p)
# Verifikasi apakah p * q = n
assert p * q == n, "Factorization failed!"
# Hitung totient
phi = (p - 1) * (q - 1)
# Hitung private key d
d = inverse(e, phi)
# Dekripsi pesan
m = pow(c, d, n)
# Konversi ke string
flag = long_to_bytes(m)
print(flag.decode())
Final Flag🎯
Hasil eksekusi:
THM{Just_s0m3_small_amount_of_RSA!}
Kesimpulan
RSA bisa dieksploitasi jika bilangan prima dipilih dengan pola tertentu.
Mengetahui struktur pemilihan p dan q mempermudah faktorisasi .
Metode prevprime() dan nextprime() sangat efektif untuk menemukan faktor bilangan prima ketika ada hubungan khusus antara p dan q.
Penting untuk menggunakan bilangan prima yang dipilih secara acak agar sistem RSA tetap aman.
Melalui tantangan ini, saya belajar lebih dalam tentang keamanan dalam kriptografi dan bagaimana RSA dapat menjadi rentan jika implementasinya tidak dilakukan dengan benar.
