RSA-enkripsi. Deskripsi dan pelaksanaan algoritma RSA

RSA-enkripsi adalah salah satu kriptografi kunci publik pertama praktis yang banyak digunakan untuk transmisi data yang aman. Perbedaan utamanya dari layanan serupa adalah bahwa kunci enkripsi terbuka dan berbeda dari kunci dekripsi, yang dirahasiakan. Teknologi RSA , asimetri ini didasarkan pada kesulitan praktis anjak pemutaran dua bilangan prima besar (masalah anjak piutang).

Sejarah penciptaan

RSA Nama terdiri dari huruf awal nama keluarga Rivest, Shamir dan Adleman - para ilmuwan yang pertama kali secara terbuka dijelaskan ini algoritma enkripsi pada tahun 1977. Klifford Koks, seorang matematikawan Inggris, yang bekerja untuk badan intelijen Inggris, yang pertama untuk mengembangkan sebuah sistem yang setara pada tahun 1973, tetapi tidak diklasifikasikan sampai 1997

RSA pengguna menciptakan dan kemudian menerbitkan kunci publik berdasarkan dua bilangan prima besar bersama-sama dengan nilai tambahan. bilangan prima harus dirahasiakan. Siapapun dapat menggunakan kunci publik untuk mengenkripsi pesan, tetapi jika itu cukup besar, maka hanya seseorang dengan pengetahuan tentang bilangan prima dapat membaca sandi pesan. RSA enkripsi pengungkapan dikenal sebagai masalah utama saat ini adalah diskusi terbuka tentang bagaimana mekanisme yang dapat diandalkan.

Algoritma RSA relatif lambat, yang alasan itu tidak seperti yang banyak digunakan untuk langsung mengenkripsi pengguna. Dalam kebanyakan kasus, metode ini digunakan untuk transmisi dalam kunci bersama dienkripsi untuk kunci enkripsi simetris, yang pada gilirannya dapat melakukan operasi enkripsi massal dan dekripsi pada kecepatan jauh lebih tinggi.

Ketika ada cryptosystem dalam bentuk yang sekarang?

Ide kunci kriptografi asimetris dikaitkan dengan Diffie dan Hellman, yang diterbitkan konsep pada tahun 1976, memperkenalkan tanda tangan digital, dan mencoba menerapkan teori angka. formulasi mereka menggunakan kunci rahasia bersama yang dihasilkan dari sejumlah eksponensial modulo bilangan prima. Namun, mereka meninggalkan membuka masalah realisasi fungsi ini, karena prinsip-prinsip anjak piutang tidak dipahami dengan baik pada saat itu.

Rivest, Adi Shamir, dan Adleman di MIT telah melakukan beberapa upaya selama bertahun-tahun untuk membuat fungsi satu arah yang sulit untuk memecahkan kode. Rivest dan Shamir (sebagai ilmuwan komputer) telah mengusulkan banyak fungsi potensial, sementara Adleman (seperti matematika) untuk mencari "titik lemah" dari algoritma. Mereka menggunakan banyak pendekatan dan akhirnya mengembangkan sistem akhir, sekarang dikenal sebagai RSA pada bulan April 1977.

tanda tangan elektronik dan kunci publik

Digital signature atau tanda tangan elektronik, merupakan bagian integral dari jenis dokumen elektronik. Hal ini dibentuk pada perubahan data kriptografi tertentu. Dengan atribut ini mungkin untuk memeriksa integritas dari dokumen, kerahasiaannya, serta untuk menentukan siapa pemiliknya. Bahkan, sebuah alternatif untuk tanda tangan standar biasa.

cryptosystem ini (RSA-dienkripsi) menawarkan kunci publik, seperti simetris. Prinsip operasinya adalah bahwa dua kunci yang berbeda digunakan - ditutup (dienkripsi) dan outdoor. Yang pertama digunakan untuk menghasilkan tanda tangan digital dan kemudian dapat mendekripsi teks. Kedua - untuk enkripsi aktual dan tanda tangan elektronik.

Menggunakan tanda tangan untuk lebih memahami enkripsi RSA, contoh yang dapat dikurangi sebagai rahasia normal "ditutup dari mencongkel mata," dokumen.

Apa algoritma?

algoritma RSA terdiri dari empat langkah: pembangkitan kunci, distribusi, enkripsi dan dekripsi. Seperti telah disebutkan, RSA-enkripsi termasuk kunci publik dan sebuah kunci pribadi. Outdoor dapat diketahui semua dan digunakan untuk mengenkripsi pesan. Esensinya terletak pada kenyataan bahwa pesan dienkripsi dengan kunci publik hanya dapat didekripsi dalam jangka waktu tertentu menggunakan kunci rahasia.

Untuk alasan keamanan, bilangan bulat untuk dipilih secara acak dan identik dalam ukuran, tetapi berbeda panjang dengan beberapa nomor untuk membuat anjak lebih sulit. jumlah yang sama yang sama dapat secara efektif ditemukan oleh tes dalam kesederhanaan mereka, sehingga enkripsi informasi tentu harus rumit.

Kunci publik terdiri dari modulus dan eksponen publik. Indoor Unit dan terdiri dari tokoh pribadi, yang harus dirahasiakan.

enkripsi RSA file dan kelemahan

Namun, ada sejumlah hacking mekanisme RSA sederhana. Ketika enkripsi dengan rendah dan kecil nilai angka kode dapat dengan mudah dibuka, jika memilih akar ciphertext atas bilangan bulat.

Karena RSA-enkripsi adalah algoritma deterministik (yaitu, tidak memiliki komponen random), penyerang berhasil dapat memulai teks serangan terbuka yang dipilih terhadap kriptosistem dengan mengenkripsi plaintexts mungkin di bawah kunci publik dan cek apakah mereka ciphertext yang sama. Semantik cryptosystem aman disebut dalam hal penyerang tidak dapat membedakan antara dua enkripsi dari satu sama lain, bahkan jika dia tahu teks yang relevan dalam bentuk diperluas. Seperti dijelaskan di atas, RSA layanan lainnya tanpa padding tidak semantik aman.

algoritma tambahan untuk enkripsi dan perlindungan

Untuk menghindari masalah di atas, dalam pelaksanaan praktis dari RSA biasanya dimasukkan ke dalam beberapa bentuk terstruktur, mengisi acak sebelum enkripsi. Hal ini memastikan bahwa konten tidak jatuh dalam kisaran plainteks tidak aman, dan bahwa pesan ini tidak dapat diselesaikan oleh seleksi acak.

Keamanan RSA cryptosystem dan enkripsi didasarkan pada dua masalah matematika: masalah anjak jumlah besar dan masalah RSA yang sebenarnya. pengungkapan penuh dari ciphertext dan tanda tangan di RSA dianggap tidak dapat diterima pada asumsi bahwa kedua masalah ini tidak dapat diselesaikan secara kolektif.

Namun, dengan kemampuan untuk memulihkan faktor prima, penyerang dapat menghitung eksponen rahasia kunci publik dan kemudian mendekripsi teks menggunakan prosedur standar. Terlepas dari kenyataan bahwa saat ini tidak ada metode yang ada untuk anjak bilangan bulat besar pada komputer klasik tidak dapat ditemukan, itu belum terbukti bahwa ia tidak ada.

otomatisasi

Alat, yang disebut Yafu, dapat digunakan untuk mengoptimalkan proses. Otomatisasi dalam YAFU adalah fitur canggih yang menggabungkan algoritma faktorisasi dalam metodologi intelektual dan adaptif yang meminimalkan waktu untuk menemukan faktor-faktor nomor masukan sewenang-wenang. Kebanyakan implementasi multithreaded algoritma yang memungkinkan Yafu penuh penggunaan multi atau banyak prosesor multi-core (termasuk SNFS, SIQS dan ECM). Pertama-tama, itu dikendalikan oleh alat baris perintah. Waktu yang dihabiskan untuk mencari faktor enkripsi Yafu menggunakan komputer konvensional, hal itu dapat dikurangi menjadi detik 103,1746. Alat ini memproses biner kapasitas 320 bit atau lebih. Ini adalah perangkat lunak yang sangat kompleks yang memerlukan sejumlah keterampilan teknis untuk menginstal dan mengkonfigurasi. Dengan demikian, RSA-enkripsi mungkin rentan C.

Upaya hacking dalam beberapa kali

Pada tahun 2009, Bendzhamin Mudi menggunakan kunci RSA-512 bit sedang mengerjakan mengartikan kriptoteksta selama 73 hari, menggunakan perangkat lunak hanya terkenal (GGNFS) dan desktop rata-rata (dual-core Athlon64 di 1900 MHz). Seperti yang ditunjukkan oleh pengalaman, diperlukan sedikit kurang dari 5 GB disk dan sekitar 2,5 gigabyte memori untuk proses "penyaringan."

Pada 2010, jumlah terbesar adalah faktor RSA 768 bit panjang (232 angka desimal, atau RSA-768). pengungkapan nya berlangsung dua tahun di beberapa ratus komputer sekaligus.

Dalam prakteknya, kunci RSA panjang - biasanya 1024-4096 bit. Beberapa ahli percaya bahwa kunci 1024-bit dapat menjadi tidak dapat diandalkan dalam waktu dekat atau bahkan lebih lama dapat retak penyerang sangat baik yang didanai. Namun, beberapa akan berpendapat bahwa kunci 4096-bit juga dapat diungkapkan dalam waktu dekat.

prospek

Oleh karena itu, sebagai suatu peraturan, diasumsikan bahwa RSA adalah aman jika nomor tersebut cukup besar. Jika jumlah dasar 300 bit atau lebih pendek, dan tanda tangan digital ciphertext dapat diuraikan dalam beberapa jam pada komputer pribadi menggunakan perangkat lunak yang tersedia sudah dalam domain publik. Sebuah panjang kunci 512 bit, seperti yang ditunjukkan, dapat dibuka pada awal tahun 1999, dengan penggunaan beberapa ratus komputer. Saat ini adalah mungkin dalam beberapa minggu menggunakan perangkat keras yang tersedia untuk umum. Dengan demikian, adalah mungkin bahwa di buduschembudet mudah diungkapkan RSA-dienkripsi dengan jari, dan sistem akan menjadi putus asa usang.

Secara resmi pada tahun 2003, dipertanyakan keamanan kunci 1024-bit. Saat ini, dianjurkan untuk memiliki panjang minimal 2048 bit.