Senin, 31 Oktober 2011

KRIPTOGRAFI

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