Even RSA : picoCTF Crypto Challenge (Easy)

Even RSA : picoCTF Crypto Challenge (Easy)

Challenge Overview

Deskripsi Challenge:

This service provides you an encrypted flag. Can you decrypt it with just N & e?Flag: picoCTF{tw0_1$_pr!m341c6ed35}

Pendahuluan

Challenge ini judulnya provokatif banget, "Even RSA Can Be Broken???". Biasanya RSA itu aman selama modulus N-nya besar dan prime factor-nya (p dan q) dipilih secara benar-benar acak. Tapi di soal ini kita cuma dikasih N dan e publik, terus disuruh dekripsi ciphertext-nya. Kalau semuanya digenerate dengan benar, ini seharusnya mustahil tanpa factoring N yang notabene 1024-bit, alias butuh waktu bertahun-tahun. Jadi pasti ada yang salah dari cara kunci ini digenerate.

Mengenal Konsep: Kekuatan RSA Bergantung pada Randomness

Keamanan RSA itu bertumpu penuh di satu titik: p dan q harus benar-benar random dan besar. Kalau generator prime yang dipakai (get_primes() di source code soal) punya pool angka yang kecil, atau random seed-nya predictable, ada risiko besar dua N dari dua request yang berbeda ternyata berbagi salah satu faktor prima yang sama.

Kalau itu terjadi, N jadi gampang banget difaktorkan, cukup dengan gcd(N1, N2) buat dapetin faktor primanya, tanpa perlu brute-force atau algoritma factoring berat sama sekali. Begitu p dan q ketemu, tinggal hitung:

• Phi = (p-1)(q-1)
• D = inverse(e, Phi) → private key
• Plaintext = ciphertext^D mod N

Source code encrypt.py dari soal ini konfirmasi dugaan tersebut:

def gen_key(k):
    p,q = get_primes(k//2)
    N = p*q
    d = inverse(e, (p-1)*(q-1))
    return ((N,e), d)

Prime-nya digenerate lewat fungsi custom get_primes(), bukan library standar yang sudah teruji cryptographically secure, jadi wajar kalau ini jadi celah utamanya.

Penyelesaian Challenge

Langkah 1: Connect ke Server

Jalankan nc sesuai instruksi soal:

nc verbal-sleep.picoctf.net 53538

Server langsung balas dengan public key dan ciphertext-nya:

N: 150878353809341207584129537211859912170389420466756781340782...
e: 65537
cyphertext: 118979741410285453199842752546045709491055527947000...

Langkah 2: Cek dCode RSA Cipher

Karena N-nya lemah, nggak perlu ngumpulin beberapa N dari request berbeda buat cari gcd manual. Tools dCode RSA Cipher (dcode.fr/rsa-cipher) sudah punya fitur otomatis buat mendekomposisi N yang "self-limited" jadi faktor prima P dan Q.

Buka https://www.dcode.fr/rsa-cipher, lalu isi:

• C (cipher message) → nilai cyphertext dari netcat
• E (public exponent) → 65537
• N (public key value) → nilai N dari netcat

Klik Calculate/Decrypt.

Langkah 3: Baca Hasilnya

dCode otomatis:

• Melakukan factorization pada N → dapat P dan Q
• Hitung D (private key) via modular inverse
• Dekripsi ciphertext langsung jadi plaintext

Hasilnya langsung keluar flag-nya:

picoCTF{tw0_1$_pr!m341c6ed35}

Kesimpulan

Beberapa hal yang bisa diambil dari challenge Even RSA ini:

• Nama flag-nya sendiri sudah kasih clue: "two is prime", mengacu ke prime factor yang predictable/berulang akibat generator random yang lemah.
• Keamanan RSA nggak cuma soal ukuran bit N yang besar, tapi juga kualitas randomness saat generate p dan q. N sebesar 1024-bit pun bisa jebol kalau prime generator-nya nggak benar-benar acak.
• Nggak semua serangan RSA butuh algoritma factoring canggih. Kalau kuncinya lemah, tools decoder online biasa kayak dCode saja sudah cukup buat mendekripsi tanpa private key sama sekali.
• Selalu pakai library cryptography yang sudah teruji (seperti Crypto.PublicKey.RSA dari PyCryptodome) buat generate prime, jangan bikin generator sendiri kalau nggak paham betul soal entropy dan randomness.

Flag: picoCTF{tw0_1$_pr!m341c6ed35}

Selamat mencoba challenge lainnya di PicoCTF! 🚩