Algoritma RSA

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