Enkripsi dan Dekripsi Menggunakan RSA Cipher

RSA Cipher atau kriptografi kunci publik merupakan salah satu kriptografi asimetris, dimana kunci untuk melakukan enkripsi dan dekripsi berbeda. Nama RSA diambil dari inisial orang yang menciptakannya yaitu Ron Rivest, Adi Shamir, dan Leonard Adleman, dan dipublikasikan pada jurnal ilmiah Communication of ACM tahun 1977. Kekuatan utama dari RSA adalah kesulitan dalam memfaktorkan bilangan yang besar (NP Hard Problem), sehingga dapat dimanfaatkan untuk mengamankan data.
(Untuk dapat lebih memahami materi kriptografi RSA, penulis menyarankan terlebih dahulu untuk membaca tentang teori bilangan bulat, penulis melampirkan link ke salah satu sumber yang cukup bagus, silahkan klik disini atau dari Referensi dibagian paling bawah.)

Langkah-langkah dalam mengenkripsi atau mengdekripsi RSA adalah sebagai berikut :

1. Pilih 2 buah bilangan prima p dan q.
2. Hitung nilai n = p * q , (usahakan agar setidaknya n > 255 agar dapat mewakili seluruh karakter ASCII).
3. Hitung nilai m = (p-1) * (q-1).
4. Cari nilai e , dimana e merupakan relatif prima dari m.
5. Cari nilai d , yang memenuhi persamaan ed ≡ 1 mod m atau d = e^-1 mod m.
6. Kunci public (e , n) dan kunci private (d , n).
7. Fungsi enkripsi → E (t_a)=t_a^e mod n ; dimana t_a merupakan karakter ke-a dari message (pesan) yang akan dienkripsi.
8. Fungsi dekripsi → D (c_a)=c_a^d mod n ; dimana c_a merupakan karakter ke-a dari ciphertext yang akan didekripsikan.

Contoh kasus, misalnya terdapat dua orang, Andi yang ingin mengirimkan pesan kepada Budi, maka komputer Andi akan memberitahukan kepada komputer Budi untuk membuat kunci publik dan kunci private (kunci dibuat oleh orang yang akan menerima pesan, sehingga kunci private tidak akan pernah meninggalkan komputer penerima, sedangkan kunci publik akan dikirimkan kepada komputer pengirim pesan, dimana kunci publik hanya bisa digunakan untuk meng- enkripsi pesan).

Komputer Budi akan melakukan langkah-langkah berikut :

1. Men- generate bilangan prima p = 59 dan q = 67.
2. Menghitung nilai n = 59 * 67 = 3953.
3. Menghitung nilai m = (59-1) * (67-1) = 3828.
4. Mencari nilai e yang relatif prima terhadap m.
Klik untuk melihat perhitungan nilai e:
Nilai e merupakan sembarang bilangan dimana FPB(e,m) = 1, komputer dapat men- generate bilangan acak kemudian menggunakan algoritma euclidean untuk membuktikannya, atau (menurut penulis) agar lebih cepat, komputer Budi dapat memilih sembarang bilangan Prima e dimana e > 2 dan m mod e ≠ 0.

Contoh :

e=277

Buktikan FPB(3828,277)=1 dengan algoritma euclidean dengan mengubah nilai m dan e menjadi persamaan m=e.q+r dan lakukan secara rekursif dengan merubah nilai e menjadi m dan nilai r menjadi e hingga r=0.

• 3828=277.13+227
• 277=227.1+50
• 227=50.4+27
• 50=27.1+23
• 27=23.1+4
• 23=4.5+3
• 4=3.1+1 ← nilai r kedua terakhir
• 3=1.3+0 ← stop jika r=0
Jika nilai r=0 maka nilai FPB-nya adalah nilai r kedua terakhir yaitu 1, jadi FPB(3828,277)=1 atau relatif prima.
5. Pada langkah berikutnya, akan dicari nilai d dimana ed ≡ 1 (mod m) atau d=e^-1 mod m
Klik untuk melihat perhitungan d :
Untuk mencari nilai d, dapat menggunakan extended euclidean algorithm yang dijabarkan dibawah :

Diketahui :
m = 3828 , e = 277 Ubah menjadi persamaan euclidean m=e.q+r


• 3828 = 277.13+227

Lakukan secara rekursif dengan cara merubah nilai e menjadi m dan nilai r menjadi e secara rekursif hingga nilai r=1.


• 277=227.1+50
• 227=50.4+27
• 50=27.1+23
• 27=23.1+4
• 23=4.5+3
• 4=3.1+1


Ubah persamaan pada langkah sebelumnya sehingga membentuk r=m-e.q


• 227=3828-277.13 ... (a)
• 50=277-227.1 ...(b)
• 27=227-50.4 ...(c)
• 23=50-27.1 ...(d)
• 4=27-23.1 ...(e)
• 3=23-4.5 ...(f)
• 1=4-3.1 ...(g)


Substitusikan persamaan dari g hingga a, hingga membentuk persamaan 1=m.q+e.d


1. Substitusikan persamaan f ke g
• 1=4-((23-4.5).1)
• 1=4-(23-4.5)
• 1=4+23.-1+4.5
• 1=4.6+23.-1 ...(h)
2. Substitusikan persamaan e ke h
• 1=((27-23.1).6)+23.-1
• 1=(27.6+23.-6)+23.-1
• 1=27.6+23.-6+23.-1
• 1=27.6+23.-7 ...(i)
3. Substitusikan persamaan d ke i
• 1=27.6+((50-27.1).-7)
• 1=27.6+(50.-7+27.7)
• 1=27.6+50.-7+27.7
• 1=27.13+50.-7 ...(j)
4. Substitusikan persamaan c ke j
• 1=((227-50.4).13)+50.-7
• 1=(227.13+50.-52)+50.-7
• 1=227.13+50.-52+50.-7
• 1=227.13+50.-59 ...(k)
5. Substitusikan persamaan b ke k
• 1=227.13+((277-227.1).-59)
• 1=227.13+(277.-59+227.59)
• 1=227.13+277.-59+227.59
• 1=227.72+277.-59 ...(l)
6. Substitusikan persamaan a ke l
• 1=((3828-277.13).72)+277.-59
• 1=(3828.72+277.-936)+277.-59
• 1=3828.72+277.-936+277.-59
• 1=3828.72+277.-995 ...(m)
Jadi dari hasil persamaan m, 1=3828.72+277.-995 jika disesuaikan dengan bentuk persamaan 1=m.q+e.d maka nilai d=-995 , Namun kita membutuhkan nilai positif dari nilai d agar dapat melakukan modulo eksponen pada langkah berikutnya dengan cara d=3828-995=2833.


Pembuktian dapat dilakukan dengan cara :

• e.d≡1(mod m)
• 277.2833≡1(mod 3828)
• 3828 | (784741) - 1
• 3828 | 784740
3828 habis membagi 784740 maka terbukti bahwa d = 2833 merupakan invers modulo dari 277(mod 3828).
6. Langkah selanjutnya adalah menentukan kunci publik dan kunci private sebagai berikut :
• Kunci publik = 277, 3953
• Kunci private = 2833, 3953
Kunci private tetap berada dikomputer Budi, namun kunci publik dikirimkan ke komputer Andi, dimana komputer Andi akan menggunakan kunci publik untuk meng-enkripsi pesan yang akan dikirimkan ke komputer Budi.
7. Langkah selanjutnya komputer Andi akan mengenkripsi pesan yaitu : "GO" maka komputer Andi perlu mengetahui kode ASCII karakter "G" dan "O" yaitu : 71 dan 79 , kemudian melakukan enkripsi dengan fungsi enkripsi → E(t_a)=t_a^e mod n :
• E(71)=71²⁷⁷ mod 3953 = 1798
• E(79)=79²⁷⁷ mod 3953 = 2444
Jadi komputer Andi akan mengirimkan pesan dengan angka c₁=1798 dan c₂=2444 kepada komputer Budi.
Dalam perhitungan diatas, untuk mencari sisa bagi pangkat yang besar dapat menggunakan algoritma modular exponent 


8. Langkah terakhir komputer Budi akan mendekripsi ciphertext c₁=1798 dan c₂=2444 dengan fungsi dekripsi → D(c_a)=c_a^d mod n


• D(1798)=1798²⁸³³ mod 3953 = 71 → "G"
• D(2444)=2444²⁸³³ mod 3953 = 79 → "O"
Dapat terlihat bahwa ciphertext yang dikirimkan oleh Andi dikembalikan menjadi pesan "GO"

Referensi

1. Rosen, K. H. 1986. Elementary Number Theory and Its Applications. Addison-Wesley Publishing Company: USA
2. Schneier, B. 1995. Applied cryptography (2nd ed.): protocols, algorithms, and source code in C. John Wiley & Sons, Inc:New York, NY, USA
3. http://stackoverflow.com/questions/4422633/rsa-private-key-calculation-with-extended-euclidean-algorithm
4. http://www.webkeren.net/2015/03/cara-membuat-spoiler-di-blog-blogger-blogspot.html
5. https://en.wikipedia.org/wiki/RSA_(cryptosystem)
6. http://kur2003.if.itb.ac.id/file/Teori%20Bilangan%20Bulat.doc