Minggu, 07 Oktober 2012

Menentukan Rute Terdekat Menggunakan Djikstra’s Algorithm

Shortest path finder adalah metoda berupa algoritma yang digunakan untuk mencari rute terdekat. Ada banyak algoritma yang bisa digunakan. Dua algoritma yang paling poluler adalah Djikstra dan A* (baca: A star). Walaupun sama-sama bisa digunakan untuk mencari rute terdekat, namun keduanya memiliki prinsip yang berbeda.

Hal itu menyebabkan keduanya digunakan pada jenis kasus yang bebeda pula. Bahasan kali ini akan difokuskan pada algoritma djikstra. A* insya allah akan dibahas pada tulisan yang akan datang. Algoritma djikstra diperkenalkan pertama kali oleh Edsger Dijkstra, seorang ilmuan komputer berkebangsaan Belanda pada tahun 1959. Algoritma ini menjadi tulang punggung dari link-state routing. Link-state routing adalah satu dari dua kelas utama dari routing protocol yang digunakan pada packet switching networks dalam dunia komunikasi komputer (computer communications).

Agar bisa menentukan rute terdekat, djikstra memerlukan informasi berupa sebuah routing table. Routing table ini berisi kumpulan informasi simpul (vertex/node) dalam bentuk tabular. Sekumpulan simpul/nodes/vertex Perhatikan gambar di samping. A, B, C, D, E, dan F adalah simpul atau node atau vertex. Dari gambar terlihat bahwa simpul-simpul tersebut saling terhubung satu sama lain sedemikian sehingga membentuk rute. Bayangkan simpul tersebut adalah sebuah kota yang satu dengan lainnya dihubungkan oleh jalan. Maka untuk pergi ke kota F, seseorang yang berada di kota A sedikitnya bisa menempuh dua rute perjalanan yang berbeda, yaitu A → B → D → E → F dan A → C → F. Agar bisa sampai di kota F, tentunya orang yang melakukan perjalanan tersebut harus mempunyai informasi ke kota mana saja masing-masing kota terhubung secara langsung. Seperti pada gambar, kota A terhubung secara langsung dengan kota B dan C. Kota B terhubung langsung dengan kota A, C, dan D. Informasi inilah yang disebut sebagai informasi rute atau routing information. Informasi rute dari masing-masing kota ini yang kemudian dikumpulkan menjadi sebuah tabel rute atau routing table yang mencakup keenam kota tersebut. Kongkritnya, routing table dari kumpulan simpul/node/vertex seperti gambar di atas adalah sebagai berikut. routing table example Pada routing table di atas, selain parameter simpul asal (origin) dan simpul tujuan (destination), ada satu parameter lagi yaitu bobot (weight).

Parameter ini merepresentasikan seberapa besar usaha yang diperlukan untuk pergi dari simpul asal menuju simpul tujuan. Bobot di sini bisa direpresentasikan menjadi berbagai macam besaran seperti panjang, kerapatan, kepadatan, dan lain-lain tergantung implementasinya. Jika seperti analogi kota di atas, mungkin parameter bobot bisa merepresentasikan gabungan jarak dan kepadatan (tingkat kemacetan) yang tentu saja dengan komposisi tertentu. Agar mempermudah pemahaman, kita asumsikan saja semua jalan antar kota mempunyai bobot yang sama sehingga rute terdekat adalah sudah pasti yang jumlah simpulnya paling sedikit. Contoh, untuk pergi ke kota F dari kota A, rute A → C → F akan lebih dekat jika dibandingkan dengan A → B → D → E → F.
Atas pemahaman yang telah dipaparkan di ataslah algoritma djikstra dibuat. Animasi berikut akan membantu anda untuk lebih memahami algoritma djikstra dan lebih mudah untuk membayangkan bagaimana langkah-langkah untuk menulis kode programnya. program. Animasi djikstraDengan melihat animasi di samping, langkah-langkah dari algoritma djikstra adalah sebagai berikut:

1. Tentukan simpul asal (origin) dan simpul tujuan (destination).
 Seperti pada animasi, simpul asal adalah simpul a atau 1, sedangkan tujuannya adalah simpul b atau 5.

 2. Tandai semua simpul dengan tanda “belum dikunjungi” atau “unvisited”, kecuali simpul asal bisa langsung diset menjadi dikunjungi atau “visited”. Secara implementasi, tanda visited maupun unvisited bisa dengan cara mengeset salah satu atribut simpul dengan nilai 0 untuk mengganti tanda visited atau tak hingga (∞) untuk mengganti tanda unvisited.

 3. Untuk setiap iterasi, periksa bobot antara simpul saat ini sedang berada dengan simpul-simpul tetangganya. Misalnya sekarang sedang berada pada simpul 1, maka periksa bobot 1 → 2, 1 → 3, dan 1 → 6.

Dari gambar jelas terlihat bahwa bobot terkecil adalah 1 → 2 = 7. Sehingga jika sekarang berada pada simpul 1 maka simpul selanjutnya adalah simpul 2. Karena perjalanan telah sampai disimpul 2, maka atribut ∞ dari simpul ini diset menjadi 0 untuk menandakan telah dikunjungi.

4. Ulangi langkah 3 di atas untuk simpul selanjutnya, hingga berakhir pada pada simpul tujuan dalam kasus ini adalah simpul 5.

Pseudo code dari algoritma djikstra bisa dituliskan sebagai berikut:

function Dijkstra(Graph, source):
      for each vertex v in Graph:            // Initializations
          dist[v] := infinity ;              // Unknown distance function from source to v
          previous[v] := undefined ;         // Previous node in optimal path from source
      end for ;
      dist[source] := 0 ;                    // Distance from source to source
      Q := the set of all nodes in Graph ;   // All nodes in the graph are unoptimized - thus are in Q
      while Q is not empty:                  // The main loop
          u := vertex in Q with smallest distance in dist[] ;
          if dist[u] = infinity:
              break ;                        // all remaining vertices are inaccessible from source
          end if ;
          remove u from Q ;
          for each neighbor v of u:          // where v has not yet been removed from Q.
              alt := dist[u] + dist_between(u, v) ;
              if alt < dist[v]:              // Relax (u,v,a)
                  dist[v] := alt ;
                  previous[v] := u ;
                  decrease-key v in Q;       // Reorder v in the Queue
              end if ;
          end for ;
      end while ;
      return dist[] ;
  end Dijkstra.
 
Algoritma djikstra biasanya digunakan pada service dan aplikasi yang berhubungan dengan routing protocol.
 

Sabtu, 06 Oktober 2012

Algoritma RC4 dan Implementasi Kode

RC4 adalah penyandian stream cipher yang dibuat oleh Ron Riverst pada tahun 1987 untuk pengamanan RSA. Algoritmanya didasarkan pada permutasi acak. Kunci dengan panjang variable 1 – 256 bytes digunakan untuk inisialisasi sebuah state.

Vector S dengan panjang 256 byte, dengan elemen S[0], S[1],…,S[255]. S terdiri dari permutasi semua bilangan 8 bit dari 0 – 255 untuk enkripsi atau deskripsi, sebuah byte K dibangkitkan dari S dengan memilih 1 dari 255 entri dengan cara sistematis. Setiap kali k dibangkitkan, entri-entri pada S sekali lagi dipermutasikan. ^ inisialisasi S Entri – entri S di set dari 0 – 255 dengan urutan naik; S[0] = 0, S[1] = 1,….,S[255] = 255.

 vektor sementara T juga dibuat. Jika panjang kunci dari K =256 byte, lalu K di transper ke T. Jika tidak, untuk setiap kunci dengan panjang keylen byte, elemen keylen pertama T dicopykan dari K. Dan K diulang beberapa kali untuk mengisi T. /* inisialisasi */ for i = 0 to 255 do S[i] = i; T[i] = K [i % keylen];

 lalu kita menggunakan T untuk menginisialisasi permutasi S. Dimulai dengan S[0] hingga S[255] dan untuk setiap S[i], tukar S[i] dengan byte lainnya pada S berdasarkan skema. /* inisial permutasi */ j = 0; for i = 0 to 255 do j = (j + S[i] + T[i] % 256 ); swap ( s[i], S[j] );

karena operasi pada S hanya pertukaran maka hanya terjadi permutasi dengan S tetap semua bilangan antara 0 – 255. ^ Pembangkitan Stream Setelah S diinisialisasi, key input tidak lagi dipakai.

 Pembangkitan stream dimulai dengan S[0] – S[255] dan untuk setiap S[i], menukar S[i] dengan byte lainnyadalam S berdasarkan skema berikut.

 Setelah S[255] dicapai proses berlanjut, dimulai kembali dari S[0]. /* stream generation */ i,j = 0; While (true) i = ( i+1 ) % 256; j = ( j + S[i]) % 256; swap ( S[i], S[j] ); t = ( S[i], S[j] )% 256; k= S[t]; untuk enkripsi, XOR nilai K dengan byte selanjutnnya pada plainteks.

Untuk dekripsi, XOR nilai K denganbyte selanjutnya pada cipherteks.

 import java.io.*;
 public class RC4 { f
inal String plaintext="Halo Adi Apa Kabar";
final String kunci="halo apa kabar";
 public static void main (String [] args) throws IOException { RC4 xx=new RC4(); xx.mulai(); }
 void mulai(){ int i, j = 0; char [] key;
 int keylen = 0; int k = 0;

 int [] SBox = new int [256]; key = new char[kunci.length()]; for (k=0; k"+Integer.toHexString(chiper).toUpperCase()+"\t"+"CHIPPER\t\t=>"+Character.toChars(chiper)); //chipertext } } }

 public class RC4 { private byte state[] = new byte[256];
 private int x; 

 private int y; public RC4(String key) throws NullPointerException { this(key.getBytes()); }
 public RC4(byte[] key) throws NullPointerException { 
for (int i=0; i < 256; i++) { state[i] = (byte)i; }
 x = 0; y = 0; int index1 = 0; int index2 = 0; 
byte tmp; if (key == null || key.length == 0) { 
throw new NullPointerException(); }

 for (int i=0; i < 256; i++) {
 index2 = ((key[index1] & 0xff) + (state[i] & 0xff) + index2) & 0xff; tmp = state[i];
 state[i] = state[index2]; state[index2] = tmp; index1 = (index1 + 1) % key.length; } }

 public byte[] rc4(String data) { if (data == null) { return null; } 

 byte[] tmp = data.getBytes(); this.rc4(tmp); return tmp; }
 public byte[] rc4(byte[] buf) {
 //int lx = this.x;
 //int ly = this.y;
 int xorIndex; 
byte tmp;

 if (buf == null) { return null; }

 byte[] result = new byte[buf.length]; 
 for (int i=0; i < buf.length; i++) { 
 x = (x + 1) & 0xff; y = ((state[x] & 0xff) + y) & 0xff; 
tmp = state[x]; state[x] = state[y];
 state[y] = tmp; 
xorIndex = ((state[x] &0xff) + (state[y] & 0xff)) & 0xff;
 result[i] = (byte)(buf[i] ^ state[xorIndex]); } 
//this.x = lx; //this.y = ly; return result; } }

Algorima Knapsack dan Penerapan di Kode Java

Salah satu algoritma public key adalah algoritma knapsack. Apa sih algoritma Knapsack itu? Algoritma Knapsack adalah algoritma kriptografi kunci-publik yang keamanannya terletak pada sulitnya memecahkan persoalan knapsack(Knapsack Problem). Knapsack di sini artinya adalah kantung. Di algorima ini dikenal permasalahan yang disebut Knapsack Problem. Knapsack Problem Jika m merupakan bobt knapsack dan n adalah banyaknya objek yang masing-masing mempunyai bobot w1,w2,…,wn. Tentukan nilai bi sedemikian sehingga M=b1w1+b2w2+…+bnwn Yang dalam hal ini bi hanya bernilai 0 dan 1. Jika b=1, maka objek I dimasukkan ke dalam Knapsack, sebaliknya jika b=0, maka tidak dimasukkan ke dalam knapsack. Algoritma Knapsack Sederhana Ide dasar Knapsack adalah mengkodekan pesan sebagai rangkaian solusi dari persoalan knapsack. Setiap bobot w1 di dalam persoalan knapsack merupakan kunci privat, sedangkan bit-bit plainteks menyatakan b1 Contoh : Misalkan n=6 dan w1=1, w2=5, w3=6, w4=11, w5=14 dan w6=20. Plainteks = 111001010110000000011000 Jawab: Plainteks dibagi menjadi blok yang panjangnya n, kemudian setiap bit di dalam blok dikalikan dengan w1 yang berkoresponden sesuai persamaan di atas: Blok plainteks ke-1 : 111001 Blok plainteks ke-2 : 010110 Blok plainteks ke-3 : 000000 Blok plainteks ke-4 : 011000 Knapsack : 1,5,6,11,14,20 Kriptogram ke-1 : (1×1) + (1×5) + (1×6) + (1×20) =32 Kriptogram ke-2 : (1×5) + (1×11) + (1×14) = 30 Kriptogram ke-3 : 0 Kriptogram ke-4 : (1×5) + (1×6) = 11 Jadi, cipherteks yang dihasilkan : 32, 30, 0, 11 Untuk algoritma di atas hanya bias digunakan untuk enkripsi saja. Misalkan kita diberikan kriptogram 32, maka kita harus mencari nilai b1,b2,…,b6 untuk persamaan 32 = b1+5b2+6b3+11b4+14b5+20b6 Solusi dari persamaan di atas tidak dapat dipecahkan dalam orde waktu polynomial dengan orde waktu polynomial dengan semakin besar n dan barisan bobot tidak dalam urutan naik. Superincreasing knapsack Superincreasing knapsack adalah persoalan knapsack yang dapat dipecahkan dalam orde 0(n) yang bersifat polynomial. Ini adalah perrsoalan knapsack yang mudah. Kita dapat membentuk barisan superincreasing kannpsack. Barisan superincreasing adalah suatu barisan di mana setiap nilai di dalam barisan lebih besar daripada jumlah semua nilai sebelumnya, misalnya(1,3,6,13,27,52). Solusi dari superincreasing knapsack mudah dicari dengan cara berikut: 1.Jumlahkan semua bobot dalam barisan. 2.Bandingkan bobot total dengan bobot terbesar di dalam barisan. Jika bobot terbesar lebih kecil atau sama dengan bobot total, maka ia dimasukkan ke dalam knapsack, jika tidak, maka tidak dimasukkan. 3.Kurangi bobot total dengan bobot yang telah dimasukkan, kemudian bandingkan bobot total sekarang dengan bobot terbesar selanjutnya. Demikian seterusnya sampai seluruh bobot di dalam barisan selesai dibandingkan. 4.Jika bobot total menjadi nol, maka terdapat solusi superincreasing knapsack, tetapi jika tidak nol, maka tidak ada solusinya. Contoh : Misalkan bobot-bobot yang membentuk barisan superincreasing adalah (2,3,6,13,27,52) dan diketahui bobot knapsack (m) = 70. untuk mencari nilai bi, caranya adalah sebagai berikut: 1.Bandingkan 70 dengan nilai terbesar yaitu 52. Karena 52< 52="18," 13="5">5, maka 6 tidak termasuk 6. Bandingkan bobot 3 dengan bobot total. Karena 3<5, 3="2." 2="0." 70 =" (1×2)" m="105," n="31." 105 =" 62" 105 =" 93" 105 =" 81" 105 =" 88" 105 =" 102" 105 =" 37" 1=" 1" 1=" 1"> n. n-1= 1 + km => n. n-1= (1+km)/n, k sembarang bilangan bulat..Kalikan setiap kriptogram dengan n-1 mod m, lalu nyatakan hasil kalinya sebagai penjumlahan elemen-elemen kunci privat untuk memperoleh plainteks dengan menggunakan algoritma pencarian solusi superincreasing knapsack.Contoh:Dari contoh sebelumnya, dengan menggunakan kunci privat (62,93,81,88,102,37). Di sini, n=31 dan m=105. Nilai n-1 diperoleh dari: n-1 = (1+105k)/31, dengan mencoba k=0,1,2,…, maka kita akan memperoleh nilai n-1 jika k=18.n-1 = (1+105.18)/31 = 61Plain teks yang berkoresponden diperoleh kembali dengan cara membuka di awal yang telah kita bahas. Hasilnya akan diperoleh174.61 mod 105 = 9 , bobotnya 3+6, berkoresponden dengan 011000280.61 mod 105 = 70 , bobotnya 2+3+13+52, berkoresponden dengan 110101333.61 mod 105 = 48 , bobotnya 2+6+13+27, berkoresponden dengan 101110 Jadi plainteksnya adalah: 011000 110101 101110 public class Knapsack { public static void main(String[] args) { int[] weights = {2, 3, 4, 3}; int[] values = {2, 3, 4, 5}; int capacity = 1; int[][] solution = getSolutionMatrix(values, weights, capacity); int[] optimalSubset = getOptimalSubset(solution, weights); printMatrix(solution, "Solution Matrix"); printArray(optimalSubset, "Optimal Subset"); } /** * * Returns the solution matrix for the Knapsack problem associated with the * given values, weights and knapsack capacity. * * @param values The values of the items. * @param weights The weights of the items. * @param capacity The capacity of the knapsack. * */ private static int[][] getSolutionMatrix(int[] values, int[] weights, int capacity) { int[][] matrix = new int[values.length + 1][capacity + 1]; for(int i = 1; i <= values.length; i++) { for (int j = 0; j <= capacity; j++) { if (j - weights[i-1] >= 0) { matrix[i][j] = Math.max(matrix[i-1][j], values[i-1] + matrix[i-1][j-weights[i-1]]); } else { matrix[i][j] = matrix[i-1][j]; } } } return matrix; } /** * * Returns the optimal subset of items that should be included in the knapsack * given a completed solution matrix. * * @param solutionMatrix An N by W matrix, where N is the number of items and W * is the capacity of the knapsack. * @param weights An array of size N containing the weights of each of the items. * */ private static int[] getOptimalSubset(int[][] solutionMatrix, int[] weights) { int[] subset = new int[weights.length]; int numItems = 0; int i = solutionMatrix.length - 1; for (int j = solutionMatrix[0].length - 1; j >= 0 && i > 0;i--) { // If the item is in the optimal subset, add it and subtract its weight // from the column we are checking. if (solutionMatrix[i][j] != solutionMatrix[i-1][j]) { subset[numItems] = i; j -= weights[i-1]; numItems++; } } return Arrays.copyOfRange(subset, 0, numItems); } /** * Prints an array to the console, applying the given title. */ private static void printArray(int[] array, String title) { StringBuilder builder = new StringBuilder(); builder.append("\n").append(title).append(":\n{"); if (array.length != 0) builder.append(array[0]); for (int i = 1; i < array.length; i++) { builder.append(", ").append(array[i]); } builder.append("}"); System.out.println(builder.toString()); } /** * Prints a matrix (2-dimensional array) to the console, applying the given title. */ private static void printMatrix(int[][] matrix, String title) { StringBuilder builder = new StringBuilder(); builder.append(title).append(":\n"); for (int i = 0; i < matrix.length; i++) { for (int j = 0; j < matrix[0].length; j++) { builder.append(matrix[i][j]).append("\t"); } builder.append("\n"); } System.out.print(builder.toString()); } }

Algoritma ElGamal dan Code

Algoritma ElGamal Algoritma Elgamal juga adalah algoritma kriptografi kunci-publik.
 Algoritma ini pada mulanya digunakan untuk digital signature, namun kemudian dimodifikasi sehingga juga bisa digunakan untuk enkripsi dan dekripsi. Kekuatan algoritma ini terletak pada sulitnya menghitung logaritma diskrit.

 Besaran-besaran yang digunakan d dalam algoritma ElGamal:
1. Bilangan prima, p (tidak rahasia)
2. Bilangan acak, g ( g < p) (tidak rahasia)
3. Bilangan acak, x (x < p) (rahasia)
 4. M (plainteks) (rahasia)
 5. a dan b (cipherteks) (tidak rahasia)

Prosedur Membuat Pasangan Kunci
 1. Pilih sembarang bilangan prima p.
 2. Pilih dua buah bilangan acak, g dan x, dengan syarat g < p dan x < p.
3. Hitung y = gx mod p.
4. Kunci publik adalah y, kunci rahasia adalah x.

 Nilai g dan p tidak dirahasiakan dan dapat diumumkan kepada anggota kelompok.
 Enkripsi Plainteks disusun menjadi blok-blok m1, m2, …, sedemikian sehingga setiap blok merepresentasikan nilai di dalam rentang 0 sampai p – 1.
Pilih bilangan acak k, yang dalam hal ini 0 == k == p – 1, sedemikian sehingga k relatif prima dengan p – 1. Setiap blok m dienkripsi dengan rumus a = g^k mod p b = y^km mod p Pasangan a dan b adalah cipherteks untuk blok pesan m. Jadi, ukuran cipherteks dua kali ukuran plainteksnya.

Dekripsi Untuk mendekripsi a dan b digunakan kunci rahasia, x, dan plainteks m diperoleh kembali dengan persamaan m = b/a^x mod p

Catatlah bahwa karena
a^x == g^kx (mod p) maka b/a^x == y^km/a^x == g^xkm/g^xk == m (mod p) berarti bahwa plainteks dapat ditemukan kembali dari pasangan cipherteks a dan b.


 import java.math.*;
 import java.util.*;
 import java.security.*;
import java.io.*;

public class ElGamal {

 public static void main(String[] args) throws IOException {
 BigInteger p, b, c, secretKey;
Random sc = new SecureRandom();
secretKey = new BigInteger("12345678901234567890"); // // public key calculation // System.out.println("secretKey = " + secretKey);
 p = BigInteger.probablePrime(64, sc);
 b = new BigInteger("3");
c = b.modPow(secretKey, p);
System.out.println("p = " + p);
System.out.println("b = " + b);
System.out.println("c = " + c); // // Encryption //
System.out.print("Enter your Big Number message -->");

String s = Tools.getString();
 BigInteger X = new BigInteger(s);
BigInteger r = new BigInteger(64, sc);
BigInteger EC = X.multiply(c.modPow(r, p)).mod(p);
BigInteger brmodp = b.modPow(r, p);
System.out.println("Plaintext = " + X);
System.out.println("r = " + r);
System.out.println("EC = " + EC);
System.out.println("b^r mod p = " + brmodp); // // Decryption //
BigInteger crmodp = brmodp.modPow(secretKey, p);
BigInteger d = crmodp.modInverse(p);
 BigInteger ad = d.multiply(EC).mod(p);
 System.out.println("\n\nc^r mod p = " + crmodp);
 System.out.println("d = " + d);
 System.out.println("Alice decodes: " + ad);
 }
 }

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

          af(r) º 1 (mod r)                                                  (1)

yang dalam hal ini,
1.    a harus relatif prima terhadap r
2.    f(r) = r(1 – 1/p1)(1 – 1/p2) … (1 – 1/pn), yang dalam hal ini p1, p2, …, pn 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 am º bm (mod r) untuk m bilangan bulat ³ 1, maka persamaan (1) dapat ditulis menjadi


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

atau

                   amf(r) º 1 (mod r)                                                (2)

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

Xmf(r) º 1 (mod r)                                               (3)

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

Xmf(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:

EPK(X) = Y º XPK mod r                                     (8)

DSK(Y) = X º YSK mod r                                     (9)

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

ESK(DSK(X)) = DSK(EPK(X)) º XPK mod r          (10)

·       Oleh karena XPK 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 = p2 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 x1, x2, …, sedemikian sehingga setiap blok merepresentasikan nilai di dalam rentang 0 sampai r – 1.
·       Setiap blok xi dienkripsi menjadi blok yi dengan rumus

yi = xi PK mod r   


Dekripsi

·       Setiap blok cipherteks yi didekripsi kembali menjadi blok xi dengan rumus

xi = yi 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:

          x1 = 726               x4 = 273
          x2 = 582               x5 = 787
          x3 = 733               x6 = 003

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

Blok-blok plainteks dienkripsikan sebagai berikut:

72679 mod 3337 = 215 = y1
58279 mod 3337 = 776 = y2
73379 mod 3337 = 1743 = y3
27379 mod 3337 = 933 = y4
78779 mod 3337 = 1731 = y5
00379 mod 3337 = 158 = y6

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:

2151019 mod 3337 = 726 = x1
7761019 mod 3337 = 582 = x2
17431019 mod 3337 = 733 = x3

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: