Apakah masalah faktorisasi bilangan bulat lebih sulit daripada faktorisasi RSA: ?

Ini adalah pos-silang dari math.stackexchange.

Biarkan FACT menunjukkan masalah anjak bilangan bulat: diberikan cari bilangan prima dan bilangan bulat sehingga $n \in \mathbb{N},$ $p_i \in \mathbb{N},$ $e_i \in \mathbb{N},$ $n = \prod_{i=0}^{k} p_{i}^{e_i}.$

Biarkan RSA menunjukkan kasus khusus masalah anjak dimana dan adalah bilangan prima. Yaitu, diberikan temukan bilangan prima atau NONE jika tidak ada faktorisasi tersebut. $n = pq$ $p,q$ $n$ $p,q$

Jelas, RSA adalah turunan dari FACT. Apakah FACT lebih sulit daripada RSA? Mengingat sebuah oracle yang memecahkan RSA dalam waktu polinomial, dapatkah ia digunakan untuk menyelesaikan FACT dalam waktu polinomial?

(Sebuah penunjuk ke literatur sangat dihargai.)

Sunting 1: Menambahkan batasan pada daya komputasi menjadi waktu polinomial.

Sunting 2: Seperti yang ditunjukkan dalam jawaban oleh Dan Brumleve bahwa ada makalah yang memperdebatkan dan menentang RSA lebih keras (atau lebih mudah daripada) FACT. Saya menemukan makalah-makalah berikut sejauh ini:

D. Boneh dan R. Venkatesan. Melanggar RSA mungkin lebih mudah daripada memfaktorkan. EUROCRYPT 1998. http://crypto.stanford.edu/~dabo/papers/no_rsa_red.pdf

D. Brown: Mematahkan RSA mungkin sesulit memfaktorkan. Cryptology ePrint Archive, Report 205/380 (2006) http://eprint.iacr.org/2005/380.pdf

G. Leander dan A. Rupp. Tentang Kesetaraan RSA dan Anjak Piutang tentang Algoritma Generik Cincin. ASIACRYPT 2006. http://www.iacr.org/archive/asiacrypt2006/42840239/42840239.pdf

D. Aggarwal dan U. Maurer. Melanggar RSA Secara Umum Setara dengan Anjak Piutang. EUROCRYPT 2009. http://eprint.iacr.org/2008/260.pdf

Saya harus melalui mereka dan menemukan kesimpulan. Apakah seseorang mengetahui hasil ini dapat memberikan ringkasan?

cc.complexity-theory reference-request np-hardness cr.crypto-security factoring Komunitas
sumber

jika saya ingat dengan benar, maka menghitung atau mencari tahu d sama dengan anjak tetapi karena itu mungkin ada beberapa cara RSA lebih lemah daripada anjak. Singkatnya penyelesaian RSA mungkin tidak menyiratkan penyelesaian masalah anjak piutang. Tidak ada bukti formal yang diketahui setara (sejauh yang saya tahu)

ϕ (n)

$\phi(n)$

singhsumit

Mohammad, mengapa FACT tidak dapat direduksikan ke RSA?

Dan Brumleve

Mungkin saya salah memahami sesuatu yang mendasar. Bagaimana menunjukkan bahwa keberadaan suatu algoritma untuk memfaktorkan semiprime dalam waktu polinomial tidak menyiratkan keberadaan suatu algoritma untuk memfaktorkan suatu bilangan dengan tiga faktor prima dalam waktu polinomial?

Dan Brumleve

Bagaimana Anda tahu itu artinya?

Dan Brumleve

Jika tidak ada pengurangan waktu-poli antara dua masalah yang dinyatakan, maka akan sulit untuk menunjukkan ini, kan? Untuk membuktikan tidak ada pengurangan waktu-poli dapat ada mengharuskan kami membuktikan .

P \neq N P

$P\neq NP$

Fixee

Jawaban:

Saya menemukan makalah ini berjudul Melanggar RSA Mungkin Lebih Mudah Dari Anjak . Mereka berpendapat bahwa komputasi th akar modulo mungkin lebih mudah daripada anjak . $e$ $n=pq$ $n=pq$

Namun, mereka tidak menjawab pertanyaan yang Anda tanyakan: mereka tidak mempertimbangkan apakah atau tidak memperhitungkan bilangan bulat dari bentuk mungkin lebih mudah daripada memfaktorkan bilangan bulat sewenang-wenang. Akibatnya, jawaban ini sangat tidak relevan dengan pertanyaan khusus Anda. $n=pq$

Dan Brumleve
sumber

Terima kasih! Saya menemukan beberapa makalah lain dengan judul terkait, referensi silang. Saya akan memposting tautan di bawah ini. (Sunting: tautan di bawah ini jelek. Saya tidak bisa mendapatkan pemformatan yang tepat dalam komentar.)

D. Boneh dan R. Venkatesan. Melanggar RSA mungkin lebih mudah daripada memfaktorkan. Eurocrypt 1998. crypto.stanford.edu/~dabo/papers/no_rsa_red.pdf D. Brown: Breaking RSA mungkin sesulit anjak piutang. Cryptology ePrint Archive, Report 205/380 (2006) eprint.iacr.org/2005/380.pdf D. Aggarwal dan U. Maurer. Melanggar RSA Secara Umum Setara dengan Anjak Piutang. EUROCRYPT 2009. eprint.iacr.org/2008/260.pdf G. Leander dan A. Rupp. Tentang Kesetaraan RSA dan Anjak Piutang tentang Algoritma Generik Cincin. ASIACRYPT 2006. iacr.org/archive/asiacrypt2006/42840239/42840239.pdf

Saya membaca abstraknya, dan makalah Aggarwal dan Maurer tampaknya tentang masalah yang sedikit berbeda (memfaktorkan semiprime vs menghitung fungsi phi?) Yang lain mengatakan secara eksplisit bahwa masalahnya terbuka. Saya kira itu masih kecuali ada hasil yang lebih baru dari tahun 2006?

Dan Brumleve

Mungkin patut disebutkan bahwa makalah Boneh dan Venkatesan adalah tentang kekerasan anjak semifrim vs kekerasan melanggar RSA. Apa yang disebut oleh pertanyaan "RSA" sebenarnya adalah masalah memfaktorkan semiprimes, yang mungkin lebih sulit daripada melanggar RSA (yang disarankan oleh makalah Boneh-Venkatesan)

Sasho Nikolov

e

$e$

n

$n$

n

$n$

n

$n$

n = p q

$n=pq$

$N$ $f$ $\lfloor N^\frac{1}{f} \rfloor$ $\frac{f N^\frac{1}{f}}{\log(N)}$ $f$ $f$ $f=2$

Selanjutnya, General Number Field Sieve , algoritma pemfaktoran klasik yang paling cepat diketahui, dan algoritma Shor, algoritma pemfaktoran kuantum waktu polinomial, bekerja dengan baik untuk non-semiprimes. Secara umum, tampaknya jauh lebih penting bahwa faktor-faktor oleh koprime daripada faktor-faktor itu menjadi prima.

Saya pikir bagian dari alasan untuk ini adalah versi keputusan dari factoring co-primes paling alami digambarkan sebagai masalah janji , dan cara apa pun untuk menghapus janji input menjadi semiprime adalah dengan

memperkenalkan pengindeksan pada semiprimes (yang dengan sendirinya saya kira sama sulitnya dengan memfaktorkannya), atau
dengan menggeneralisasikan masalah untuk memasukkan non-semiprimes.

$P\neq NP$

Terakhir, patut untuk ditunjukkan bahwa RSA (cryptosystem, bukan masalah anjak yang Anda tetapkan di atas) secara sepele menggeneralisasi di luar semi-primes.

Joe Fitzsimons
sumber

P

$P$

P \neq N P

$P \neq NP$

P^{R S A} = P^{F A C T}

$P^{RSA} = P^{FACT}$

P^{R S A} = P^{F A C T}

$P^{RSA} = P^{FACT}$

P^{R S A} \neq P^{F A C T}

$P^{RSA} \neq P^{FACT}$

F A C T \in P^{R S A} ?

$FACT \in P^{RSA}?$

F A C T \in P

$FACT \in P$

F A C T \notin P

$FACT \notin P$

F A C T \in P^{R S A}

$FACT \in P^{RSA}$

Bukan jawaban yang cukup lengkap, tetapi tampaknya merupakan peningkatan:

Makalah penelitian yang dikutip di atas membandingkan masalah komputasi et root mod N, yaitu melakukan operasi kunci privat dalam kriptografi RSA, dengan masalah anjak piutang, yaitu menemukan kunci privat, dalam kedua kasus, hanya menggunakan kunci publik. Dalam kasus ini, masalah anjak bukan kasus umum, tetapi kasus semiprime. Dengan kata lain, mereka mempertimbangkan pertanyaan yang berbeda.

Saya percaya bahwa diketahui, lihat AoCP Knuth, bahwa sebagian besar angka N memiliki faktorisasi utama yang panjang bitnya membandingkan panjang bit dengan N, rata-rata sekitar 1/2, 1/4, 1/8, ..., atau mungkin bahkan jatuh lebih tajam, seperti pada 2/3, 2/9, 2/27, ... tapi mungkin mendatar. Jadi, untuk N acak ukuran umum cukup kecil sehingga faktor-faktor yang lebih kecil dapat diharapkan ditemukan dengan cepat oleh divisi percobaan atau ECM Lenstra, maka yang tersisa mungkin semiprime, meskipun yang tidak seimbang. Ini adalah semacam reduksi, tetapi sangat bergantung pada distribusi faktor, dan ini merupakan reduksi lambat, karena ia memanggil algoritma faktorisasi lainnya.

Juga, tidak ada tes yang diketahui untuk menentukan apakah suatu angka semiprime atau tidak. Ini hanya berarti bahwa jika seseorang baru saja menerapkan algoritma faktorisasi semiprime ke nomor umum, dan selalu gagal, maka seseorang telah memecahkan masalah yang tidak diketahui.

pengguna18217
sumber

Algoritma faktorisasi harus dijalankan dalam waktu polinomial. Jadi sebenarnya Anda mengatakan "jika Anda memiliki algoritma faktorisasi poli-waktu, Anda akan memecahkan masalah yang tidak diketahui". Karena seseorang dapat menggunakan algoritma faktorisasi naif untuk mengetahui apakah suatu bilangan adalah semiprime atau tidak.

Elliot Gorokhovsky