Mengingat RSA, mengapa kita tidak tahu apakah kriptografi kunci publik dimungkinkan?

Saya berada di wikipedia pada daftar masalah ilmu komputer yang belum terpecahkan dan menemukan ini: Apakah kriptografi kunci publik mungkin?

Saya pikir enkripsi RSA adalah bentuk kriptografi kunci publik? Mengapa ini menjadi masalah?

Kami tidak tahu pasti RSA aman. Bisa jadi RSA dapat dipecah dalam waktu polinomial, misalnya jika anjak piutang dapat dilakukan secara efisien. Yang terbuka adalah keberadaan cryptosystem kunci publik yang terbukti aman . Kami tidak tahu pasti bahwa cryptosystem semacam itu ada sama sekali; yang kami tahu, setiap cryptosystem bisa rusak secara efisien.

Masalah lain yang tidak terkait dengan RSA adalah bahwa hal itu dapat dipecahkan oleh komputer kuantum. Ini adalah masalah yang tidak berhubungan karena definisi cryptosystem kunci publik yang aman hanya mensyaratkan bahwa cryptosystem tidak dapat dipecah oleh komputer klasik (non-kuantum).

Secara praktis, RSA tampaknya aman, dan digunakan sepanjang waktu. Ini disebabkan oleh kesenjangan antara teori dan praktik. Walaupun secara teoritis kita tidak tahu pasti RSA aman, secara praktis kita harus menggunakan beberapa kriptografi kunci publik, dan RSA adalah pilihan yang baik karena orang telah mencoba untuk merusaknya dan gagal. Secara umum, kriptografi yang diketahui orang peduli lebih aman daripada yang tidak jelas, karena telah menolak upaya kriptografi. Ini bukan merupakan bukti bahwa itu aman - mungkin tidak - tetapi itu yang terbaik yang bisa kita lakukan.

Berikut adalah beberapa sudut / perincian lain tentang pertanyaan ini, lebih spesifik & secara umum. Seperti YF menulis dalam sebuah komentar, meskipun ada penampilan, RSA tidak terbukti setidaknya sekeras anjak piutang. Melanggar RSA melibatkan masalah log diskrit yang tentu saja terkait erat dengan anjak dalam kompleksitas, tetapi tidak terbukti kompleksitas yang sama. Tetapi (seperti yang ditunjukkan) bahkan anjak piutang tidak terbukti sulit.

YF juga menyebutkan perhitungan kuantum. Karena orang dalam sangat menyadari, RSA tidak aman terhadap perhitungan kuantum yang terbukti mampu memperhitungkan waktu P menggunakan algoritma Shors . Algoritma Shors dianggap sebagai terobosan pada saat itu. Dan terobosan lain untuk disebutkan dalam area "terdekat" adalah algoritma primitif AKS yang membuktikan bahwa pengujian primality berada dalam P. Terobosan teoretis dalam teori kompleksitas jarang terjadi tetapi tidak pernah terjadi.

YF tidak menyebutkan, tetapi selalu mengintai di latar belakang pertanyaan-pertanyaan ini, "pertanyaan besar" dari P =? NP masih terbuka. Secara umum dianggap bahwa "algoritme algoritmik bisa mustahil" (kecuali untuk bantalan sekali pakai) jika P = NP, yang umumnya tidak dipercaya oleh para ahli.

Cara terbaik untuk membuat konsep ini secara ilmiah adalah dunia Impagliazzos 5 , tinjauan oleh Kabanets . luar biasa, para ahli teori kompleksitas tidak tahu "di mana dari 5 dunia yang kita tinggali" meskipun ada bukti tidak langsung yang condong ke beberapa cara. Dunia apa yang kita tinggali bergantung pada dugaan teori kompleksitas terbuka. Mereka juga berhubungan dengan masalah terbuka pada keberadaan fungsi pintu jebakan dan fungsi satu arah . (RSA diduga sebagai keduanya.) Ada konferensi penelitian 2009 tentang dunia Impagliazzos dengan pemikiran terbaru yang dilaporkan.

Satu hal yang perlu didefinisikan di sini adalah definisi yang mungkin. Ada dua cara untuk menjawab ini. Yang pertama adalah, dapatkah cryptosystem kunci publik dianggap aman secara informasi? Dalam arti luas ini mensyaratkan bahwa algoritma harus aman bahkan ketika mengalami serangan yang melibatkan daya komputasi tak terbatas. Ada satu sistem yang diketahui telah mencapai ini, pad satu waktu, namun ini hanya dalam teori karena kita tidak dapat membuat angka acak yang diperlukan, dan merupakan kunci privat. Cara kedua pertanyaan itu dapat dilihat adalah, dapatkah cryptosystem kunci publik dianggap aman tanpa syarat ?. Definisi kedua ini lebih longgar. Dalam kasus RSA, jika seseorang membuktikan bahwa faktorisasi bilangan bulat sama sulitnya dengan yang kita pikirkan saat ini, dan membuktikan tidak ada asumsi atau kelemahan lain dalam sistem, maka RSA akan aman tanpa syarat. Keamanan tanpa syarat menghilangkan persyaratan daya komputasi yang tak terbatas, dan menjadikannya mustahil di dunia fisik. Karena algoritma kunci publik kami semua bergantung pada asumsi besar pada kemampuan komputabilitas, mereka tidak memenuhi definisi kedua.