Algoritma RSA dan Implementasi

--Untuk mengamankan data, salah satu cara dapat diterapkan suatu algoritma kriptografi
untuk melakukan enkripsi. Dengan enkripsi data tidak dapat terbaca karena teks asli atau
plaintext telah diubah ke teks yang tak terbaca atau disebut chipertext. Ada banyak algoritma
kriptografi yang dapat digunakan, berdasarkan sifat kuncinya dibagi menjadi dua yaitu simetris
yang hanya memakai satu kunci rahasia dan asimetris (public key algorithm) yang memakai
sepasang kunci publik dan kunci rahasia
.
Pada penelitian ini algoritma kriptografi yang akan digunakan adalah algoritma kriptografi
asimetris RSA yang ditemukan oleh Ron Rivest, Adi Shamir, dan Leonard Adleman pada tahun
1978 dan RSA merupakan singkatan inisial dari nama mereka bertiga.
RSA digunakan karena merupakan algoritma kriptografi asimetris yang paling sering
digunakan pada saat ini dikarenakan kehandalannya. Panjang kunci dalam bit dapat diatur,
dengan semakin panjang bit maka semakin sukar untuk dipecahkan karena sulitnya
memfaktorkan dua bilangan yang sangat besar tersebut, tetapi juga semakin lama pada proses
dekripsinya.>

·       Algoritma RSA dibuat oleh 3 orang peneliti dari MIT (Massachussets Institute of Technology) pada tahun 1976, yaitu: Ron (R)ivest, Adi (S)hamir, dan Leonard (A)dleman.

·       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.

·       Besaran-besaran yang digunakan pada algoritma RSA:

1.  p dan q bilangan prima                                 (rahasia)

2.  r = p × q                                                          (tidak rahasia)

3.  f(r) = (p – 1)(q – 1)                                      (rahasia)

4.  PK     (kunci enkripsi)                                  (tidak rahasia)

5.  SK     (kunci dekripsi)                                  (rahasia)

6.  X     (plainteks)                                              (rahasia)

7.  Y    (cipherteks)                                             (tidak rahasia)    

·       Algoritma RSA didasarkan pada teorema Euler (lihat bahan kuliah Teori Bilangan Bulat) yang menyatakan bahwa

          a^f(r) º 1 (mod r)                                                  (1)

yang dalam hal ini,

1.    a harus relatif prima terhadap r

2.    f(r) = r(1 – 1/p₁)(1 – 1/p₂) … (1 – 1/p_n), yang dalam hal ini p₁, p₂, …, p_n adalah faktor prima dari r.

·       f(r) adalah fungsi yang menentukan berapa banyak dari bilangan-bilangan 1, 2, 3, …, r yang relatif prima terhadap r.

·       Berdasarkan sifat a^m º b^m (mod r) untuk m bilangan bulat ³ 1, maka persamaan (1) dapat ditulis menjadi

a ^mf(r) º 1^m (mod r)     

atau

                   a^mf(r) º 1 (mod r)                                                (2)

·       Bila a diganti dengan X, maka persamaan (2) menjadi

X^mf(r) º 1 (mod r)                                               (3)

·       Berdasarkan sifat ac º bc (mod r), maka bila persamaan (3) dikali dengan X menjadi:

X^{mf(r) + 1} º X (mod r)                                          (4)

yang dalam hal ini X relatif prima terhadap r.

·       Misalkan SK dan PK dipilih sedemikian sehingga

SK × PK º 1 (mod f(r))                                      (5)

atau

SK × PK = mf(r) + 1                                           (6)

·       Sulihkan (6) ke dalam persamaan (4) menjadi:

X ^{SK × PK} º X (mod r)                                           (7)

         

·       Persamaan (7) dapat ditulis kembali menjadi

(X ^PK)^SK º X (mod r)                                           (8)

yang artinya, perpangkatan X dengan PK diikuti dengan perpangkatan dengan SK menghasilkan kembali X semula.

·       Berdasarkan persamaan (8), maka enkripsi dan dekripsi dirumuskan sebagai berikut:

E_PK(X) = Y º X^PK mod r                                     (8)

D_SK(Y) = X º Y^SK mod r                                     (9)

                            

·       Karena SK × PK = PK × SK, maka enkripsi diikuti dengan dekripsi ekivalen dengan dekripsi diikuti enkripsi:

E_SK(D_SK(X)) = D_SK(E_PK(X)) º X^PK mod r          (10)

·       Oleh karena X^PK mod r º (X + mr)^PK mod r untuk sembarang bilangan bulat m, maka tiap plainteks X, X + r, X + 2r, …, menghasilkan cipherteks yang sama. Dengan kata lain, transformasinya dari banyak ke satu. Agar transformasinya satu-ke-satu, maka X harus dibatasi dalam himpunan {0, 1, 2, …, r – 1} sehingga enkripsi dan dekripsi tetap benar seperti pada persamaan (8) dan (9).

Prosedur Membuat Pasangan Kunci

1.    Pilih dua buah bilangan prima sembarang, p dan q.

2.    Hitung r = p × q. Sebaiknya p ¹ q, sebab jika p = q maka r = p² sehingga p dapat diperoleh dengan menarik akar pangkat dua dari r.

3.    Hitung f(r) = (p – 1)(q – 1).

4.    Pilih kunci publik, PK, yang relatif prima terhadap f(r).

5.    Bangkitkan kunci rahasia dengan menggunakan persamaan (5), yaitu SK × PK º 1 (mod f(r)).

Perhatikan bahwa SK × PK º 1 (mod f(r)) ekivalen dengan  SK × PK = 1 + mf(r), sehingga SK dapat dihitung dengan

                                                            (11)

Akan terdapat bilangan bulat m yang menyebabkan  memberikan bilangan bulat SK.

Catatan: PK dan SK dapat dipertukarkan urutan pembangkitannya. Jika langkah 4 diganti dengan “Pilih kunci rahasia, SK, yang …”, maka pada langkah 5 kita menghitung kunci publik dengan rumus yang sama.

Contoh 1. Misalkan p = 47 dan q = 71 (keduanya prima). Selanjutnya, hitung nilai

r = p × q = 3337

dan

f(r)= (p – 1)(q – 1) = 3220.

Pilih kunci publik SK = 79, karena 79 relatif prima dengan 3220.    PK dan r dapat dipublikasikan ke umum.

Selanjutnya akan dihitung kunci dekripsi SK seperti yang dituliskan pada langkah instruksi 5 dengan menggunakan persamaan (11),

                                                                                     

Dengan mencoba nilai-nilai m = 1, 2, 3, …, diperoleh nilai SK yang bulat adalah 1019. Ini adalah kunci dekripsi yang harus dirahasiakan.

Enkripsi

·       Plainteks disusun menjadi blok-blok x₁, x₂, …, sedemikian sehingga setiap blok merepresentasikan nilai di dalam rentang 0 sampai r – 1.

·       Setiap blok x_i dienkripsi menjadi blok y_i dengan rumus

y_i = x_i ^PK mod r   

Dekripsi

·       Setiap blok cipherteks y_i didekripsi kembali menjadi blok x_i dengan rumus

x_i = y_i ^SK mod r   

Contoh 2. Misalkan plainteks yang akan dienkripsikan adalah

X = HARI INI

atau dalam sistem desimal (pengkodean ASCII) adalah

7265827332737873

Pecah X menjadi blok yang lebih kecil, misalnya X dipecah menjadi enam blok yang berukuran 3 digit:

          x₁ = 726               x₄ = 273

          x₂ = 582               x₅ = 787

          x₃ = 733               x₆ = 003

Nilai-nilai x_i ini masih terletak di dalam rentang 0 sampai 3337 – 1 (agar transformasi menjadi satu-ke-satu).

Blok-blok plainteks dienkripsikan sebagai berikut:

726⁷⁹ mod 3337 = 215 = y₁

582⁷⁹ mod 3337 = 776 = y₂

733⁷⁹ mod 3337 = 1743 = y₃

273⁷⁹ mod 3337 = 933 = y₄

787⁷⁹ mod 3337 = 1731 = y₅

003⁷⁹ mod 3337 = 158 = y₆

Jadi, cipherteks yang dihasilkan adalah

 Y = 215 776 1743 933 1731 158.

Dekripsi dilakukan dengan menggunakan kunci rahasia

SK = 1019

Blok-blok cipherteks didekripsikan sebagai berikut:

215¹⁰¹⁹ mod 3337 = 726 = x₁

776¹⁰¹⁹ mod 3337 = 582 = x₂

1743¹⁰¹⁹ mod 3337 = 733 = x₃

…

Blok plainteks yang lain dikembalikan dengan cara yang serupa. Akhirnya kita memperoleh kembali plainteks semula

P = 7265827332737873

yang dalam karakter ASCII adalah

P = HARI INI.                                                   

Kekuatan dan Keamanan RSA

·       Keamanan algoritma RSA terletak pada tingkat kesulitan dalam memfaktorkan bilangan non prima menjadi faktor primanya, yang dalam hal ini r = p ´ q.

·       Sekali r berhasil difaktorkan menjadi p dan q, maka  f(r) = (p – 1) (q – 1) dapat dihitung. Selanjutnya, karena kunci enkrispi PK diumumkan (tidak rahasia), maka  kunci dekripsi SK dapat dihitung dari persamaan PK × SK º 1 (mod f(r)).

         

·       Penemu algoritma RSA menyarankan nilai p dan q panjangnya lebih dari 100 digit. Dengan demikian hasil kali r = p ´ q akan berukuran lebih dari 200 digit. Menurut Rivest dan kawan-kawan, uasaha untuk mencari faktor bilangan 200 digit membutuhkan waktu komputasi selama 4 milyar tahun! (dengan asumsi bahwa algoritma pemfaktoran yang digunakan adalah algoritma yang tercepat saat ini dan komputer yang dipakai mempunyai kecepatan 1 milidetik).

·       Untunglah algoritma yang paling mangkus untuk memfaktorkan bilangan yang besar belum ditemukan. Inilah yang membuat algoritma RSA tetap dipakai hingga saat ini. Selagi belum ditemukan algoritma yang mangkus untuk memfaktorkan bilangan bulat menjadi faktor primanya, maka algoritma RSA tetap direkomendasikan untuk menyandikan pesan.

Source code for RSA.java:

import java.math.BigInteger; 
import java.util.Random;
import java.io.*;
 
 
public class RSA { 
     
    private BigInteger p; 
    private BigInteger q; 
    private BigInteger N; 
    private BigInteger phi; 
    private BigInteger e; 
    private BigInteger d; 
    private int bitlength = 1024; 
    private int blocksize = 256; //blocksize in byte 
     
    private Random r; 
     public RSA() { 
        r = new Random(); 
        p = BigInteger.probablePrime(bitlength, r); 
        q = BigInteger.probablePrime(bitlength, r); 
          N = p.multiply(q); 
           
        phi = p.subtract(BigInteger.ONE).multiply(q.subtract(BigInteger.ONE)); 
          e = BigInteger.probablePrime(bitlength/2, r); 
         
        while (phi.gcd(e).compareTo(BigInteger.ONE) > 0 && e.compareTo(phi) < 0 ) { 
            e.add(BigInteger.ONE); 
        } 
 d = e.modInverse(phi);  
    } 
     
    public RSA(BigInteger e, BigInteger d, BigInteger N) { 
        this.e = e; 
        this.d = d; 
        this.N = N; 
    } 
     
    public static void main (String[] args) throws IOException
{ 
        RSA rsa = new RSA(); 
           DataInputStream in=new DataInputStream(System.in);  
        String teststring ;
         System.out.println("Enter the plain text:");
        teststring=in.readLine();
        System.out.println("Encrypting String: " + teststring); 
        System.out.println("String in Bytes: " + bytesToString(teststring.getBytes())); 
 
        // encrypt 
        byte[] encrypted = rsa.encrypt(teststring.getBytes());                   
        System.out.println("Encrypted String in Bytes: " + bytesToString(encrypted)); 
         
        // decrypt 
        byte[] decrypted = rsa.decrypt(encrypted);       
        System.out.println("Decrypted String in Bytes: " +  bytesToString(decrypted)); 
         
        System.out.println("Decrypted String: " + new String(decrypted)); 
         
    } 
 
   private static String bytesToString(byte[] encrypted) { 
        String test = ""; 
        for (byte b : encrypted) { 
            test += Byte.toString(b); 
        } 
        return test; 
    } 
     
     public byte[] encrypt(byte[] message) {      
        return (new BigInteger(message)).modPow(e, N).toByteArray(); 
    } 
       
    public byte[] decrypt(byte[] message) { 
        return (new BigInteger(message)).modPow(d, N).toByteArray(); 
    } 
     
}

OUTPUT: