RSA - Apakah $e = d$ masalah?

Question

Saya sedang mengerjakan proyek RSA kecil di universitas. Saat ini saya telah melakukan ini:

1. Larik bilangan prima dihasilkan dari rentang yang dipilih.
2. $p$ dan $q$ dipilih secara acak dari larik ini
3. $n$ dihitung
4. $\phi(n)$ dihitung
5. $e$ dihitung
6. $d$ dihitung

Apa yang Anda pikirkan $e$ dan $d$ dalam hal itu?

• $p = 29$
• $q = 53$
• $n = 1537$
• $\phi(n) = 1456$
• $e = 545$
• $d = 545$

Answer 1

Ini akan menjadi bencana jika prosedur pembuatan kunci RSA memiliki kemungkinan yang cukup besar untuk diakhiri $e=d$, karena dalam kasus tersebut, kunci publik mengungkapkan kunci privat, yang harus dirahasiakan dari perspektif keamanan.

Tapi $e=d$ adalah gejala dari masalah yang lebih besar yang terletak pada langkah 1 dan 2 dari prosedur pembuatan kunci: RSA hanya dapat aman jika $p$ dan $q$ dipilih sedemikian rupa sehingga anjak piutang $n$ itu sulit, dan itu artinya $p$ dan $q$harus bilangan prima besar. Garis dasar modern adalah$n$ dari $2048$ bit, itu $617$ angka desimal, bukan $4$angka desimal. Untuk ini,$p$ dan $q$ dipilih secara acak di antara subset yang cukup besar dari bilangan prima sekitar $309$digit. Ada tentang$10^{305}$bilangan prima seperti itu, sehingga menghasilkan semuanya kemudian memilih di dalam yang tidak layak. Prosedur yang tepat adalah langsung menghasilkan$p$ dan $q$.

Dengan $p$ dan $q$ bilangan prima acak sebesar ini, dan pilihan acak dari $e$ seperti yang $\gcd(e,\phi(n))=1$ (atau pilihan bilangan prima acak $p$ dan $q$ dengan satu-satunya ketergantungan pada $e$ bahwa $\gcd(e,p-1)=1$ dan $\gcd(e,q-1)=1$, seperti praktik umum), itu sangat tidak mungkin $d=e$, atau lebih umum bahwa satu atau beberapa enkripsi ulang mengarah pada dekripsi. Lihat pertanyaan - pertanyaan ini tentang serangan bersepeda .

---

Ada prosedur pembuatan kunci RSA di FIPS 186-4 lampiran B.3 . Abaikan yang diusulkan$1024$ukuran kunci -bit, yang sudah usang. Usulan$2048$ adalah garis dasarnya, $3072$ semakin umum, meluas hingga $4096$-bit tidak masuk akal. Prosedur ini berbeda dari yang digunakan dalam pertanyaan dengan beberapa poin termasuk:

• Menghasilkan bilangan prima besar $p$ dan $q$ tak terduga dalam interval yang ditentukan $[2^{(k-1)/2},2^{k/2}]$, dimana $k$ adalah ukuran bit yang diinginkan dari $n$ (misalnya $3072$)
• Membutuhkan ganjil $e$ dengan $2^{16}<e<2^{256}$ (semakin rendah karena itu bertindak sebagai perlindungan terhadap pilihan padding RSA yang buruk, semakin tinggi untuk interoperabilitas dan membuat beberapa pilihan buruk lainnya menjadi tidak mungkin)
• Menggunakan $d=e^{-1}\bmod\lambda(n)$ (dimana $\lambda$adalah fungsi Carmichael ) daripada$d=e^{-1}\bmod\phi(n)$. Keduanya baik secara matematis, tetapi menggunakan$\lambda$ mengasuransikan menghasilkan eksponen pribadi positif terkecil $d$ bekerja untuk sesuatu $(n,e)$.
• Membutuhkan ukuran minimum $d$ (jauh lebih besar dari $2^{256}$, yang menjamin $d>e$), lebih sebagai perlindungan terhadap kesalahan daripada karena kebutuhan matematika.