Pengenalan Algoritma RSA

Algoritma RSA :
---------------

Key generation :

1. Hasilkan dua buah integer prima besar, p dan q
   Untuk memperoleh tingkat keamanan yang tinggi pilih p dan q 
   yang berukuran  besar, misalnya 1024 bit.
2. Hitung m = (p-1)*(q-1)
3. Hitung n = p*q
4. Pilih d yg relatively prime terhadap m 
   e relatively prime thd m artinya faktor pembagi terbesar keduanya 
   adalah 1, secara matematis disebut gcd(e,m) = 1. Untuk mencarinya 
   dapat digunakan algoritma Euclid.
5. Cari d, sehingga e*d = 1 mod (m), atau d = (1+nm)/e
   Untuk bilangan besar, dapat digunakan algoritma extended Euclid.
6. Kunci publik  : e, n
   Kunci private : d, n


Public key encryption

B mengenkripsi message M untuk A

Yg harus dilakukan B :
  1. Ambil kunci publik A yg otentik (n, e)
  2. Representasikan message sbg integer M dalam interval [0,n-1]
  3. Hitung C = M ^ e (mod n)
  4. Kirim C ke A

Untuk mendekripsi, A melakukan :
  Gunakan kunci pribadi d untuk menghasilkan M = C^(d)  (mod n)


Contoh Penerapan :
------------------

Misalkan :
Di sini saya pilih bilangan yg kecil agar memudahkan perhitungan, 
namun dalam aplikasi nyata pilih bilangan prima besar untuk 
meningkatkan keamanan.
 
p = 3
q = 11

n = 3 * 11 = 33
m = (3-1) * (11-1) = 20

e = 2 => gcd(e, 20) = 2
e = 3 => gcd(e, 20) = 1 (yes)

n = 0 => e = 1 / 3
n = 1 => e = 21 / 3 = 7 (yes)


Public key  : (3, 33)
Private key : (7, 33)


Let's check the math using numbers
----------------------------------

* Try encryption : message "2"

  C = 2 ^ 3 (mod 33)
    = 8

  Try to decrypt : ciphertext "8"

  M = 8 ^ 7 (mod 33)
    = 2097152 (mod 33)
    = 2

** Encrypt : message " " (ASCII=20)

  C = 20 ^ 3 (mod 33)
    = 8000 (mod 33)
    = 14

  Decrypt : ciphertext 32 
  
  M = 14 ^ 7 (mod 33)
    = 105413504 (mod 33)
    = 20


Make as many as software using this RSA algorithm.