tutorial RSA
azis nurdiansyah
Oktober 31, 2018
Sejarah RSA
Algortima RSA dijabarkan pada tahun 1977 oleh tiga
orang : Ron Rivest, Adi Shamir dan Len Adleman dari Massachusetts Institute
of Technology. Huruf RSA itu sendiri berasal dari inisial
nama mereka (Rivest—Shamir—Adleman).
Clifford Cocks, seorang
matematikawan Inggris yang bekerja untuk GCHQ, menjabarkan tentang
sistem ekuivalen pada dokumen internal pada tahun 1973. Penemuan Clifford
Cocks tidak terungkap hingga tahun 1997 karena
alasan top-secret classification.
Algoritme tersebut dipatenkan oleh Massachusetts Institute of
Technology pada tahun 1983 di Amerika Serikat sebagai U.S. Patent 4.405.829. Paten tersebut
berlaku hingga 21 September 2000. Semenjak Algoritme
RSA dipublikasikan sebagai aplikasi paten, regulasi di sebagian besar
negara-negara lain tidak memungkinkan penggunaan paten. Hal ini menyebabkan
hasil temuan Clifford Cocks di kenal secara umum, paten di Amerika Serikat
tidak dapat mematenkannya.
Operasional
Pembuatan Kunci
Semisal Alice
berkeinginan untuk mengizinkan Bob untuk mengirimkan kepadanya sebuah pesan
pribadi (private message) melalui media transmisi yang tidak aman (insecure).
Alice melakukan langkah-langkah berikut untuk membuat pasangan kunci public key dan private key:
1. Pilih dua bilangan prima p ≠ q secara acak dan terpisah untuk
tiap-tiap p dan q.
Hitung N = p
q. N hasil perkalian dari p dikalikan dengan q.
2. Hitung φ = (p-1)(q-1).
3. Pilih bilangan bulat (integer) antara satu dan φ (1 < e < φ) yang juga merupakan koprima dari φ.
4. Hitung d hingga d e ≡ 1 (mod φ).
·
bilangan
prima dapat diuji probabilitasnya menggunakan Fermat's little theorem-
a^(n-1) mod n = 1 jika n adalah bilangan prima, diuji dengan beberapa nilai a
menghasilkan kemungkinan yang tinggi bahwa n ialah bilangan prima. Carmichael numbers (angka-angka Carmichael) dapat melalui
pengujian dari seluruh a, tetapi hal ini sangatlah langka.
·
langkah
3 dan 4 dapat dihasilkan dengan algoritme extended
Euclidean; lihat juga aritmetika
modular.
·
langkah
4 dapat dihasilkan dengan menemukan integer x sehingga d = (x(p-1)(q-1) +
1)/e menghasilkan bilangan
bulat, kemudian menggunakan nilai dari d (mod (p-1)(q-1));
·
langkah
2 PKCS#1 v2.1 menggunakan &lamda; = lcm(p-1, q-1) selain daripada φ = (p-1)(q-1)).
Pada public key terdiri atas:
·
N, modulus yang digunakan.
·
e, eksponen publik (sering juga disebut eksponen enkripsi).
Pada private key terdiri atas:
·
N, modulus yang digunakan, digunakan pula pada public key.
·
d, eksponen pribadi (sering juga disebut eksponen dekripsi), yang
harus dijaga kerahasiaannya.
Biasanya,
berbeda dari bentuk private
key (termasuk parameter CRT):
·
p dan q,
bilangan prima dari pembangkitan kunci.
·
d mod
(p-1) dan d mod (q-1) (dikenal sebagai dmp1 dan dmq1).
·
(1/q)
mod p (dikenal sebagai iqmp).
Bentuk ini
membuat proses dekripsi lebih cepat dan signing menggunakan Chinese Remainder Theorem (CRT). Dalam bentuk ini, seluruh bagian dari private key harus dijaga kerahasiaannya.
Alice
mengirimkan public key kepada Bob, dan tetap merahasiakan private key yang digunakan. p dan q sangat sensitif dikarenakan merupakan
faktorial dari N, dan
membuat perhitungan dari d menghasilkan e. Jika p dan q tidak disimpan dalam bentuk CRT dari private key, maka p dan q telah terhapus bersama nilai-nilai
lain dari proses pembangkitan kunci.
Proses enkripsi pesan
Misalkan Bob ingin mengirim pesan m ke Alice. Bob mengubah m menjadi angka n < N, menggunakan protokol yang sebelumnya telah disepakati dan dikenal sebagai padding schame.
Maka Bob memiliki n dan mengetahui N dan e, yang telah diumumkan oleh Alice. Bob kemudian menghitung ciphertext c yang terkait pada n:
Perhitungan tersebut dapat diselesaikan dengan cepat menggunakan metode exponentiation by squaring. Bob kemudian mengirimkan c kepada Alice.
Proses dekripsi pesan
Alice menerima c dari Bob, dan mengetahui private key yang digunakan oleh Alice sendiri. Alice kemudian memulihkan n dari c dengan langkah-langkah berikut:
Perhitungan di atas akan menghasilkan n, dengan begitu Alice dapat mengembalikan pesan semula m. Prosedur dekripsi bekerja karena
- .
Kemudian, dikarenakan ed ≡ 1 (mod p-1) dan ed ≡ 1 (mod q-1), hasil dari Fermat's little theorem.
dan
Dikarenakan p dan q merupakan bilangan prima yang berbeda, mengaplikasikan Chinese Remainder Theorem akan menghasilkan dua macam kongruen
- .
serta
- .
Contoh proses
Berikut ini merupakan contoh dari enkripsi RSA dan dekripsinya. Parameter yang digunakan disini berupa bilangan kecil.
Kita membuat
| p = 61 | — bilangan prima pertama (harus dijaga kerahasiannya atau dihapus secara hati-hati) |
| q = 53 | — bilangan prima kedua (harus dijaga kerahasiannya atau dihapus secara hati-hati) |
| N = pq = 3233 | — modulus (diberikan kepada publik) |
| e = 17 | — eksponen publik (diberikan kepada publik) |
| d = 2753 | — eksponen pribadi (dijaga kerahasiannya) |
Public key yang digunakan adalah (e,N). Private key yang digunakan adalah d. Fungsi pada enkripsi ialah:
- encrypt(n) = ne mod N = n17 mod 3233
dimana n adalah plaintext Fungsi dekripsi ialah:
- decrypt(c) = cd mod N = c2753 mod 3233
dimana c adalah ciphertext.
Untuk melakukan enkripsi plaintext bernilai "123", perhitungan yang dilakukan
- encrypt(123) = 12317 mod 3233 = 855
Untuk melakukan dekripsi ciphertext bernilai "855" perhitungan yang dilakukan
- decrypt(855) = 8552753 mod 3233 = 123
Kedua perhitungan di atas diselesaikan secara effisien menggunakan square-and-multiply algorithm pada modular exponentiation.
Padding schemes
Padding Scheme harus dibangun secara hati-hati sehingga tidak ada nilai dari m yang menyebabkan masalah keamanan. Sebagai contoh, jika kita ambil contoh sederhana dari penampilan ASCII dari m dan menggabungkan bit-bit secara bersama-sama akan menghasilkan n, kemudian pesan yang berisi ASCII tunggal karakter
NUL (nilai numeris 0) akan menghasilkan n= 0, yang akan menghasilkan ciphertext 0 apapun itu nilai dari e dan N yang digunakan. Sama halnya dengan karakter ASCII tunggal SOH (nilai numeris 1) akan selalu menghasilkan ciphertext 1. Pada kenyataannya, untuk sistem yang menggunakan nilai e yang kecil, seperti 3, seluruh karakter tunggal ASCII pada pesan akan disandikan menggunakan skema yang tidak aman, dikarenakan nilai terbesar n adalah nilai 255, dan 2553 menghasilkan nilai yang lebih kecil dari modulus yang sewajarnya, maka proses dekripsi akan menjadi masalah sederhana untuk mengambil pola dasar dari ciphertext tanpa perlu menggunakan modulus N. Sebagai konsekuensinya, standar seperti PKCS didesain dengan sangat hati-hati sehingga membuat pesan asal-asalan dapat terenkripsi secara aman. Dan juga berdasar pada bagian Kecepatan, akan dijelaskan kenapa m hampir bukanlah pesan itu sendiri tetapi lebih pada message key yang dipilh secara acak.sumber : https://id.wikipedia.org/wiki/RSA
tutorial RSA
Reviewed by azis nurdiansyah
on
Oktober 31, 2018
Rating:
Reviewed by azis nurdiansyah
on
Oktober 31, 2018
Rating:
