[Programming] Cryptography: RSA Algorithm

Subject: [Programming] Cryptography: RSA Algorithm Fri Oct 22, 2010 1:30 pm

RSA (Rivest-Shamir-Adleman)
Algoritma RSA diperkenalkan oleh tiga peneliti dari MIT (Massachussets Institute of Technology), yaitu Ron Rivest, Adi Shamir, dan Len Adleman, 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 (sehingga disebut kunci publik), namun kunci untuk dekripsi dirahasiakan. Kunci dekripsi dibuat dari beberapa bilangan prima bersama-sama dengan kunci enkripsi. Untuk menemukan kunci dekripsi, harus difaktorkan suatu bilangan komposit menjadi faktor primanya. Kenyataannya, memfaktorkan bilangan nonprima menjadi faktor primanya bukanlah hal yang mudah. Belum ada algoritma yang efisien yang ditemukan dalam pemfaktoran itu. Semakin besar bilangan nonprimanya tentu semakin sulit pula pemfaktorannya. Semakin sulit pemfaktorannya, semakin kuat pula algoritma RSA. Secara ringkas, algoritma RSA adalah sebagai berikut.

Algoritma RSA:

Kekuatan dan Keamanan RSA
Seperti yang telah dijelaskan sebelumnya, kekuatan algoritma RSA terletak pada tingkat kesulitan dalam memfaktorkan bilangan nonprima menjadi faktor primanya, yang dalam hal ini n = ab. Sekali n berhasil difaktorkan, maka m = (a - 1)(b - 1). Selanjutnya, karena kunci enkripsi e tidak dirahasiakan, maka kunci dekripsi d dapat dihitung pula. Ini berarti proses dekripsi dapat dilakukan oleh orang yang tidak berhak.

Penemu algoritma RSA menyarankan nilai a dan b yang panjangnya lebih dari 100 digit. Dengan demikian hasil kalinya akan berukuran lebih dari 200 digit. Menurut Rivest dkk. usaha untuk memfaktorkan bilangan tersebut membutuhkan waktu komputasi selama 4000 tahun!

(dengan asumsi clock speed komputer yang digunakan 1 GHz).

Untungnya algoritma paling efisien untuk memfaktorkan bilangan yang besar tersebut belum ditemukan. Inilah yang membuat algoritma RSA tetapi dipakai sebagai alat yang ampuh!

Saran untuk memanfaatkan dan memperkuat algoritma RSA Anda dalam pemrosesan file
Dalam pemrosesan file, yang diproses adalah tiap-tiap byte. Dalam file teks, byte merepresentasikan suatu karakter. Dibandingkan dengan algoritma kriptografi lainya, pemrosesan file dengan algoritma RSA membutukan waktu yang lebih lama. Dengan demikian, blok plaintext dan chipertext yang digunakan, disarankan adalah nilai-nilai tiap byte (antara 0 sampai 255). Akan tetapi jika niali byte langsung digunakan sebagai blok, mungkin masih ada kemungkinan bocor, karena chiperteks untuk byte yang sama adalah sama. Oleh karena itu, sebaiknya ditambahkan algoritma untuk membaca dua atau lebih byte sekaligus yang kemudiannya memanipulasi byte tersebut sedemikian dengan cara/trik yang tidak lazim, dengan syarat manipulasi tersebut harus bersifat reversibel karena akan digunakan algoritma enkripsi dan dekripsi yang saling invers. Dengan demikian dijamin 99,99% tidak mungkin ada yang berhasil memecahkannya.

Sumber
- Rinaldi, Munir. 2008. Struktur Diskrit. Bandung: Penerbit ITB
- http://en.wikipedia.org/wiki/RSA

NB: Lihat contoh pemanfaatan algoritma RSA pada Game Maker di: http://www.rpgmakerid.com/game-maker-scripts-f14/gm8-gml-rsa-algorithm-t2513.htm :kabur:

» [Programming] Dijkstra's Algorithm
» [GML] RSA Algorithm