picoCTF — Mind your Ps and Qs Write-Up

Deskripsi

"Bits are expensive, I used only a little bit over 100 to save money."

Challenge ini memberikan parameter RSA berupa ciphertext c, modulus n, dan public exponent e. Petunjuk yang diberikan mengarah pada ukuran modulus yang sangat kecil sehingga dapat difaktorkan secara langsung.

Parameter yang Diberikan

c = 15341890103764929939105506004034128738090325640037083301857608662849501626260517

n = 948406957756830799684818171639547165784816468744946013083947881743680617123566349

e = 65537

Analisis

Kerentanan: Modulus RSA Terlalu Kecil

Keamanan RSA bergantung pada sulitnya memfaktorkan modulus:

n = p × q

Pada implementasi RSA modern, ukuran modulus umumnya minimal 2048-bit sehingga faktorisasi menjadi tidak praktis.

Namun pada challenge ini, nilai n hanya sekitar 256-bit. Dengan ukuran sekecil ini, faktor prima penyusunnya dapat ditemukan dengan mudah menggunakan tool seperti:

• FactorDB
• YAFU
• msieve

Begitu nilai p dan q diketahui, seluruh kunci privat dapat direkonstruksi.

Mengapa Ini Berbahaya?

Karena n sangat kecil, serangan tidak memerlukan teknik RSA lanjutan. Faktorisasi langsung sudah cukup untuk memperoleh plaintext.

Solusi

Langkah-Langkah

1. Faktorkan n menjadi p dan q
2. Hitung φ(n) = (p−1)(q−1)
3. Cari private exponent:
      d = e⁻¹ mod φ(n)
4. Dekripsi ciphertext:
      m = c^d mod n
5. Konversi hasil ke bytes
6. Balik urutan string karena output tersimpan terbalik

Hasil Faktorisasi

p = 1891771437429478964908181306574287207137
q = 501332739776173570344039681219489434626477

Exploit Script

from Crypto.Util.number import inverse, long_to_bytes

c = 15341890103764929939105506004034128738090325640037083301857608662849501626260517
n = 948406957756830799684818171639547165784816468744946013083947881743680617123566349
e = 65537

p = 1891771437429478964908181306574287207137
q = 501332739776173570344039681219489434626477

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

m = pow(c, d, n)

decrypted = long_to_bytes(m)
print("Decoded bytes:", decrypted)

Output

b'}19ea7cd1_do0g_0n_N_11ams{FTCocip'

Output terlihat terbalik. Membalik string menghasilkan:

flag = b"}19ea7cd1_do0g_0n_N_11ams{FTCocip"[::-1]
print(flag.decode())

Output Akhir

picoCTF{sma11_N_n0_g0od_1dc7ae91}

Flag

picoCTF{sma11_N_n0_g0od_1dc7ae91}

Nama flag secara langsung menggambarkan kelemahan challenge ini: modulus N yang terlalu kecil sehingga tidak aman.

Diagram Serangan

Public Key:
    (n, e)

          |
          v

   Faktorkan n
      n = p × q

          |
          v

 Hitung φ(n)

          |
          v

 Cari d = e⁻¹ mod φ(n)

          |
          v

 Dekripsi:
   m = c^d mod n

          |
          v

   Konversi ke bytes
   & balik string

          |
          v

         FLAG

Key Takeaways

1. Ukuran modulus RSA sangat penting — Jika n terlalu kecil, faktorisasi menjadi mudah dilakukan.

2. Keamanan RSA bergantung pada kesulitan faktorisasi — Mengetahui p dan q berarti mengetahui seluruh kunci privat.

3. Public exponent yang aman tidak cukup — Walaupun e = 65537 merupakan nilai standar, RSA tetap runtuh jika n terlalu kecil.

4. Gunakan ukuran kunci modern — Minimal 2048-bit untuk penggunaan praktis saat ini.

Tools yang Digunakan

• FactorDB — Untuk menemukan faktor prima modulus.
• Python — Untuk menghitung private key dan melakukan dekripsi RSA.
• PyCryptodome — inverse() dan long_to_bytes().