Algoritma RSA

Algoritma Rivest-Shamir-Adleman (RSA) merupakan salah satu teknik enkripsi dan dekripsi dengan menggunakan dua buah kunci. Kunci-kunci tersebut diperoleh dari hasil perhitungan eksponensial, perkalian, pembagian, penjumlahan dan pengurangan. Perhitungan dilakukan terhadap dua buah bilangan prima. Walaupun RSA cenderung aman bukan berarti tidak bisa dilakukan “attack” terhadap enkripsinya. Didukung perkembangan hardware komputer yang semakin cepat maka semakin terbuka kemungkinan memecahkan enkripsi RSA. Pada tahun 1977 Rivest, Shamir dan Adleman mempublikasikan tantangan memecahkan enkripsi RSA yang memakai 129 digit bilangan bulat. Tantangan ini diharapkan bisa bertahan dari “attack” untuk waktu yang lama. Tetapi pada tahun 1994 tantangan ini dipecahkan dengan menggunakan komputer yang kekuatan komputasinya berimbang dengan komputer untuk membuat film animasi “Toy Story” (kumpulan, 87 unit komputer dual prosesor, 30 unit komputer empat procesor, 100Mhz SPARCstation). 

Dibawah ini diterangkan beberapa kemungkinan melakukan “attack” terhadap RSA:

1. Cara untuk memecahkan enkripsi RSA oleh penyerang adalah mencari kunci pribadi berdasarkan kunci publik. Jalan menuju itu adalah melakukan pemfaktoran bilangan n dari kunci publik. Kemudian dari n bisa didapatkan p dan q, bersama dengan e maka bisa didapatkan d. Masalahnya adalah memfaktorkan bilangan n.  Apabila bilangan yang dipakai cukup besar maka akan memperkecil penyerangan dengan cara ini.
2. Cara lain adalah mencari cara untuk menghitung akar pangkat e mod n, dari persamaan c=m^e, c akar pangkat e, maka akan didapatkan m. Tetapi faktor dari n tidak bisa diketahui. Sampai sekarang belum ada metode yang diketahui untuk penyerangan yang dilakukan dengan cara ini.
3. Cara pemecahan enkripsi RSA lainnya adalah dengan menebak sebagian dari kata atau Single Message Attack, kemudian kata tersebut dienkripsi dengan menggunakan kunci publik dan membandingkan hasilnya dengan data asli yang terenkripsi. Cara ini memang bisa dilakukan, tetapi masih bisa ditangkal dengan menyusupi bit-bit random dalam pesan.
4. Cara “attack“ yang paling baik yang dikenal adalah GNFS (General Number Field Sieve), caranya adalah memfaktorkan n ke bilangan prima p dan q, sama seperti ide no.1. Tetapi waktu yang dibutuhkan untuk RSA dengan besar kunci 1024 bit, sekitar 3x10^11 MIPS-year(MIPS-year, komputasi 1 juta instruksi perdetik selama setahun), atau dengan komputer 300 MIPS membutuhkan 2^30 tahun komputer. Kecepatan masih bisa ditingkatkan dengan hardware yang lebih baik.
5. Jadi banyak cara yang bisa dilakukan untuk memecahkan enkripsi RSA, walaupun ada cara yang belum dapat dilakukan saat ini. Semakin meningkatnya daya komputasi komputer dari waktu-kewaktu harus diakui semakin memperbesar kemungkinan memecahkan enkripsi RSA. Tetapi RSA masih bisa tetap digunakan karena digit bilangan bulat yang dipakai masih dapat diperbesar dan disesuaikan dengan teknologi yang ada sekarang. Semakin besar nilai kunci yang digunakan RSA, maka semakin aman juga teks yang terenkripsi tersebut.

Dengan demikian kekuatan dari algoritma RSA tergantung pada kesulitan pemfaktoran p dan q dari n (Menezes, 1996). Saat ini, tidak ada algoritma yang diketahui dapat memfaktorkan perkalian dari dua bilangan prima untuk nilai yang sangat besar (ratusan digit desimal) dengan cepat. Rekor tercepat dalam memfaktorkan perkalian dua bilangan prima dicatat pada tanggal 22 Agustus 1999 oleh sebuah tim yang dipimpin oleh Herman te Riele di Amsterdam. Bilangan yang berhasil difaktorkan adalah bilangan 512-bit (155-digit decimal) yang merupakan perkalian dua bilangan prima 78-digit desimal. Total waktu yang diperlukan adalah 7,4 bulan dengan menggunakan algoritma General Number Field Sieve.

Menanggapi hal ini RSA Laboratories pada FAQ versi 4.1 menyarankan kunci RSA yang digunakan adalah minimal 1024-bit yang dengan menggunakan teknologi sekarang masih diperlukan waktu bertahun – tahun untuk memfaktorkannya.

Secara garis besar, algoritma kunci publik RSA dapat dijabarkan sebagai berikut

Algoritma RSA - Key Generation

 Algoritma RSA - Public Key Encryption and Decryption

Contoh Penerapan Algoritma RSA

Misalkan :

Dalam contoh ini dipilih bilangan yang kecil agar memudahkan perhitungan, namun dalam aplikasi nyata dapat  dipilih bilangan prima besar untuk meningkatkan keamanan.

p = 3

q = 11

n = 3 * 11 = 33

m = (3-1) * (11-1) = 20

e = 2 => gcd(e, 20) = 2

e = 3 => gcd(e, 20) = 1 (yes)

n = 0 => d = 1 / 3

n = 1 => d = 21 / 3 = 7 (yes)

Publik key  : (3, 33)

Private key : (7, 33)

Let's check the math using numbers

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

* Try encryption : message "2"

  C = 2 ^ 7 (mod 33)

    = 29

  Try to decrypt : ciphertext "29"

  M = 29 ^ 3 (mod 33)

    = 24389 (mod 33)

    = 2

** Encrypt : message " " (ASCII=20)

  C = 20 ^ 7 (mod 33)

    = 8000 (mod 33)

    = 26

  Decrypt : ciphertext 26 

  M = 26 ^ 3 (mod 33)

    = 17576 (mod 33)

    = 20