Arti dari: "'Jika memfaktorkan bilangan bulat besar itu sulit, maka melanggar RSA itu sulit,' tidak terbukti"

Saya membaca CLRS dan berkata:

Jika memperhitungkan bilangan bulat besar itu mudah, maka memecahkan cryptosystem RSA itu mudah.

Yang masuk akal bagi saya karena dengan pengetahuan dan , mudah untuk membuat kunci rahasia yang menjadi pengetahuan kunci publik. Padahal, itu menjelaskan pernyataan sebaliknya, yang saya tidak mengerti:$p$$q$

Pernyataan sebaliknya, bahwa jika anjak bilangan bulat besar sulit, maka melanggar RSA sulit, tidak terbukti.

Apa arti pernyataan di atas secara formal? Jika kita menganggap anjak sulit (dalam beberapa cara formal), mengapa itu tidak menyiratkan bahwa melanggar sistem kripto RSA sulit?

Sekarang pertimbangkan bahwa jika kita berasumsi bahwa anjak sulit ... dan kita menemukan bahwa itu berarti kriptografi RSA sulit untuk dipecahkan. Apa artinya itu secara formal?

Cara termudah untuk memikirkannya adalah dengan memikirkan alat kontrasepsi.

Pernyataan:

jika factoring bilangan bulat besar sulit, maka melanggar RSA sulit

setara dengan yang berikut:

jika melanggar RSA itu mudah, maka memfaktorkan bilangan bulat besar itu mudah

Pernyataan ini belum terbukti.

Apa yang mereka katakan adalah, asumsikan kita memiliki algoritma yang memecahkan anjak piutang dalam waktu polinomial. Kemudian kita dapat menggunakannya untuk membangun algoritma yang memecahkan RSA dalam waktu polinomial.

Tapi, mungkin ada beberapa cara lain untuk memecahkan RSA yang tidak melibatkan bilangan bulat anjak piutang. Mungkin saja kita akan menemukan bahwa kita dapat memecahkan RSA dengan cara yang tidak membiarkan kita memfaktorkan bilangan bulat dalam waktu polinomial.

Singkatnya, kita tahu bahwa RSA setidaknya semudah memfaktorkan. Ada dua hasil yang mungkin: RSA dan anjak piutang memiliki kesulitan yang setara, atau RSA adalah masalah yang lebih mudah daripada anjak piutang. Kami tidak tahu yang mana masalahnya.

Keberadaan jalan yang keras tidak menyiratkan tidak ada jalan yang mudah.

Mungkin ada sejumlah cara untuk memecahkan RSA dan kita hanya perlu menemukan salah satunya.

Salah satu cara ini adalah memfaktorkan bilangan bulat besar, jadi jika itu mudah kita bisa melakukannya dengan cara ini dan RSA rusak. Ini juga satu-satunya cara yang kita tahu. Jika tidak mungkin untuk melakukan itu, kita masih dapat menemukan cara lain, yang secara komputasi kurang menuntut untuk melakukan tugas kita tanpa perlu secara eksplisit menghitung p dan q dari n .

Untuk membuktikan RSA rusak, kita perlu membuktikan bahwa salah satu cara untuk melakukannya adalah mudah.

Untuk membuktikan RSA aman, kita perlu membuktikan bahwa semua cara untuk melakukannya sulit.

Akhirnya, pernyataan Anda tidak terbukti karena tidak terbukti bahwa tidak ada metode lain yang lebih mudah yang mengekstraksi informasi dari cyphertext.

Satu cara tambahan untuk melihatnya, adalah bahwa melanggar RSA hanya membutuhkan kasus anjak piutang khusus, yang mungkin atau mungkin tidak mudah terlepas dari pertanyaan umum mengenai anjak piutang.

$3$

Ini berarti bahwa masalah RSA tampaknya (saat ini) lebih spesifik daripada anjak piutang.

$pq$$e,$$v,$$m$$v \equiv m^e \mod pq$

Masalah anjak piutang adalah ini: mengetahui semiprime temukan dan .$pq,$$p$$q$

Jika Anda dapat secara efisien menyelesaikan masalah anjak piutang, maka Anda dapat secara efisien menyelesaikan masalah RSA: ambil semiprime, faktor, gunakan beberapa teorema tentang modulus utama untuk menghitung eksponen terbalik yang mengungkapkan semua ciphertext sebagai . (Sebenarnya teorema ini adalah bagaimana pengaturan untuk RSA bekerja: kita tahu dua bilangan prima selama fase pengaturan.)$d$$m \equiv v^d$

Namun, tidak diketahui bahwa memecahkan masalah di atas untuk pesan arbitrer akan memberi tahu Anda apa pun tentang faktor-faktor modulus atau eksponen yang terlibat. Mungkin atau mungkin tidak; kita tidak tahu. Banyak orang pintar mungkin melihat masalah ini, tetapi tidak ada yang jelas muncul di antara mereka. Jadi tidak diketahui bahwa masalah anjak diselesaikan dengan solusi untuk masalah RSA (ditambah upaya polinomial), hanya bahwa masalah RSA diselesaikan oleh solusi untuk masalah anjak piutang (ditambah upaya polinomial).$m$

Bahkan pada tahun 1998, Boneh dan Venkatesan menerbitkan bukti bahwa kelas algoritma tertentu (ditambah, kali, eksponen, tidak ada jenis barang XOR / NAND) tidak dapat digunakan untuk mengubah solusi masalah RSA menjadi algoritma anjak piutang. Argumen ini memiliki kecerdikan sederhana untuk itu: dengan memanipulasi operasi aritmatika secara matematis, kita dapat mengetahui bahwa "algoritma reduksi" (untuk presisi: ini adalah algoritma yang menggunakan "oracle" RSA untuk faktor semiprime ke faktor semiprime) berubah menjadi algoritma anjak sendiri, sehingga kita dapat memodifikasinya menjadi varian yang tidak membuat panggilan ke oracle-nya. Jadi kita memiliki trikotomi: salah satu (a) tidak ada algoritma reduksi seperti itu, atau (b) algoritma reduksi tidak memiliki interpretasi aritmatika yang bagus atau (c) anjak piutang adalah polinomial-waktu seperti halnya algoritma reduksi.

RSA tergantung pada dua tugas matematika abstrak yang diyakini sulit: bilangan bulat, seperti yang Anda tahu, tetapi juga masalah logaritma diskrit . Anda dapat memecahkan RSA jika Anda dapat dengan cepat memfaktorkan angka yang merupakan produk dari dua bilangan prima besar yang tidak diketahui; tetapi Anda juga dapat merusak RSA jika Anda dapat dengan cepat menemukan dalam grup hingga , di mana dan adalah eksponen dan modulus RSA publik, dan adalah ciphertext.$\log_e C$$\mathbb{Z}_{m}$$e$$m$$C$

Kedua tugas matematika ini saling berkaitan, tetapi (jika saya ingat dengan benar) itu diyakini bahwa solusi untuk satu tidak akan menyiratkan solusi untuk yang lain. Saya tidak tahu apakah mereka satu-satunya dua cara untuk memecahkan RSA secara matematis.