RSA: Perbedaan antara revisi

'''RSA (Rivest–Shamir–Adleman)''' di bidang [[kriptografi]] adalah sebuah [[algoritmaalgoritme]] pada [[enkripsi]] ''[[Public Key Infrastructure|public key]]''. RSA merupakan algoritmaalgoritme pertama yang cocok untuk ''[[digital signature]]'' seperti halnya ekripsienkripsi, dan salah satu yang paling maju dalam bidang kriptografi ''public key''. RSA masih digunakan secara luas dalam [[protokol]] ''[[electronic commerce]]'', dan dipercaya dalam mengamnkanmengamankan dengan menggunakan kunci yang cukup panjang.

Algortima RSA dijabarkan pada tahun [[1977]] oleh tiga orang: [[Ron Rivest]], [[Adi Shamir]] dan [[Len Adleman]] dari [[Massachusetts Institute of Technology]]. HurufSingkatan '''RSA''' itu sendiri berasal dari inisial nama mereka ('''R'''ivest—ivest—'''S'''hamir—hamir—'''A'''dleman).

[[Clifford Cocks]], seorang matematikawan [[Inggris]] yang bekerja untuk [[GCHQ]], menjabarkan tentang sistem equivalenekuivalen pada dokumen internal dipada tahun [[1973]]. Penemuan Clifford Cocks tidak terungkap hingga tahun [[1997]] karena alasan ''top-secret classification''.

AlgoritmaAlgoritme tersebut dipatenkan oleh Massachusetts Institute of Technology pada tahun [[1983]] di [[Amerika Serikat]] sebagai {{US patent|4405829}}. Paten tersebut berlaku hingga [[21 September]] [[2000]]. Semenjak AlgoritmaAlgoritme 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.

=== PembangkitanPembuatan Kunci ===

# 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''.

# Hitung φφ = (''p''-1)(''q''-1).

# Pilih [[bilangan bulat]] (''integer'') antara satu dan &phi;φ (1 < ''e'' < &phi;φ) yang juga merupakan [[coprimeKoprima (bilangan)|koprima]] dari &phi;φ.

# Hitung ''d'' hingga ''d e'' &equiv;≡ 1 (mod &phi;φ).

* bilangan prima dapat diuji [[probabilitas|probabilitasnya]]nya 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 algoritmaalgoritme ''[[extended Euclidean]]''; lihat juga [[aritmetika modular]].

* langkah 2 PKCS#1 v2.1 menggunakan &lamda; = lcm(''p''-1, ''q''-1) selain daripada &phi;φ = (''p''-1)(''q''-1)).

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.

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_schemesPadding schemes|padding scheme]]''.

Perhitungan tersebut dapat diselesaikan dengan cepat menggunakan metode ''[[exponentiation by squaring]]''. Bob kemudian mengirimkan ''c'' kepada Alice.

Perhitungan diatasdi atas akan menghasilkan ''n'', dengan begitu Alice dapat mengembalikan pesan semula ''m''.

Kemudian, dikarenakan ''ed'' &equiv;≡ 1 (mod p-1) dan ''ed'' &equiv;≡ 1 (mod q-1), hasil dari ''[[Fermat's little theorem]]''.

: <math>n^{ed} \equiv n \pmod{p}</math>

Dikarenakan ''p'' dan ''q'' merupakan bilangan prima yang berbeda, mengaplikasikan ''Chinese remainderRemainder theorem''Theorem akan menghasilkan dua macam kongruen

|width="15%"|''p'' = 61 || &mdash;— bilangan prima pertama (harus dijaga kerahasiannya atau dihapus secara hati-hati)

|''q'' = 53 || &mdash;— bilangan prima kedua (harus dijaga kerahasiannya atau dihapus secara hati-hati)

|''N'' = ''pq'' = 3233 || &mdash;— modulus (diberikan kepada publik)

|''e'' = 17 || &mdash;— eksponen publik (diberikan kepada publik)

|''d'' = 2753 || &mdash;— eksponen pribadi (dijaga kerahasiannya)

Kedua perhitungan diatasdi atas diselesaikan secara effisien menggunakan ''[[square-and-multiply algorithm]]'' pada ''[[modular exponentiation]]''.

''[[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-bit]] secara bersama-sama akan menghasilkan ''n'', kemudian pessanpesan yang berisi ASCII tunggal karakter <code>NUL</code> (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 <code>SOH</code> (nilai numeris 1) akan selalu menghasilkan ''chiphertextciphertext'' 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 255³ 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|Kecepatan]], akan dijelaskan kenapa ''m'' hampir bukanlah pesan itu sendiri tetapi lebih pada ''message key'' yang dipilh secara acak.

Penyerangan yang paling umum pada RSA ialah pada penanganan masalah [[faktorisasi]] pada bilangan yang sangat besar. Apabila terdapat faktorisasi metode yang baru dan cepat telah dikembangkan, maka ada kemungkinan untuk membongkar RSA.

Pada tahun [[2005]], bilangan faktorisasi terbesar yang digunakan secara umum ialah sepanjang 663 bit, menggunakan metode distribusi mutakhir. Kunci RSA pada umumnya sepanjang 1024&mdash;20481024—2048 bit. Beberapa pakar meyakini bahwa kunci 1024-bit ada kemungkinan dipecahkan pada waktu dekat (hal ini masih dalam perdebatan), tetapi tidak ada seorangpun yang berpendapat kunci 2048-bit akan pecah pada masa depan yang terprediksi.

Semisal Eve, seorang ''eavesdropper'' (pencuri dengar&mdash;pengupingdengar—penguping), mendapatkan ''public key'' ''N'' dan ''e'', dan ''ciphertext'' ''c''. Bagimanapun juga, Eve tidak mampu untuk secara langsung memperoleh ''d'' yang dijaga kerahasiannya oleh Alice. Masalah untuk menemukan ''n'' seperti pada ''n^e=c'' mod N di kenal sebagai permasalahan RSA.

Pada thaun [[1993]], [[Peter Shor]] menerbitkan [[AlgoritmaAlgoritme Shor]], menunjukkan bahwa sebuah [[komputer quantum]] secara prinsip dapat melakukan faktorisasi dalam waktu polinomial, mengurai RSA dan algoritmaalgoritme lainnya. Bagaimanapun juga, masih terdapat pedebatan dalam pembangunan komputer quantum secara prinsip.

=== PembangkitanPembuatan kunci ===

Seseorang seharusnya tidak melakukan metodametode pencarian bilangan prima yang hanya akan memberikan informasi penting tentang bilangan prima tersebut kepada penyerang. Biasanya, pembangkit bilangan acak yang baik akan memulai nilai bilangan yang digunakan. Harap diingat, bahwa kebutuhan disini ialah "acak" '''''dan''''' "tidak-terduga". Berikut ini mungkin tidak memenuhi kriteria, sebuah bilangan mungkin dapat dipilah dari proses acak (misal, tidak dari pola apapun), tetapi jika bilangan itu mudah untuk ditebak atau diduga (atau mirip dengan bilangan yang mudah ditebak), maka metode tersebut akan kehilangan kemampuan keamanannya. Misalnya, tabel bilangan acak yang diterbitkan oleh [[Rand Corp]] pada tahun [[1950-an]] mungkin memang benar-benar teracak, tetapi dikarenakan diterbitkan secara umum, hal ini akan mempermudah para penyerang dalam mendapatkan bilangan tersebut. Jika penyerang dapat menebak separuh dari digit ''p'' atau ''q'', para penyerang dapat dengan cepat menghitung separuh yang lainnya (ditunjukkan oleh [[Donald Coppersmith]] pada tahun [[1997]]).

Sangatlah penting bahwa kunci rahasia ''d'' bernilai cukup besar, Wiener menunjukkan pada tahun [[1990]] bahwa jika ''p'' diantaradi antara ''q'' dan 2''q'' (yang sangat mirip) dan ''d'' lebih kecil daripada ''N''^1/4/3, maka ''d'' akan dapat dihitung secara effisien dari ''N'' dan ''e''.

RSA memiliki kecepatan yang lebih lambat dibandingkan dengan [[DES]] dan [[algoritmaalgoritme simetrik]] lainnya. Pada prakteknyapraktiknya, Bob menyandikan pesan rahasia menggunakan algoritmaalgoritme simetrik, menyandikan kunci simetrik menggunakan RSA, dan mengirimkan kunci simetrik yang dienkripsi menggunakan RSA dan juga mengirimkan pesan yang dienkripasidienkripsi secara simetrik kepada Alice.

Sebagaimana halnya ''cipher'', bagaimana ''public key'' RSA didistribusi menjadi hal penting dalam keamanan. Distribusi kunci harus aman dari ''[[man-in-the-middle attack]]'' (''penghadang-ditengahdi tengah-jalan''). Anggap Eve dengan suatu cara mampu memberikan kunci arbitari kepada Bob dan membuat Bob percaya bahwa kunci tersebut milik Alice. Anggap Eve dapan "menghadang" sepenuhnya transmisi antara Alice dan Bob. Eve mengirim Bob ''public key'' milik Eve, dimana Bob percaya bahwa ''public key'' tersebut milik Alice. Eve dapat menghadap seluruh ''ciphertext'' yang dikirim oleh Bob, melakukan dekripsi dengan kunci rahasia milik Eve sendiri, menyimpan salinan dari pesan tersebut, melakukan enkripsi menggunakan ''public key'' milik Alice, dan mengirimkan ''ciphertext'' yang baru kepada Alice. Secara prinsip, baik Alice atau Bob tidak menyadari kehadiran Eve diantaradi antara transmisi mereka. Pengamanan terhadap serangan semacam ini yaitu menggunakan [[sertifikat digital]] atau komponen lain dari infrastuktur ''public key''.

Kocher menjelaskan sebuah serangan baru yang cerdas pada RSA dipada tahun [[1995]]: jika penyerang, Eve, mengetahui perangkat keras yang dimiliki oleh Alice secara terperinci dan mampu untuk mengukur waktu yang dibutuhkan untuk melakukan dekripsi untuk beberapa ''ciphertext'', Eve dapat menyimpulkan kunci dekripsi ''d'' secara cepat. Penyerangan ini dapat juga diaplikasikan pada skema "tanda tangan" RSA. SAlah satu cara untuk mencegah penyerangan ini yaitu dengan memastikan bahwa operasi dekripsi menggunakan waktu yang konstan untuk setiap ''ciphertext'' yang diproses. Cara yang lainnya, yaitu dengan menggunakan properti multipikatif dari RSA. Sebagai ganti dari menghitung ''c^d mod N'', Alice pertama-tama memilih nilai bilangan acak ''r'' dan menghitung ''(r^ec)^d mod N''. Hasil dari penghitungan tersebut ialah ''rm mod N'' kemudian efek dari ''r'' dapat dihilangkan dengan perkalian dengan inversenya. Nilai baru dari ''r'' dipilih pada tiap ''ciphertext''. Dengan teknik ini, dikenal sebagai ''message blinding'' (pembutaan pesan), waktu yang diperlukan untuk proses dekripsi tidak lagi berhubungan dengan nilai dari ''ciphertext'' sehingga penyerangan waktu akan gagal.

== Lihat jugapula ==

* {{en}} [http://www.rsasecurity.com/rsalabs/node.asp?id=2125 PKCS #1: Standar Kriptografi RSA] {{Webarchive|url=https://web.archive.org/web/20051029040347/http://rsasecurity.com/rsalabs/node.asp?id=2125 |date=2005-10-29 }} (website [[Laboratorium RSA]])

* {{en}} [http://theory.lcs.mit.edu/~rivest/rsapaper.pdf Metode untuk mendapatkan ''Digital Signature'' dan ''Public Key Cryptosystems''] {{Webarchive|url=https://web.archive.org/web/20070127130201/http://theory.lcs.mit.edu/~rivest/rsapaper.pdf |date=2007-01-27 }}, R. Rivest, A. Shamir, L. Adleman, Komunikasi ACM, Seri. 21 (2), 1978, halaman 120--126120–126. Dirilis sebagai MIT "Technical Memo" pada April [[1977]].

* {{en}} [http://www.devhood.com/tutorials/tutorial_details.aspx?tutorial_id=544&printer=t Pengenalan tentang RSA ''Cryptosystem''] {{Webarchive|url=https://web.archive.org/web/20050504064303/http://www.devhood.com/tutorials/tutorial_details.aspx?tutorial_id=544&printer=t |date=2005-05-04 }}, M. Griep, Okt. 2002,