RSA
RSA di bidang kriptografi adalah sebuah algoritme pada enkripsi "public key". RSA merupakan algoritme pertama yang cocok untuk "digital signature" seperti halnya ekripsi, dan salah satu yang paling maju dalam bidang kriptografi "public key". RSA masih digunakan secara luas dalam protokol "electronic commerce", dan dipercaya dalam mengamnkan dengan menggunakan kunci yang cukup panjang.
Algortima RSA dijabarkan pada tahun 1977 oleh tiga orang: Ron Rivest, Adi Shamir dan Len Adleman dari Massachusetts Institute of Technology. Huruf RSA itu sendiri berasal dari inisial nama mereka (Rivest-Shamir-Adleman).
Clifford Cocks, seorang matematikawan Inggris yang bekerja untuk GCHQ, menjabarkan tentang sistem ekuivalen pada dokumen internal pada tahun 1973. Penemuan Clifford Cocks tidak terungkap hingga tahun 1997 karena alasan "top-secret classification".
Algoritme tersebut dipatenkan oleh Massachusetts Institute of Technology pada tahun 1983 di Amerika Serikat sebagai. Paten tersebut berlaku hingga 21 September 2000. Semenjak Algoritme RSA dipublikasikan sebagai aplikasi paten, regulasi di sebagian besar negara-negara lain tidak memungkinkan penggunaan paten. Hal ini menyebabkan hasil temuan Clifford Cocks di kenal secara umum, paten di Amerika Serikat tidak dapat mematenkannya.
Semisal Alice berkeinginan untuk mengizinkan Bob untuk mengirimkan kepadanya sebuah pesan pribadi ("private message") melalui media transmisi yang tidak aman ("insecure"). Alice melakukan langkah-langkah berikut untuk membuat pasangan kunci "public key" dan "private key":Pada "public key" terdiri atas:
Biasanya, berbeda dari bentuk "private key" (termasuk parameter CRT): Bentuk ini membuat proses dekripsi lebih cepat dan "signing" menggunakan Chinese Remainder Theorem (CRT). Dalam bentuk ini, seluruh bagian dari "private key" harus dijaga kerahasiaannya.
Alice mengirimkan "public key" kepada Bob, dan tetap merahasiakan "private key" yang digunakan. "p" dan "q" sangat sensitif dikarenakan merupakan faktorial dari "N", dan membuat perhitungan dari "d" menghasilkan "e". Jika "p" dan "q" tidak disimpan dalam bentuk CRT dari "private key", maka "p" dan "q" telah terhapus bersama nilai-nilai lain dari proses pembangkitan kunci.
Misalkan Bob ingin mengirim pesan "m" ke Alice. Bob mengubah "m" menjadi angka "n"  "N", menggunakan protokol yang sebelumnya telah disepakati dan dikenal sebagai "padding scheme".
Maka Bob memiliki "n" dan mengetahui "N" dan "e", yang telah diumumkan oleh Alice. Bob kemudian menghitung "ciphertext" "c" yang terkait pada "n": Perhitungan tersebut dapat diselesaikan dengan cepat menggunakan metode "exponentiation by squaring". Bob kemudian mengirimkan "c" kepada Alice.
Alice menerima "c" dari Bob, dan mengetahui "private key" yang digunakan oleh Alice sendiri. Alice kemudian memulihkan "n" dari "c" dengan langkah-langkah berikut: Perhitungan di atas akan menghasilkan "n", dengan begitu Alice dapat mengembalikan pesan semula "m". Prosedur dekripsi bekerja karena
Kemudian, dikarenakan "ed"  1 (mod p-1) dan "ed"  1 (mod q-1), hasil dari "Fermat's little theorem".
Dikarenakan "p" dan "q" merupakan bilangan prima yang berbeda, mengaplikasikan Chinese Remainder Theorem akan menghasilkan dua macam kongruen
Berikut ini merupakan contoh dari enkripsi RSA dan dekripsinya. Parameter yang digunakan disini berupa bilangan kecil.
"Public key" yang digunakan adalah ("e","N"). "Private key" yang digunakan adalah "d". Fungsi pada enkripsi ialah: dimana "n" adalah "plaintext" Fungsi dekripsi ialah: dimana "c" adalah "ciphertext"
"Padding Scheme" harus dibangun secara hati-hati sehingga tidak ada nilai dari "m" yang menyebabkan masalah keamanan. Sebagai contoh, jika kita ambil contoh sederhana dari penampilan ASCII dari "m" dan menggabungkan bit-bit secara bersama-sama akan menghasilkan "n", kemudian pesan yang berisi ASCII tunggal karakter codice_1 (nilai numeris 0) akan menghasilkan
"n"= 0, yang akan menghasilkan "ciphertext" 0 apapun itu nilai dari "e" dan "N" yang digunakan. Sama halnya dengan karakter ASCII tunggal codice_2 (nilai numeris 1) akan selalu menghasilkan "ciphertext" 1. Pada kenyataannya, untuk sistem yang menggunakan nilai "e" yang kecil, seperti 3, seluruh karakter tunggal ASCII pada pesan akan disandikan menggunakan skema
yang tidak aman, dikarenakan nilai terbesar "n" adalah nilai 255, dan 255 menghasilkan nilai yang lebih kecil dari modulus yang sewajarnya, maka proses dekripsi akan menjadi masalah sederhana untuk mengambil pola dasar dari "ciphertext" tanpa perlu menggunakan modulus "N". Sebagai konsekuensinya, standar seperti PKCS didesain dengan sangat
hati-hati sehingga membuat pesan asal-asalan dapat terenkripsi secara aman. Dan juga berdasar pada bagian Kecepatan, akan dijelaskan kenapa "m" hampir bukanlah pesan itu sendiri tetapi lebih pada "message key" yang dipilh secara acak.
RSA dapat juga digunakan untuk mengesahkan sebuah pesan. Misalkan Alice ingin mengirim pesan kepada Bob. Alice membuat sebuah "hash value" dari pesan tersebut, di pangkatkan dengan bilangan "d" dibagi "N" (seperti halnya pada deskripsi pesan), dan melampirkannya sebagai "tanda tangan" pada pesan tersebut. Saat Bob menerima pesan yang telah "ditandatangani", Bob memangkatkan "tanda tangan"
tersebut dengan bilangan "e" dibagi "N" (seperti halnya pada enkripsi pesan), dan membandingkannya dengan nilai hasil dari "hash value" dengan "hash value" pada pesan tersebut. Jika kedua cocok, maka Bob dapat mengetahui bahwa pemilik dari pesan tersebut adalah Alice, dan pesan pun tidak pernah diubah sepanjang pengiriman.
Harap dicatat bahwa "padding scheme" merupakan hal yang esensial untuk mengamankan pengesahan pesan seperti halnya pada enkripsi pesan, oleh karena itu kunci yang sama tidak digunakan pada proses enkripsi dan pengesahan.
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 "n=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).
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.