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.
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.
Kriptografi Kunci Publik
Konsep fundamental dari kriptografi kunci publik atau asymmetric cryptography ditemukan oleh Whitfield Diffie dan Martin Hellman, dan secara terpisah oleh Ralph Merkle.
Konsep dasar public-key cryptography terletak pada pemahaman bahwa kunci/key 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.
Penggunaan algoritma ini harus memenuhi kriteria berikut.
- Memungkinkan untuk mencari nilai $e$, $d$, $n$ sedemikian rupa sehingga $M^e$ atau $M^d \bmod n = M, \forall M < n$.
- Relatif mudah untuk menghitung nilai $M^e \bmod n$ dan $C^d \bmod n \forall M < n$.
- Tidak memungkinkan mencari nilai $d$ jika diberikan nilai $n$ dan $e$.
Syarat nilai $e$ dan $d$ ini adalah $gcd(d,e) = 1$ (relatif prima).
Variabel
RSA membutuhkan beberapa variabel:
- $p$ dan $q$, 2 bilangan prima yang dirahasiakan,
- $n$, dari hasil $p \cdot q$,
- kunci publik $e$, dengan ketentuan $gcd (\phi(n), e) = 1$,
- kunci privat $d = e^{-1} (\bmod \phi(n))$.
Skenario
Bagian ini menjelaskan skenario bagaimana kriptografi kunci publik bekerja. Kita akan menggunakan partisipan klasik Alice dan Bob sebagai dua pihak yang melakukan pertukaran informasi.
- Alice dan Bob setuju untuk menggunakan public-key cryptosystem.
- Bob mengirimkan public key-nya kepada Alice.
- Alice meng-encrypt pesan yang dibuatkan dengan menggunakan public key milik Bob dan mengirimkan pesan yang sudah di-encrypt kepada Bob.
- Bob men-decrypt pesan dari Alice menggunakan private key miliknya.
Fungsi Enkripsi dan Dekripsi
Fungsi enkripsi yaitu :
$$c = m^e \bmod n$
Fungsi dekripsi yaitu:
$$m = c^d \bmod n$
dimana:
- $c$ = Cipherteks
- $m$ = Message/plainteks
- $e$ = kunci publik
- $d$ = kunci privat
- $n$ = modulo pembagi (akan dijelaskan lebih lanjut)
Pembangkitan Kunci
Misalkan Alice ingin Bob mengirimnya sebuah pesan melalui jalur yang aman. Alice akan memberikan public keynya kepada Bob dan menyimpan private key untuk dirinya.
Pilih 2 bilangan prima, misalnya $p = 17$ dan $q = 11$.
Hitung $n = p \cdot q = 17 \times 11 = 187$.
Hitung $ \phi(n) = (p - 1)(q - 1) = 16 \times 10 = 160$.
Pilih nilai $e$ sedemikian sehingga relatif prima terhadap $\phi(n) = 160$, $e < \phi(n)$; misalnya $e = 7$.
Hitung $d$ sedemikian sehingga $d \cdot e \equiv 1 (\bmod 160)$ dan $d < 160$. Nilai yang didapatkan $d = 23$,karena $23 \times 7 = 161 = (1 \times 160) + 1$; $d$ dapat dihitung dengan Extended Euclidean Algorithm.
Nah, nilai e dan d inilah yang kita sebut sebagai public key (e) dan private key (d). Pasangan Kunci publiknya = ${7,187}$ dan kunci privatnya = ${23, 187}$
Enkripsi Pesan
Misalkan Bob ingin mengirim sebuah pesan $88$ kepada Alice.
Alice harus membuat keynya; sehingga ia memiliki private dan public keys.
private key = (M,d)
public key = (M,e)
Untuk proses enkripsi, kita akan menghitung
$$c = 88^7 \bmod 187 = 408 \cdots \bmod 187 = 11$
Nah, kita mendapatkan nilai $c = 11$.
Untuk melakukannya, kita dapat menggunakan python:
import math
c = pow(88, 7) % 187
Bob mengirimkan bilangan tersebut kepada Alice sehingga Alice dapat melakukan dekripsi menggunakan private keynya.
Dekripsi Pesan
Misalkan Alice menerima sebuah pesan terencrypt yaitu $11$, ia akan men-decrypt-nya.
$$m = 11^{23} \bmod 187 = 895… \bmod 187 = 88$
Alice menerima pesan yang telah didekripsi yaitu $88$.
Untuk melakukannya, kita dapat menggunakan python:
import math
c = pow(11, 23) % 187
Penutup
RSA merupakan contoh yang powerful dan cukup aman dari public key cryptography. Berdasarkan matematika, proses yang digunakan berdasarkan fungsi-fungsi trap-door satu arah. Sehingga melakukan enkripsi dengan menggunakan public key sangat mudah bagi semua orang, namun proses dekripsi menjadi sangat sulit.
Proses decryption sengaja dibuat sulit agar seseorang, walaupun menggunakan Cray supercomputers dan ribuan tahun, tidak dapat mendecrypt pesan tanpa mempunyai private key.
Perlu diingat juga bahwa pemilihan $p \cdot q = M$ haruslah sebuah bilangan yang sangat besar sehingga sulit dicari eksponen decoding-nya karena sulit melakukan pemfaktoran bilangan prima.
Reference
Childs, Lindsay N. A Concrete Introduction to Higher Algebra. Undergraduate Texts in Mathematics. Springer-Verlaag: New York, 2000.
Schneier, B. Applied Cryptography, 2nd Ed. John Wiley & Sons, Inc: Canada, 1996.
Rivest R.L., Shamir A., Adleman L. “A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. MIT: Massachusetts. 1977.
Lampiran
#include <bits/stdc++.h>
using namespace std;
string plainteks, cipherteks;
long int p, q, n, e, d, totient, temp[100];
int apakahPrime(long int x)
{
long int i, j;
j = sqrt(x);
for(i=2; i<=j; i++){
if(x%i == 0){
return 0;
}
}
return 1;
}
int hitung_d(long int e, long int totient)
{
long int k, h, d;
k = 1;
while(1){
d = k*e;
h = d%totient;
if(h == 1){
cout << "Kunci privat (d) : " << k << endl;
return k;
}else{
k = k + 1;
}
}
}
int gcd(long int a, long int b)
{
long int r, temp;
if(a < b){
temp = a;
a = b;
b = temp;
}
while (b != 0){
r = a % b;
a = b;
b = r;
}
return a;
}
void pembangkitanKunci()
{
int test;
cout << "Kunci p: "; cin >> p;
test = apakahPrime(p);
if(test==0){
cout << "Not prime" << endl;
exit(0);
}
cout << "Kunci q: "; cin >> q;
test = apakahPrime(q);
if(test==0){
cout << "Not prime" << endl;
exit(0);
}
n = p * q;
totient = (p-1) * (q-1);
cout << "Kunci publik (e): ";
cin >> e;
cout << "Hasil" << endl;
cout << "Totient = " << totient << endl;
test = gcd(e, totient);
if(test == 1){
d = hitung_d(e, totient);
}else{
cout << "e tidak relatif prima";
exit(0);
}
}
void enkripsi()
{
int panjang;
long int hasil, m, i, j;
char c;
cout << "Input m: ";
cin.ignore();
getline(cin, plainteks);
panjang = plainteks.length();
cipherteks = "";
for(i=0; i<panjang; i++){
m = plainteks[i];
m = m - 96;
hasil = 1;
for(j=0; j<e; j++){
hasil = hasil * m;
hasil = hasil % n;
}
temp[i] = hasil;
c = hasil + 96;
cipherteks = cipherteks + c;
}
cout << "Cipherteks: " << cipherteks << endl;
}
void dekripsi()
{
int panjang;
long int c, hasil, i, j;
char m;
panjang = cipherteks.length();
plainteks = "";
for(i=0; i<panjang; i++){
c = temp[i];
hasil = 1;
for(j=0; j<d; j++){
hasil = hasil * c;
hasil = hasil % n;
}
m = hasil + 96;
plainteks = plainteks + m;
}
cout << "Plainteks: " << plainteks << endl;
}
int main()
{
bool stop;
int pil;
stop = false;
while(!stop){
cout << "1. Pembangkitan kunci" << endl;
cout << "2. Enkripsi" << endl;
cout << "3. Dekripsi" << endl;
cout << "4. Exit" << endl;
cout << "Pilihan: ";
cin >> pil;
switch(pil){
case 1: pembangkitanKunci(); break;
case 2: enkripsi(); break;
case 3: dekripsi(); break;
case 4: stop = true; break;
}
}
}