Algoritma RSA di Java

Dalam postingan ini, saya akan menerangkan secara sederhana tentang Algoritma RSA dan bagaimana implementasinya dalam Java.

RSA
RSA di bidang kriptografi adalah sebuah algoritma pada enkripsi public key. RSA merupakan algoritma pertama yang cocok untuk digital signature seperti halnya ekripsi, dan salah satu yang paling maju dalam bidang kriptografi public key. RSA masih digunakan secara luas dalam commerce electronic protocol, dan dipercaya dalam mengamankan dengan menggunakan kunci yang cukup panjang.

Algoritma RSA pertama dijabarkan pada tahun 1977 oleh tiga orang: Ron Rivest, Adi Shamir dan Len Adleman dari Massachusetts Institute of Technology. Hurus RSA itu sendiri berasal dari nama mereka masing-masin (Rivest-Shamir-Adleman).

Algoritma tersebut dipatenkan oleh MIT opada tahun 1983 di Amerika Serikat sebagai U.S. Patent 4.405.829. Paten tersebut berlaku hingga 21 September 2000. Semenjak Algoritma RSA dipublikasikan sebagai aplikasi paten, regulasi di sebagian besar negara-negara lain tidak memungkinkan penggunaan paten.

RSA merupakan terobosan baru dalam sistem enkripsi data karena sebelumnya menge

Contoh ilustrasi Algoritma RSA bekerja.

Semisal Alice berkeinginan untuk mengizinkan Bob untuk mengirimkan kepadanya sebuah pesan pribadi (private message) melalui media transmisi yang tidak aman (insecure). Alice melakukan langkah-langkah berikut untuk membuat pasangan kunci public key dan private key:

Proses pembuatan kunci:

1. Pilih dua bilangan prima p ≠ q secara acak dan terpisah untuk tiap-tiap p dan q. Hitung N = p q. N hasil perkalian dari p dikalikan dengan q.
2. Hitung φ = (p-1)(q-1).
3. Pilih bilangan bulat (integer) antara satu dan φ (1 < e < φ) yang juga merupakan koprima dari φ.
4. Hitung d hingga d e ≡ 1 (mod φ).

• bilangan prima dapat diuji probabilitasnya menggunakan Fermat's little theorem- a^(n-1) mod n = 1 jika n adalah bilangan prima, diuji dengan beberapa nilai a menghasilkan kemungkinan yang tinggi bahwa n ialah bilangan prima. Carmichael numbers (angka-angka Carmichael) dapat melalui pengujian dari seluruh a, tetapi hal ini sangatlah langka.
• langkah 3 dan 4 dapat dihasilkan dengan algoritma extended Euclidean; lihat juga aritmetika modular.
• langkah 4 dapat dihasilkan dengan menemukan integer x sehingga d = (x(p-1)(q-1) + 1)/e menghasilkan bilangan bulat, kemudian menggunakan nilai dari d (mod (p-1)(q-1));
• langkah 2 PKCS#1 v2.1 menggunakan &lamda; = lcm(p-1, q-1) selain daripada φ = (p-1)(q-1)).

Pada public key terdiri atas:

• N, modulus yang digunakan.
• e, eksponen publik (sering juga disebut eksponen enkripsi).

Pada private key terdiri atas:

• N, modulus yang digunakan, digunakan pula pada public key.
• d, eksponen pribadi (sering juga disebut eksponen dekripsi), yang harus dijaga kerahasiaannya.

Biasanya, berbeda dari bentuk private key (termasuk parameter CRT):

• p dan q, bilangan prima dari pembangkitan kunci.
• d mod (p-1) dan d mod (q-1) (dikenal sebagai dmp1 dan dmq1).
• (1/q) mod p (dikenal sebagai iqmp).

Bentuk ini membuat proses dekripsi lebih cepat dan signing menggunakan Chinese Remainder Theorem (CRT). Dalam bentuk ini, seluruh bagian dari private key harus dijaga kerahasiaannya.

Alice mengirimkan public key kepada Bob, dan tetap merahasiakan private key yang digunakan. p dan q sangat sensitif dikarenakan merupakan faktorial dari N, dan membuat perhitungan dari d menghasilkan e. Jika p dan q tidak disimpan dalam bentuk CRT dari private key, maka p dan q telah terhapus bersama nilai-nilai lain dari proses pembangkitan kunci.

Proses enkripsi pesan:
Misalkan Bob ingin mengirim pesan m ke Alice. Bob mengubah m menjadi angka n < N, menggunakan protokol yang sebelumnya telah disepakati dan dikenal sebagai padding scheme.

Maka Bob memiliki n dan mengetahui N dan e, yang telah diumumkan oleh Alice. Bob kemudian menghitung ciphertext c yang terkait pada n:
 c = n^e \mod{N}


Perhitungan tersebut dapat diselesaikan dengan cepat menggunakan metode exponentiation by squaring. Bob kemudian mengirimkan c kepada Alice.

Proses dekripsi pesan:
Alice menerima c dari Bob, dan mengetahui private key yang digunakan oleh Alice sendiri. Alice kemudian memulihkan n dari c dengan langkah-langkah berikut:
n = c^d \mod{N}

Perhitungan di atas akan menghasilkan n, dengan begitu Alice dapat mengembalikan pesan semula m. Prosedur dekripsi bekerja karena
c^d \equiv (n^e)^d \equiv n^{ed} \pmod{N}.

Kemudian, dikarenakan ed ≡ 1 (mod p-1) dan ed ≡ 1 (mod q-1), hasil dari Fermat's little theorem.
n^{ed} \equiv n \pmod{p}

dan
n^{ed} \equiv n \pmod{q}.

Dikarenakan p dan q merupakan bilangan prima yang berbeda, mengaplikasikan Chinese remainder theorem akan menghasilkan dua macam kongruen
n^{ed} \equiv n \pmod{pq}

serta
c^d \equiv n \pmod{N}.

Contoh Prosesnya
Berikut ini merupakan contoh dari enkripsi RSA dan dekripsinya. Parameter yang digunakan disini berupa bilangan kecil.

Kita membuat :

• p = 61 = bilangan prima pertama (harus dijaga kerahasiannya atau dihapus secara hati-hati)
• q = 53 = bilangan prima kedua (harus dijaga kerahasiannya atau dihapus secara hati-hati)
• N = pq = 3233 = modulus (diberikan kepada publik)
• e = 17 = eksponen publik (diberikan kepada publik)
• d = 2753 = eksponen pribadi (dijaga kerahasiannya)

Public key yang digunakan adalah (e,N). Private key yang digunakan adalah d. Fungsi pada enkripsi ialah:

• encrypt(n) = ne mod N = n17 mod 3233

dimana n adalah plaintext Fungsi dekripsi ialah:

• decrypt(c) = cd mod N = c2753 mod 3233

dimana c adalah ciphertext.

Untuk melakukan enkripsi plaintext bernilai "123", perhitungan yang dilakukan:

• encrypt(123) = 12317 mod 3233 = 855

Untuk melakukan dekripsi ciphertext bernilai "855" perhitungan yang dilakukan:

• decrypt(855) = 8552753 mod 3233 = 123

Kedua perhitungan di atas diselesaikan secara effisien menggunakan square-and-multiply algorithm pada modular exponentiation.

Gambar untuk penjelasan proses Algoritma RSA bekerja bisa dilihat dibawah ini :
















Keamanan
Penyerangan yang paling umum pada RSA ialah pada penanganan masalah faktorisasi pada bilangan yang sangat besar. Apabila terdapat faktorisasi metode yang baru dan cepat telah dikembangkan, maka ada kemungkinan untuk membongkar RSA.

Pada tahun 2005, bilangan faktorisasi terbesar yang digunakan secara umum ialah sepanjang 663 bit, menggunakan metode distribusi mutakhir. Kunci RSA pada umumnya sepanjang 1024—2048 bit. Beberapa pakar meyakini bahwa kunci 1024-bit ada kemungkinan dipecahkan pada waktu dekat (hal ini masih dalam perdebatan), tetapi tidak ada seorangpun yang berpendapat kunci 2048-bit akan pecah pada masa depan yang terprediksi.

Semisal Eve, seorang eavesdropper (pencuri dengar—penguping), mendapatkan public key N dan e, dan ciphertext c. Bagimanapun juga, Eve tidak mampu untuk secara langsung memperoleh d yang dijaga kerahasiannya oleh Alice. Masalah untuk menemukan n seperti pada ne=c mod N di kenal sebagai permasalahan RSA.

Cara paling efektif yang ditempuh oleh Eve untuk memperoleh n dari c ialah dengan melakukan faktorisasi N kedalam p dan q, dengan tujuan untuk menghitung (p-1)(q-1) yang dapat menghasilkan d dari e. Tidak ada metode waktu polinomial untuk melakukan faktorisasi pada bilangan bulat berukuran besar di komputer saat ini, tapi hal tersebut pun masih belum terbukti.

Masih belum ada bukti pula bahwa melakukan faktorisasi N adalah satu-satunya cara untuk memperoleh n dari c, tetapi tidak ditemukan adanya metode yang lebih mudah (setidaknya dari sepengetahuan publik).

Bagaimanapun juga, secara umum dianggap bahwa Eve telah kalah jika N berukuran sangat besar.

Jika N sepanjang 256-bit atau lebih pendek, N akan dapat difaktorisasi dalam beberapa jam pada Personal Computer, dengan menggunakan perangkat lunak yang tersedia secara bebas. Jika N sepanjang 512-bit atau lebih pendek, N akan dapat difaktorisasi dalam hitungan ratusan jam seperti pada tahun 1999. Secara teori, perangkat keras bernama TWIRL dan penjelasan dari Shamir dan Tromer pada tahun 2003 mengundang berbagai pertanyaan akan keamanan dari kunci 1024-bit. Santa disarankan bahwa N setidaknya sepanjang 2048-bit.

Pada thaun 1993, Peter Shor menerbitkan Algoritma Shor, menunjukkan bahwa sebuah komputer quantum secara prinsip dapat melakukan faktorisasi dalam waktu polinomial, mengurai RSA dan algoritma lainnya. Bagaimanapun juga, masih terdapat pedebatan dalam pembangunan komputer quantum secara prinsip.

Implementasi di Java
berikut adalah source code pengimplementasiannya di Java:

import java.math.BigInteger;

import java.security.SecureRandom;

public class RSA {

  private BigInteger n, d, e;

  private int bitlen = 1024;

  /** Create an instance that can encrypt using someone elses public key. */

  public RSA(BigInteger newn, BigInteger newe) {

    n = newn;

    e = newe;

  }

  /** Create an instance that can both encrypt and decrypt. */

  public RSA(int bits) {

    bitlen = bits;

    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);

  }

  /** Encrypt the given plaintext message. */

  public synchronized String encrypt(String message) {

    return (new BigInteger(message.getBytes())).modPow(e, n).toString();

  }

  /** Encrypt the given plaintext message. */

  public synchronized BigInteger encrypt(BigInteger message) {

    return message.modPow(e, n);

  }

  /** Decrypt the given ciphertext message. */

  public synchronized String decrypt(String message) {

    return new String((new BigInteger(message)).modPow(d, n).toByteArray());

  }

  /** Decrypt the given ciphertext message. */

  public synchronized BigInteger decrypt(BigInteger message) {

    return message.modPow(d, n);

  }

  /** Generate a new public and private key set. */

  public synchronized void generateKeys() {

    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);

  }

  /** Return the modulus. */

  public synchronized BigInteger getN() {

    return n;

  }

  /** Return the public key. */

  public synchronized BigInteger getE() {

    return e;

  }

  /** Trivial test program. */

  public static void main(String[] args) {

    RSA rsa = new RSA(1024);

    String text1 = "Yellow and Black Border Collies";

    System.out.println("Plaintext: " + text1);

    BigInteger plaintext = new BigInteger(text1.getBytes());

    BigInteger ciphertext = rsa.encrypt(plaintext);

    System.out.println("Ciphertext: " + ciphertext);

    plaintext = rsa.decrypt(ciphertext);

    String text2 = new String(plaintext.toByteArray());

    System.out.println("Plaintext: " + text2);

  }

}

Semoga membantu. :D