Jabarkan Keamanan dari RSA

Penyerangan yang paling umum pada RSA ialah pada penanganan masalah faktorisasi pada bilangan yang sangat besar. Apabila terdapat faktorisasi metode yang baru dan cepat telah dikembangkan, maka ada kemungkinan untuk membongkar RSA.

Pada tahun 2005, bilangan faktorisasi terbesar yang digunakan secara umum ialah sepanjang 663 bit, menggunakan metode distribusi mutakhir. Kunci RSA pada umumnya sepanjang 1024—2048 bit. Beberapa pakar meyakini bahwa kunci 1024-bit ada kemungkinan dipecahkan pada waktu dekat (hal ini masih dalam perdebatan), tetapi tidak ada seorangpun yang berpendapat kunci 2048-bit akan pecah pada masa depan yang terprediksi.

Semisal Eve, seorang eavesdropper (pencuri dengar—penguping), mendapatkan public key N dan e, dan ciphertext c. Bagimanapun juga, Eve tidak mampu untuk secara langsung memperoleh d yang dijaga kerahasiannya oleh Alice. Masalah untuk menemukan n seperti pada ne=c mod N di kenal sebagai permasalahan RSA.

Cara paling efektif yang ditempuh oleh Eve untuk memperoleh n dari c ialah dengan melakukan faktorisasi N kedalam p dan q, dengan tujuan untuk menghitung (p-1)(q-1) yang dapat menghasilkan d dari e. Tidak ada metode waktu polinomial untuk melakukan faktorisasi pada bilangan bulat berukuran besar di komputer saat ini, tapi hal tersebut pun masih belum terbukti.

Masih belum ada bukti pula bahwa melakukan faktorisasi N adalah satu-satunya cara untuk memperoleh n dari c, tetapi tidak ditemukan adanya metode yang lebih mudah (setidaknya dari sepengatahuan publik).

Bagaimanapun juga, secara umum dianggap bahwa Eve telah kalah jika N berukuran sangat besar.

Jika N sepanjang 256-bit atau lebih pendek, N akan dapat difaktorisasi dalam beberapa jam pada Personal Computer, dengan menggunakan perangkat lunak yang tersedia secara bebas.

Jika N sepanjang 512-bit atau lebih pendek, N akan dapat difaktorisasi dalam hitungan ratusan jam seperti pada tahun 1999. Secara teori, perangkat keras bernama TWIRL dan penjelasan dari Shamir dan Tromer pada tahun 2003 mengundang berbagai pertanyaan akan keamanan dari kunci 1024-bit. Santa disarankan bahwa N setidaknya sepanjang 2048-bit.

Pada thaun 1993, Peter Shor menerbitkan Algoritme Shor, menunjukkan bahwa sebuah komputer quantum secara prinsip dapat melakukan faktorisasi dalam waktu polinomial, mengurai RSA dan algoritme lainnya. Bagaimanapun juga, masih terdapat pedebatan dalam pembangunan komputer quantum secara prinsip.