Modulus n
φ(n) (p − 1)(q − 1)
Kunci publik (e, n)
Kunci privat d e · d mod φ(n) = 1

Kunci

    Cara menemukan d: algoritma Euklides yang diperluas

    Setiap baris diperoleh dengan membagi dua baris di atasnya. Pada baris dengan sisa 1, kolom terakhir adalah d (tambahkan φ(n) jika negatif).

    Hasil bagiSisaKoefisien e

    Pesan

    Karakter Kode m Hasil

    Dikirim lewat jaringan

    BitKuadratKalikan dengan m

    Membobol kunci

    Tindakan

    Informasi lebih lanjut tentang RSA

    Demo enkripsi RSA

    RSA memungkinkan siapa pun mengunci pesan dengan kunci publik Anda, sementara hanya Anda yang bisa membukanya dengan kunci privat Anda. Di baliknya ada beberapa baris aritmetika sekolah: dua bilangan prima, sebuah perkalian, sebuah sisa pembagian, dan sebuah invers yang cerdik. Bangun pasangan kunci dari bilangan prima pilihan Anda, enkripsi dan dekripsi pesan karakter demi karakter, tanda tangani pesan itu agar siapa pun bisa memeriksa bahwa pesan itu berasal dari Anda, lalu berperanlah sebagai penyerang dan faktorkan n untuk melihat mengapa kunci sungguhan memerlukan ratusan digit. Pilih dua bilangan prima p dan q, atau tekan Prima baru. Aplikasi membangun kunci publik (e, n) dan kunci privat d, serta menunjukkan bagaimana algoritma Euklides yang diperluas menemukan d. Ketik pesan: setiap karakter dienkripsi dengan kunci publik dan didekripsi dengan kunci privat. Klik sebuah baris untuk melihat pangkat yang dihitung dengan pengkuadratan berulang. Beralih ke Tanda tangani untuk menandatangani dengan kunci privat, dan tekan Faktorkan n untuk melihat seberapa cepat kunci kecil terbobol.

    Cara kerjanya

    1. Masukkan dua bilangan prima p dan q, atau pilih ukuran dan tekan Prima baru; aplikasi menghitung n, φ(n), e, dan d, serta menunjukkan cara d ditemukan.
    2. Ketik pesan dan pilih Enkripsi atau Tanda tangani. Setiap karakter diubah menjadi bilangan lalu dipangkatkan mod n; klik sebuah baris untuk melihat pengkuadratan berulangnya.
    3. Tekan Faktorkan n agar Eve memecah n menjadi dua bilangan primanya dan memulihkan kunci privat.

    Cara kerja kunci

    Kalikan dua bilangan prima: n = p × q. Dengan p = 61 dan q = 53, n = 3233. Bilangan φ(n) = (p − 1)(q − 1) = 3120 menghitung bilangan di bawah n yang tidak memiliki faktor persekutuan dengannya, dan hanya bisa dihitung oleh orang yang mengetahui p dan q. Pilih e = 17, yang tidak memiliki faktor persekutuan dengan 3120, lalu temukan d sehingga e × d bernilai 1 lebih dari suatu kelipatan φ(n): di sini d = 2753, karena 17 × 2753 = 46801 = 15 × 3120 + 1. Umumkan (e, n) dan simpan d. Pesan m menjadi c = mᵉ mod n, dan teorema Euler menjamin bahwa cᵈ mod n mengembalikan m.

    Mengapa sulit dibobol

    Semua yang dibutuhkan penyerang tersembunyi dalam faktor-faktor n. Dengan n = 3233, itu sama sekali bukan perlindungan: mencoba pembagi ganjil menemukan 53 setelah sekitar dua lusin percobaan. Namun usahanya tumbuh seiring akar kuadrat n. Modulus 2048 bit memiliki sekitar 617 digit, dan tidak ada metode yang diketahui, di komputer mana pun yang ada saat ini, yang dapat memfaktorkannya dalam waktu yang wajar. Penandatanganan menjalankan RSA secara terbalik: s = mᵈ mod n hanya bisa dibuat dengan kunci privat, dan siapa pun bisa memeriksa bahwa sᵉ mod n mengembalikan m.

    Pertanyaan yang sering diajukan

    Mengapa tidak ada yang bisa menghitung d dari kunci publik?

    Untuk menemukan d Anda memerlukan φ(n) = (p − 1)(q − 1), dan untuk mendapatkan φ(n) Anda memerlukan p dan q. Memulihkan keduanya dari n berarti memfaktorkannya, dan untuk bilangan dengan ratusan digit tidak ada metode cepat yang diketahui. Demo ini memungkinkan Anda memfaktorkan kunci mainan dalam sepersekian detik, yang menunjukkan dengan tepat mengapa kunci sungguhan begitu besar.

    Mengapa pesan dienkripsi satu karakter demi satu karakter?

    Karena kunci mainannya kecil: RSA hanya bisa mengenkripsi bilangan yang lebih kecil dari n. Dengan n = 3233, setiap kode karakter muat, tetapi satu kalimat utuh tidak. RSA sungguhan memakai modulus 2048 bit atau lebih, menambahkan byte acak ke pesan agar pesan yang sama tidak pernah dienkripsi dengan cara yang sama dua kali, dan dalam praktik hanya mengenkripsi kunci pendek untuk sandi yang lebih cepat seperti AES.

    Apa fungsi pengkuadratan berulang?

    Pengkuadratan berulang menghitung pangkat raksasa seperti m²⁷⁵³ mod n tanpa pernah menuliskan bilangan raksasanya. Tulis eksponen dalam biner, lalu telusuri bit-bitnya: kuadratkan hasil sementara untuk setiap bit dan kalikan dengan m untuk setiap 1, dengan mengambil sisa mod n setiap kali. Eksponen 2048 bit hanya memerlukan sekitar 2048 pengkuadratan.

    Apa bedanya mengenkripsi dan menandatangani?

    Enkripsi memakai kunci publik penerima, sehingga hanya kunci privat penerima yang bisa membukanya. Penandatanganan memakai kunci privat pengirim, sehingga siapa pun bisa memeriksanya dengan kunci publik pengirim dan tahu bahwa pesan itu berasal dari pemegang kunci tersebut dan tidak diubah.

    Apakah pesan saya dikirim ke suatu tempat?

    Tidak. Semuanya dihitung di browser Anda, dan bilangan prima serta pesan Anda tetap tersimpan di penyimpanan lokal browser ini.

    Siap mencobanya?

    Buka PictorX di browser Anda — tanpa instalasi, tanpa kartu kredit untuk memulai.

    Ke Editor