Algoritma RSA

Algoritma RSA diperkenalkan oleh tiga peneliti dari MIT, yaitu Ron Rivest, Adi Shamir, dan Len Addleman
pada tahun 1976. RSA mendasarkan proses enkripsi dan dekripsinya pada konsep bilangan prima
dan aritmetika modulo. Baik kunci enkripsi maupun dekripsi keduanya merupakan bilangan bulat.
Kunci enkripsi tidak dirahasiakan dan diketahui umum (kunci publik), namun kunci untuk dekripsi
bersifat rahasia. Kunci dekripsi dibangkitkan dari beberapa buah bilangan prima bersama-sama dengan
kunci enkripsi. Untuk menemukan kunci dekripsi, orang harus memfaktorkan suatu bilangan non prima
menjadi faktor primanya. Kenyataannya, memfaktorkan bilangan non prima menjadi faktor primanya 
bukanlah pekerjaan yang mudah. Semakin besar bilangan primanya tentu semakin sulit pula pemfaktorannya
Semakin sulit pemfaktorannya semakin kuat pula algoritma RSA. Secara ringkas, algoritma RSA terdiri
dari 3 bagian, yaitu bagian untuk membangkitkan pasangan kunci, bagian untk enkripsi, dan bagian 
untuk dekripsi :

-------------------------------------------------------------------------------------------------------------------------------------------
ALGORITMA RSA

=>Pembangkitan pasangan kunci 
1. Pilih 2 buah bilangan prima sembarang, sebut a dan b. Rahasiakan a dan b ini.
2. Hitung n=a.b hasil n tidak perlu dirahasiakan.
3. Hitung m=(a-1)(b-1). Sekali m telah dihitung, a dan b dapat dihapus untuk mencegah diketahui
oleh pihak lain
4. Pilih sebuah bilangan bulat untuk kunci publik, sebutnamnya e, yang relatif prima terhadap m
5. Hitung kunci dekripsi,d, dengan kekongruenan ed=1 (mod m)

=>Enkripsi
1. Nyatakan pesan menjadi blok-blok plainteks: p1,p2,p3... (harus dipenuhi persyaratan bahwa nilai
pi, harus terletak dalam himpunan nilai 0,1,2,...,n-1 untuk menjamin hasil perhitunan tidak berada
diluar himpunan)
2. Hitung blok cipherteks ci, untuk blok plainteks pi dengan persamaan

ci=pi^e mod n
yang dalam hal ini, e adalah kunci publik

=>Dekripsi
1. Proses dekripsi dapat dilakukan dengan menggunakan persamaan

pi=ci^d mod n
yang dalam hal ini, d adalah kunci pribadi

-------------------------------------------------------------------------------------------------------------------------------------------

Perhatikan langkah 5 pada proses pembangkitan pasangan kunci. Kekongruenan ed=1 (mod m)
sama dengan ed mod m=1. Persamaan a=b (mod m) ekivalen dengan a=b+km, maka ed=1 (mod m)
ekivalen dengan ed=1+km, sehingga d dapat dihitung dengan cara yang sederhana dengan persamaan

d=1+km/e

Dalam implementasi sebenarnya nilai a dan b disarankan nilai yang sangat besar (100 angka) agar
pekerjaan memfaktorkan n menjadi faktor primanya menjadi sangat sukar bahkan hampir tidak mungkin
dapat dilakukan.