Algoritma RSA

Fri 19 Mar 2010 - 22:40

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.

(Rinaldi Munir, Discrete Math)

Pusing ? Saya sangat pusing :hammerhead: Contohnya menyusul ya.

Tambahan :
-RSA Id Wikipedia
-Algoritma RSA IF ITB

Sun 21 Mar 2010 - 23:26

=>Contoh RSA<=
--------------------------------------------------------------------------------------------------------------------------------------------------------------------
Kita akan mengenkripsikan dengan algoritma RSA. Pertama, bangkitkan sepasang kunci. Sebagai contoh, pilih a = 47 dan b = 71 (harus dalam bilangan besar supaya mefaktorkannya susah), maka dihitung n=ab=47.71=3337 dan selanjutnya m=(a-1)(b-1)=3220. Pilih kunci publik e=79 (yang relatif prima dengan 3220 karena pembagi terbesarnya adalah 1). Nila e dan n dapat dipublikasikan ke umum.
Selanjutnya akan dihitung kunci dekripsi d seperti yang dituliskan sebelumnya,

e d= 1 (mod m)

Dengan menggunakan cara diatas maka kita dapat menghitung kunci dekripsi sebagai berikut:

d=1+(k.3220)/79

Dengan mencoba nilai-nilai k = 1,2,3… maka diperoleh nilai d yang bulat adalah 1019. Ini adalah kunci dekripsi yang harus dirahasiakan.
Misalkan plainteks yang akan dienkripsikan adalah P=HARI INI (kita convert ke ASCII (decimal) adalah 7265827332737873). Pecah P menjadi blok yang lebih kecil, misalnya P dipecah menjadi 6 blok yang berukuran 3 digit:
P1=726 P4=273
P2=582 P5=787
P3=733 P6=003
Nilai-nilai pi ini masih terletak di dalam rentang nilai 0 sampai 3337 -1. Blok pertama di enkripsikan sebagai
726^79 mod 3337=1,4304567688284660347123409940007.10^226 mod 3337=215=c1
Blok kedua dienkripsikan juga sampai blok ke enam
582^79 mod 3337=776=c2
…
003^79 mod 3337=158=c6
Maka akan dihasilkan cipherteks C= 215 776 1743 933 1731 158
Untuk proses dekripsi dilakukan dengan menggunakan kunci rahasia d=1019, jadi tiap blok didekripsikan
215^1019 mod 3337=726=p1
…
158^1019 mod 3337=003=p6
Jadi dengan proses dekripsi diatas maka dihasilkan plainteks semula =7265827332737873 yang dalam bentuk karakter (decimal ASCII) adalah HARI INI.

(Rinaldi Munir, Discrete Math)

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