Algoritma Kriptografi RSA
RSA adalah salah satu contoh kriptografi yang menerapkan konsep public key. Algoritma ini
pertama kali dipublikasikan di tahun 1977 oleh Ron Rivest, Adi Shamir, dan Leonard Adleman dari
Massachusetts Institute of Technology (MIT). Nama RSA sendiri adalah singkatan dari nama
belakang mereka bertiga.
Clifford Cocks, seorang matematikawan Inggris sebenarnya juga telah mengembangkan
algoritma yang hampir sama dengan RSA ini pada tahun 1973. Namun algoritma buatannya tidak
begitu dikenal oleh publik, dan baru dipublikasi pada tahun 1997 karena merupakan proyek rahasia.
Walau begitu algoritma yang dikembangkan Rivest, Shamir, dan Adleman tidak berhubungan
dengan pekerjaan Cocks.
Pada algoritma RSA terdapat 3 langkah utama yaitu key generation (pembangkitan kunci),
enkripsi, dan dekripsi.
Kunci pada RSA mencakup dua buah kunci, yaitu public key dan private key. Public key
digunakan untuk melakukan enkripsi, dan dapat diketahui oleh orang lain. Sedangkan private key
tetap dirahasiakan dan digunakan untuk melakukan dekripsi.
Pembangkitan kunci atau key generation dari RSA adalah sebagai berikut :
1. Pilih dua buah bilangan prima sembarang a dan b. Jaga kerahasiaan a dan b ini.
2. Hitung n = a * b. Besaran n ini tidak perlu dirahasiakan.
3. Hitung m = (a-1) * (b-1). Sekali m telah dihitung, a dan b dapat dihapus untuk
mencegah diketahuinya oleh pihak lain.
4. Pilih sebuah bilangan bulat untuk kunci publik, sebut namanya e, yang relatif prima
terhadap m (relatif prima berarti GCD(e, m) = 1) dengan syarat e ≠ (p-1), e ≠ (q-1),
dan e < n
5. Hitung kunci dekripsi, d, dengan kekongruenan ed ≡1 (mod m).
Proses enkripsi dapat dilakukan dengan :
Ci = Pi
e mod n
Sedangkan proses dekripsi dilakukan dengan :
Pi = Ci
d mod n
6
Blok-blok plainteks dinyatakan dengan p1, p2, p3, ... (harus dipenuhi persyaratan bahwa nilai pi
harus terletak dalam himpunan nilai 0, 1, 2, ..., n-1 untuk menjamin hasil perhitungan tidak berada
di luar himpunan).
Pada langkah kelima pembangkitan kunci atau key generation, kekongruenan ed ≡ 1 (mod m)
sama dengan ed mod m = 1. Sehingga dapat pula dikatakan bahwa ed ≡1 (mod m) ekivalen dengan
ed = 1 + km.
Maka d dapat dihitung dengan cara yang sederhana dengan persamaan d=1km
e
Dengan mencoba nilai k = 1, 2, 3, ..., diperoleh nilai d yang bulat. Nilai itu yang akan dipakai
sebagai kunci pribadi untuk dekripsi pesan.
Dalam implementasi sebenarnya, nilai a dan b diharapkan sangat besar sekali (misalnya 100
digit) agar pekerjaan memfaktorkan n menjadi faktor primanya menjadi sangat sukar, sehingga
lebih susah untuk ditembus.
Contoh penerapan algoritma RSA.
1. Menentukan bilangan acak a dan b
a = 13
b = 5
2. Hitung n dan m
n = 13 * 5 = 65
m = 12 * 4 = 48
3. Cari nilai e
GCD(e, 48) = 1
Misalnya,
e = 2 maka GCD(2, 48) = 2
e = 3 maka GCD(3, 48) = 3
e = 4 maka GCD(4, 48) = 4
e = 5 maka GCD(5, 48) = 1 , jadi digunakan e = 5
4. Lalu cari nilai d
d=1km
e
Misalnya
k = 1 maka d = 9,8
k = 2 maka d = 19,4
k = 3 maka d = 29 , jadi digunakan d = 29
7
Kita coba mengenkripsi pesan menggunakan angka-angka yang telah didapatkan. Misalkan
pesan yang dikirim adalah angka 48.
E = 48 ^ 5 mod 65
= 254803968 mod 65
= 3
Setelah dilakukan enkripsi, didapat nilai sekarang adalah 3. Kemudian akan kita coba lakukan
dekripsi pada nilai tersebut.
D = 3 ^ 29 mod 65
= 68630377364883 mod 65
= 48
Perhatikan bahwa nilai yang didapat sama dengan nilai awal, yaitu 48.
Kekuatan algoritma RSA terletak pada tingkat kesulitan dalam memfaktorkan bilangan
menjadi faktor primanya, dalam hal ini memfaktorkan n menjadi a dan b. Karena sekali n berhasil
difaktorkan, maka menghitung nilai m adalah perkara mudah. Selanjutnya, walau nilai e
diumumkan, perhitungan kunci d tidaklah mudah pula karena nilai m yang tidak diketahui.
Program Artic
Program yang dibuat kelompok adalah program untuk melakukan transfer file antar komputer
yang terhubung dengan jaringan TCP/IP. File dapat di tranfer baik melalui LAN ataupun internet.
Program yang dibuat berjalan di atas platform Linux, dan menggunakan bahasa C++ dengan
kompiler gcc versi 4.2.4.
Algoritma program adalah sebagai berikut:
1. Membaca setiap option yang dimasukkan oleh user.
2. Jika program dijalankan sebagai pengirim, maka baca IP penerima serta lokasi file dan lanjutkan ke langkah ke-3, jika tidak lanjutkan ke langkah ke-9.
3. Jika file yang ingin dikirimkan ada, maka lanjutkan ke langkah 4, jika tidak, tampilkan pesan error dan keluar.
4. Jika koneksi ke alamat yang dituju dapat dibuat, maka lanjutkan ke langkah 5, jika tidak tampilkan pesan error dan keluar.
5. Terima kunci publik dari penerima.
6. Lakukan enkripsi terhadap file yang diinginkan dengan menggunakan kunci yang
telah diterima. Enkripsi dilakukan dengan cara :
a) Baca setiap karakter yang ada di file. Untuk setiap karakter, ubah menjadi nilai ASCII-nya.
b) Dari nilai-nilai ASCII-nya, masukkan ke rumus enkripsi.
c) Tulis hasil enkripsi dalam heksadesimal, dan simpan di file cryptSend.txt.
7. Kirim file yang telah dienkripsi kepada penerima.
8. Lanjut ke langkah ke-16.
9. Jika ada koneksi dari pengirim, maka lanjutkan ke langkah ke-10, jika tidak kembali
ke langkah ke-9.
10. Bangkitkan bilangan kunci e, d, dan n dengan langkah-langkah sbb:
a) Bangkitkan bilangan-bilangan prima.
b) Pilih dua nilai dari bilangan-bilangan prima tersebut sebagai p dan q.
c) Hitung m dan n.
d) Cari nilai e yang memiliki GCD terhadap m = 1
e) Hitung nilai d dengan metode yang sudah diterangkan sebelumnya.
11. Kirim kunci e dan n kepada pengirim.
12. Terima pesan yang sudah terenkripsi dari pengirim.
13. Lakukan dekripsi terhadap pesan tersebut menggunakan kunci d dengan langkah-langkah sbb :
a) Baca setiap bilangan heksadesimal yang telah diterima.
b) Ubah setiap bilangan heksadesimal menjadi bilangan desimal.
c) Dekripsi bilangan tersebut dengan menggunakan rumus dekripsi.
d) Ubah nilai hasil dekripsi itu menjadi karakter.
e) Tulis karakter tersebut ke dalam file.
14. Jika penerima ingin menyimpan file hasil enkripsi, maka jangan hapus file enkripsi.
Jika tidak, maka hapus file enkripsi.
15. Simpan pesan yang sudah di dekripsi tersebut.
16. Selesai.
Option yang ada di program ini :
-h --help Display this usage information.
-r --receive Receive sent file.
-d --no-delete Do not delete encrypted file.
-V --verbose Verbose operation.
-v --version Output version information and exit.
Contoh proses perhitungan jika yang ingin kita proses adalah file yang berisi string “AKU”.
Maka pertama-tama penerima akan membangkitkan bilangan acak sehingga didapatkan nilai e, d,
dan n. Misalkan nilai e = 79, d = 1019, dan n = 3337.
String “AKU” akan diproses per karakter. Jadi yang diproses pertama kali adalah huruf “A”,
kemudian huruf “K”, dan huruf “U”.
Enkripsi akan menggunakan nomor ASCII dari karakter tersebut. Jadi ASCII “A” adalah 65,
maka enkripsinya adalah
E=6579 mod 3337=541
Lakukan pula langkah di atas untuk karakter “K”, dan “U”. Sementara itu, dengan
menggunakan hasil enkripsi pada contoh karakter “A” di atas dapat kita lakukan proses dekripsi.
D=5411019 mod3337=65
Program artic ini tidak memiliki Graphical User Interface (GUI). Pengoperasian program ini
melalui konsol (terminal) di Linux.
Program dijalankan dari terminal dengan menggunakan argumen-argumen sebagai berikut :
1. Sebagai pengirim : option (jika ada), alamat IP tujuan, dan file yang ingin dikirimkan.
2. Sebagai penerima : option -r dan option lainnya jika ada.
Keterbatasan Program :
1. Hanya dapat memproses file teks yang berisikan karakter ASCII (tidak men-support
unicode).
2. Tampilan tanpa GUI menyusahkan bagi pengguna yang awam terhadap penggunaan
aplikasi melalui konsol atau terminal.
3. Tidak cross platform. Hanya dapat dijalankan di sistem operasi Linux.
4. Bilangan prima acak yang dibangkitkan masih terlalu kecil sehingga keamanannya
tidak terlalu kuat.
5. Untuk melakukan pengiriman, program harus dijalankan dari sisi pengirim dan
penerima.
6. Hanya dapat mengirimkan 1 file setiap kali pengiriman.
Keunggulan Program :
1. Karena menggunakan perhitungan komputer, maka proses enkripsi dapat dipercepat.
2. Dapat mengirimkan file dengan berbagai tipe seperti file text (txt), file Portable
Document Format (PDF), file OpenOffice Writer (odt), file OpenOffice Presentation
(odp).
Referensi :
Stallings, William. 2005. Cryptography and Network Security 4 th Edition . Prentice Hall
Cormen, Thomas and Leiserson, Rivest, Stein. 2001. Introduction to Algorithms 2 nd Edition . MIT
Press
Munir, Rinaldi. 2005. Matematika Diskrit Edisi Ketiga. Bandung : Penerbit Informatika
Cryptography RSA. http://en.wikipedia.org/RSA
Hendryli Janson, Ratna Ani, Tryanto, Surya William.
www.jansonhendryli.net/download/rsa.pdf