How RSA Works

RSA adalah sebuah penemuan breakthrough dalam dunia kriptografi. Ditemukan oleh tiga orang pakar matematika: Riverst, Shamir, dan Adleman tahun 1977, akan tetapi baru di publikasikan tahun 1997.

RSA digunakan untuk enkripsi asimetryc yaitu menggunakan public key dan private key. RSA banyak digunakan di applikasi online internet saat ini seperti Email (PGP), https, dan lain-lain.

Cara kerja RSA cukup sederhana yaitu menemukan 2 bilangan yang saling invers satu dengan yang lain.

Contoh:

A: 100

Public key: 4

Private key: 0.25

Apabila informasi tentang A akan di kirim, maka di lakukan proses enkripsi (misal dengan perkalian).

A x Public Key = 4 *100 = 400

Jika informasi ini sampai bocor di tengah jalan, maka si penerima tidak akan menyangka bahwa angka A itu sebenarnya adalah 100.

Apabila sampai di penerima yang dituju, maka si penerima akan melakukan proses dekripsi (dengan metode yang sama yaitu perkalian)

A' x Private Key = 400 x 0.25 = 100

Si penerima akan mengetahui bahwa nilai A sebenarnya adalah 100.

Kalau tadi operasi inverse adalah dengan perkalian. Sedangkan RSA operasinya adalah dengan MODULUS.

Cara Kerja RSA secara sederhana:

Public key : (5, 14)

Text: B --> 2 (dimana A=1, B=2, C=3, D=4, E=5, dst)

Ingin di kirim jarak jauh, maka dilakukan operasi enkripsi RSA:

B equivalent 2.

2^5 mod 14 = 4 --> D

Maka text yang dikirim adalah D

Pada sisi penerima, si penerima sudah punya Private Key.

Private Key: (11, 5)

Text: D --> 4

Operasi Dekripsi RSA:

4^11 mod 14 = 2 --> B

Maka si penerima akan tahu bahwa text yang dikirim adalah B.

Pertanyaannya bagaimana cara mendapatkan angka 5, 14, dan 11?

Langkah-langkah membuat Private Key dan Public key adalah sbb:

1. Tentukan 2 bilangan prima

misal p = 2 dan q = 7

2. N = p x q = 2 x 7 = 14

3. Tentukan nilai Phi(N), yaitu bilangan 1 sd 14 yang bukan faktor persekutuan 14 dari 2 dan 7. Jika di jabarkan: 6. Atau menggunakan rumus Phi(N) = (p-1)(q-1).

Phi(14)=(2-1)x(7-1) = 6
Phi(N)=6

4.  Tentukan nilai e yang memenuhi 2 kriteria: (i) 1 < e < Phi(N) dan (ii) bukan faktor persekutuan N dan Phi(N),

Jika di jabarkan: e=5

Sekarang didapatkan Public Key (e, N) yaitu (5, 14)

5. Menentukan d, dimana berlaku persamaan : de mod Phi(N) = 1.

Atau  5d mod 6 = 1

Jika di hitung maka kemungkinannya nilai d adalah 5, 11, 17, 23, dst

Si penerima harus memilih salah satu (dan ini dirahasiakan) yaitu misalkan 11.

Maka d=11

Sehingga: Private Key (11, 14).

Info yang di dapat hacker: Public key (5, 14).Dengan informasi ini maka sulit untuk menebak Private key (d, 14). Artinya sulit menebak nilai d. Kenapa?

Karena nilai d = 11 itu di turunkan dari Phi(N). Nilai N diketahui oleh hacker. Akan tetapi nilai N yaitu 6 adalah perkalian 2 nilai bilangan prima besar (yaitu p dan q), yang mana hanya si pembuat kunci yang tahu berapa nilai p dan q yang dia pilih.

Nilai p dan q adalah bilangan prima dalam rentang 1 sd 2^2048 (untuk RSA dengan 2048 bit key). Dan bilangan tsb sangat besar, sehingga kalau dilaukan perhitungan iterasi matematika nilai d ini akan ditemukan setelah bertahun-tahun.

Note1: menurut wikipedia, RSA 1024 bit tidak dapat di crack sampai tahun 2010. Sedangkan RSA 2048 bit tidak dapat di crack sampai tahun 2030.

Note2: 

Pada contoh diatas si pembuat Private key memilih nilai 11 untuk varibel d. Bisa juga si pembuat Private Key memilih 17 misalkan dengan hasil operasi dekripsi tetap sama.

Apabila di pilih 17, maka contoh diatas 4^17 mod 14 = 2

RSA dalam dunia nyata:

Bilangan p dan q adalah bilangan prima yang dipilih bilangan prima yang sangat besar, yaitu 2048 bit, sehingga nilai d variannya sangat banyak. Ini yang menyebabkan sangat sulit untuk menebak berapa nilai d ini, karena kemungkinan nilai d ini sangat banyak sekali. Apabila akan di lakukan iterasi akan memakan waktu bertahun-tahun untuk mengetahui nilai mana yang dipilih oleh si pembuat Private dan Public key tsb.