Pembahasan Kriptografi RSA Lengkap

• ·           SEJARAH RSA

       Algortima RSA dijabarkan pada tahun 1977 oleh tiga orang : Ron Rivest, Adi Shamir dan Len Adleman dari Massachusetts Institute of Technology. Huruf RSA itu sendiri berasal dari inisial nama mereka (Rivest—Shamir—Adleman). Clifford Cocks, seorang matematikawan Inggris yang bekerja untuk GCHQ, menjabarkan tentang sistem equivalen pada dokumen internal di tahun 1973. Penemuan Clifford Cocks tidak terungkap hingga tahun 1997 karena alasan top-secret classification.      Algoritma tersebut dipatenkan oleh Massachusetts Institute of Technology pada tahun 1983 di Amerika Serikat sebagai U.S. Patent 4.405.829. Paten tersebut berlaku hingga 21 September 2000. Semenjak Algoritma RSA dipublikasikan sebagai aplikasi paten, regulasi di sebagian besar negara-negara lain tidak memungkinkan penggunaan paten. Hal ini menyebabkan hasil temuan Clifford Cocks di kenal secara umum, paten di Amerika Serikat tidak dapat mematenkannya.

·           PENGERTIAN RSA

RSA di bidang kriptografi adalah sebuah algoritma pada enkripsi public key. RSA merupakan algoritma pertama yang cocok untuk digital signature seperti halnya ekripsi, dan salah satu yang paling maju dalam bidang kriptografi public key. RSA masih digunakan secara luas dalam protokol electronic commerce, dan dipercaya dalam mengamnkan dengan menggunakan kunci yang cukup panjang.

Dari sekian banyak algoritma kriptografi kunci-publik yang pernah dibuat, algoritma yang paling populer adalah algoritma RSA. Algoritma RSA dibuat oleh 3 orang peneliti dari MIT (Massachussets Institute of Technology) pada tahun 1976, yaitu: Ron (R)ivest, Adi (S)hamir, dan Leonard (A)dleman. Keamanan algoritma RSA terletak pada sulitnya memfaktorkan bilangan yang besar menjadi faktor-faktor prima. Pemfaktoran dilakukan untuk memperoleh kunci pribadi. Selama pemfaktoran bilangan besar menjadi faktor-faktor prima belum ditemukan algoritma yang mangkus, maka selama itu pula keamanan algoritma RSA tetap terjamin.

Besaran-besaran yang digunakan pada algoritma RSA:

1.  p dan q bilangan prima                                           (rahasia)

2.  r = p  q                                                                   (tidak rahasia)

3.  (r) = (p – 1)(q – 1)                                      (rahasia)

4.  PK     (kunci enkripsi)                                            (tidak rahasia)

5.  SK     (kunci dekripsi)                                            (rahasia)

6.  X     (plainteks)                                                       (rahasia)

7.  Y    (cipherteks)                                                      (tidak rahasia)

·           TEOREMA FERMAT.

Jika p adalah bilangan  prima  dan m adalah  bilangan  bulat  yang tidak  habis  dibagi  dengan p,  yaitu  FPB (a, p)  =  1, maka

·           FUNGSI EULER

Fungsi Euler  mendefinisikan   untuk r ≥ 1 menyatakan  jumlah  bilangan  bulat  positif  yang lebih kecil dari r dan relatif prima terhadap r. Dengan  memperhatikan  Teorema  Fermat dan  definisi  dari  Fungsi  Euler,  dapat diturunkan sebuah bentuk umum dari Teorema Fermat yaitu jika FPB(a, r) = 1, maka

·           ALGORITMA RSA

Algoritma ini  diturunkan  dari  Fungsi  Euler  dan  Teorema Fermat  serta  memanfaatkan  sifat-sifat  dari aritmatika  modulo.  Berikut  adalah  proses penurunan algoritma dimulai dari persamaan (2).

Berdasarkan  sifat  persamaan (2) dapat ditulis menjadi

Atau

Bila a diganti dengan X, maka persamaan (4) menjadi

X^m(r)  1 (mod r)

Berdasarkan  sifat ac ≡  bc (mod r)  jika a ≡  b (mod r),  maka  perkalian  persamaan  (4)  dengan X akan menghasilkan

Misalkan SK dan PK dipilih sedemikian sehingga

Dengan mensubtitusikan persamaan (6) ke dalam persamaan (5) diperoleh

yang  artinya  perpangkatan  X  dengan SK  diikuti dengan  perpangkatan  dengan  PK  dan  dilakukan operasi  modulo  terhadap r akan  menghasilkan X semula.  Sehingga  enkripsi  dan  dekripsi  dapat dirumuskan sebagai berikut

Karena SK  PK = PK  SK, maka enkripsi diikuti dekripsi ekivalen dengan dekripsi diikuti enkripsi

·           PEMBANGKITAN PASANGAN KUNCI

Secara  umum  pasangan  kunci  algoritma  RSA dapat dibangkitkan dengan cara berikut:

·         Pilih dua buah bilangan prima sembarang, p dan q.

·         Hitung r = p  q. Sebaiknya p  q, sebab jika p = q maka r = p² sehingga p dapat diperoleh dengan menarik akar pangkat dua dari r.

·         Hitung (r) = (p – 1)(q – 1).

·         Pilih kunci publik, PK, yang relatif prima terhadap (r).

·         Bangkitkan kunci rahasia dengan menggunakan persamaan (6), yaitu SK  PK  1 (mod (r)).

Contoh 1.

Misalkan p = 47 dan q = 71 (keduanya prima). Selanjutnya, hitung nilai

r = p  q = 3337

dan

(r)= (p – 1)(q – 1) = 3220.

Pilih kunci publik SK = 79, karena 79 relatif prima dengan 3220. PK dan r dapat dipublikasikan ke umum.

Selanjutnya akan dihitung kunci dekripsi SK seperti yang dituliskan pada langkah instruksi 5 dengan menggunakan persamaan (11),                                                                                  

Dengan mencoba nilai-nilai m = 1, 2, 3, …, diperoleh nilai SK yang bulat adalah 1019. Ini adalah kunci dekripsi yang harus dirahasiakan.

·                PEMBANGKIT BILANGAN PRIMA

Ada berbagai metode yang dapat digunakan untuk menghasilkan sebuah bilangan prima. Untuk menghasilkan bilangan prima yang besar dengan menggunakan ruang memori dan waktu. Secara umum pembangkitan bilangan prima dapat dikelompokkan menjadi dua, yaitu dengan membangkitkan bilangan prima dari bilangan prima terkecil dengan pengujian yang menghasilkan 100% bilangan prima atau dengan membangkitkan bilangan acak dan menguji kemungkinan bilangan tersebut prima.

·         ALTERNATIF SATU

Secara umum alternatif ini akan membangkitkan tabel bilangan prima sehingga untuk mengambil sebuah bilangan prima cukup diambil satu dari beberapa bilangan yang terdapat pada tabel. Pada alternatif ini, dapat digunakan beberapa metode yang memiliki kelebihan dan kekurangan tersendiri.

Pertama, digunakan teknik yang akan membagi sebuah bilangan yang akan diuji dengan semua bilangan bulat positif yang lebih kecil dari akar bilangan tersebut. Cara ini dapat disebut brute force karena mencoba setiap kemungkinan yang ada yang tentunya semakin besar nilai bilangan yang akan diuji maka semakin besar pula waktu yang dibutuhkan untuk menguji dikarenakan semakin banyak bilangan bulat yang akan digunakan sebagai pembagi. Namun cara ini dapat dibilang tidak memakan ruang memori karena hanya membagi dengan bilangan bulat positif yang lebih kecil dari akar bilangan tersebut.

Cara kedua tidak jauh dengan cara pertama namun digunakan pembagi yang jauh lebih sedikit. Cara ini hanya menggunakan bilangan prima yang telah dibuktikan sebelumnya sebagai pembagi untuk bilangan baru yang lebih besar yang akan diuji. Cara ini bergantung pada media penyimpanan bilangan prima yang pernah dihasilkan yang mungkin saja ditempatkan pada memori atau pada file eksternal. Dari sisi kandidat, kandidat yang akan diuji hanya angka 2 dan bilangan ganjil. Cara ini memangkas waktu lebih jauh jika menggunakan memori sebagai tempat penyimpanan.

Cara lain yang dapat dipertimbangkan adalah mengunakan pendekatan Teori Sieve yang membuat sebuah array sepanjang kandidat prima terbesar ditambah satu yang diberi tanda prima. Kemudian untuk setiap prima yang ditemukan, setiap sel array pada index kelipatan dari bilangan tersebut akan ditandai sebagai bukan prima. Pada akhir proses, jika suatu index masih memiliki penanda prima pada sel array yang ditunjuk berarti index tersebut bilangan prima. Cara ini jelas membutuhkan ruang memori untuk mewakili setiap sel array yang dimaksud, namun cara ini akan memangkas tes modulo yang sangat memakan kinerja hardware.

·         ALTERNATIF DUA

Berbeda dengan alternatif sebelumnya, secara umum alternatif ini hanya akan membangkitkan bilangan acak dan menguji sifat primanya dan berhenti apabila bilangan tersebut diyakini prima. Alternatif ini tidak menjamin 100% bilangan tersebut adalah bilangan prima, tetapi menjamin dengan tingkat kesalahan yang relatif kecil sesuai dengan banyaknya proses tes yang dilakukan.

Metode yang cukup sering dipakai dalam pengujian adalah algoritma Lehman yang membagi suatu bilangan yang akan diuji (misal p) dengan bilangan prima kurang dari 256 pengujian dengan cara membangkitkan bilangan acak a yang lebih kecil dari p dan dihitung a(p - 1)/2 mod p yang apabila bernilai 1 atau -1 berarti p berpeluang prima sebesar 50% yang apabila langkah ini diulang dan lolos sebanyak t kali maka akan menghasilkan sebuah bilangan prima p yang mempunyai kesalahan tidak lebih dari 1/2t.

Selain dengan metode Lehmann, masih banyak metode lain yang sejenis seperti algoritma Rabin-Miller.

·           PENTINGNYA SIFAT PRIMA PADA RSA

Bila pembangkitan pasangan kunci algoritma RSA diikuti, bilangan prima menjadi penentu jalan tidaknya algoritma RSA tersebut. Penggantian peubah prima p dan q pada proses ini meskipun pada akhirnya dapat menghasilkan peubah r, PK, dan SK, tetap saja peubah tersebut tidak dapat memenuhi persamaan (10).

Sementara pada proses pembangkitan pasangan kunci algoritma RSA secara umum diawali dengan memilih dua buah bilangan prima. Bila persamaan-persamaan sebelumnya yaitu persamaan (1) hingga (10) diperhatikan kembali, tampak sama sekali tidak terpengaruh oleh dua buah bilangan prima.

Persamaan (5) dan (6) yang menentukan pasangan kunci enkripsi/dekripsi algoritma RSA tidak bergantung pada bilangan prima.

Enkripsi

Plainteks disusun menjadi blok-blok x₁, x₂, …, sedemikian sehingga setiap blok merepresentasikan nilai di dalam rentang 0 sampai r – 1.

Setiap blok x_i dienkripsi menjadi blok y_i dengan rumus

y_i = x_i ^PK mod r           

Dekripsi

Setiap blok cipherteks y_i didekripsi kembali menjadi blok x_i dengan rumus

x_i = y_i ^SK mod r           

Contoh 2.

Misalkan plainteks yang akan dienkripsikan adalah

X = HARI INI

atau dalam sistem desimal (pengkodean ASCII) adalah

7265827332737873

Pecah X menjadi blok yang lebih kecil, misalnya X dipecah menjadi enam blok yang berukuran 3 digit:

            x₁ = 726                       x₄ = 273

            x₂ = 582                       x₅ = 787

            x₃ = 733                       x₆ = 003

Nilai-nilai x_i ini masih terletak di dalam rentang 0 sampai 3337 – 1 (agar transformasi menjadi satu-ke-satu).

Blok-blok plainteks dienkripsikan sebagai berikut:

726⁷⁹ mod 3337 = 215 = y₁

582⁷⁹ mod 3337 = 776 = y₂

733⁷⁹ mod 3337 = 1743 = y₃

273⁷⁹ mod 3337 = 933 = y₄

787⁷⁹ mod 3337 = 1731 = y₅

003⁷⁹ mod 3337 = 158 = y₆

Jadi, cipherteks yang dihasilkan adalah

 Y = 215 776 1743 933 1731 158.

Dekripsi dilakukan dengan menggunakan kunci rahasia

SK = 1019

Blok-blok cipherteks didekripsikan sebagai berikut:

215¹⁰¹⁹ mod 3337 = 726 = x₁

776¹⁰¹⁹ mod 3337 = 582 = x₂

1743¹⁰¹⁹ mod 3337 = 733 = x₃

…

Blok plainteks yang lain dikembalikan dengan cara yang serupa. Akhirnya kita memperoleh kembali plainteks semula

P = 7265827332737873

yang dalam karakter ASCII adalah

P = HARI INI.                                                                    

·           KEKUATAN DAN KEAMANAN RSA

Keamanan algoritma RSA terletak pada tingkat kesulitan dalam memfaktorkan bilangan non prima menjadi faktor primanya, yang dalam hal ini r = p  q. Sekali r berhasil difaktorkan menjadi p dan q, maka  (r) = (p – 1) (q – 1) dapat dihitung. Selanjutnya, karena kunci enkrispi PK diumumkan (tidak rahasia), maka  kunci dekripsi SK dapat dihitung dari persamaan PK  SK  1 (mod (r)). Penemu algoritma RSA menyarankan nilai p dan q panjangnya lebih dari 100 digit. Dengan demikian hasil kali r = p  q akan berukuran lebih dari 200 digit. Menurut Rivest dan kawan-kawan, uasaha untuk mencari faktor bilangan 200 digit membutuhkan waktu komputasi selama 4 milyar tahun! (dengan asumsi bahwa algoritma pemfaktoran yang digunakan adalah algoritma yang tercepat saat ini dan komputer yang dipakai mempunyai kecepatan 1 milidetik). Untunglah algoritma yang paling mangkus untuk memfaktorkan bilangan yang besar belum ditemukan. Inilah yang membuat algoritma RSA tetap dipakai hingga saat ini. Selagi belum ditemukan algoritma yang mangkus untuk memfaktorkan bilangan bulat menjadi faktor primanya, maka algoritma RSA tetap direkomendasikan untuk menyandikan pesan.

·           KESIMPULAN

Melihat bagaimana algoritma RSA diturunkan, dapat disimpulkan pada dasarnya bilangan prima tidak mutlak harus digunakan, namun penggunaan bilangan prima jauh sangat mempermudah pembangkitan kunci untuk algoritma RSA.

Meskipun terkesan sederhana dan tidak menghabiskan ruang memori dan waktu eksekusi, pembangkitan bilangan prima dengan cara yang tidak menjamin kepastian sifat bilangan prima sebaiknya dihindari bila akan digunakan untuk membangkitkan pasangan kunci enkripsi/dekripsi algoritma RSA. Namun, cara ini tetap dapat dipakai dengan cara memastikan terlebih dahulu pasangan kunci yang dihasilkan apakah memenuhi persamaan (10) atau tidak.

Tidak ada salahnya menunggu lama dan menggunakan sumber daya yang besar untuk menghasilkan bilangan prima sebagai pembangkit pasangan kunci algoritma RSA yang kuat, mengingat sebenarnya pasangan kunci ini tidak terlalu diperlukan banyak pada satu personal atau afiliasi.