Sabtu, 27 September 2014

Algortima Chipper dalam java


import java.util.LinkedHashSet;
import java.util.Set;

public class Chiper {
  //baris alphabet acuan
  private  String  alp  =
"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuv
wxyz0123456789 .,?!@()-_=+";//,./';[]!@#$%^&*()_+-=<>?\"{}`~\\ 
  //key  bawaan  aplikasi,  digunakan  di  inisialisasi  jika  key  yang digunakan bukan bawaan aplikasi
  private String key = "<oGHsoienJGDdop90?>";
  //panjang alphabet, digunakan untuk penggeseran dan modulus alphabet
  private int alen = this.alp.length();
  
  //constructor umum
  public Chiper(){
    this.adjustKeyWord();
  }
  
  public Chiper(String phone){
    if(!phone.equals(""))
      this.key = this.mixKeyword(phone);
    
    this.adjustKeyWord();
  }
  
  //constructor dengan keyword custom
  public Chiper(String phone,String keyword){
    if(!phone.equals(""))
      this.key = this.mixKeyword(phone);
    
    if(!keyword.equals(""))
      this.key = this.mixKeyword(keyword);
    
    this.adjustKeyWord();
  }
  
  //constructor dengan baris abjad custom dan keyword custom
  public Chiper(String phone,String keyword,String alphabet){
    this.alp = alphabet;
    this.alen = this.alp.length();
    
    if(!phone.equals(""))
      this.key = this.mixKeyword(phone);
    
    if(!keyword.equals(""))
      this.key = this.mixKeyword(keyword);
    
    this.adjustKeyWord();
  }
  //fungsi mixing 2 string keyword
  private String mixKeyword(String keyword) {
    String rkey = "";
    
    int lbk = this.key.length();
    int lik = keyword.length();
    
    int tnk = lbk>lik ? lbk : lik ;
    
    for(int i = 0;i<tnk;i++){
      if(i<lbk)
        rkey += this.key.charAt(i);
      if(i<lik)
        rkey += keyword.charAt(i);
    }
    
    return rkey;
    
  }
  
  private void adjustKeyWord(){
    this.key = adjustKeyWord(this.key);
  }
  
  //fungsi adjustment key memastikan 1 buah char/g ad yg sama
  private String adjustKeyWord(String keyword) {
    String kw = "";
    Set<Character>  keyChars  =  new
LinkedHashSet<Character>(keyword.length());
    for(char c : keyword.toCharArray()){
      if((alp.indexOf(c)  !=  -1)  &&
keyChars.add(c)){
        kw += String.valueOf(c);
      }
    }
    //Log.i("keyword",kw);
    
    return kw;

  }
  
  //fungsi fibonanci key
  private void getFibonanciKey(int llen,int klen,String line){
    //selisih panjang kalimat dengan panjang key
    int loss = llen - klen;
    //Log.i("loss",String.valueOf(loss));
    //rumus fibonanci
    int mt = 1;
    for (char c : this.key.toCharArray()){
      mt += this.alp.indexOf(c);
    }
    mt %= klen;
    //Log.i("loss",String.valueOf(mt));
    //END rumus fibonanci
    String temkey = this.key;
    while(temkey.length()<llen){
      temkey += this.key;
    }
    //Log.i("repeater",temkey);
    
    String holder = "";
    int tmp2;
    for(int i=0;i<loss;i++){
      
      tmp2  =  this.alp.indexOf(temkey.charAt(i))  + this.alp.indexOf(temkey.charAt(i+mt));
      tmp2 += this.alen;
      tmp2 %= this.alen;
      holder += this.alp.charAt(tmp2);
    }
    
    this.key = mixKeyword(holder);
    //Log.i("keywordFibo",this.key);
    //return this.key;
  }


Vigenere Chipper dalam Java

adalah : metode menyandikan teks alfabet
dengan menggunakan deretan sandi Caesar berdasarkan huruf-huruf pada kata kunci.

Sandi
Vigenère merupakan bentuk sederhana dari sandi substitusipolialfabetik.




Sebagai berikut coding di atas:

package lp2maray.com;

public class vc{

String enkripsi(String p,String k){
String l="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789!@#&%*()-_=:,.'?/$^ ";
    int pms=l.length();
    int pln=p.length();
    int ky=k.length();
   
        String     y =k;
        int m = pln%ky;
            for( int i=1; i<pln/ky ; i++){k=k+y;}
            k=k+k.substring(0,m);   
String c="";   
for (int j=0; j<pln; j++ ){
    char hsl=l.charAt((l.indexOf(k.charAt(j)) + l.indexOf(p.charAt(j)))%pms);
    c=c + l.charAt((l.indexOf(k.charAt(j)) + l.indexOf(p.charAt(j)))%pms);
    }
return c;
}
           
//==================================================================================
String dekripsi(String p,String k){
String l="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789!@#&%*()-_=:,.'?/$^ ";
    int pms=l.length();
    int cpr=p.length();
    int ky=k.length();
   
    String     y =k;
        int m = cpr%ky;
            for( int i=1; i<cpr/ky ; i++){k=k+y;}
            k=k+k.substring(0,m);   
String pl = "";       
for (int j=0; j<cpr; j++ ){
    char hsl=l.charAt(((l.indexOf(p.charAt(j)) - l.indexOf(k.charAt(j))) +pms )%pms);
    pl=pl + hsl;
    }   
return pl;
}
//==================================================================================   
}

Algoritma Kompressi data Huffman

IMPLEMENTASI KOMPRESI DAN ENKRIPSI DATA
DENGAN METODE HUFFMAN CODE
DALAM APLIKASI MOBILE

Riadi Marta Dinata.

Email: adiarray@yahoo.com

Abstrak
Penerapan metode kompresi pada saat pengiriman pesan teks melalui layanan SMS dapat
mengurangi biaya kirim pesan. Dua hingga tiga buah pesan dapat dikompres menjadi hanya satu pesan
sehingga biaya yang dibutuhkan untuk mengirim satu buah pesan saja. Metode kompresi yang akan digunakan adalah
Algoritma huffman
.
Pengiriman pesan akan tetap menggunakan layanan SMS sebagai sarana pengiriman dan penerimaan
pesan, sehingga otomatis juga harus ada program untuk mengkompre

PENDAHULUAN

Dengan pesatnya perkembangan teknologi seluler dan semakin maraknya persaingan di bidang seluler, maka setiap operator dan vendor seluler berlomba-lomba memberikan fasilitas yang terbaik dengan tujuan mendapatkan pelanggan sebanyak-banyaknya.
Salah satu fasilitas yang merupakan menu wajib yang disertakan oleh setiap operator seluler adalah fasilitas Short Message Service yang biasa disingkat dengan istilah SMS. SMS merupakan menu yang relatif paling dibutuhkan dan paling sering dipergunakan oleh setiap pelanggan seluler untuk menyampaikan suatu pesan, karena biaya yang digunakan lebih murah jika dibandingkan dengan langsung menelepon ke nomor tertentu.

Namun ada satu hal yang selama ini masih dilupakan oleh para operator seluler yaitu jumlah karakter per SMS sangat terbatas, hanya 160 karakter per SMS padahal biaya per SMS lumayan mahal.
Kompresi merupakan suatu hal penting dalam teknologi informasi. Proses kompresi merupakan proses untuk memperkecil bit tiap karakter sehingga memungkinkan  untuk menampung lebih dari 160 karakter untuk sekali SMS. Bahkan jika simbol-simbol tertentu tidak diikutsertakan pada penulisan SMS dan hanya menggunakan satu jenis tulisan saja, seperti penulisan SMS hanya menggunakan huruf kapital semua atau huruf kecil semua, maka SMS bisa dikompresi dengan hasil yang lebih baik, namun hal ini tergantung dengan karakter-karakter yang digunakan dalam menulis SMS. Hal ini tentu sangat menguntungkan bagi pelanggan karena selama ini jumlah karakter per SMS hanya 160 karakter.




Kode Huffman
Kode Huffman adalah algoritma yang menggunakan frekuensi/probabilitas kemunculan dari simbol pada sebuah string sebagai input dan menghasilkan output berupa prefix code yang mengkodekan string menggunakan bit paling sedikit dari seluruh kemungkinan binary prefix code yang mungkin. Algoritma ini dikembangkan oleh David A. Huffman pada paper yang ditulisnya sebagai prasyarat kelulusannya di MIT.
Kode Huffman salah satu algoritma dasar untuk kompresi data, yang bertujuan untuk mengurangi jumlah bit yang diperlukan untuk merepresentasikan informasi/pesan.

Dari Kamus atau daftar huffman yang sudah tersedia ditambahkan awalan dan diikuti dengan badannya. Untuk huruf kecil, yang harusnya sering digunakan, awalannya 0.
Sedang untuk Kurasa huruf besar digunakan  awalan 100.
Angka dan beberapa simbol diberiawalan 111, tanda baca umum 110, spasi 1011, dan khusus huruf kecil 'e' jadi 1010. Sisanya (simbol langka, Unicode lainnya), diberi awalan 1111110 diikuti kode char aslinya 16 bit. Awalan dan badan digabung, menghasilkan ubahan.



Gambar 1.1 Tabel Kamus Huffan 0, 100,  ada di atas







Gambar 1.3 Tabel Kamus Huffan 101 dan 110















Dari table yang di dapat, dimisalkan data yang akan dikompresi adalah kalimat sbb:
“HALO APA KABAR”
semuanya capital !

gambar 1.4 Scanning Karakter ke Huffam Kode












Gambar 1.5 Merubah Kode Huffan menjadi String






Gambar 1.6 Proses Dekompressi














Gambar 1.7 Proses Dekompressi












Kesimpulan
Contoh Kompressi data :
“HALO APA KABAR”
14 karakter x 8 bit = 112 bit => dikonfersi ke Huffman=>97 karakter=>13 byte
ratio: 13/14=>100%-90%=10%
Hasil kompressi akan lebih kecil lagi, jika menggunakan huruf kecil dan menghindari penggunaan huruf yang memiliki kode huffamn panjang.





sebagai berikut adalah coding masternya...silakan di modifikasi kembali untuk android, blackberry, iphone, web atau lainnya......

import java.io.PrintStream;
public class Huffman{
    public Huffman(){}
    static void init(){
        if(udahInit){return;}
        else{
            udahInit = true;
            cc[32] = "1011";
            cc[33] = "1100011";
            cc[34] = "1100110";
            cc[39] = "1100100";
            cc[40] = "11111010";
            cc[41] = "11111011";
            cc[44] = "1100001";
            cc[45] = "1100101";
            cc[46] = "1100000";
            cc[47] = "1111011";
            cc[48] = "1110000";
            cc[49] = "1110001";
            cc[50] = "1110010";
            cc[51] = "1110011";
            cc[52] = "1110100";
            cc[53] = "1110101";
            cc[54] = "1110110";
            cc[55] = "1110111";
            cc[56] = "1111000";
            cc[57] = "1111001";
            cc[58] = "1111100";
            cc[63] = "1100010";
            cc[64] = "1111010";
            cc[65] = "1000000";
            cc[66] = "10000101";
            cc[67] = "1001101";
            cc[68] = "10001011";
            cc[69] = "1100111";
            cc[70] = "10011001";
            cc[71] = "10010101";
            cc[72] = "1001000";
            cc[73] = "1000001";
            cc[74] = "100110001001";
            cc[75] = "1001100011";
            cc[76] = "1001001";
            cc[77] = "10010100";
            cc[78] = "1000110";
            cc[79] = "1000100";
            cc[80] = "10010110";
            cc[81] = "1001100010000";
            cc[82] = "1000111";
            cc[83] = "1000011";
            cc[84] = "100111";
            cc[85] = "10010111";
            cc[86] = "1000101001";
            cc[87] = "1000101000";
            cc[88] = "10011000101";
            cc[89] = "10000100";
            cc[90] = "1001100010001";
            cc[97] = "00000";
            cc[98] = "000101";
            cc[99] = "01101";
            cc[100] = "001011";
            cc[101] = "1010";
            cc[102] = "011001";
            cc[103] = "010101";
            cc[104] = "01000";
            cc[105] = "00001";
            cc[106] = "0110001001";
            cc[107] = "01100011";
            cc[108] = "01001";
            cc[109] = "010100";
            cc[110] = "00110";
            cc[111] = "00100";
            cc[112] = "010110";
            cc[113] = "01100010000";
            cc[114] = "00111";
            cc[115] = "00011";
            cc[116] = "0111";
            cc[117] = "010111";
            cc[118] = "00101001";
            cc[119] = "00101000";
            cc[120] = "011000101";
            cc[121] = "000100";
            cc[122] = "01100010001";
            return;
        }
    }

    static String huffmanSisanya(char kar){
        String s = Integer.toBinaryString(kar);
        s = "0000000000000000".substring(0, 16 - s.length()) + s;
        return ccSISANYA + s;
    }

    static byte[] stringKeByteA(String st){
        int lenAsli = st.length();
        st = st + "11111111";
        byte hs[] = new byte[(lenAsli + 7) / 8];
        for(int i = 0; i < lenAsli; i += 8)
        {
            String sebyte = st.substring(i, i + 8);
            byte b = (byte)Integer.parseInt(sebyte, 2);
            hs[i / 8] = b;
        }

        return hs;
    }

    static String byteAKeString(byte ba[]){
        String hs = "";
        for(int i = 0; i < ba.length; i++){
            int b = ba[i];
            if(b < 0)
                b += 256;
            String tp = Integer.toBinaryString(b);
            tp = "00000000".substring(0, 8 - tp.length()) + tp;
            hs = hs + tp;
        }

        return hs;
    }

    public static byte[] huffman(String st){
        init();
        String jadi = "";
        for(int i = 0; i < st.length(); i++)
        {
            char kar = st.charAt(i);
            if(kar >= '\200')
                jadi = jadi + huffmanSisanya(kar);
            else
            if(cc[kar] != null)
                jadi = jadi + cc[kar];
            else
                jadi = jadi + huffmanSisanya(kar);
        }

        return stringKeByteA(jadi);
    }

    static int cariKar(String buf)
    {
        if(buf.length() > 23)
            return -2;
        if(buf.length() == 23 && buf.substring(0, 7).equals(ccSISANYA))
            return Integer.parseInt(buf.substring(7), 2);
        for(int i = 0; i < 128; i++)
            if(cc[i] != null && cc[i].equals(buf))
                return i;

        return -1;
    }

    public static String dehuffman(byte ba[])
    {
        init();
        String st = byteAKeString(ba);
        String hs = "";
        String buf = "";
        for(int i = 0; i < st.length(); i++)
        {
            char kar = st.charAt(i);
            buf = buf + kar;
            int c = cariKar(buf);
            if(c >= 0)
            {
                buf = "";
                hs = hs + (char)c;
            } else
            if(c == -2)
                buf = "";
        }

        return hs;
    }



}




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 &lt; 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);
 }
 }