RSA
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.
Menemukan bilangan prima besar "p" dan "q" pada biasanya didapat dengan mencoba serangkaian bilangan acak dengan ukuran yang tepat menggunakan probabilitas bilangan prima yang dapat dengan cepat menghapus hampir semua bilangan bukan prima.
"p" dan "q" seharusnya tidak "saling-berdekatan", agar faktorisasi fermat pada "N" berhasil. Selain itu pula, jika "p"-1 atau "q"-1 memeiliki faktorisasi bilangan prima yang kecil, "N" dapat difaktorkan secara mudah dan nilai-nilai dari "p" atau "q" dapat diacuhkan.
Seseorang seharusnya tidak melakukan metode pencarian bilangan prima yang hanya akan memberikan informasi penting tentang bilangan prima tersebut kepada penyerang. Biasanya, pembangkit bilangan acak yang baik akan memulai nilai bilangan yang digunakan. Harap diingat, bahwa kebutuhan disini ialah "acak" dan "tidak-terduga". Berikut ini mungkin tidak memenuhi kriteria, sebuah bilangan
mungkin dapat dipilah dari proses acak (misal, tidak dari pola apapun), tetapi jika bilangan itu mudah untuk ditebak atau diduga (atau mirip dengan bilangan yang mudah ditebak), maka metode tersebut akan kehilangan kemampuan keamanannya. Misalnya, tabel bilangan acak yang diterbitkan oleh Rand Corp pada tahun 1950-an mungkin memang benar-benar teracak, tetapi dikarenakan
diterbitkan secara umum, hal ini akan mempermudah para penyerang dalam mendapatkan bilangan tersebut. Jika penyerang dapat menebak separuh dari digit "p" atau "q", para penyerang dapat dengan cepat menghitung separuh yang lainnya (ditunjukkan oleh Donald Coppersmith pada tahun 1997).
Sangatlah penting bahwa kunci rahasia "d" bernilai cukup besar, Wiener menunjukkan pada tahun 1990 bahwa jika "p" di antara "q" dan 2"q" (yang sangat mirip) dan "d" lebih kecil daripada "N"/3, maka "d" akan dapat dihitung secara effisien dari "N" dan "e". Kunci enkripsi "e" = 2 sebaiknya tidak digunakan.
RSA memiliki kecepatan yang lebih lambat dibandingkan dengan DES dan algoritme simetrik lainnya. Pada praktiknya, Bob menyandikan pesan rahasia menggunakan algoritme simetrik, menyandikan kunci simetrik menggunakan RSA, dan mengirimkan kunci simetrik yang dienkripsi menggunakan RSA dan juga mengirimkan pesan yang dienkripsi secara simetrik kepada Alice.
Prosedur ini menambah permasalahan akan keamanan. Singkatnya, Sangatlah penting untuk menggunakan pembangkit bilangan acak yang kuat untuk kunci simetrik yang digunakan, karena Eve dapat melakukan "bypass" terhadap RSA dengan menebak kunci simterik yang digunakan.
Sebagaimana halnya "cipher", bagaimana "public key" RSA didistribusi menjadi hal penting dalam keamanan. Distribusi kunci harus aman dari "man-in-the-middle attack" ("penghadang-di tengah-jalan"). Anggap Eve dengan suatu cara mampu memberikan kunci arbitari kepada Bob dan membuat Bob percaya bahwa kunci tersebut milik Alice. Anggap Eve dapan "menghadang" sepenuhnya transmisi antara Alice dan Bob. Eve
mengirim Bob "public key" milik Eve, dimana Bob percaya bahwa "public key" tersebut milik Alice. Eve dapat menghadap seluruh "ciphertext" yang dikirim oleh Bob, melakukan dekripsi dengan kunci rahasia milik Eve sendiri, menyimpan salinan dari pesan tersebut, melakukan enkripsi menggunakan "public key" milik Alice, dan mengirimkan "ciphertext" yang baru kepada Alice. Secara prinsip, baik Alice atau Bob tidak
menyadari kehadiran Eve di antara transmisi mereka. Pengamanan terhadap serangan semacam ini yaitu menggunakan sertifikat digital atau komponen lain dari infrastuktur "public key".
Kocher menjelaskan sebuah serangan baru yang cerdas pada RSA pada tahun 1995: jika penyerang, Eve, mengetahui perangkat keras yang dimiliki oleh Alice secara terperinci dan mampu untuk mengukur waktu yang dibutuhkan untuk melakukan dekripsi untuk beberapa "ciphertext", Eve dapat menyimpulkan kunci dekripsi "d" secara cepat. Penyerangan ini dapat juga diaplikasikan pada skema "tanda tangan" RSA. SAlah
satu cara untuk mencegah penyerangan ini yaitu dengan memastikan bahwa operasi dekripsi menggunakan waktu yang konstan untuk setiap "ciphertext" yang diproses. Cara yang lainnya, yaitu dengan menggunakan properti multipikatif dari RSA. Sebagai ganti dari menghitung "c mod N", Alice pertama-tama memilih nilai bilangan acak "r" dan menghitung "(rc) mod N". Hasil dari penghitungan tersebut ialah
"rm mod N" kemudian efek dari "r" dapat dihilangkan dengan perkalian dengan inversenya. Nilai baru dari "r" dipilih pada tiap "ciphertext". Dengan teknik ini, dikenal sebagai "message blinding" (pembutaan pesan), waktu yang diperlukan untuk proses dekripsi tidak lagi berhubungan dengan nilai dari "ciphertext" sehingga penyerangan waktu akan gagal.
Pada tahun 1998, Daniel Bleichenbacher menjelaskan penggunaan penyerangan "ciphertext" adaptive, terhadap pesan yang terenkripsi menggunakan RSA dan menggunakan PKCS #1 v1 "padding scheme". Dikarenakan kecacatan pada skema PKCS #1, Bleichenbacher mampu untuk melakukan serangkaian serangan terhadap implementasi RSA pada protokol Secure Socket Layer, dan secara potensial mengungkap kunci-kunci yang digunakan. Sebagai hasilnya,
para pengguna kriptografi menganjurkan untuk menggunakan "padding scheme" yang relatif terbukti aman seperti "Optimal Asymmetric Encryption Padding", dan Laboratorium RSA telah merilis versi terbaru dari PKCS #1 yang tidak lemah terdapat serangan ini.