Algoritma RSA

Algoritma RSA

Dalam berkomunikasi menggunakan jaringan internet, lubang keamanan menjadi masalah serius karena perkembangan e-mail, e-banking, e-business dan jenis komunikasi lainnya makin pesat untuk mentranfer data-data penting. Sebagai contoh kasus Alice dan Bob yang ingin berkomunikasi dengan privasi tinggi, pada kenyataannya ada pihak ketiga yang dapat mengakses kemunikasi mereka, dalam hal ini Eve.

·         Enkripsi Simetrik

Salah satu solusi untuk Alice dan Bob dalam kasus ini adalah tukar-menukar data disertai suatu kunci digital, dimana keduanya telah sama-sama mengetahui kunci rahasia tersebut. Alice menggunakan kunci ini untuk mengkodekan    pesan yang dia kirimkan, dan Bob merekonstruksi pesan tersebut kembali dengan kunci yang sama. Pesan yang dienkrip (ciphertexts) tetap dapat diterima Eve tetapi tidak dapat membacanya karena tidak mempunyai kunci yang sama untuk mendekripsi kode pesan tersebut.

·         Enkripsi Kunci Publik 

Dalam penggunaan model enkripsi ini, kunci publik yang digunakan berbeda untuk enkripsi dan dekripsi. Digambarkan dalam diagram di atas, Key generator akan menghasilkan dua buah kunci publik, dimana setiap orang dapat mengetahui dan menggunakan kunci publik ini, tetapi hanya Bob yang mengetahui kunci privatnya untuk melakukan dekripsi pesan yang dikirim. Metoda ini memungkinkan Alice dan Bob tetap dapat berkomunikasi tanpa terganggu oleh pihak ke tiga.

Key Generation 1.        Dapatkan dua bilangan prima besar, p dan q 2.        Dapatkan nilai n, dimana n= pq 3.        Dapatkan nilai m, dimana m= ( p-1)(q-1) 4.        Pilih sebuah angka kecil e, coprime untuk m 5.        Cari nilai d,dimana d.e% m= 1 Publish e dan n sebagai kunci publik          Ambil d dan n sebagai kunci privat	Encryption C = Pe % n
	Decryption P = Cd % n
	x % y maksudnya adalah suatu nilai sisa x dibagi y (% = modulus)

Penjelasan metode ini selengkapnya adalah sebagai berikut  :

1.             Key Generation

a.     Dapatkan 2 bilangan prima, p dan q

Besar kecilnya bilangan prima ini menentukan tingkat keamanan data, semakin besar bilangan semakin banyak faktorialnya yang mengakibatkan semakin sulit data dapat dipecahkan dalam waktu singkat, sebagai contoh :

P=7

Q=19

b.    Dapatkan nilai n, dimana n= pq

n = 7 * 19

   = 133

c.     Dapatkan nilai m, dimana m= ( p-1)(q-1)

m = (7 - 1)(19 - 1)

   = 6 * 18

   = 108

d.    Pilih sebuah angka kecil e, coprime untuk m.

e coprime untuk m, maksudnya adalah bilangan terbesar yang dapat membagi  e dan m untuk menghasilkan nilai 1 (pembagi ini dinyatakan dengan gcd --greatest common divisor). Algoritma Euclid's digunakan untuk mencari  gcd dua bilangan sebagai berikut :

e = 2 => gcd(e, 108) = 2 (no)

e = 3 => gcd(e, 108) = 3 (no)

e = 4 => gcd(e, 108) = 4 (no)

e = 5 => gcd(e, 108) = 1 (yes!)

e.     Cari nilai d,dimana d.e% m = 1

Ini sama dengan seperti mencari nilai d memenuhi d.e = 1 + m.n, dimana n adalah bilangan integer, kita dapat menuliskan kembali pernyataan tersebut dengan d = (1+m.n)/e sehingga nilai-nilai n  dapat diselesaikan sampai didapat sebuah nilai yang integer seperti di bawah ini :

n = 0 => d = 1 / 5 (no)

n = 1 => d = 109 / 5 (no)

n = 2 => d = 217 / 5 (no)

n = 3 => d = 325 / 5

                                                 = 65 (yes!)

Setelah langkah ini selesai didapatkan kesimpulan :

Public Key n = 133 E = 5

Secret Key n = 133 d = 65

2.     Komunikasi

·         Enkripsi

Pesan dalam proses enkripsi harus merupakan suatu bilangan  lebih kecil dari nilai p dan q. Bagaimanapun, dalam posisi ini kita tidak mengetahui p atau q, tapi dalam prakteknya suatu lower bound/nilai yang lebih rendah pada p dan q harus dimunculkan. Contoh proses ini, kita gunakan nilai "6".

C = Pe      % n

  = 65      % 133

  = 7776 % 133   = 62

·         Dekripsi

Setelah proses enkripsi seperti di atas, maka dapat dilakukan proses dekripsi dalam beberapa langkah sebagai berikut  :

P = Cd % n

  = 6265 % 133

  = 62 * 6264 % 133

  = 62 * (622)32 % 133

  = 62 * 384432 % 133

  = 62 * (3844 % 133)32 % 133

  = 62 * 12032 % 133

Selanjutnya mengulangi urutan operasi yang mengurangi 62⁶⁵ sampai 120³² untuk mengurangi eksponen operasi tersebut hingga menjadi 1.

  = 62 * 3616 % 133

  = 62 * 998 % 133

  = 62 * 924 % 133

  = 62 * 852 % 133

  = 62 * 43 % 133

  = 2666 % 133

  = 6

Dengan melakukan langkah di atas, dapat dilihat bahwa pesan/data telah sama dengan data asli sebelum enkripsi yaitu “6”.

Implementasi RSA menggunakan Java

import java.math.BigInteger;

import java.security.SecureRandom;

class Rsa

{

  private BigInteger n, d, e;

  public Rsa(int bitlen)

  {

    SecureRandom r = new SecureRandom();

    BigInteger p = new BigInteger(bitlen / 2, 100, r);

    BigInteger q = new BigInteger(bitlen / 2, 100, r);

    n = p.multiply(q);

    BigInteger m = (p.subtract(BigInteger.ONE))

                 .multiply(q.subtract(BigInteger.ONE));

    e = new BigInteger("3");

    while(m.gcd(e).intValue() > 1) e = e.add(new BigInteger("2"));

    d = e.modInverse(m);

  }

  public BigInteger encrypt(BigInteger message)

  {

    return message.modPow(e, n);

  }

  public BigInteger decrypt(BigInteger message)

  {

    return message.modPow(d, n);

  }

}