Lebih jauh, RSA adalah algoritma yang mudah untuk diimplementasikan dan dimengerti. Algoritma RSA adalah sebuah aplikasi dari sekian banyak teori seperti extended euclid algorithm, euler's function sampai fermat theorem.
Artikel ini menjelaskan algoritma RSA dari dasar. Saya akan menggunakan nilai-nilai yang kecil untuk menjelaskan bagaimana cara kerja algoritma RSA.
----| Public-Key Cryptography
Konsep fundamental dari Public-Key Cryptography ditemukan oleh Whitfield
Diffie dan Martin Hellman, dan secara terpisah oleh Ralph Merkle.
Sedangkan konsep dasar Public-Key Cryptography terletak pada pemahaman
bahwa keys selalu berpasangan: encryption key dan decryption key. Juga perlu
diingat bahwa sebuah key tidak dapat digenerate dari key lainnya. Pemahaman
encryption dan decryption key sering disebut sebagai public dan private key.
Seseorang harus memberikan public key-nya agar pihak lain dapat meng-encrypt
sebuah pesan. Decryption hanya terjadi jika seseorang mempunyai private key.
----| Scenario
Bagian ini menjelaskan skenario bagaimana public-key cryptosystem bekerja.
Saya akan menggunakan partisipan klasik Alice dan Bob sebagai orang-orang
yang melakukan pertukaran informasi.
1. Alice dan Bob setuju untuk menggunakan public-key cryptosystem.
2. Bob mengirimkan public key-nya kepada Alice.
3. Alice meng-encrypt pesan yang dibuatkan dengan menggunakan public
key milik Bob dan mengirimkan pesan yang sudah di-encrypt kepada
Bob.
4. Bob men-decrypt pesan dari Alice menggunakan private key
miliknya.
------| Mathematical Notation
Untuk memahami algoritma RSA, seseorang harus memahami beberapa notasi
matematika dasar, teori dan formula. Hal tersebut dibutuhkan untuk mendukung
semua kalkulasi yang dilakukan dalam algoritma RSA.
1. Modulo (didenotasikan dengan 'x mod m' atau 'x % m' dalam beberapa
bahasa komputer)
- x % m = x mod m = pembagian x dengan m dan mengambil sisanya.
- Contoh: 25 mod 5 = 0 karena 5 habis membagi 25
25 mod 4 = 1 karena 25 / ( 4 * 6 ) menyisakan 1
x mod m = x jika dan hanya jika x < m
2. Z/mZ
- Z/7Z : { 0,1,2,3,4,5,6 } dimana [7]=[0], [8]=[1], [9]=[2] dan seterusnya.
- Operasi yang didukung dalam Z/mZ aalah penjumlahan, pengurangan, pembagian dan perkalian.
- Inverse: Sebuah elemen dalam Z/mZ seperti A, memiliki sebuah inverse B jika dan hanya jika [A]x[B] = [1]
- Units: Setiap elemen dalam Z/mZ yang memiliki inverse adalah sebuah unit.
- Contoh: Z/7Z
Penjumlahan: [2]+[3] = [5] ; [5]+[5] = [10] ... [10-7] = [3]
Pengurangan: [2]-[3] = [-1] = [6] ; [6]-[4] = [2]
Pembagian : [6]/[2] = [3] ; [6]/[4] = [5] ([4]x[5] = [20] = [6])
Perkalian : [2]x[6] = [12] = [5] ;
Soal: [6]/[4]
a. Tempatkan dalam formula [6] = [X][4]
b. Cari inverse dari [4], yaitu [2] ... [4]x[2] = [8] = [1]
c. Kali inverse dengan [6] ... [2]x[6] = [12] = [5]
d. Sehingga [4]x[5] = [20] = [13] = [6]
3. GCD(A,B)
GCD = greatest common divisor.
GCD(A,B) = D
GCD(78,32) = 2, karena tidak ada bilangan yang lebih besar dari dua yang membagi 78 dan 32.
GCD(A,B) dapat ditemukan dengan menggunakan algoritma extended euclid.
Jika GCD(A,B) = 1 maka A and B dalah coprime satu sama lainnya (dengan kata lain, A dan B adalah relatively prime).
4. Memecahkan 8x mod 13 = 1, dimana x adalah bilangan yang belum diketahui.
- Cari gcd(8,13) yang berarti 1 ... yang berarti persamaan dapat diselesaikan.
- Membuat sebuah matriks dan menggunakan operasi gaussian dalam matriks.
8 | 1 0 r2=r2-r1 8 | 1 0 r1=r1-r2
13 | 0 1 ---------> 5 | -1 1 --------->
3 | 2 -1 r2=r2-r1 3 | 2 -1
5 | -1 1 ---------> 2 |-3 2
lakukan sampai kita mendapatkan format : 1 | s t 0 | s' t'
s, t, s', t' dapat berupa bilangan apa saja.
Jika hasil akhir yang di dapat sbb: 0 | s' t' , kita harus 1 | s t
rotasi atas-bawah hasil nya menjadi format: 1 | s t 0 | s' t'
sehingga sekarang kita mendapatkan d = 1, s = 5, t = -3, sehingga x = s = 5.
5. Euler's phi function (jangan sampai keliru dengan phi = 3.14)
- Euler's phi function adalah sebuah total bilangan unit dalam Z/mZ
- Theorem
a. Jika p adalah sebuah bilangan prima, maka phi(p) = p - 1 p dan phi(p) adalah (contoh: gcd(p,phi(p)) = 1)
ii): phi(m*n) = phi(m) * phi (n)
phi(p^a) = (p^a) - p^(a-1)
b. Contoh:
-- phi(7) = 6
-- phi(840) = phi(8) * phi(105) = phi(2^3) * phi(3*5*7)
= [(2^3) - (2^2)] * phi(3) * phi(5) * phi(7)
6. Pangkat. pow(a,b)
Saya akan menggunakan notasi '^' seperti pada a^b
----| Key Generation
Misalkan Alice ingin Bob mengirimnya sebuah pesan melalui jalur yang aman. Alice akan memberikan public keynya kepada Bob dan menyimpan private key untuk dirinya.
a. Pilih 2 bilangan prima besar seperti p,q dimana p tidak sama dengan q.
b. Hitung M = p x q
c. Hitung phi(M) = phi(p) * phi(q)
d. Pilih sebuah integer 'e' dimana 1 < e < phi(M) dan 'e' serta phi(M) adalah coprime.
e. Hitung 'd' integer sehingga (d * e) mod M = 1
f. (M,e) adalah public key dimana M adalah modulo dan e adalah eksponen encryption.
g. (M,d) adalah private key dimana M adalah modulo dan d adalah eksponen decryption.
----| Encrypting Message
Misalkan Bob ingin mengirim sebuah pesan 'H' kepada Alice.
a. Alice harus membuat keynya; sehingga ia memiliki private dan public keys.
private key = (M,d)
public key = (M,e)
b. Mengubah 'H' menjadi sebuah bilangan yang menggunakan alphabet yang valid dengan tabel bilangan. Sebuah contoh mudah adalah mapping A = 1, B = 2 ... Z = 26.
sehingga H = 8
c. C = 8^e (mod M)
C adalah sebuah bilangan ter-encrypt.
d. Bob mengirimkan bilangan tersebut kepada Alice sehingga Alice dapat melakukan decode ulang menggunakan private keynya.
------| Decrypting Message
Misalkan Alice menerima sebuah pesan ter-encrypt, ia akan men-decrypt-nya menggunakan tahapan-tahapan berikut:
a. Alice mempunyai private key dari langkah-langkah di atas (M,d)
b. N = C^d (mod M)
c. N adalah bilangan. Gunakan konversi table alphabet untuk mengubah N menjadi karakter yang direpresentasikannya.
----| Example
a. Generate Key (kita dapat melewati langkah ini untuk menemukan p dan q)
1. M = 101 , sebuah bilangan prima --> phi(M) = 100
2) a] Misalkan e = 13
b] Cari d (e*d) mod M = 1 Gunakan persamaan (a*x) mod M = 1
d = 77
b. Kata "HELLO" digunakan sebagai pesan, dan diubah menurut numerical representation-nya.
HELLO = 08 05 12 12 15
c. Encoding pesan.
8^13 mod 101 = 18
5^13 mod 101 = 56
12^13 mod 101 = 53
15^13 mod 101 = 7
Sehingga pesan ter-encrypt atau ciphertext adalah 18,56,53,53,07.
d. Decoding pesan.
18^77 mod 101 = x1
56^77 mod 101 = x2
53^77 mod 101 = x3 = x4
07^77 mod 101 = x5
------| Closure
RSA merupakan contoh yang powerful dan cukup aman dari Public-Key Cryptography. Berdasarkan matematika, proses yang digunakan berdasarkan fungsi-fungsi trap-door satu arah. Sehingga melakukan encryption dengan menggunakan public key sangat mudah bagi semua orang, namun proses decryption menjadi sangat sulit.
Proses decryption sengaja dibuat sulit agar seseorang, walaupun menggunakan Cray supercomputers dan ribuan tahun, tidak dapat men-decrypt pesan tanpa mempunyai private key.
Perlu diingat juga bahwa pemilihan p*q = M haruslah sebuah bilangan yang sangat besar sehingga sulit dicari eksponen decoding-nya karena sulit melakukan pemfaktoran bilangan prima.
------| Reference
[1] Childs, Lindsay N. A Concrete Introduction to Higher Algebra.
Undergraduate Texts in Mathematics. Springer-Verlaag: New York,
2000.
[2] Schneier, B. Applied Cryptography, 2nd Ed. John Wiley & Sons, Inc:
Canada, 1996.
[3] Rivest R.L., Shamir A., Adleman L. "A Method for Obtaining Digital
Signatures and Public-Key Cryptosystems. MIT: Massachusetts. 1977.
download simulator dan panduannya. http://www.mediafire.com/?2zxg1etdr2dxppc
thanks to by duniasantai.com
