Feeds:
Posts
Comments

Archive for November 22nd, 2006

RSA Public Key Encryption

Algoritma RSA merupakan algoritma kunci publik yang dibuat oleh Ron Rivest, Adi Shamir dan Leonard Adleman. Berikut merupakan perhitungan matematika dibalik enkripsi kunci publik RSA :

  1. Pilih P dan Q, dua bilangan prima besar
  2. Pilih E dimana E lebih besar dari 1, E adalah kurang dari PQ dan E relatif prima terhadap (P-1)(Q-1) (tidak memiliki faktor prima yang sama). E tidak harus prima tetapi harus ganjil.  (P-1)(Q-1) tidak dapat prima karena merupakan bilangan genap.
  3. Hitung D dimana (DE-1) dibagi sempurna oleh (P-1)(Q-1). Ahli matematika menuliskan sebagai DE = 1 (mod(P-1)(Q-1)) dan mereka menyebut D multiplicative inverse dari E. Lebih mudahnya pilih integer X yang menghasilkan D = (X(P-1)(Q-1)+1)/E yang menghasilkan bilangan integer (bulat), gunakan nilai D.
  4. Fungsi Enkripsi adalah C = (T^E) mod PQ, dimana C adalah ciphertext (positive integer), T adalah plaintext (positive integer), dan ^ menunjukkan pangkat. Message yang dienkripsi, T, harus lebih kecil dari modulus PQ.
  5. Fungsi Dekripsi adalah T = (C^D) mod PQ, dimana C adalah ciphertext (positive integer), T adalah plaintext (positive integer), dan ^ menunjukkan pangkat.


Public key adalah pasangan (PQ, E).

Private key adalah D.

Perkalian PQ adalah modulus (biasa disebut N dalam literatur).

E adalah public exponent. D adalah secret exponent.

 

Public key dapat dipublikasikan, karena tidak ada metode yang mudah untuk menghitung D,P, atau Q bila yang diberikan hanya (PQ, E).

Jika P dan Q masing-masing 1024 bit, susah dan membutuhkan waktu yang sangat lama untuk dapat memfaktorkan modulus menjadi P dan Q.

 Contoh :

 P  = 61

Q  = 53

PQ = 3233

E  = 17

D  = 2753

 
Public Key adalah (E, PQ)

Private Key adalah D

 Enkripsi :

 encrypt(T) = (T^E) mod PQ

                     = (T^17) mod 3233

 encrypt(123) = (123^17) mod 3233

                         = 337587917446653715596592958817679803 mod 3233

                         = 855

 

Dekripsi :

 decrypt(C) = (C^D) mod PQ

                     = (C^2753) mod 3233

 

 decrypt(855) = (855^2753) mod 3233

                         = 123

 

Satu cara untuk menghitung nilai 855^2753 mod 3233 adalah sebagai berikut:

 2753 = 101011000001 basis 2, kemudian

             2753 = 1 + 2^6 + 2^7 + 2^9 + 2^11

                     = 1 + 64  + 128 + 512 + 2048

 
Tabel Perpangkatan dari 855:

             855^1 = 855 (mod 3233)

            855^2 = 367 (mod 3233)

            855^4 = 367^2 (mod 3233) = 2136 (mod 3233)

            855^8 = 2136^2 (mod 3233) = 733 (mod 3233)

            855^16 = 733^2 (mod 3233) = 611 (mod 3233)

            855^32 = 611^2 (mod 3233) = 1526 (mod 3233)

            855^64 = 1526^2 (mod 3233) = 916 (mod 3233)

            855^128 = 916^2 (mod 3233) = 1709 (mod 3233)

            855^256 = 1709^2 (mod 3233) = 1282 (mod 3233)

            855^512 = 1282^2 (mod 3233) = 1160 (mod 3233)

            855^1024 = 1160^2 (mod 3233) = 672 (mod 3233)

            855^2048 = 672^2 (mod 3233) = 2197 (mod 3233)

 
Berdasarkan tabel perhitungan tersebut diatas, diperoleh:

             855^2753 (mod 3233)

            = 855^(1 + 64  + 128 + 512 + 2048) (mod 3233)

            = 855^1 * 855^64 * 855^128 * 855^512 * 855^2048 (mod 3233)

            = 855 * 916 * 1709 * 1160 * 2197 (mod 3233)

            = 794 * 1709 * 1160 * 2197 (mod 3233)

            = 2319 * 1160 * 2197 (mod 3233)

            = 184 * 2197 (mod 3233)

            = 123 (mod 3233)

            = 123

Read Full Post »