Pada 2 Desember 2019, mailing list teori nomor
nmbrthry@listserv.nodak.edu melaporkan
faktorisasi nomor RSA-240 (240 tempat desimal, 795 bit). Ini adalah pencapaian baru dalam teori kriptografi dan angka dan penugasan yang diselesaikan selanjutnya dari daftar
RSA Factoring Challenge .
Berikut ini jumlah dan faktor-faktornya:
RSA-240 = 124620366781718784065835044608106590434820374651678805754818788883289666801188210855036039570272508747509864768438458621054865537970253930571891217684318286362846948405301614416430468066875699415246993185704183030512549594371372159029236099 = 509435952285839914555051023580843714132648382024111473186660296521821206469746700620316443478873837606252372049619334517 * 244624208838318150567813139024002896653802092578931401452041221336558477095178155258218897735030590669041302045908071447
Berdasarkan tren saat ini, Anda dapat membayangkan kira-kira kapan RSA-1024 (309 angka desimal) dan RSA-2048 (617 angka) akan diretas.
Prestasi sebelumnya adalah
faktorisasi angka 768-bit (232 tempat desimal) pada 2009 dan
logaritma diskrit dari angka 768-bit pada 2016 .
Banyak algoritma enkripsi kunci publik bergantung pada angka yang sangat besar, yang merupakan produk dari dua bilangan prima. Lainnya bergantung pada kesulitan memecahkan beberapa masalah logaritmik diskrit. Dengan ukuran kunci yang cukup besar, tidak ada cara yang diketahui untuk memecahkan enkripsi semacam itu. Faktorisasi jumlah besar dan perhitungan logaritma diskrit menghancurkan jaminan kriptografi untuk ukuran kunci tertentu dan memaksa pengguna untuk meningkatkan jumlah bit entropi saat menghasilkan rahasia.
Cipher yang semakin canggih secara bertahap retak saat kinerja CPU tumbuh dan algoritma meningkat.
Setelah penemuan algoritma saringan angka umum (GNFS) pada awal 90-an, tidak ada yang revolusioner muncul di bidang faktorisasi bilangan bulat, meskipun beberapa optimasi signifikan dilakukan. Sebagai contoh, dalam beberapa tahun terakhir, para peneliti telah mampu mempercepat fase menemukan polinomial yang cocok.
Faktorisasi RSA-240 juga keluar dari barisan umum, karena dilakukan tidak hanya dengan meningkatkan daya komputasi, tetapi juga karena optimalisasi perangkat lunak dan algoritma. Untuk membuktikan efektivitas perubahan yang dibuat, para peneliti meluncurkan program pada peralatan yang sama yang digunakan untuk menghitung logaritma diskrit 768-bit pada tahun 2016. Mereka menemukan bahwa memilah matriks nomor 795-bit di atasnya adalah 25% lebih cepat daripada memilah matriks dari angka 768-bit tanpa optimasi.
Kelompok peneliti yang sama menghitung logaritma diskrit dengan ukuran yang sama. Untuk pertama kalinya dalam sejarah, catatan untuk logarming diskrit dan faktorisasi angka dengan ukuran yang sama ditetapkan pada waktu yang sama, dan bahkan pada perangkat keras dan lunak yang sama.
Berkat optimalisasi algoritma dan perangkat lunak, logaritma diskrit dari nomor 795-bit dipercepat sebesar 33% dibandingkan dengan logaritma angka 768-bit tanpa optimasi pada perangkat keras yang sama.
Menurut teori, logaritma angka 795-bit adalah 2,25 kali lebih rumit daripada angka 768-bit. Ini berarti bahwa efek optimisasi sebenarnya tiga kali (2,25 × 1,33 = 3).
Kedua jenis perhitungan dilakukan dengan menggunakan algoritma bidang nomor ayakan dalam program
CADO-NFS open source. Di antara optimasi - peningkatan paralelisasi dan penggunaan memori, serta banyak pekerjaan untuk menemukan parameter perhitungan yang lebih optimal (perangkat lunak khusus dikembangkan untuk menguji dan menentukan peringkat berbagai parameter perhitungan).
Jumlah waktu komputasi untuk kedua catatan baru tersebut adalah sekitar 4000 tahun pengoperasian inti fisik prosesor Intel Xeon Gold 6130 (pada frekuensi 2,1 GHz), jika prosesor ini diambil sebagai referensi.
Perincian waktu menjadi faktorisasi dan logaritma:
- Skrining RSA-240: 800 tahun inti
- RSA-240 Matrix: 100 tahun inti
- Pemutaran DLP-240: 2400 inti-tahun
- Matrix DLP-240: 700 inti-tahun
Prestasi ini dicatat dengan mengorbankan kelompok ilmiah yang dipimpin oleh Emmanuel Thomé, seorang peneliti terkemuka di
Institut Nasional Informatika dan Matematika Terapan Perancis .
Para penemu sandi RSA telah menerbitkan
nomor RSA
dari semua ukuran hingga RSA-2048. Setiap orang dapat mencoba meretasnya.
Berdasarkan tren saat ini, Anda dapat menghitung kapan RSA-1024 (309 karakter) dan RSA-2048 (617 karakter) akan diretas. Jika Anda memperkirakan jadwal, Anda mendapatkan sekitar 2031 dan 2073, masing-masing. Tetapi kami melihat bahwa optimalisasi perangkat lunak dan algoritma secara signifikan dapat membawa istilah ini lebih dekat. Mungkin RSA-2048 akan diretas selama hidup kita.
Dalam praktiknya, RSA merekomendasikan penggunaan ukuran kunci RSA minimum 2048 atau 4096 bit.
Dilihat oleh perkembangan komputer kuantum, mereka tidak akan segera mendekati kunci pemecahan ukuran ini, meskipun sulit untuk memprediksi sesuatu di sini. Pada 2012,
algoritma Shore diatasi dengan
faktorisasi 21 (3 × 7), lima bit entropi. Angka ini telah lama tetap menjadi catatan faktorisasi kuantum, tetapi pada 2018, faktorisasi produk primes
4088459 didemonstrasikan pada prosesor IBM 5- dan 16-qubit, yang sudah 22 bit.
