KRIPTOGRAFI RSA

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. RSA adalah salah satu teknik kriptografi dimana kunci untuk melakukan enkripsi berbeda dengan kunci untuk melakukan dekripsi. Kunci untuk melakukan enkripsi disebut sebagai kunci publik, sedangkan kunci untuk melakukan dekripsi disebut sebagai kunci privat. Orang yang mempunyai kunci publik dapat melakukan enkripsi tetapi yang dalam melakukan dekripsi hanyalah orang yang memiliki kunci privat. Kunci publik dapat dimiliki oleh sembarang orang, tetapi kunci privat hanya dimiliki oleh orang tertentu saja.

Besaran-besaran yang digunakan pada algoritma RSA:

1.  p dan q bilangan prima                            (rahasia)

2.  n = p × q                                                   (tidak rahasia)

3.  m = (p – 1)(q – 1)                                     (rahasia)

4.  e     (kunci enkripsi)                                 (tidak rahasia)

5.  d     (kunci dekripsi)                                 (rahasia)

6.  P     (plainteks)                                         (rahasia)

7.  C    (cipherteks)                                        (tidak rahasia)    

Untuk pembangkitan pasangan kunci RSA, digunakan algoritma sebagai berikut: 

1. Dipilih dua buah bilangan prima sembarang yang besar, p dan q.

2. Dihitung n = p x q.. 

3. Dihitung m = (p – 1)(q – 1).

4. Dipilih sebuah bilangan bulat sebagai kunci publik, disebut namanya e, e relatif prima terhadap m artinya faktor pembagi terbesar keduanya adalah 1,

secara matematis disebut FPB (e,m) = 1. Untuk mencarinya dapat digunakan algoritma Euclid.

5. Dihitung kunci privat, disebut namanya d sedemikian agar (d x e) mod m = 1.

Untuk mencari nilai d yang sesuai dapat juga digunakan algoritma Extended Euclid.

Maka hasil dari algoritma tersebut diperoleh : 

• Kunci publik adalah pasangan (e,n). Bersifat tidak rahasia. 

• Kunci private adalah pasangan (d,n). Bersifat rahasia.

Algoritma Enkripsi/Dekripsi 

Enkripsi 

1.  Ambil kunci publik penerima pesan, e, dan n

2.  Nyatakan plainteks P menjadi blok-blok P1, P2, …, sedemikian sehingga setiap blok merepresentasikan nilai di dalam selang [0, n – 1]

Setiap blok Mi dienkripsi menjadi blok Ci dengan rumus Ci = Pi ^ e mod n

Dekripsi 

Setiap blok cipherteks Ci didekripsi kembali menjadi blok Pi dengan rumus Pi = Ci ^ d mod n

Algoritma Euclid

Algoritma ini mencari FPB dengan cara melakukan pembagian berulang-ulang dimulai dari kedua bilangan yang hendak kita cari FPBnya sampai kita mendapatkan sisa 0 dari hasil pembagian.

Marilah kita lihat contoh yang lain, cari FPB dari 40 dan 64 :

• 64 ÷ 40 = 1 dengan sisa 24 

• 40 ÷ 24 = 1 dengan sisa 16 

• 24 ÷ 16 = 1 dengan sisa 8 

• 16 ÷ 8 = 2 dengan sisa 0.

Kita berhenti di sini sebab kita sudah mendapat sisa 0. Bilangan terakhir yang kita gunakan untuk membagi adalah 8, jadi FPB dari 40 dan 64 adalah 8 

Contoh RSA Sederhana 

1.  p = 47 dan q = 71 (keduanya prima). 
2. n = p ⋅ q = 3337 
3. m = (p – 1)(q – 1) = 3220 
4. Pilih e yg relativ prime terhadap m,
   FPB (e,m) = 1.
   e = 79 => FPB (79, 3337) = 1 
5. Cari nilai d
   d*e = 1 mod (m) 
   d*79 = 1 mod 3220
   d*79 mod 3220 = 1
   d = 1019

Sehingga didapatkan : 

Public key : (79, 3337) 

Private key : (1019, 3337) 

Proses Enkripsi

Setelah didapat perhitungan di atas, maka akan dilakukan enkripsi plaintext P = AKU. Pertama-tama plaintext tersebut diubah menjadi format ASCII sebagai berikut : 

Karakter          A                K           U 

ASCII             65               75          85 

P1 = 657 P2 = 585

Setelah dibagi perblock, maka akan dihitung menggunakan rumus  Ci  = Pi ^ e mod n

• C1 = 657 ^ 79 mod 3337 = 2349 

• C2 = 585 ^ 79 mod 3337 = 685 

Maka, chipertext yang didapatkan adalah C = 320328

Proses Dekripsi

Setelah chipertext dari kata AKU didapat, untuk mengubahnya kembali jadi plaintext menggunakan dekripsi dengan rumus   Pi = Ci ^ d mod n

• P1 = 2349 ^ 1019 mod 3337 = 657 

• P2 = 685 ^ 1019 mod 3337 = 585   

Maka, setelah di dekripsi hasilnya akan sama. Yaitu 657585.

Kekuatan dan Keamanan RSA

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

Kekuatan algoritma RSA terletak pada tingkat kesulitan dalam memfaktorkan bilangan menjadi faktor primanya, dalam hal ini memfaktorkan n menjadi p dan q. Karena sekali n berhasil difaktorkan, maka menghitung nilai m adalah perkara mudah. Selanjutnya, walau nilai e diumumkan, perhitungan kunci d tidaklah mudah pula karena nilai m yang tidak diketahui. Kelebihan lain algoritma RSA terletak pada ketahanannya terhadap berbagai bentuk serangan, terutama serangan brute force. Hal ini dikarenakan kompleksitas dekripsinya yang dapat ditentukan secara dinamis dengan cara menentukan nilai p dan q yang besar pada saat proses pembangitkan pasangan kunci, sehingga dihasilakan sebuah key space yang cukup besar, sehingga tahan terhadap serangan.

SEMOGA BERMANFAAT :):):)

Read More

PERMUTASI DES

       DES termasuk ke dalam sistem kriptografi simetri dan tergolong jenis cipher blok. DES beroperasi pada ukuran blok 64 bit. DES mengenkripsikan 64 bit plainteks menjadi 64 bit cipherteks dengan menggunakan 56 bit kunci internal (internal key). Kunci internal dibangkitkan dari kunci eksternal (external key) yang panjangnya 64 bit.

       Algoritma DES dikembangkan di IBM dibawah kepemimpinan W.L. Tuchman pada tahun 1972.  Algoritma ini didasarkan pada algoritma LUCIFER yang dibuat oleh Horst Feistel dan telah disetujui oleh National Bureau of Standard (NBS) setelah penilaian kekuatannya oleh National Security Agency (NSA) Amerika Serikat.

Pertama yang harus kita ketahui dari algoritma ini adalah Skema global yang ada pada algoritma DES, diuraikan sebagai berikut.

a. Blok plainteks dipermutasi dengan permutasi awal (IP, Initial Permutation).

b. Hasil permutasi awal kemudian dienciphering sebanyak 16 kali (16 putaran). Setiap putaran menggunakan kunci internal yang berbeda dengan perhitungan Li  dan  Ri dengan 1 ≤ i ≤ 16.

c. Hasil enciphering kemudian dipermutasi dengan matriks permutasi balikan (invers initial permutation atau IP-1) menjadi blok cipherteks.

Permutasi Awal (Initial Permutation)

Sebelum putaran pertama, terhadap blok plainteks dilakukan permutasi awal (Initial Permutation atau IP). Tujuan permutasi awal adalah mengacak plainteks sehingga urutan-bit-bit di dalamnya berubah. Lihat pada gambar dibawah, Matriks pada Tabel (a) sebagai plainteks masukan, kemudian dilakukan pengacakan dengan menggunakan matriks permutasi awal Tabel (b):

Cara membaca tabel/matriks: dua entry ujung kiri atas (58 dan 50) artinya:

"letakkan  bit ke-58 ke posisi bit 1"

"letakkan bit ke-50 ke posisi bit 2", dst

Kemudian plainteks yang akan disandikan kemudian dibagi menjadi dua blok (ditunjukkan dengan warna yang berbeda pada Tabel (b)), yaitu blok atas menghasilkan  L0  dan blok bawah menghasilkan  R0  yang masing‐masing lebarnya 4 byte (32-bit).

Pembangkitan Kunci Internal DES

Pada langkah ini dibutuhkan kunci internal sebanyak 16 buah, yaitu K1, K2,…,K16. Kunci-kunci internal ini dapat dibangkitkan sebelum proses enkripsi atau bersamaan dengan proses enkripsi. Kunci internal dibangkitkan dari kunci eksternal yang diberikan oleh pengguna. Kunci eksternal pada DES panjangnya 64-bit atau 8 karakter seperti dibawah.

                      

Dalam permutasi ini, tiap bit kedelapan (parity bit) dari delapan byte kunci diabaikan. Hasil permutasinya adalah sepanjang 56 bit, lalu 56 bit ini dibagi menjadi 2 bagian, masing-masing nanjangnya 28 bit, yang disimpan di dalam  C0 ( dari tabel bagian gelap ) dan D0 ( dari tabel bagian putih ) .

Selanjutnya, kedua bagian digeser ke kiri (left shift) sepanjang satu atau dua-bit bergantung pada tiap putaran. Jumlah pergeseran pada tiap putaran ditunjukkan pada tabel dibawah. Misalkan (Ci, Di) menyatakan penggabungan Ci dan Di. (Ci-1, Di-1) diperoleh dengan menggeser Ci dan Di satu atau dua-bit.

Putaran ke - i	Jumlah Pergeseran(Left Shift)
1	1
2	1
3	2
4	2
5	2
6	2
7	2
8	2
9	1
10	2
11	2
12	2
13	2
14	2
15	2
16	1

Dengan permutasi ini, kunci internal Ki diturunkan dari (Ci, Di) yang dalam hal ini Ki merupakan panggabungan-bit-bit Ci pada sisi gelap tabel (f), dengan-bit-bit Di pada sisi putih tabel (f). Setiap kunci internal Ki mempunyai panjang 48-bit. Proses Pembangkitan kunci-kunci internal dapat dilakukan dengan mengikuti tabel berikut ini. Sesuai dengan C1-C16 dan D1-D16 maka K juga akan dihasilkan sampai K16.

Proses Enkripsi DES

Setiap putaran enkripsi DES secara matematis dinyatakan sebagai :

Untuk menemukan R1 sampai R16 kita harus melakukan langkah-langkah sebagai berikut.

Langkah pertama yaitu kita akan melakukan ekspansi terhadap Ri sesuai dengan tabel dibawah ini.

Fungsi ekspansi yang memperluas blok Ri 32-bit menjadi blok 48-bit. Fungsi ekspansi direalisasikan dengan matriks permutasi ekspansi disamping.

Hasil ekpansi E(Ri) kemudian di-XOR-kan dengan Ki menghasilkan vektor A 48-bit.
Matriks A dikelompokkan menjadi 8 kelompok, masing-masing 6-bit, dan menjadi masukan bagi proses substitusi. Proses substitusi dilakukan dengan menggunakan delapan buah kotak-S (S-box), S1 sampai S8. Setiap kotak-S menerima masukan 6-bit dan menghasilkan keluaran 4-bit. Kelompok 6-bit pertama menggunakan S1, kelompok 6-bit kedua menggunakan S2, dan seterusnya. Kedelapan kotak-S tersebut ditunjukkan pada tabel sebagai berikut.

 

Setelah itu hasil dari substitusi yang dibagi menjadi 8 kelompok tadi digabungkan kembali menjadi vektor B yang panjangnya 32-bit. Vektor B menjadi masukan untuk proses permutasi. Tujuan permutasi adalah untuk mengacak hasil proses substitusi kotak-S. Permutasi dilakukan dengan menggunakan matriks permutasi P (P-box) sesuai tabel berikut.

 
Bit-bit P(B) merupakan keluaran dari fungsi f.


                      Akhirnya, bit-bit P(B) di-XOR-kan dengan Li–1 untuk  

mendapatkan Ri

Permutasi Akhir (Invers Inisial Permutasi)

Permutasi terakhir dilakukan setelah 16 kali putaran terhadap gabungan blok kiri dan blok kanan. Setelah dilakukan proses dengan langkah-langkah diatas dan dihasilkan R16 dan L16. Selanjutnya bit-bit dari R16 dan L16 tersebut digabungkan sehingga memiliki panjang 64 bit. Permutasi menggunakan matriks permutasi awal balikan (IP-1 ) sebagai berikut.

Kemudian  bit-bit tersebut dibagi menjadi 2 dan dikelompokkan per 8 bit. Dari kelompok bit tersebut akan menghasilkan 8 urutan (berisi 8bit tadi) yang akan menjadi huruf maupun angka dari hasil enkripsi  setelah diterjemahkan dalam tabel ASCII.
 

LATIHAN 

 
SEMOGA BERMANFAAT :):):)

Read More