it-swarm-id.com

Haruskah eksponen publik RSA hanya dalam {3, 5, 17, 257 atau 65537} karena pertimbangan keamanan?

Dalam proyek saya, saya menggunakan nilai eksponen publik 4451h. Saya pikir itu aman dan ok sampai saya mulai menggunakan satu perpustakaan enkripsi RSA komersial. Jika saya menggunakan eksponen ini dengan perpustakaan ini, ia melempar pengecualian.

Saya menghubungi pengembang perpustakaan ini dan mendapat jawaban berikut: "Fitur ini untuk mencegah beberapa serangan terhadap kunci RSA. Konsekuensinya adalah bahwa nilai eksponen terbatas pada {3, 5, 17, 257 atau 65537}. Menonaktifkan pemeriksaan ini adalah masih diselidiki, karena risikonya mungkin besar. "

Ini pertama kalinya dalam hidup saya, saya mendengar bahwa nilai selain {3, 5, 17, 257 atau 65537} digunakan untuk mendobrak RSA. Saya tahu hanya menggunakan 3 dengan padding yang tidak layak menjadi rentan.

Benarkah begitu? Tentunya, saya dapat menggunakan perpustakaan lain, tetapi setelah jawaban seperti itu saya khawatir tentang keamanan solusi saya.

70

Tidak ada kelemahan yang diketahui untuk eksponen publik pendek atau panjang untuk RSA, selama eksponen publik "benar" (yaitu relatif utama untuk p-1 untuk semua bilangan prima p yang membagi modulus).

Jika Anda menggunakan eksponen kecil dan Anda tidak menggunakan lapisan apa pun untuk enkripsi dan Anda mengenkripsi pesan yang sama persis dengan beberapa kunci publik yang berbeda, maka pesan Anda berisiko: jika e = 3, dan Anda mengenkripsi pesan m dengan kunci publik n1, n2 dan n3, maka Anda memiliki csaya = m3 mod nsaya untuk i = 1 ke 3. Dengan Teorema Sisa Cina , Anda dapat membangun kembali m3 mod n1n2n3, yang ternyata m3 (tanpa modulo apa pun) karena n1n2n3 adalah bilangan bulat yang lebih besar. Ekstraksi cube root (non modular) kemudian cukup untuk mengekstrak m.

Kelemahannya, di sini, adalah bukan eksponen kecil; melainkan penggunaan padding yang tidak tepat (yaitu, tidak ada padding sama sekali) untuk enkripsi. Padding sangat penting untuk keamanan RSA, baik enkripsi atau tanda tangan; jika Anda tidak menggunakan padding yang tepat (seperti yang dijelaskan dalam PKCS # 1 ), maka Anda memiliki banyak kelemahan, dan yang diuraikan dalam paragraf di atas bukanlah yang terbesar, sejauh ini. Namun demikian, setiap kali seseorang merujuk pada kelemahan terkait ukuran eksponen, ia lebih atau kurang secara langsung merujuk pada kejadian ini. Itu sedikit pengetahuan lama dan salah, yang kadang-kadang terbalik menjadi larangan terhadap besar eksponen (karena itu adalah mitos, mitos sebaliknya juga mitos dan tidak lebih - dan tidak ada kurang - dibuktikan); Saya percaya ini yang Anda amati di sini.

Namun, orang dapat menemukan beberapa alasan mengapa eksponen publik besar harus dihindari:

  • Eksponen publik kecil mempromosikan efisiensi (untuk operasi kunci publik).

  • Ada masalah keamanan tentang memiliki eksponen kecil pribadi; serangan pemulihan kunci telah dijelaskan ketika panjang eksponen pribadi tidak lebih dari 29% dari panjang eksponen publik. Saat Anda ingin memaksa eksponen privat menjadi pendek (mis. Untuk mempercepat operasi kunci privat), Anda kurang lebih harus menggunakan eksponen publik besar (sebesar modulus); membutuhkan eksponen publik untuk menjadi pendek kemudian dapat dipandang sebagai semacam penanggulangan tidak langsung.

  • Beberapa implementasi RSA yang banyak digunakan mencekik eksponen publik RSA besar. Misalnya. kode RSA di Windows (CryptoAPI, digunakan oleh Internet Explorer untuk HTTPS) bersikeras untuk mengkodekan eksponen publik dalam 32-bit Word tunggal; itu tidak dapat memproses kunci publik dengan eksponen publik yang lebih besar.

Namun, "risiko mungkin besar" sepertinya pembenaran umum ("ini adalah masalah keamanan" adalah cara yang lazim untuk mengatakan "kami tidak menerapkannya tetapi kami tidak ingin mengakui segala bentuk kemalasan").

64
Thomas Pornin

Pengembangnya tidak benar. Tidak ada yang salah dengan eksponen 0x4451 (desimal 17489); itu tidak membuat masalah keamanan.

Dahulu orang dulu berpikir bahwa eksponen kecil adalah masalah, karena serangan yang dijelaskan Thomas Pornin dengan mengirim pesan yang sama ke banyak penerima. Tetapi hari ini kita mengerti bahwa para eksponen tidak ada hubungannya dengan itu; masalah itu padding yang tidak tepat. Serangan-serangan itu dicegah dengan penggunaan padding yang tepat. Setiap pustaka crypto yang bernilai garam harusnya lebih baik menggunakan padding yang tepat (jika tidak Anda punya masalah yang jauh lebih buruk).

Jadi tidak ada alasan yang baik bagi perpustakaan crypto untuk secara tegas melarang penggunaan eksponen itu.

Yang mengatakan, dari perspektif kinerja, semakin kecil eksponen, semakin baik kinerjanya. Pilihan terbaik adalah e = 3, karena itu memberikan kinerja terbaik dan tidak memiliki masalah keamanan yang diketahui. (Sebenarnya, e = 2 bahkan sedikit lebih baik. Ini juga dikenal sebagai enkripsi Rabin. Namun, skema itu tidak terlalu dikenal dan membutuhkan kode yang sedikit berbeda, sehingga tidak banyak digunakan.)

21
D.W.

Kelima angka itu adalah Fermat primes .

Karena mereka berbentuk 2 k  +1, enkripsi adalah m e  = m · (( m 2)2... k kali...)2, yang lebih sederhana dan lebih cepat dari eksponensial dengan eksponen dengan ukuran yang sama di kasus umum .

Karena mereka bilangan prima, tes yang e adalah coprime ke ( p - 1) ( q - 1) hanyalah sebuah tes yang e tidak membaginya.

Jadi ini lebih cenderung tentang kecepatan atau konvensi daripada tentang keamanan. Bukan berarti ada yang salah dengan menjadi efisien. Tetapi yang pasti, mintalah referensi sebagai jawaban lain disarankan.

Juga lihat posting ini .

19
aaz

Saya tidak mengetahui alasan mengapa eksponen publik kunci RSA hanya boleh di set {3,5,17,257,65537}. Seperti yang Anda sebutkan, eksponen kecil seperti 3 atau 5 lebih berisiko untuk digunakan, karena efek negatif kesalahan implementasi (seperti padding yang tidak tepat) bisa lebih besar. NIST hanya memungkinkan eksponen publik yang lebih besar dari 2 ^ 16, tapi saya tidak tahu alasan untuk keputusan mereka.

Anda seharusnya tidak puas dengan jawaban yang diberikan oleh pengembang perpustakaan yang Anda gunakan dan meminta referensi konkret. Terlalu sering, ternyata beberapa kertas disalahpahami. Misalnya saya dapat membayangkan bahwa beberapa pengembang membaca Bagian 4 dari makalah "Bisakah Kita Percayai Perangkat Lunak Kriptografi? Kelemahan Kriptografi dalam GNU Privacy Guard v1.2.3" oleh Phong Nguyen dan sampai pada kesimpulan yang salah, seperti yang di atas. Makalah ini memperhatikan bahwa ketika kunci publik yang dihasilkan oleh GnuPG ternyata menjadi beberapa nilai yang tidak biasa seperti 65539, maka penyerang belajar sedikit informasi tentang kunci rahasia. Kesimpulannya ada bahwa algoritma pembuatan kunci GnuPG dapat ditingkatkan, tetapi bukan berarti 65539 adalah kunci publik yang buruk.

8
Accipitridae

Saya tidak dapat menemukan referensi bahwa nilai-nilai lain untuk eksponen publik rentan. Tangguh menggunakan eksponen publik yang mendekati kekuatan 2 disarankan untuk alasan kinerja, menurut RSA.com panduan untuk algoritma RSA

Menurut Wikipedia , NIST tidak mengizinkan eksponen publik yang lebih kecil dari 65537, karena eksponen yang lebih kecil adalah masalah jika tidak diisi dengan benar.

7
Andreas Arnold