Algoritma RSA

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. 

Bagian ini menjelaskan skenario bagaimana public-key cryptosystem bekerja. Saya akan menggunakan partisipan klasik Alice dan Bob sebagai orang-orang yang melakukan pertukaran informasi.

1. Alice dan Bob setuju untuk menggunakan public-key cryptosystem.

2. Bob mengirimkan public key-nya kepada Alice.

3. Alice meng-encrypt pesan yang dibuatkan dengan menggunakan public key milik Bob dan mengirimkan pesan yang sudah di-encrypt kepada Bob.

4. Bob men-decrypt pesan dari Alice menggunakan private key miliknya.

Dari sekian banyak algoritma kriptografi kunci-publik yang pernah dibuat, algoritma yang paling populer adalah algoritma RSA. RSA adalah sebuah algoritma berdasarkan skema public-key cryptography. Diberi nama RSA sebagai inisial para penemunya: Ron Rivest, Adi Shamir, dan Leonard Adleman. RSA dibuat di MIT pada tahun 1977 dan dipatenkan oleh MIT pada tahun 1983. Setelah bulan September tahun 2000, paten tersebut berakhir, sehingga saat ini semua orang dapat menggunakannya dengan bebas. Lebih jauh, RSA adalah algoritma yang mudah untuk diimplementasikan dan dimengerti. Algoritma RSA adalah sebuah aplikasi dari sekian banyak teori seperti extended euclid algorithm, euler’s function sampai fermat theorem. 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. Masuk ke penggunaannya nih,, 

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.

Misalkan Alice menerima sebuah pesan ter-encrypt, ia akan men-decrypt-nya menggunakan 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 mengubah N menjadi karakter yang direpresentasikannya. Secara singkat, ini nih algoritma pembangkitan kuncinya:

1. Hasilkan dua buah integer prima besar, p dan q Untuk memperoleh tingkat keamanan yang tinggi pilih p dan q yang berukuran besar, misalnya 1024 bit.

2. Hitung m = (p-1)*(q-1)

3. Hitung n = p*q

4. Pilih d yg relatively prime terhadap m

e relatively prime thd m artinya faktor pembagi terbesar keduanya adalah 1, secara matematis disebut gcd(e,m) = 1. Untuk mencarinya

dapat digunakan algoritma Euclid.

5. Cari d, sehingga e*d = 1 mod (m), atau d = (1+nm)/e Untuk bilangan besar, dapat digunakan algoritma extended Euclid.

6. Kunci publik : e, n

Kunci private : d, n