Penjelasan RSA
Setiap kali browser menampilkan ikon gembok, sebuah pesan ditandatangani, atau perangkat lunak memeriksa pembaruan, kriptografi kunci publik sedang bekerja, dan RSA adalah bentuknya yang paling terkenal. Gagasannya adalah bahwa kunci yang mengunci pesan boleh diumumkan, sementara kunci yang membukanya tetap rahasia. Hebatnya, seluruh sistem ini bertumpu pada aritmetika yang diajarkan di sekolah: bilangan prima, perkalian, dan sisa pembagian.
Masalah yang dipecahkan RSA
Sandi konvensional, dari sandi geser Caesar hingga AES modern, memakai kunci yang sama untuk mengunci dan membuka, sehingga kedua pihak harus terlebih dahulu berbagi kunci rahasia secara pribadi. Kriptografi kunci publik menghilangkan langkah itu. Setiap orang memiliki dua kunci: kunci publik yang boleh dipakai siapa pun untuk mengenkripsi pesan kepadanya, dan kunci privat yang hanya dipegangnya sendiri dan satu-satunya yang bisa mendekripsi pesan itu. Whitfield Diffie dan Martin Hellman mendeskripsikan gagasan ini pada tahun 1976, dan setahun kemudian Ron Rivest, Adi Shamir, dan Leonard Adleman di MIT menemukan cara mewujudkannya, yang dinamai RSA menurut inisial mereka.
Membuat kunci
Pilih dua bilangan prima besar, p dan q, lalu kalikan: n = p × q. Hitung φ(n) = (p − 1)(q − 1), fungsi totient Euler, yang menghitung bilangan di bawah n yang tidak memiliki faktor persekutuan dengannya. Pilih eksponen publik e yang tidak memiliki faktor persekutuan dengan φ(n); 65537 adalah pilihan yang lazim. Lalu temukan eksponen privat d sehingga e × d bersisa 1 jika dibagi φ(n). Algoritma Euklides yang diperluas melakukannya dengan cepat. Kunci publik adalah pasangan (e, n); kunci privat adalah d. Dengan p = 61 dan q = 53, hasilnya n = 3233, φ(n) = 3120, e = 17, dan d = 2753.
Enkripsi dan dekripsi
Pesan terlebih dahulu diubah menjadi bilangan m yang lebih kecil dari n. Untuk mengenkripsinya, hitung c = mᵉ mod n, yaitu sisa mᵉ setelah dibagi n. Untuk mendekripsi, hitung cᵈ mod n. Teorema Euler menjamin bahwa ini mengembalikan m, karena e × d bernilai satu lebih dari suatu kelipatan φ(n). Dengan kunci di atas, huruf A, kode 65, menjadi 65¹⁷ mod 3233 = 2790, dan 2790²⁷⁵³ mod 3233 kembali menjadi 65. Pangkat sebesar ini tidak pernah dituliskan lengkap: pengkuadratan berulang menghitungnya dengan satu pengkuadratan per bit eksponen, sambil mengambil sisa di setiap langkah.
Tanda tangan digital
RSA juga bekerja secara terbalik. Memangkatkan pesan dengan eksponen privat, s = mᵈ mod n, menghasilkan tanda tangan yang hanya bisa dibuat oleh pemilik kunci. Siapa pun bisa memeriksanya dengan kunci publik: jika sᵉ mod n mengembalikan m, pesan itu berasal dari pemegang d dan tidak diubah dalam perjalanan. Dalam praktik, yang ditandatangani adalah hash pendek dari pesan, bukan pesan itu sendiri. Tanda tangan seperti ini melindungi pembaruan perangkat lunak, situs web yang aman, dan dokumen elektronik.
Mengapa RSA aman
Semua orang bisa melihat n dan e. Untuk menemukan d, penyerang memerlukan φ(n), dan untuk menemukan φ(n) ia memerlukan p dan q, sehingga membobol RSA bermuara pada memfaktorkan n. Mengalikan dua bilangan prima hanya butuh sepersekian mikrodetik bagi komputer; memecah hasil kalinya kembali menjadi kedua bilangan itu diyakini sangat sulit. Bilangan tantangan RSA terbesar yang berhasil difaktorkan sejauh ini, RSA-250 pada tahun 2020, memiliki 829 bit dan memakan sekitar 2700 tahun waktu komputer. Kunci yang dipakai saat ini memiliki setidaknya 2048 bit, sekitar 617 digit.
Rahasia yang ditemukan dua kali
Pada tahun 1973, empat tahun sebelum RSA, matematikawan Inggris Clifford Cocks menemukan skema yang sama saat bekerja di badan intelijen GCHQ, dengan membangun di atas gagasan rekannya James Ellis. Karya itu dirahasiakan dan baru diumumkan pada tahun 1997. RSA sendiri dipatenkan di Amerika Serikat pada tahun 1983; patennya berakhir pada September 2000, dua minggu setelah algoritma ini dilepas ke domain publik.
RSA dalam praktik
RSA sungguhan tidak pernah mengenkripsi teks secara langsung. Pesan diberi padding berupa byte acak, dengan skema seperti OAEP, sehingga pesan yang sama dienkripsi secara berbeda setiap kali dan pola tidak bisa bocor. Karena lambat, RSA sebagian besar dipakai untuk mempertukarkan atau melindungi kunci pendek bagi sandi simetris yang cepat seperti AES, atau untuk menandatangani. Komputer kuantum yang cukup besar dapat memfaktorkan n dengan cepat menggunakan algoritma Shor dari tahun 1994, itulah sebabnya metode pascakuantum baru mulai diperkenalkan berdampingan dengan RSA.
Jelajahi sendiri
Buka demo enkripsi RSA untuk membangun kunci dari bilangan prima Anda sendiri atau bilangan prima acak 2 hingga 8 digit, melihat algoritma Euklides yang diperluas menemukan d baris demi baris, mengenkripsi atau menandatangani pesan karakter demi karakter, dan mengikuti pengkuadratan berulang untuk karakter mana pun. Lalu biarkan Eve memfaktorkan n dan saksikan bagaimana waktu yang ia butuhkan bertambah seiring ukuran bilangan prima.
Pertanyaan yang sering diajukan
Mengapa RSA memerlukan bilangan prima?
Karena φ(n) mudah dihitung hanya jika Anda tahu bagaimana n terurai menjadi bilangan prima. Untuk n = p × q dengan p dan q prima, φ(n) = (p − 1)(q − 1). Bilangan prima juga membuat n sesulit mungkin difaktorkan untuk ukurannya, karena n sama sekali tidak memiliki faktor kecil.
Mengapa e sering bernilai 65537?
65537 = 2¹⁶ + 1 adalah bilangan prima dan hanya memiliki dua angka 1 dalam biner, sehingga mengenkripsi dengannya hanya memerlukan 16 pengkuadratan dan satu perkalian. Bilangan ini juga cukup besar untuk menghindari kelemahan eksponen yang sangat kecil seperti 3.
Apa perbedaan RSA dan Diffie–Hellman?
Diffie–Hellman memungkinkan dua orang menyepakati kunci rahasia bersama melalui saluran terbuka; dengan sendirinya ia tidak mengenkripsi atau menandatangani apa pun. RSA mengenkripsi dan menandatangani secara langsung dengan pasangan kunci. Keduanya bertumpu pada masalah yang mudah ke satu arah dan sulit ke arah sebaliknya: faktorisasi untuk RSA, logaritma diskret untuk Diffie–Hellman.
Bisakah kunci dari demo ini dipakai untuk enkripsi sungguhan?
Tidak. Bilangan primanya paling banyak selusin digit, sehingga kunci apa pun yang dibuatnya bisa difaktorkan dalam hitungan detik atau kurang, dan demo ini mengenkripsi setiap karakter secara terpisah tanpa padding. Demo ini dimaksudkan untuk melihat cara kerja RSA, bukan untuk melindungi apa pun.
Siap mencobanya?
Buka PictorX di browser Anda — tanpa instalasi, tanpa kartu kredit untuk memulai.
Buka demo enkripsi RSA