ALGORITMA RSA
1.
PENJELASAN
SINGKAT
Sandi RSA merupakan
algoritma kriptografi kunci public (asimetris). Ditemukan pertama kali pada
tahun 1977 oleh R. Rivest, A. Shamir, dan L. Adleman. Nama RSA sendiri diambil
dari ketiga penemunya tersebut.
Sebagai algoritma kunci
publik, RSA mempunyai dua kunci, yaitu kunci publik dan kunci rahasia. Kunci
publik boleh diketahui oleh siapa saja, dan digunakan untuk proses enkripsi.
Sedangkan kunci rahasia hanya pihak-pihak tertentu saja yang boleh
mengetahuinya, dan digunakan untuk proses dekripsi. Keamanan sandi RSA terletak
pada sulitnya memfaktorkan bilangan yang besar. Sampai saat ini RSA masih
dipercaya dan digunakan secara luas di internet.
Gambar
1. Skema Algoritma Kunci Publik
Sandi RSA terdiri dari
tiga proses, yaitu proses pembentukan kunci, proses enkripsi dan proses
dekripsi. Sebelumnya diberikan terlebih dahulu beberapa konsep perhitungan
matematis yang digunakan RSA.
2.
PEMBAHASAN
A.
Public-Key Cryptography
Konsep
fundamental dari Public-Key Cryptography ditemukan oleh Whitfield Diffie dan
Martin Hellman, dan secara terpisah oleh Ralph Merkle.
Sedangkan
konsep dasar Public-Key Cryptography terletak pada pemahaman bahwa keys selalu berpasangan:
encryption key dan decryption key. Juga perlu diingat bahwa sebuah key tidak
dapat digenerate dari key lainnya. Pemahaman encryption dan decryption key
sering disebut sebagai public dan private key. Seseorang harus memberikan public
key-nya agar pihak lain dapat meng-encrypt sebuah pesan. Decryption hanya
terjadi jika seseorang mempunyai private key.
B.
Scenario
Bagian ini menjelaskan skenario bagaimana
public-key cryptosystem bekerja. Saya
akan menggunakan partisipan klasik Alice dan Bob sebagai orang-orangyang
melakukan pertukaran informasi.
a)
Alice dan Bob setuju untuk
menggunakan public-key cryptosystem.
b)
Bob mengirimkan public key-nya
kepada Alice.
c)
Alice meng-encrypt pesan yang
dibuatkan dengan menggunakan public key milik Bob dan mengirimkan pesan yang
sudah di-encrypt kepada Bob.
d)
Bob men-decrypt pesan dari Alice
menggunakan private keymiliknya.
C.
Mathematical Notation
Untuk memahami algoritma RSA, seseorang
harus memahami beberapa notasi matematika
dasar, teori dan formula. Hal tersebut dibutuhkan untuk mendukung semua kalkulasi yang dilakukan
dalam algoritma RSA.
a)
Modulo (didenotasikan dengan 'x mod
m' atau 'x % m' dalam beberapa bahasa komputer)
x % m = x mod m = pembagian x
dengan m dan mengambil sisanya.
Contoh: 25 mod 5 = 0 karena 5 habis membagi 25
25 mod 4 = 1 karena 25 / ( 4 * 6
) menyisakan 1
x mod m = x jika dan hanya jika x < m
b)
GCD(A,B)
GCD
= Greatest Common Divisor.
GCD(A,B) = D
GCD(78,32)
= 2, karena tidak ada bilangan yang lebih besar dari dua yang membagi 78 dan32.
GCD(A,B)
dapat ditemukan dengan menggunakan algoritma extended euclid.
Jika
GCD(A,B) = 1 maka A and B dalah coprime satu sama lainnya (dengankata lain, A
dan B adalah relatively prime).
D.
Key Generation
Misalkan
Alice ingin Bob mengirimnya sebuah pesan melalui jalur yang aman. Alice akan memberikan public keynya
kepada Bob dan menyimpan private key untuk
dirinya.
a)
Pilih 2 bilangan prima besar
seperti p,q dimana p tidak samadengan q.
b)
Hitung M = p x q
c)
Hitung phi(M) = phi(p) * phi(q)
d)
Pilih sebuah integer 'e' dimana 1
< e < phi(M) dan 'e' sertaphi(M) adalah coprime.
e)
Hitung 'd' integer sehingga (d * e)
mod M = 1
f)
(M,e) adalah public key dimana M
adalah modulo dan e adalaheksponen encryption.
g)
(M,d) adalah private key dimana M
adalah modulo dan d adalah
eksponen decryption.
E.
Encrypting Message
Misalkan
Bob ingin mengirim sebuah pesan 'H' kepada Alice.
a)
Alice harus membuat keynya;
sehingga ia memiliki private dan public keys.
private
key = (M,d)
public
key = (M,e)
b)
Mengubah 'H' menjadi sebuah
bilangan yang menggunakan alphabet yang valid dengan tabel bilangan. Sebuah
contoh mudah adalah mapping A = 1, B = 2 ... Z = 26 sehingga H = 8
c)
C = 8^e (mod M)
C
adalah sebuah bilangan ter-encrypt.
d)
Bob mengirimkan bilangan tersebut
kepada Alice sehingga Alice dapat melakukan decode ulang menggunakan private
keynya.
F.
Decrypting Message
Misalkan
Alice menerima sebuah pesan ter-encrypt, ia akan men-decrypt-nyamenggunakan
tahapan-tahapan berikut:
a)
Alice mempunyai private key dari
langkah-langkah di atas (M,d)
b)
N = C^d (mod M)
c)
N adalah bilangan. Gunakan konversi
table alphabet untuk mengubahN menjadi karakter yang direpresentasikannya.
Contoh Algoritma RSA
|--------------------------------------------------------------------------------------------------|
Jika
diketahui :
p =
3
q =
7
Penyelesaian
:
n =
p.q
= 3 x 7
= 21
M=
(p-1) (q-1)
=
(3 -1)(7 – 1)
= 12
e *
d mod 12 = 1 (Cari bilangan prima yang jika mod M hasilnya 1)
e =
5
d =
17
public
key = (e,n) = (5,21)
private
key = (d,n) = (17,21)
S
I
S
J
A R
83
73
83
74 65
82
|--------------------------------------------------------------------------------------------------|
Proses
Enkripsi dan Deskripsi
S =
83
|
Enkripsi
|
Deskripsi
|
|
C = M ^ e mod
n
|
M = C ^
d mod n
|
|
8 ^ 5 mod 21
= 8
|
8 ^ 17 mod 21
= 8
|
|
3 ^ 5 mod 21
= 12
|
12 ^ 17 mod
21 = 3
|
I =
73
|
Enkripsi
|
Deskripsi
|
|
C = M ^ e mod
n
|
M = C ^
d mod n
|
|
7 ^ 5 mod 21
= 7
|
7 ^ 17 mod 21
= 7
|
|
3 ^ 5 mod 21
= 12
|
12 ^ 17 mod
21 = 3
|
S =
83
|
Enkripsi
|
Deskripsi
|
|
C = M ^ e mod
n
|
M = C ^
d mod n
|
|
8 ^ 5 mod 21
= 8
|
8 ^ 17 mod 21
= 8
|
|
3 ^ 5 mod 21
= 12
|
12 ^ 17 mod
21 = 3
|
J =
74
|
Enkripsi
|
Deskripsi
|
|
C = M ^ e mod
n
|
M = C ^
d mod n
|
|
7 ^ 5 mod 21
= 7
|
7 ^ 17 mod 21
= 7
|
|
4 ^ 5 mod 21
= 16
|
16 ^ 17 mod
21 = 4
|
A =
64
|
Enkripsi
|
Deskripsi
|
|
C = M ^ e mod
n
|
M = C ^
d mod n
|
|
6 ^ 5 mod 21
= 6
|
6 ^ 17 mod 21
= 6
|
|
4 ^ 5 mod 21
= 16
|
16 ^ 17 mod
21 = 4
|
R =
82
|
Enkripsi
|
Deskripsi
|
|
C = M ^ e mod
n
|
M = C ^
d mod n
|
|
8 ^ 5 mod 21
= 8
|
8 ^ 17 mod 21
= 8
|
|
2 ^ 5 mod 21
= 11
|
11 ^ 17 mod
21 = 2
|
