it-swarm-id.com

Bagaimana cara memperkirakan waktu yang diperlukan untuk memecahkan enkripsi RSA?

Bagaimana cara memperkirakan waktu yang diperlukan untuk memecahkan enkripsi RSA? Maksud saya waktu yang diperlukan untuk memecahkan enkripsi Rsa dengan panjang kunci 1024, 2048, 3072, 4096, 5120, 6144, 5120, 7168, 8192, 9216, 10240, 11264, 12288, 13312, 14336, 15360, dan 16384?

67
Predator

Lihat situs ini untuk ringkasan perkiraan kekuatan utama yang digunakan oleh berbagai peneliti dan organisasi.

"512-bit dalam 12μs" benar-benar palsu. Mari kita lihat dari mana asalnya. 1999 adalah tahun ketika faktorisasi umum 512-bit pertama dilakukan, pada tantangan yang diterbitkan oleh RSA (perusahaan) dan disebut RSA-155 (karena jumlahnya terdiri dari 155 digit desimal - dalam biner , panjangnya 512 bit). Faktorisasi itu memakan waktu 6 bulan. Pada acara Eurocrypt diselenggarakan pada tahun yang sama (pada bulan Mei; pada saat itu upaya faktorisasi 512-bit telah dimulai tetapi belum selesai), Adi Shamir , dari Weizmann Institute, mempresentasikan perangkat teoretis yang disebut TWINKLE yang, mungkin, dapat sedikit membantu dalam upaya faktorisasi. Itu harus terdiri dari sejumlah besar dioda berkedip pada frekuensi yang dipilih dengan cermat, dalam semacam tabung hitam. Shamir membawa alat khusus yang, dari jarak 10 meter, tampak seperti mesin kopi. Dia meminta orang untuk mematikan lampu, sehingga peserta Eurocrypt dapat mengagumi empat dioda merah berkedip pada interval 2, 3, 5 dan 7 detik. Ooh! dan Aah! mereka pergi, meskipun mesin yang sebenarnya, apakah itu akan dibangun, akan memerlukan beberapa juta dioda dan frekuensi dalam 10 atau 100 gigahertz. Jadi idenya menyenangkan (setidaknya bagi para peneliti kriptologi, yang dikenal memiliki selera humor yang aneh) tetapi belum melampaui langkah sketsa teoretis. Shamir adalah pemain sandiwara yang hebat.

Namun, TWINKLE hanya "membantu". Algoritma faktorisasi yang paling dikenal disebut General Number Field Sieve ; dua algoritma yang muncul berikutnya adalah Saringan Kuadratik dan Metode Kurva Elliptic . Angka 512-bit berada di luar jangkauan QS dan ECM dengan teknologi saat ini, dan fortiori dengan teknologi tahun 1999. GNFS sangat kompleks (secara matematis berbicara), terutama karena ia memerlukan seleksi cermat dari beberapa parameter kritis ("pemilihan polinomial"). Jadi harus ada upaya awal oleh otak yang sangat pintar (dengan komputer besar, tetapi otak adalah yang paling penting di sini). Setelah itu, GNFS terdiri dari dua bagian, saringan dan pengurangan linear. Saringan dapat dibuat secara paralel lebih dari ratusan atau ribuan mesin, yang masih harus relatif besar (dalam RAM), tetapi ini bisa dilakukan. Reduksi linear melibatkan komputasi hal-hal dengan matriks yang terlalu besar untuk muat di komputer (oleh beberapa urutan besarnya, dan bahkan jika kita berasumsi bahwa komputer tersebut memiliki terabytes RAM cepat). Ada algoritma untuk menjaga matriks (yang cukup jarang) dalam format terkompresi dan masih dapat menghitungnya, tetapi ini sulit. Dalam faktorisasi 512-bit, pengayakan membutuhkan sekitar 80% dari total waktu, tetapi untuk jumlah yang lebih besar pengurangan linier adalah hambatan.

TWINKLE hanya tentang mempercepat bagian pengayakan. Itu tidak melakukan apa pun tentang pengurangan linear. Dengan kata lain, itu mempercepat bagian yang mudah (relatif berbicara). Bahkan setengah pengayakan TWINKLE-ditingkatkan akan berada di dekat 12μs. Alih-alih, itu lebih baik membantu upaya penyaringan empat bulan ke, katakanlah, tiga minggu. Yang bagus, secara ilmiah, tetapi bukan pemecah rekor, terutama karena reduksi linear mendominasi untuk ukuran yang lebih besar. Sosok 12μs tampaknya berasal dari kebingungan dengan binatang yang bahkan lebih mistis, Quantum Computer , yang dapat dengan mudah faktor angka besar jika QC dengan 512 "qubit" dapat dibangun. D-Wave baru-baru ini mengumumkan komputer kuantum dengan 128 qubit, tetapi ternyata ini bukan qubit "nyata", dan mereka tidak cocok untuk faktorisasi (mereka masih dapat melakukan, secara teoritis, beberapa pendekatan efisien dalam masalah optimasi, yang sangat bagus tetapi pada dasarnya tidak berlaku untuk kriptografi, karena algoritma kriptografi tidak dapat menerima perkiraan - mereka dirancang sedemikian sehingga satu bit yang salah mengacak semuanya). QC "nyata" terbaik sejauh ini tampaknya merupakan prototipe oleh IBM dengan, sejauh yang saya ingat, memiliki 5 qubit, memungkinkannya untuk menetapkan bahwa 15 sama dengan 3 kali 5.

Catatan faktorisasi RSA saat ini adalah untuk bilangan bulat 768-bit , diumumkan pada bulan Desember 2009. Butuh empat tahun dan melibatkan sejumlah ahli teori paling cerdas yang saat ini hidup di Bumi, termasuk Lenstra dan Montgomery, yang agaknya memiliki suka status di lingkaran itu. Baru-baru ini saya mengetahui bahwa pemilihan parameter untuk faktorisasi angka 1024-bit telah dimulai (itulah bagian "cerdas"); pengayakan secara teknis layak (itu akan mahal dan melibatkan waktu komputasi bertahun-tahun pada banyak cluster universitas) tetapi, untuk saat ini, tidak ada yang tahu bagaimana melakukan bagian pengurangan linear untuk integer 1024-bit. Jadi jangan berharap istirahat 1024-bit dalam waktu dekat.

Saat ini, seorang amatir yang berdedikasi menggunakan kode yang diterbitkan (mis. Msieve ) dapat mencapai faktorisasi 512-bit jika ia memiliki akses ke komputer yang kuat (beberapa lusinan PC besar, dan setidaknya satu jam penuh RAM cepat) ) dan beberapa bulan waktu luang; pada dasarnya, "amatir yang berdedikasi" berarti "mahasiswa ilmu komputer yang bosan di universitas yang kaya". Apa pun yang melebihi 512 bit berada di luar jangkauan seorang amatir.

Ringkasan: dalam kode Anda, Anda dapat mengembalikan "praktis tak terbatas" sebagai waktu cracking untuk semua panjang kunci. Pengguna biasa tidak akan merusak kunci RSA 1024-bit, tidak sekarang dan tidak dalam sepuluh tahun. Ada sekitar selusin orang di Bumi yang dapat, dengan kredibilitas apa pun, mengklaim bahwa itu dapat dibayangkan, dengan probabilitas rendah tetapi tidak nol, bahwa mereka mungkin dapat memperhitungkan 1024- tunggal. bit integer pada waktu yang tidak ditentukan sebelum tahun 2020.

(Namun, sangat mudah untuk merusak implementasi RSA atau aplikasi apa pun yang menggunakan RSA sedemikian rupa sehingga data rahasia apa yang dipegangnya dapat dipulihkan tanpa repot dengan kunci RSA sama sekali. Jika Anda menggunakan kunci RSA 1024-bit, Anda dapat yakin bahwa ketika aplikasi Anda akan diretas, itu tidak akan melalui faktorisasi kunci RSA.)

90
Thomas Pornin

Jawaban singkat : Metode termudah adalah dengan menggunakan teorema bilangan prima , tetapi perlu diketahui bahwa ini merupakan perkiraan. Perkirakan berapa lama waktu yang Anda butuhkan untuk mencoba masing-masing bilangan prima itu; waktu per prima * jumlah bilangan prima memberi Anda total waktu. Ini akan memberi Anda perkiraan untuk pencarian brute force.

Anda juga dapat menggunakan estimasi waktu berjalan untuk ayakan kuadrat atau ayakan bidang bilangan umum . Ini akan memberi Anda perkiraan untuk algoritma anjak piutang yang sebenarnya digunakan oleh orang yang melanggar angka RSA.

Latar belakang panjang :

Waktu teori bilangan!

Pertama, mari kita lihat ukuran angka yang Anda bicarakan. Diberikan 2 ^ 3 = 8, yang merupakan 1000 dalam biner, kita dapat melihat ini adalah angka empat bit, jumlah minimum yang dimungkinkan. Jadi, 2 ^ 2 = 4 adalah angka 3 bit (100). Jadi untuk x yang diberikan, nilai minimum yang mungkin untuk memastikan kami memiliki bit yang cukup adalah 2 ^ (x-1). 2 ^ 2047 = 16158503035655503650357438344334975980222051334857742016065172713762327569433945446598600705761456731844358980460949009747059779575245460547544076193224141560315438683650498045875098875194826053398028819192033784138396109321309878080919047169238085235290822926018152521443787945770532904303776199561965192760957166694834171210342487393282284747428088017663161029038902829665513096354230157075129296432088558362971801859230928678799175576150822952201848806616643615613562842355410104862578550863465661734839271290328348967522998634176499319107762583194718667771801067716614802322659239302476074096777926805529798115328. Itulah ukuran nomor Anda sedang berhadapan dengan di sini, yaitu ukuran n diperhitungkan.

Pertanyaan besar selanjutnya adalah bagaimana n dibangun? n=pq Seperti yang Anda ketahui dari definisi RSA, jadi Anda mencari dua bilangan prima sebagai faktor dari angka itu. Pertanyaannya kemudian menjadi bagaimana kita menentukan angka adalah prima dan dapatkah kita menghitungnya?

Jadi, menurut definisi, angka tidak dapat direduksi jika, untuk nomor apa pun x kurang dari itu, \gcd(p, x) = 1 dengan pengecualian x=1. Namun, kita dapat memperbaiki itu. Anda harus segera menyadari bahwa untuk nomor berapa pun, itu prima atau tidak. Jika tidak prima, maka gcd itu dan setidaknya satu prima harus lebih besar dari 1 (kalau tidak itu akan prima). Kami menyimpulkan dari sini bahwa bilangan bulat non-prima harus dapat dibagi oleh sekumpulan bilangan prima. Bukti matematis formal sebenarnya bukan lompatan besar dari sini.

Ini disebut teorema mendasar aritemik dan sedikit menyederhanakan masalah. Jadi sekarang, ketika berolahraga jika angka adalah prima, kita tidak perlu lagi mencoba setiap angka, hanya angka yang sudah kita tahu prima!

Ini jelas masih sangat lambat, jadi mari kita amati lagi - mengingat faktor terjadi berpasangan, yang paling rendah dari dua angka paling banyak adalah akar kuadrat dari angka tersebut. Jika kita terbatas pada N (himpunan bilangan alami) itu merupakan batas atas pada nilai terbesar yang mungkin perlu kita periksa. Jadi sekarang, untuk setiap angka N, kita harus mencari setiap bilangan bulat mulai dari 2 dan menuju ke sqrt (N) untuk setiap nomor yang kita tentukan sebagai prima dalam daftar itu. Kita dapat, jika kita menemukan yang utama, menyimpulkan apakah itu faktor N itu sendiri. Saya tidak akan memperkirakan jangka waktu itu karena saya pasti akan mengatakan hal yang salah, tetapi itu akan memakan waktu lama.

Sekarang Anda melihat kekuatan RSA. Pilih perdana yang sangat besar dan Anda memiliki jalan yang panjang. Seperti saat ini berdiri, kita harus mulai dari 2, yang jelas mengerikan.

Primality testing bertujuan untuk meningkatkan yang menggunakan berbagai teknik. Metode naif adalah yang baru saja kita diskusikan. Saya pikir diskusi terperinci tentang teknik-teknik ini mungkin lebih tepat untuk Matematika, jadi izinkan saya meringkasnya: semua runtime adalah sampah dan menggunakan ini sebagai cara untuk menghitung bilangan prima akan sangat menghebohkan.

Jadi, kita tidak dapat menghitung jumlah bilangan prima dengan andal kurang dari bilangan tanpa mengambil selamanya, karena ini secara efektif analog dengan factorisation bilangan. Bagaimana dengan fungsi yang entah bagaimana menghitung bilangan prima dengan cara lain?

Masukkan \pi(n) = \frac{n}{\log(n) - 1.08366}, satu percobaan di Prime Number Theorem perkiraan ke jumlah bilangan prima. Namun demikian, persis seperti itu; tujuan dari fungsi tersebut adalah untuk menghitung jumlah bilangan prima secara tepat tetapi saat ini hanya memberi Anda perkiraan. Untuk keperluan Anda, ini bisa dianggap cukup baik.

Namun, ini benar-benar masih merupakan perkiraan. Lihatlah sisa artikel ini. Antara lain, estimasi lain bergantung pada Hipotesis Riemann.

Ok, jadi, bagaimana dengan factoration integer ? Nah, metode terbaik kedua sampai saat ini disebut Saringan Kuadratik dan yang terbaik disebut saringan bidang bilangan umum . Kedua metode ini menyentuh beberapa matematika yang cukup maju; dengan asumsi Anda serius tentang faktor bilangan prima saya akan membaca ini. Tentu saja Anda harus dapat menggunakan estimasi untuk keduanya sebagai perbaikan untuk menggunakan teorema bilangan prima, karena jika Anda akan menentukan faktor bilangan prima besar, Anda ingin menggunakan ini dan bukan pencarian brute force.

Tapi saya ingin tahu tentang kuantum?

OK cukup adil. Factorisasi integer pada komputer kuantum dapat dilakukan dalam waktu yang sangat singkat dengan asumsi kita akan dapat mengimplementasikan Algoritma Shor . Saya harus menunjukkan, bagaimanapun, ini membutuhkan komputer kuantum. Sejauh yang saya ketahui, pengembangan komputer kuantum skala yang dapat memecahkan RSA saat ini masih jauh. Lihat perkembangan komputasi kuantum .

Bagaimanapun, Algoritma Shor akan secara eksponensial lebih cepat. Halaman di atasnya memberi Anda perkiraan untuk jangka waktu itu, yang mungkin ingin Anda sertakan dalam perkiraan Anda.

25
user2213

Pilihan lain adalah membuat database besar kunci yang mungkin dan menggunakannya sebagai tabel pencarian. Tampaknya Anda bahkan tidak membutuhkan SEMUA bilangan prima, hanya beberapa yang akan membantu Anda melalui persentase besar lalu lintas internet.

Sumber: https://freedom-to-tinker.com/blog/haldermanheninger/how-is-nsa-breaking-so-much-crypto/

0
Evgeny