Istilah yang terkenal "prestasi pemproses" ialah parameter objektif yang dikira yang diukur dalam flop. Walau bagaimanapun, kebanyakan orang mengukurnya dalam gigahertz, secara naif mempercayai bahawa mereka adalah perkara yang sama. Tiada siapa yang tahu istilah "prestasi kod", dan saya akan segera menerangkan sebabnya.

Alasannya ialah saya baru sahaja menciptanya dan belum memberitahu sesiapa mengenainya lagi. Walau bagaimanapun, prestasi kod, seperti prestasi pemproses, mempunyai ciri objektif yang boleh diukur. Artikel ini khusus mengenai prestasi kod yang dilaksanakan oleh teras pemproses.

Bagaimanakah prestasi kod diukur? Memandangkan saya adalah orang pertama yang bercakap tentang perkara ini, dengan hak penemu saya akan mengukurnya dalam unit RTT;).

Sekarang dengan serius. Dalam pemproses moden, transformasi utama adalah operasi pada nombor 32-bit; semua yang lain, pada umumnya, eksotik. Oleh itu, kami akan mengambil kira perkara utama - operasi dengan nombor 32-bit. Berapa banyak operasi 32-bit yang anda fikir teras pemproses moden boleh dilakukan secara serentak?

Pelajar akan menjawab - satu, gurunya akan berfikir dan mengatakan bahawa terdapat empat, profesional - bahawa hanya terdapat dua belas operasi setakat ini.

Jadi, kod program yang memuatkan semua unit pelaksanaan pemproses secara serentak sepanjang keseluruhan masa pelaksanaan kod akan mempunyai prestasi sebanyak 12 RTT. maksimum! Sejujurnya, saya tidak pernah menulis kod sedemikian sebelum ini, tetapi dalam artikel ini saya akan cuba membuat usaha.

Saya akan membuktikan bahawa kod dengan pelaksanaan serentak dua belas operasi 32-bit adalah mungkin

Kod program yang menggunakan satu penggerak dalam teras pemproses secara semula jadi akan mempunyai prestasi 1 RTT. Program yang dihasilkan oleh penyusun bahasa peringkat tinggi dan jurubahasa mesin maya boleh berbangga dengan prestasi kod tersebut. Tidak perlu menganggap bahawa penunjuk beban pemproses, yang boleh dilihat dalam pengurus tugas OS, boleh berfungsi sebagai kriteria objektif untuk kecekapan kod. Beban teras pemproses boleh menjadi 100%, tetapi kod program akan menggunakan satu unit pelaksanaan di dalamnya (prestasi 1 RTT). Dalam kes ini, pada beban 100%, teras pemproses akan beroperasi pada 1/12 daripada prestasi maksimumnya. Dalam erti kata lain, apabila Pengurus Tugas Windows menunjukkan beban pemproses maksimum, prestasi sebenar mungkin berbeza dari 1 hingga 12 RTT. Jika anda melihat beban 100% pada mana-mana teras pemproses dalam tetingkap prestasi, adalah salah untuk menganggap bahawa semua penggerak berfungsi dalam teras ini, tidak sama sekali!

Satu-satunya kriteria untuk menilai secara tidak langsung operasi teras pemproses pada prestasi maksimum ialah penggunaan kuasanya dan, sebagai akibatnya, bunyi penyejuk. Sekarang, jika penyejuk itu bising, maka ya, beban telah pergi ke maksimum. Walau bagaimanapun, sudah tiba masanya untuk menyelesaikan dengan konsep umum dan beralih kepada amalan keras.

Pelaksanaan tradisional GOST 28147-89

Saya bukan profesional dalam bidang keselamatan maklumat, tetapi saya masih biasa dengan topik penyulitan. Saya telah diilhamkan untuk mengkaji penyulitan aliran simetri secara khusus melalui perbualan dengan seorang kriptografi profesional yang amat saya hormati. Dan, setelah mengambil topik ini, saya cuba melakukannya dengan baik, dan bukan hanya dengan baik, tetapi juga dengan cepat, melaksanakan bilangan maksimum operasi setiap unit masa. Dengan kata lain, saya berhadapan dengan tugas menulis kod program dengan nilai RTT maksimum.

Transformasi kriptografi mengikut GOST 28147-89 digunakan untuk penyulitan aliran maklumat dalam saluran komunikasi dan pada pemacu cakera.

Pada masa ini, pelaksanaan perisian GOST ini pada RON pemproses pusat digunakan secara meluas. Dalam kaedah yang diketahui untuk melaksanakan GOST, semua maklumat rahsia (kunci penyulitan, blok gantian) terletak dalam RAM. Ini mengurangkan kebolehpercayaan penyulitan, kerana mempunyai pembuangan RAM boleh mendedahkan sepenuhnya semua elemen rahsia transformasi kripto. Di samping itu, kaedah ini mempunyai had prestasi kerana lokasi objek penukaran crypto utama dalam OP dan pemuatan unit eksekutif ALU yang tidak lengkap. Pemproses moden, melaksanakan prosedur crypto menggunakan kaedah yang terkenal, boleh memberikan kelajuan penyulitan 40-60 megabait sesaat. Dan jika kita benar-benar memahaminya hingga akhir, sebab prestasi rendah dan keselamatan penukaran crypto yang lemah adalah pelaksanaan perisian blok penggantian. Untuk penerangannya dalam GOST, lihat Rajah. 1.

Menurut klausa 1.2 GOST, blok ini melaksanakan pilih atur tetrad (empat bit) dalam perkataan 32-bit, tetapi seni bina pemproses x86/64 dan sistem arahannya tidak mampu memanipulasi tetrad dengan berkesan.

Untuk pelaksanaan perisian blok penggantian, jadual khas dalam RAM digunakan, disediakan pada peringkat permulaan fungsi kripto. Jadual ini menggabungkan nod gantian tetrad bersebelahan ke dalam jadual bait 8 × 8-bit, sekali gus meletakkan empat jadual 256-bait dalam RAM.

Dalam pelaksanaan yang lebih maju, jadual ini bersaiz 1024 bait (256 perkataan daripada empat bait). Ini dilakukan untuk melaksanakan dalam jadual peralihan kitaran tambahan sebanyak 11 kedudukan perkataan 32-bit yang diperoleh hasil daripada penggantian (operasi seterusnya algoritma penukaran mengikut GOST). Contoh pelaksanaan GOST menggunakan kaedah ini ditunjukkan dalam Lampiran 1 (pada cakera).

Maklumat blok penggantian adalah komponen rahsia fungsi kripto (seperti yang dirumuskan dalam GOST, lihat Rajah 2).

Meletakkan jadual ini dengan kekunci blok penggantian dalam OP bercanggah dengan keperluan GOST (klausa 1.7), kerana maklumat rahsia tersedia untuk program pihak ketiga yang dijalankan pada pemasangan pengkomputeran. FSB, yang juga memperakui pelaksanaan perisian penyulitan mengikut GOST, melihat pelanggaran ini, secara sederhana, merendahkan. Jika, untuk meletakkan kunci dalam OP, FSB masih memerlukan "daun ara" - menutup kunci menggunakan operasi XOR, maka tiada apa yang diperlukan untuk blok penggantian dalam OP; ia disimpan dalam bentuk yang jelas.

Ringkasnya, FSB membenarkan pelaksanaan perisian kriptoprosedur sedemikian berlalu, walaupun terdapat penurunan jelas dalam keselamatan penyelesaian sedemikian dan pelanggaran langsung terhadap keperluannya sendiri mengikut GOST (klausa 1.7). Dan ini walaupun terdapat kaedah yang terkenal untuk memecahkan sifir dengan mengambil tempat pembuangan memori...

Kami akan kembali kepada isu menyimpan kunci dan blok penggantian dalam daftar dalaman pemproses sedikit kemudian (ada penyelesaian yang cantik dan pantas), tetapi buat masa ini kami hanya akan menyimpan kunci penyulitan dalam daftar MMX, ini lebih dipercayai.

Tetapi cukup dengan lirik, apa yang penting untuk topik yang sedang dipertimbangkan ialah kod program ini mempunyai prestasi 1 RTT. Sekarang mari kita tulis kod dengan prestasi 2 RTT.

Pelaksanaan berbilang benang GOST 28147-89

Satu-satunya cara untuk mempercepatkan prosedur crypto dalam algoritma yang diketahui adalah dengan memperkenalkan multithreading. Titik perubahan dalam pelaksanaan algoritma ini adalah untuk mengira beberapa blok data secara selari.

Kebanyakan pengaturcara bermaksud dengan pemprosesan selari secara eksklusif kerja beberapa teras pemproses, disegerakkan melalui gangguan dan semaphore dalam ingatan.

Walau bagaimanapun, terdapat pilihan lain untuk pemprosesan data selari pada teras pemproses tunggal. Biar saya jelaskan idea yang tidak jelas ini.

Pemproses moden termasuk sekurang-kurangnya dua, malah tiga hingga enam unit logik aritmetik. ALU ini (FPU, unit aritmetik alamat, dan sebagainya) boleh beroperasi secara bebas antara satu sama lain satu-satunya syarat untuk operasi selarinya ialah objek perisian yang mereka kendalikan tidak bersambung. Dalam erti kata lain, dalam arahan yang melaksanakan ALU secara serentak, alamat memori dan nombor daftar mestilah berbeza. Atau, tiada penulisan harus dilakukan kepada daftar kongsi dan alamat memori yang diakses oleh pelbagai unit pelaksanaan pemproses.

Beban kerja semua ALU dikawal oleh unit perkakasan khas di dalam teras pemproses - penjadual, yang mengimbas kod boleh laku ke hadapan, ke kedalaman 32–64 bait. Jika penjadual menemui arahan yang boleh dijalankan pada ALU tanpa konflik, maka ia menjalankannya secara serentak pada peranti pelaksanaan yang berbeza. Dalam kes ini, kaunter arahan yang dilaksanakan menunjukkan arahan yang dilaksanakan (terdapat beberapa daripadanya dalam skema sedemikian), selepas itu semua arahan telah dilaksanakan.

Kebanyakan jujukan program yang dijana secara automatik (oleh pengkompil) tidak boleh memuatkan semua ALU dan FPU yang terletak dalam teras pemproses. Dalam kes ini, perkakasan pemproses melahu, yang dengan ketara mengurangkan prestasi yang terhasil. Pembangun pemproses memahami perkara ini dan memperkenalkan mod untuk meningkatkan kekerapan teras apabila perkakasan tidak digunakan sepenuhnya. Untuk ini juga sistem hypertrading direka bentuk, dan saya akan menggunakan sistem ini untuk "menekan" kod secara maksimum pada masa hadapan.

Penyusun, walaupun yang paling dioptimumkan, dan lebih-lebih lagi enjin mesin maya, tidak dapat menjana kod yang dioptimumkan dari segi prestasi. Hanya pengaturcara yang mempunyai pengetahuan kejuruteraan boleh menulis kod yang dioptimumkan sedemikian, dan alat untuk menulisnya adalah pemasang secara eksklusif.

Ilustrasi tipikal tentang kemungkinan melaksanakan beberapa utas program bebas pada satu teras pemproses ialah pelaksanaan GOST, dilaksanakan dalam dua utas pada teras pemproses tunggal. Idea kod itu mudah: terdapat dua blok data untuk menyulitkan/menyahsulit, tetapi satu teras pemproses yang akan melakukan penukaran. Adalah mungkin untuk melakukan penukaran pada dua blok data ini secara berurutan, dan ini telah dilakukan sehingga hari ini. Dalam kes ini, masa yang diperlukan untuk menyelesaikan transformasi berganda.

Tetapi anda boleh melakukannya secara berbeza: arahan ganti yang berkaitan dengan pemprosesan blok data yang berbeza. Pilihan ini dibentangkan secara grafik dalam Rajah. 3.

Dalam rajah, contoh teratas menunjukkan susunan biasa pemprosesan dua blok bebas data. Blok pertama diproses terlebih dahulu, kemudian pemproses meneruskan untuk memproses blok kedua. Sememangnya, masa yang terhasil adalah sama dengan dua kali masa yang diperlukan untuk memproses satu blok, dan penggerak teras pemproses tidak dimuatkan sepenuhnya.

Berikut ialah contoh perintah interleaving daripada benang pemprosesan yang berbeza. Dalam kes ini, arahan yang berkaitan dengan blok data yang berbeza dijalin. Penjadual memilih arahan yang bebas antara satu sama lain dan menghantarnya untuk pelaksanaan kepada ALU1 dan ALU2. Pengumpulan perintah bagi utas pertama dan kedua pada ALU ini dijalankan secara automatik, kerana algoritma pengendalian penjadual termasuk kumpulan perintah yang dipautkan kepada data biasa pada peranti eksekutif yang sama.

Agar kod program sedemikian berfungsi tanpa masa henti ALU, setiap utas program perlu berfungsi dengan set daftarnya sendiri. Cache dalam skema ini menjadi hambatan (ia hanya mempunyai dua port output data), jadi kami menyimpan kunci dalam daftar MMX. Oleh kerana dalam kes ini, nod penggantian (dan anjakan) dalam ingatan hanya dibaca, ia boleh menjadi perkara biasa kepada kedua-dua utas program.

Ini, tentu saja, adalah penjelasan yang sangat mudah tentang prinsip pelaksanaan selari utas program pada satu teras pada hakikatnya, semuanya jauh lebih rumit. Dalam amalan, anda perlu mengambil kira seni bina saluran paip penggerak, sekatan pada akses serentak ke cache dan blok daftar RON, kehadiran nod aritmetik alamat, suis dan banyak lagi... Jadi ini adalah topik untuk profesional, yang boleh dikira dengan jari... dengan sebelah tangan.

Kaedah penyulitan selari dilaksanakan dengan berkesan hanya untuk mod operasi pemproses 64-bit, kerana dalam mod ini terdapat bilangan RON yang mencukupi (sebanyak 16 keping!). Contoh pelaksanaan GOST menggunakan kaedah ini ditunjukkan dalam Lampiran 2 (pada cakera).

Jelas bahawa pelaksanaan GOST ini mempunyai prestasi kod 2 kod RTT. Sekarang mari kita lihat bagaimana ini mempengaruhi masa pelaksanaan.

Kitaran penyulitan untuk satu utas (Lampiran 1) ialah 352 kitaran jam, dan pada masa ini 8 bait data dikira untuk pelaksanaan dua utas GOST (Lampiran 2) 416 kitaran pemproses diperlukan, tetapi 16 bait dikira. Oleh itu, kelajuan penukaran yang terhasil meningkat daripada 80 kepada 144 megabait untuk pemproses 3.6 GHz.

Gambar yang menarik muncul: kod itu mengandungi tepat dua kali lebih banyak arahan, dan melaksanakan hanya 15% lebih lama, tetapi saya fikir pembaca telah memahami sebab fenomena ini...

Secara teorinya, kod daripada contoh kedua harus dilaksanakan dalam bilangan kitaran yang sama seperti kod daripada contoh pertama, tetapi nod penjadual dibangunkan oleh jurutera Intel, tetapi mereka juga manusia, dan kita semua jauh dari sempurna. Oleh itu, adalah mungkin untuk menilai keberkesanan penciptaan mereka. Kod ini juga akan dijalankan pada pemproses AMD, dan anda boleh membandingkan hasilnya.

Jika sesiapa tidak mengambil kata-kata saya untuk itu, maka bagi orang yang tidak percaya itu, program ujian dengan pembilang jam disertakan pada cakera. Atur cara berada dalam kod sumber, secara semula jadi dalam pemasang, jadi ada peluang untuk menyemak kata-kata saya, dan pada masa yang sama, lihat beberapa helah pengekodan profesional.

Menggunakan daftar SSE dan arahan AVX pemproses moden untuk melaksanakan GOST 28147-89

Pemproses moden seni bina x86/64 termasuk satu set daftar SSE bersaiz 16 bait dan FPU khusus (sekurang-kurangnya dua) untuk melaksanakan pelbagai operasi pada daftar ini. Adalah mungkin untuk melaksanakan GOST pada peralatan ini, dan dalam kes ini, nod penggantian boleh diletakkan bukan dalam bentuk jadual dalam RAM, tetapi secara langsung pada daftar SSE khusus.

Satu daftar SSE boleh memuatkan dua jadual 16 baris sekaligus. Oleh itu, empat daftar SSE akan memuatkan sepenuhnya semua jadual gantian. Satu-satunya syarat untuk peletakan sedemikian ialah keperluan interleaving, mengikut mana tetrad bait yang sama mesti diletakkan dalam daftar SSE yang berbeza. Di samping itu, adalah dinasihatkan untuk meletakkan tetrad rendah dan tinggi bagi bait input, masing-masing, dalam tetrad rendah dan tinggi bagi bait daftar SSE.

Keperluan ini ditentukan oleh pengoptimuman untuk set arahan AVX sedia ada. Oleh itu, setiap bait daftar SSE akan mengandungi dua tetrad yang sepadan dengan bait berlainan bagi daftar input blok penggantian, manakala kedudukan bait dalam daftar SSE secara unik sepadan dengan indeks dalam jadual penggantian blok penggantian.

Gambar rajah salah satu kemungkinan penempatan nod gantian pada daftar SSE ditunjukkan dalam Rajah. 4.

Meletakkan maklumat rahsia nod gantian pada daftar SSE meningkatkan keselamatan prosedur kripto, tetapi pengasingan lengkap maklumat rahsia ini mungkin jika syarat berikut dipenuhi:

• Teras pemproses ditukar kepada mod hos hipervisor, dan blok gangguan (APIC) dilumpuhkan secara paksa di dalamnya. Dalam kes ini, teras pemproses diasingkan sepenuhnya daripada OS dan aplikasi yang dijalankan pada pemasangan pengkomputeran.
• Daftar SSE dimuatkan dan teras pengkomputeran diasingkan sebelum OS bermula; adalah optimum untuk melaksanakan prosedur ini daripada modul but dipercayai (TLM).
• Program untuk prosedur kripto mengikut GOST terletak di kawasan memori yang tidak boleh diubah suai pemasangan pengkomputeran (sama ada BIOS atau dalam memori kilat MDZ).

Pematuhan terhadap keperluan ini akan memastikan pengasingan lengkap dan kebolehubahan kod program prosedur kripto dan maklumat rahsia yang digunakan di dalamnya.

Untuk pensampelan yang cekap bagi daftar tetrad SSE, suis bait berbilang input yang disertakan dalam blok FPU digunakan. Suis ini membenarkan pemindahan dari mana-mana bait sumber ke mana-mana bait destinasi, menggunakan indeks yang terdapat dalam daftar indeks SSE khas. Selain itu, pemindahan dilakukan secara selari untuk semua 16 bait daftar penerima SSE.

Mempunyai nod storan penggantian pada daftar SSE dan suis berbilang input dalam blok FPU, adalah mungkin untuk mengatur transformasi berikut dalam blok penggantian (Rajah 5).

Dalam skema ini, daftar input dalam setiap tetrad menentukan alamat untuk suis yang sepadan, yang menghantar maklumat daripada pemacu nod gantian ke daftar keluaran melalui bas data. Skim ini boleh dianjurkan dalam tiga cara:

• Cipta reka bentuk cip yang sesuai, tetapi ini hebat untuk kami.
• Memprogram semula mikrokod dan mencipta arahan pemproses anda sendiri untuk melaksanakan fungsi ini pada pemproses sedia ada bukan lagi fantasi, tetapi, malangnya, ia tidak realistik dalam keadaan semasa.
• Tulis program menggunakan arahan AVX rasmi. Pilihan itu mungkin tidak begitu berkesan, tetapi ia boleh dilaksanakan "di sini dan sekarang." Jadi itulah yang akan kita lakukan seterusnya.

Operasi suis dikawal oleh arahan khas tiga alamat AVX VPSHUFB. Operan pertamanya ialah penerima maklumat daripada suis, yang kedua ialah sumber di mana input suis disambungkan. Operan ketiga ialah daftar kawalan untuk suis, setiap baitnya dikaitkan dengan suis yang sepadan; nilai di dalamnya menentukan bilangan arah dari mana suis membaca maklumat. Untuk penerangan arahan ini daripada dokumentasi Intel rasmi, lihat Rajah. 5. Dalam Rajah. Rajah 6 menunjukkan rajah bagaimana arahan ini berfungsi - hanya separuh daripada daftar SSE ditunjukkan, untuk separuh kedua semuanya adalah serupa.

Suis hanya menggunakan empat bit terendah untuk menentukan arah pertukaran, bit terakhir dalam setiap bait digunakan untuk memaksa bait penerima yang sepadan kepada sifar, tetapi fungsi suis ini belum lagi diperlukan dalam kes kami.

Program untuk pensampelan tetrad melalui suis FPU telah ditulis, tetapi saya tidak meletakkannya dalam aplikasi - ia terlalu menyedihkan. Mempunyai daftar 128-bit dan hanya menggunakan 32 bit di dalamnya adalah tidak profesional.

Seperti yang mereka katakan, "Garisan penamat kami adalah ufuk," jadi picit keluar, picit keluar... kami akan tekan dan masukkan ke dalam beg!

Ini bukan permainan kata, tetapi realiti FPU yang keras - daftar SSE boleh dibahagikan kepada bahagian yang sama dan transformasi yang sama boleh dilakukan pada bahagian ini dengan satu arahan. Agar pemproses memahami perkara ini, terdapat huruf ajaib "P" - paket yang diletakkan sebelum mnemonik perintah, dan tidak kurang huruf ajaib "Q", "D", "W", "B", yang diletakkan di penghujung dan mengisytiharkan Bahagian manakah yang dibahagikan kepada daftar SSE dalam arahan ini?

Kami berminat dengan mod kelompok dengan daftar SSE dibahagikan kepada empat blok 32-bit; sewajarnya, semua arahan akan diawali dengan "P" dan pada akhir dengan simbol "D". Ini memungkinkan untuk memproses empat blok 32-bit secara selari dengan satu perintah pemproses, iaitu mengira empat blok data secara selari.

Program yang melaksanakan kaedah ini tersedia dalam Lampiran 3, dengan semua penjelasan di sana.

Walau bagaimanapun, tekan begitu banyak! Pemproses moden mempunyai sekurang-kurangnya dua FPU, dan dua utas arahan bebas boleh digunakan untuk memuatkannya sepenuhnya. Jika anda menukar arahan dengan betul daripada urutan bebas, anda boleh memuatkan kedua-dua blok FPU dengan kerja sepenuhnya dan mendapatkan lapan aliran data diproses selari sekaligus. Program sedemikian telah ditulis, dan ia boleh dilihat dalam Lampiran 4, tetapi anda perlu menontonnya dengan teliti - anda boleh menjadi gila. Inilah yang dipanggil "kod itu bukan untuk semua orang...".

Harga terbitan

Penggunaan daftar SSE untuk menyimpan nod gantian boleh difahami - ia menyediakan beberapa jaminan pengasingan maklumat rahsia, tetapi maksud mengira fungsi kripto itu sendiri pada FPU tidak jelas. Oleh itu, masa pelaksanaan prosedur standard diukur menggunakan kaedah penggantian langsung mengikut GOST untuk empat dan lapan benang.

Untuk empat utas, kelajuan pelaksanaan sebanyak 472 kitaran pemproses diperolehi. Oleh itu, untuk pemproses dengan frekuensi 3.6 GHz, satu utas dikira pada kelajuan 59 megabait sesaat, dan empat utas, masing-masing, pada kelajuan 236 megabait sesaat.

Untuk lapan utas, kelajuan pelaksanaan sebanyak 580 kitaran pemproses diperolehi. Oleh itu, untuk pemproses 3.6 GHz, satu benang dikira pada 49 megabait sesaat dan lapan benang pada 392 megabait sesaat.

Seperti yang pembaca boleh lihat, kod dalam contoh #3 mempunyai prestasi 4 RTT, dan kod dalam contoh #4 mempunyai prestasi 8 RTT. Dalam contoh pada daftar SSE ini, corak adalah sama seperti semasa menggunakan RON, hanya penjadual telah mengurangkan kecekapannya. Ia pada masa ini menyediakan peningkatan 20% dalam tempoh sambil menggandakan panjang kod.

Selain itu, keputusan ini diperoleh menggunakan arahan AVX universal yang tersedia dalam kedua-dua pemproses Intel dan AMD. Jika anda mengoptimumkan pemproses AMD, hasilnya akan menjadi lebih baik. Bunyinya bertentangan dengan trend, tetapi ia adalah benar, dan inilah sebabnya: Pemproses AMD mempunyai set arahan tambahan, sambungan XOP yang dipanggil, dan dalam set arahan tambahan ini terdapat arahan yang memudahkan pelaksanaannya dengan ketara. Algoritma GOST.

Ini merujuk kepada perintah untuk anjakan bait pecah logik dan anjakan kitaran pecah bagi kata ganda. Dalam contoh yang diberikan dalam Lampiran 3 dan 4, urutan perintah universal digunakan yang melaksanakan transformasi yang diperlukan: dalam kes pertama, satu perintah "tambahan", dan dalam kes lain, empat arahan tambahan sekaligus. Jadi terdapat rizab pengoptimuman, dan banyak.

Apabila bercakap tentang pengoptimuman selanjutnya, adalah wajar mengingati kehadiran daftar 256-bit (daftar YMM), yang dengannya anda boleh menggandakan kelajuan pengiraan secara teori. Tetapi buat masa ini ini hanya prospek; pada masa ini, pemproses sangat perlahan apabila melaksanakan arahan 256-bit (FPU mempunyai lebar laluan 128 bit). Eksperimen telah menunjukkan bahawa pada pemproses moden, mengira 16 utas pada daftar YMM tidak memberi apa-apa faedah. Tetapi ini hanya buat masa ini; pada model pemproses baharu, prestasi arahan 256-bit sudah pasti akan meningkat, dan kemudian penggunaan 16 benang selari akan menjadi dinasihatkan dan akan membawa kepada peningkatan yang lebih besar dalam kelajuan prosedur crypto .

Secara teorinya, anda boleh mengharapkan kelajuan 600–700 megabait sesaat jika pemproses mempunyai dua FPU dengan lebar laluan kerja 256 bit setiap satu. Dalam kes ini, kita boleh bercakap tentang menulis kod dengan kecekapan 16 RTT, dan ini bukan fantasi, tetapi dalam masa terdekat.

Mod bercampur

Sekali lagi persoalan bilangan daftar timbul; tidak cukup daripada mereka untuk mempromosikan algoritma sedemikian. Tetapi mod hypertrading akan membantu kami. Teras pemproses mempunyai set daftar kedua yang tersedia dalam mod pemproses logik. Oleh itu, kami akan melaksanakan kod yang sama pada dua pemproses logik sekaligus. Dalam mod ini, sudah tentu, kita tidak akan mempunyai lebih banyak penggerak, tetapi disebabkan silih berganti kita boleh mendapat beban penuh semua penggerak.

Anda tidak boleh mengharapkan peningkatan sebanyak 50% di sini; kesesakan adalah memori cache di mana topeng teknologi disimpan, tetapi anda masih boleh mendapatkan peningkatan sebanyak 100 megabait tambahan. Pilihan ini tidak ditunjukkan dalam lampiran (makro adalah serupa dengan yang digunakan dalam kod 8 RTT), tetapi ia tersedia dalam fail program. Jadi jika sesiapa tidak percaya dengan kemungkinan penyulitan pada kelajuan 500 megabait sesaat pada teras pemproses tunggal, biarkan mereka menjalankan fail ujian. Terdapat juga teks dengan komen supaya tidak ada yang menyangka saya berbohong.

Tumpuan ini hanya boleh dilakukan pada pemproses Intel AMD hanya mempunyai dua unit FPU bagi setiap dua modul pemproses (sama dengan mod hiperdagangan). Tetapi terdapat empat lagi ALU yang akan menjadi dosa jika tidak digunakan.

Anda boleh meletakkan modul pemproses Jentolak ke dalam mod yang serupa dengan mod hypertrading, tetapi jalankan penukaran kepada RON pada modul yang berbeza dalam satu thread, dan pada daftar SSE dalam thread lain dan dapatkan 12 RTT yang sama. Saya belum menguji pilihan ini, tetapi saya fikir kod 12 RTT akan berfungsi dengan lebih cekap pada AMD. Mereka yang berminat boleh mencubanya; program ujian boleh dilaraskan untuk bekerja pada "Bulldozers" dengan mudah.

Siapa yang memerlukannya?

Soalan yang serius, tetapi dengan jawapan yang mudah - semua orang memerlukan ini. Tidak lama lagi kita semua akan terpikat pada awan, kita akan menyimpan kedua-dua data dan program di sana, dan di sana, oh, bagaimana kita mahu mencipta sudut peribadi kita sendiri. Untuk melakukan ini, anda perlu menyulitkan lalu lintas, dan kelajuan penukaran crypto akan menjadi faktor penentu utama kerja yang selesa di awan. Pilihan algoritma penyulitan kami adalah kecil - sama ada GOST atau AES.

Lebih-lebih lagi, anehnya, algoritma penyulitan AES yang dibina ke dalam pemproses ternyata lebih perlahan ujian menunjukkan kelajuan 100-150 megabait sesaat, dan ini adalah dengan pelaksanaan perkakasan algoritma! Masalahnya terletak pada kiraan satu benang dan blok gantian, yang beroperasi pada bait (jadual 256 baris). Jadi GOST ternyata lebih berkesan apabila dilaksanakan pada seni bina x86/64, siapa sangka...

Ini jika kita bercakap tentang tahap kelajuan penyulitan yang dicapai. Dan jika kita mengingati penghalusan teori dalam bidang meningkatkan kecekapan kod, kemungkinan besar tiada siapa yang memerlukan ini. Hampir tiada pakar di peringkat 3–6 RTT, pengkompil biasanya menjana kod pada tahap 1–2.5 RTT, dan majoriti pengaturcara tidak tahu penghimpun, dan walaupun mereka tahu ejaannya, mereka tidak memahami reka bentuk pemproses moden. Dan tanpa pengetahuan ini, tidak kira sama ada ia adalah pemasang atau sejenis SI-sharp.

Tetapi tidak semuanya begitu menyedihkan: intinya selepas seminggu tanpa tidur malam adalah algoritma baru untuk melaksanakan GOST, yang akan menjadi dosa untuk tidak paten. Dan permohonan untuk paten (sebanyak tiga) telah pun selesai dan difailkan, jadi tuan-tuan, ahli perniagaan, beratur - wanita dan kanak-kanak mendapat diskaun.

). Pada masa yang sama, dalam media Rusia dan blog pengguna Rusia, bilangan nota tentang algoritma ini semakin meningkat: kedua-duanya meliputi hasil serangan terhadap standard Rusia dengan tahap kebolehpercayaan yang berbeza-beza, dan mengandungi pendapat tentang ciri operasinya. Penulis (dan, akibatnya, pembaca) nota ini sering mendapat tanggapan bahawa algoritma penyulitan domestik sudah lapuk, perlahan dan mempunyai kelemahan yang menjadikannya lebih mudah terdedah kepada serangan daripada algoritma penyulitan asing dengan panjang kunci yang serupa. Dengan siri nota ini kami ingin memberitahu anda dalam bentuk yang boleh diakses tentang keadaan semasa dengan piawaian Rusia. Bahagian pertama akan merangkumi semua serangan ke atas GOST 28147-89 yang diketahui oleh komuniti kriptografi antarabangsa dan penilaian semasa kekuatannya. Dalam penerbitan akan datang, kami juga akan melihat dengan lebih dekat sifat-sifat standard dari sudut pandangan keupayaan untuk membina pelaksanaan yang berkesan.

Nicolas Courtois - "yang hebat dan dahsyat"

Mari kita mulakan dengan cerita tentang aktiviti Nicolas Courtois, yang merupakan pengarang keseluruhan siri karya yang dikhaskan untuk standard penyulitan blok Rusia ().

Pada Oktober 2010, proses mempertimbangkan kemasukan algoritma GOST 28147-89 dalam standard antarabangsa ISO/IEC 18033-3 bermula. Sudah pada Mei 2011, artikel oleh ahli kriptografi terkenal Nicolas Courtois muncul di arkib elektronik ePrint, ditandai dengan sikap yang sangat samar-samar terhadapnya dari komuniti kriptografi dunia. Penerbitan Courtois adalah contoh yang menyedihkan tentang manipulasi konsep, yang tidak mendedahkan apa-apa sifat baru objek yang dipersoalkan, tetapi dengan tuntutan sensasi mencetuskan penyebaran pendapat yang salah tentang sifat sebenarnya dalam persekitaran yang tidak cekap.

Kaedah algebra

Penaakulan Courtois dibina berdasarkan dua kelas kaedah kriptanalisis: kaedah algebra dan kaedah pembezaan. Mari lihat kaedah kelas pertama.

Dengan cara yang mudah, kaedah kriptanalisis algebra boleh digambarkan sebagai penyusunan dan penyelesaian sistem persamaan yang besar, setiap penyelesaiannya sepadan dengan matlamat cryptanalyst (contohnya, jika sistem disusun menggunakan satu pasangan teks biasa dan teks sifir, maka semua penyelesaian sistem ini sepadan dengan kekunci di mana teks biasa ini ditukar kepada yang ini disulitkan). Iaitu, dalam kes masalah kriptanalisis sifir blok, intipati kaedah algebra kriptanalisis ialah kunci ditemui hasil daripada menyelesaikan sistem persamaan polinomial. Kesukaran utama adalah untuk dapat mencipta sistem semudah mungkin, dengan mengambil kira ciri-ciri sifir tertentu, supaya proses menyelesaikannya mengambil masa yang sesingkat mungkin. Di sini peranan utama dimainkan oleh ciri setiap sifir tertentu yang dianalisis.

Kaedah algebra yang digunakan oleh Courtois boleh dihuraikan secara ringkas seperti berikut. Pada peringkat pertama, sifat GOST 28147-89 seperti itu digunakan sebagai kewujudan titik tetap untuk sebahagian daripada transformasi penyulitan, serta titik refleksi yang dipanggil. Terima kasih kepada sifat ini, beberapa pasangan dipilih daripada bilangan pasangan teks biasa-sifir yang cukup besar, yang memungkinkan untuk mempertimbangkan transformasi bukan pada 32, tetapi hanya pada 8 pusingan. Peringkat kedua ialah, berdasarkan keputusan 8 transformasi bulat yang diperoleh pada peringkat pertama, sistem persamaan tak linear dibina, di mana bit kunci tidak diketahui. Seterusnya, sistem ini diselesaikan (ini kedengaran mudah, tetapi sebenarnya adalah bahagian kaedah yang paling memakan masa, kerana sistem itu terdiri daripada persamaan bukan linear).

Seperti yang dinyatakan di atas, tidak ada di mana-mana dalam karya itu terdapat penerangan dan analisis terperinci tentang kerumitan peringkat kedua dan utama menentukan kunci. Ia adalah kerumitan peringkat kedua yang menentukan kerumitan keseluruhan kaedah secara keseluruhan. Sebaliknya, pengarang memberikan "fakta" terkenal yang berdasarkannya dia membuat anggaran intensiti buruh. "Fakta" ini dikatakan berdasarkan keputusan eksperimen. Analisis "fakta" dari karya Courtois secara keseluruhan diberikan dalam karya pengarang tempatan. Pengarang karya ini mencatatkan bahawa banyak "fakta" Courtois yang dibentangkan tanpa sebarang bukti didapati palsu semasa ujian eksperimen. Pengarang artikel pergi lebih jauh dan, mengikuti Courtois, menjalankan analisis kerumitan peringkat kedua menggunakan algoritma dan anggaran yang berasas. Anggaran kerumitan yang terhasil menunjukkan ketidakbolehgunaan lengkap serangan yang dibentangkan. Sebagai tambahan kepada pengarang tempatan, masalah besar yang dihadapi Courtois dengan penilaian dan justifikasi kaedahnya juga diperhatikan, sebagai contoh, dalam karya itu.

Kaedah pembezaan

Mari kita pertimbangkan kaedah Courtois kedua, yang berdasarkan analisis kriptografi pembezaan.

Kaedah umum kriptanalisis pembezaan adalah berdasarkan eksploitasi sifat pemetaan tak linear yang digunakan dalam primitif kriptografi, dikaitkan dengan pengaruh nilai utama pada kebergantungan antara perbezaan antara pasangan input dan pasangan nilai output pemetaan ini . Mari kita terangkan idea utama kaedah pembezaan analisis kriptografi bagi sifir blok. Biasanya, sifir blok mengubah data input secara berperingkat menggunakan beberapa transformasi bulat yang dipanggil, dan setiap transformasi pusingan tidak menggunakan keseluruhan kunci, tetapi hanya sebahagian daripadanya. Mari kita pertimbangkan sifir yang sedikit "dipotong", yang berbeza daripada yang asal kerana ia tidak mempunyai pusingan terakhir. Mari kita anggap bahawa adalah mungkin untuk menentukan bahawa menyulitkan dua teks biasa yang berbeza dalam beberapa kedudukan tetap menggunakan sifir "dipotong" sedemikian kemungkinan besar akan menghasilkan teks sifir yang juga berbeza dalam beberapa kedudukan tetap. Sifat ini menunjukkan bahawa sifir "dipotong" kemungkinan besar meninggalkan pergantungan antara beberapa teks biasa dan hasil penyulitannya. Untuk memulihkan sebahagian daripada kunci menggunakan kecacatan yang jelas ini, adalah perlu untuk dapat menyulitkan teks biasa yang telah dipilih pada kunci yang ingin kami pulihkan (yang dipanggil "serangan teks biasa yang dipilih"). Pada permulaan prosedur "pembukaan kunci", beberapa pasangan teks biasa dijana secara rawak, berbeza dalam kedudukan tetap yang sama. Semua teks disulitkan menggunakan sifir "penuh". Pasangan teks sifir yang terhasil digunakan untuk memulihkan bit utama yang digunakan dalam transformasi pusingan terakhir, seperti berikut. Menggunakan beberapa nilai yang dipilih secara rawak bagi bit kunci yang diingini, transformasi songsang kepada transformasi pusingan terakhir digunakan pada semua teks sifir. Sebenarnya, jika kami meneka nilai bit kunci yang dikehendaki, kami akan mendapat hasil sifir yang "dipotong", dan jika kami tidak meneka, kami sebenarnya akan "menyulitkan data dengan lebih banyak lagi," yang hanya akan mengurangkan pergantungan antara blok yang dinyatakan di atas (perbezaan adalah dalam beberapa kedudukan tetap). Dalam erti kata lain, jika antara hasil "pemprosesan tambahan" cipherteks sedemikian terdapat banyak pasangan yang berbeza dalam kedudukan tetap yang kita ketahui, maka ini bermakna kita telah meneka bit kunci yang diperlukan. Jika tidak, pasangan sedemikian akan menjadi lebih sedikit. Oleh kerana hanya sebahagian daripada kunci digunakan dalam setiap pusingan, bit yang dicari (iaitu, bit kunci yang digunakan dalam pusingan terakhir) tidak sebanyak bit dalam kunci penuh dan hanya boleh diulang dengan mengulangi langkah di atas. . Dalam kes ini, kita pasti akan tersandung pada makna yang betul suatu hari nanti.

Daripada huraian di atas, ia menunjukkan bahawa perkara yang paling penting dalam kaedah analisis pembezaan ialah bilangan kedudukan tersebut dalam teks biasa dan teks sifir, perbezaan yang memainkan peranan penting dalam memulihkan bit utama. Kehadiran asas kedudukan ini, serta set nombornya, secara langsung bergantung pada sifat transformasi tak linear yang digunakan dalam mana-mana sifir blok (biasanya semua "ketaklinearan" tertumpu dalam apa yang dipanggil kotak-S atau nod gantian).

Courtois menggunakan versi kaedah pembezaan yang diubah suai sedikit. Marilah kita segera ambil perhatian bahawa Courtois menjalankan analisisnya untuk kotak-S yang berbeza daripada yang sedia ada dan daripada yang dicadangkan dalam ISO. Kerja ini menyediakan ciri-ciri pembezaan (nombor-nombor di mana blok harus berbeza) untuk sebilangan kecil pusingan. Justifikasi untuk melanjutkan ciri untuk lebih banyak pusingan adalah, seperti biasa, berdasarkan "fakta". Courtois menyatakan, sekali lagi, tanpa apa-apa selain kuasanya, andaian yang tidak disokong bahawa menukar kotak-S tidak akan menjejaskan rintangan GOST 28147-89 terhadap serangannya (sementara atas sebab yang tidak diketahui, kotak-S dari draf kerja pertama penambahan kepada standard ISO/IEC 18033-3 tidak dipertimbangkan). Analisis yang dijalankan oleh pengarang artikel menunjukkan bahawa walaupun kita mengambil "fakta" Courtois yang tidak berasas tentang iman dan menganalisis GOST 28147-89 dengan blok-S lain, serangan itu sekali lagi ternyata tidak lebih baik daripada carian lengkap.

Analisis terperinci mengenai karya Courtois dengan bukti terperinci tentang ketidakasasan semua pernyataan mengenai penurunan rintangan piawaian Rusia telah dijalankan dalam kerja [,].

Pada masa yang sama, malah Courtois sendiri mengakui kekurangan ketepatan mutlak dalam pengiraan! Slaid berikut diambil daripada pembentangan Courtois di bahagian notis pendek FSE 2012.

Perlu diingatkan bahawa karya Courtois juga telah berulang kali dikritik oleh penyelidik asing. Sebagai contoh, kerjanya untuk membina serangan pada algoritma penyulitan blok AES menggunakan kaedah XSL mengandungi kelemahan asas yang sama seperti kerja pada analisis piawaian Rusia: kebanyakan anggaran intensiti buruh muncul dalam teks sama sekali tidak berasas dan tidak berasas - terperinci kritikan boleh didapati, sebagai contoh, dalam kerja. Di samping itu, Courtois sendiri mengakui keengganan yang meluas untuk menerbitkan karyanya di persidangan kriptografi utama dan dalam jurnal semakan rakan sebaya yang mantap, selalunya memberinya peluang untuk bercakap dalam bahagian pengumuman pendek. Sebagai contoh, anda boleh membaca tentang perkara ini dalam bahagian 3 kerja. Berikut adalah beberapa petikan daripada Courtois sendiri yang berkaitan dengan kerjanya:

• "Saya fikir penonton Asiacrypt tidak akan merasakan ia menarik." Penyemak Asiacrypt 2011.
• “… ada masalah besar, besar, besar: serangan ini, yang merupakan sumbangan utama kertas kerja itu telah pun diterbitkan di FSE’11 (malah kertas kerja terbaik), …”. Penyemak untuk Crypto 2011.

Oleh itu, bahagian profesional komuniti kriptografi antarabangsa menganggap kualiti kerja Courtois dengan tidak kurang keraguan daripada, katakan, kenyataan beberapa pakar Rusia tentang keupayaan mereka untuk memecahkan AES untuk 2,100, yang tidak disahkan oleh sebarang pengiraan yang konsisten, atau "bukti" terkini hipotesis dua muka surat tentang ketaksamaan kelas kerumitan P dan NP.

Serangan oleh Isobe dan Dinur-Dankelman-Shamir

Idea umum serangan Isobe () dan Dinur-Dankelman-Shamir (selepas ini: serangan DDS) () adalah untuk membina set sempit (bergantung kunci) tertentu bagi teks biasa suatu transformasi yang setara pada set ini, yang mempunyai struktur lebih mudah daripada transformasi penyulitan itu sendiri. Dalam kes kaedah Isobe, ini ialah set blok 64-bit x supaya F 8 -1 (Tukar(F 8 (z))) = z, dengan z = F 16 (x), melalui F 8 ( x) dan F 16 ( x) masing-masing menunjukkan 8 dan 16 pusingan pertama penyulitan GOST 28147-89 pertama, melalui Swap - operasi menukar separuh perkataan 64-bait. Jika teks biasa dimasukkan ke dalam set ini, hasil transformasi penuh 32 pusingan GOST 28147-89 bertepatan dengan keputusan 16 pusingan, yang mana yang dieksploitasi oleh pengarang serangan. Dalam kes kaedah DDS, ini ialah set x supaya F 8 (x) = x (titik tetap penjelmaan F 8). Untuk sebarang teks biasa daripada set ini, transformasi GOST 28147-89 berfungsi sama seperti 8 pusingan terakhirnya, yang memudahkan analisis.

Kerumitan serangan Isobe ialah 2,224 operasi penyulitan, serangan DDS ialah 2,192. Walau bagaimanapun, semua soalan tentang sama ada serangan Isobe dan DDS memperkenalkan sekatan baharu pada syarat untuk menggunakan algoritma kami dialih keluar dengan menilai keperluan untuk jumlah bahan yang diperlukan untuk menjalankan setiap serangan: kaedah Isobe memerlukan 2 32 pasang plaintext dan teks sifir, dan untuk kaedah DDS - 2 64. Memproses isipadu bahan sedemikian tanpa menukar kunci adalah priori yang tidak boleh diterima untuk mana-mana sifir blok dengan panjang blok 64: pada bahan jilid 2 32 , dengan mengambil kira masalah hari lahir (lihat, sebagai contoh, ), kebarangkalian kejadian blok berulang adalah hampir 1/2, yang akan menyediakan penyerang dapat membuat kesimpulan tertentu tentang plainteks daripada siferteks tanpa menentukan kunci. Kehadiran 2 64 pasang teks biasa dan disulitkan yang diperoleh pada satu kunci sebenarnya membolehkan musuh menjalankan operasi penyulitan dan penyahsulitan tanpa mengetahui kunci ini sama sekali. Ini disebabkan oleh sifat gabungan semata-mata: musuh dalam kes ini mempunyai keseluruhan jadual penukaran penyulitan. Keadaan ini sama sekali tidak boleh diterima di bawah sebarang keadaan operasi yang munasabah. Sebagai contoh, dalam CryptoPro CSP terdapat had teknikal pada jumlah bahan yang disulitkan (tanpa penukaran kunci) sebanyak 4 MB (lihat). Oleh itu, larangan ketat untuk menggunakan kunci pada bahan kelantangan sedemikian adalah wujud dalam mana-mana sifir blok dengan panjang blok 64 bit, dan oleh itu, serangan Isobe dan DDS sama sekali tidak menyempitkan skop penggunaan algoritma GOST 28147-89. sambil mengekalkan kekuatan maksimum yang mungkin sebanyak 2,256.

Sudah tentu, perlu diperhatikan bahawa penyelidik (Isobe dan Dinur-Dankelman-Shamir) telah menunjukkan bahawa beberapa sifat algoritma GOST 28147-89 memungkinkan untuk mencari laluan analisis yang tidak diambil kira oleh pencipta algoritma. Bentuk ringkas jadual utama, yang memudahkan tugas membina pelaksanaan yang berkesan dengan ketara, juga membolehkan beberapa kes kunci dan teks biasa yang jarang berlaku untuk membina penerangan yang lebih ringkas tentang transformasi yang dihasilkan oleh algoritma.

Kerja menunjukkan bahawa sifat negatif algoritma ini boleh dihapuskan dengan mudah dengan pemeliharaan sepenuhnya ciri-ciri operasi, tetapi, malangnya, ia adalah sebahagian daripada algoritma dalam bentuk yang biasa digunakan.

Perhatikan bahawa kecuaian tertentu dalam anggaran purata intensiti buruh juga terdapat dalam kerja Dinur, Dunkelman dan Shamir. Oleh itu, apabila membina serangan, perhatian sewajarnya tidak diberikan kepada perkara berikut: untuk bahagian kunci yang ketara, set teks biasa x, supaya F 8 (x) = x, kosong: mungkin tiada titik tetap. untuk 8 pusingan transformasi. Kewujudan titik tetap juga bergantung pada pilihan nod gantian. Oleh itu, serangan hanya terpakai untuk nod dan kekunci gantian tertentu.

Ia juga bernilai menyebut satu lagi kerja dengan serangan pada GOST 28147-89. Pada Februari 2012, versi artikel yang dikemas kini (bertarikh November 2011) muncul di arkib elektronik ePrint persatuan kriptografi antarabangsa, yang mengandungi serangan baharu pada GOST 28147-89. Ciri-ciri serangan yang dibentangkan adalah seperti berikut: isipadu bahan ialah 2 32 (seperti Isobe), dan intensiti buruh ialah 2 192 (seperti DDS). Oleh itu, serangan ini menambah baik serangan DDS rekod masa dari segi volum bahan daripada 2 64 kepada 2 32. Kami perhatikan secara berasingan bahawa pengarang dengan jujur ​​membentangkan semua pengiraan dengan justifikasi untuk kerumitan dan jumlah bahan. Selepas 9 bulan, ralat asas ditemui dalam pengiraan di atas, dan sejak November 2012, versi artikel yang dikemas kini dalam arkib elektronik tidak lagi mengandungi sebarang keputusan mengenai algoritma domestik.

Serangan dengan mengandaikan penyerang mengetahui "sesuatu" tentang kunci

Akhirnya mari kita ambil perhatian bahawa dalam kesusasteraan terdapat juga beberapa karya (lihat, sebagai contoh, dan ) yang dikhaskan untuk menyerang GOST 28147-89 dalam apa yang dipanggil model kunci terpaut. Model ini pada asasnya mengandungi andaian bahawa penyerang boleh mendapatkan akses untuk analisis bukan sahaja kepada pasangan teks terbuka dan disulitkan menggunakan kunci yang dikehendaki, tetapi juga kepada pasangan teks terbuka dan disulitkan yang diperoleh menggunakan kekunci (juga tidak diketahui) yang berbeza daripada yang dikehendaki. dengan cara biasa yang diketahui (contohnya, dalam kedudukan bit tetap). Dalam model ini, memang mungkin untuk mendapatkan hasil yang menarik tentang GOST 28147-89, tetapi dalam model ini adalah mungkin untuk mendapatkan hasil yang tidak kurang kukuh tentang, sebagai contoh, standard AES, yang paling banyak digunakan dalam rangkaian awam moden ( lihat, sebagai contoh,). Ambil perhatian bahawa syarat untuk menjalankan jenis serangan ini timbul apabila menggunakan sifir dalam protokol tertentu. Perlu diingatkan bahawa keputusan seperti ini, walaupun ia tidak diragui kepentingan akademik dari sudut mengkaji sifat-sifat transformasi kriptografi, sebenarnya tidak relevan untuk amalan. Sebagai contoh, semua alat perlindungan maklumat kriptografi yang diperakui oleh FSB Rusia memenuhi keperluan paling ketat untuk skim penjanaan kunci penyulitan (lihat, sebagai contoh,). Seperti yang ditunjukkan dalam keputusan analisis, jika terdapat 18 kekunci yang berkaitan dan 2 10 pasang blok teks biasa dan teks sifir, kerumitan membuka kunci persendirian sepenuhnya, dengan kebarangkalian kejayaan 1-10 -4, sebenarnya adalah 2 26 . Walau bagaimanapun, jika keperluan yang disebutkan di atas untuk pembangunan bahan utama dipenuhi, kebarangkalian untuk mencari kunci tersebut ialah 2 -4352, iaitu, 24096 kali kurang daripada jika anda hanya cuba meneka kunci rahsia pada percubaan pertama.

Kerja-kerja yang berkaitan dengan model dengan kunci yang dipautkan juga termasuk kerja, yang pada tahun 2010 menyebabkan banyak bunyi dalam penerbitan elektronik Rusia, yang tidak mengalami tabiat memeriksa dengan teliti bahan dalam perlumbaan untuk sensasi. Hasil yang dibentangkan di dalamnya tidak disokong oleh sebarang justifikasi yang ketat, tetapi mengandungi kenyataan yang kuat tentang keupayaan untuk menggodam standard negeri Persekutuan Rusia pada komputer riba yang lemah dalam beberapa saat - secara umum, artikel itu ditulis dalam tradisi terbaik. daripada Nicolas Courtois. Tetapi, walaupun artikel itu benar-benar tidak berasas kepada pembaca yang lebih kurang biasa dengan prinsip asas penerbitan saintifik, ia adalah tepat untuk meyakinkan orang ramai Rusia selepas kerja bahawa Rudsky menulis teks terperinci dan teliti yang mengandungi analisis yang komprehensif daripada kekurangan ini. Artikel dengan tajuk penjelasan sendiri "Mengenai kepentingan praktikal sifar kerja "Serangan pemulihan utama pada sifir blok GOST penuh dengan masa dan ingatan sifar"" memberikan justifikasi bahawa kerumitan purata kaedah yang diberikan adalah tidak kurang daripada kerumitan. daripada carian lengkap.

Sisa kering: apakah ketahanan dalam amalan?

Sebagai kesimpulan, kami membentangkan jadual yang mengandungi data tentang semua hasil serangan yang diterangkan dengan tegas dan wajar pada GOST 28147-89 yang diketahui oleh komuniti kriptografi antarabangsa. Ambil perhatian bahawa kerumitan diberikan dalam operasi penyulitan algoritma GOST 28147-89, dan memori dan bahan ditunjukkan dalam blok algoritma (64 bit = 8 bait).

Serang	Keamatan buruh	Ingatan	Bahan yang diperlukan
Isobe	2 224	2 64	2 32
Dinur-Dankelman-Shamir, FP, 2DMitM	2 192	2 36	2 64
Dinur-Dankelman-Shamir, FP, ingatan rendah	2 204	2 19	2 64
	2 224	2 36	2 32
Dinur-Dankelman-Shamir, Refleksi, 2DMitM	2 236	2 19	2 32
Carian lengkap	2 256	1	4
Bilangan nanosaat sejak penciptaan Alam Semesta	2 89

Walaupun kitaran penyelidikan berskala besar dalam bidang rintangan algoritma GOST 28147-89, pada masa ini tidak ada satu serangan pun yang diketahui, syarat untuk pelaksanaannya dapat dicapai dengan keperluan operasi yang disertakan untuk panjang blok 64 bit. Sekatan ke atas volum bahan yang boleh diproses pada satu kunci yang terhasil daripada parameter sifir (panjang bit kunci, panjang bit blok) adalah lebih ketat daripada volum minimum yang diperlukan untuk menjalankan sebarang serangan yang diketahui sekarang. Akibatnya, apabila memenuhi keperluan operasi sedia ada, tiada kaedah kriptanalisis yang dicadangkan sehingga kini GOST 28147-89 membenarkan penentuan kunci dengan intensiti buruh kurang daripada carian menyeluruh.

Di negara kita, algoritma bersatu untuk perwakilan kriptografi data telah ditubuhkan untuk sistem pemprosesan maklumat dalam rangkaian komputer, sistem pengkomputeran individu dan komputer, yang ditentukan GOST 28147-89.

Algoritma penukaran data kriptografi ini ialah algoritma blok 64-bit dengan kunci 256-bit, direka untuk pelaksanaan perkakasan dan perisian, memenuhi keperluan kriptografi dan tidak mengenakan sekatan ke atas tahap kerahsiaan maklumat yang dilindungi.

Apabila menerangkan algoritma, notasi berikut digunakan:

L dan R - jujukan bit;
LR ialah gabungan jujukan L dan R, di mana bit jujukan R mengikut bit jujukan L;
(+) - modulo penambahan bitwise 2 (operasi "eksklusif ATAU");
[+] - penambahan nombor 32-bit modulo 2 32;
(+) - penambahan nombor 32-bit modulo 2 32 -1.

Nombor dijumlahkan mengikut peraturan berikut:

A [+] B = A + B jika A + B< 2 32 ,
A [+] B = A + B - 2 32 jika A + B >= 2 32 . A (+) B = A + B jika A + B< 2^32 - 1, A {+} B = A + B - (2^32 - 1), если A + B >= 2^32 - 1.

Algoritma menyediakan empat mod operasi:

Walau apa pun, kunci K 256-bit digunakan untuk menyulitkan data, yang diwakili sebagai lapan subkunci 32-bit K i:

K = K 7 K 6 K 5 K 4 K 3 K 2 K 1 K 0 .

Penyahsulitan dilakukan menggunakan kunci yang sama seperti penyulitan, tetapi prosesnya adalah songsang daripada proses penyulitan data.

Mod penggantian mudah

Mod pertama dan paling mudah ialah penggantian. Data yang akan disulitkan dibahagikan kepada blok 64-bit. Prosedur penyulitan untuk blok data terbuka T 0 merangkumi 32 kitaran (j=1...32).

Blok T 0 dibahagikan kepada dua jujukan 32 bit: B(0)A(0), di mana B(0) ialah bit kiri atau tertib tinggi, A(0) ialah bit kanan atau tertib rendah.

Urutan ini dimasukkan ke dalam pemacu N 1 dan N 2 sebelum permulaan kitaran penyulitan pertama.

Kitaran pertama (j=1) prosedur penyulitan untuk blok data 64-bit diterangkan oleh formula berikut:

Di sini saya menandakan nombor lelaran (i = 1, 2,..., 32).

Fungsi f dipanggil fungsi penyulitan. Hujahnya ialah jumlah, modulo 2, daripada 32 nombor A(i), yang diperoleh pada langkah lelaran sebelumnya, dan nombor kunci X(j) (dimensi setiap nombor ini ialah 32 digit).

Fungsi penyulitan melibatkan dua operasi pada jumlah 32-bit yang terhasil. Operasi pertama dipanggil penggantian K Blok penggantian K terdiri daripada 8 nod penggantian K(1) ... K(8) dengan memori 64 bit setiap satu. Vektor 32-bit yang tiba di blok penggantian dibahagikan kepada 8 vektor 4-bit berjujukan, setiap satunya ditukar menjadi vektor 4-bit oleh nod gantian yang sepadan, iaitu jadual 16 integer dalam julat 0.. .15.

Vektor input menentukan alamat baris dalam jadual, nombor daripadanya ialah vektor keluaran. Vektor keluaran 4-bit kemudiannya disatukan secara berurutan menjadi vektor 32-bit. Jadual blok penggantian K mengandungi elemen utama yang biasa kepada rangkaian komputer dan jarang diubah.

Operasi kedua ialah anjakan kitaran ke kiri vektor 32-bit yang diperoleh hasil daripada penggantian K. Blok 64-bit data yang disulitkan T sh diwakili sebagai T sh = A (32) B (32).

Baki blok data terbuka dalam mod gantian mudah disulitkan dengan cara yang sama.

Sila ambil perhatian bahawa mod penggantian mudah hanya boleh digunakan untuk menyulitkan data dalam kes terhad. Kes ini termasuk menjana kunci dan menyulitkannya dengan penyediaan perlindungan tiruan (perlindungan terhadap pengenaan data palsu) untuk penghantaran melalui saluran komunikasi atau storan dalam memori komputer.

Mod gamma

Data terbuka, dibahagikan kepada blok 64-bit T(i) (i=1, 2,..., m, di mana m ditentukan oleh volum data yang disulitkan), disulitkan dalam mod gamma dengan penambahan bitwise modulo 2 dengan sifir gamma Гш, yang dihasilkan dalam blok 64 bit, iaitu, Гш = (Г(1),Г(2),...,Г(i),...,Г(m)).

Persamaan penyulitan data dalam mod gamma boleh dibentangkan seperti berikut:

Ш(i) = A (Y(i-1) [+] C2, Z(i-1) (+) C1) (+) T(i) = Г(i) (+) T(i) .
Di sini Ш(i) ialah blok 64-bit teks sifir,
A - fungsi penyulitan dalam mod gantian mudah (hujah fungsi ini ialah dua nombor 32-bit),
C1 dan C2 adalah pemalar yang dinyatakan dalam GOST 28147-89,
Y(i) dan Z(i) ialah kuantiti yang ditentukan secara berulang apabila gamma terbentuk seperti berikut:
(Y(0), Z(0)) = A(S), dengan S ialah jujukan binari 64-bit (mesej penyegerakan);
(Y(i), Z(i)) = (Y(i-1) [+] C2, Z(i-1) (+) C1) untuk i = 1, 2,...,m.

Penyahsulitan data hanya boleh dilakukan jika terdapat mesej penyegerakan, yang bukan elemen rahsia sifir dan boleh disimpan dalam memori komputer atau dihantar melalui saluran komunikasi bersama-sama dengan data yang disulitkan.

Mod gamma dengan maklum balas

Mod perjudian dengan maklum balas sangat serupa dengan mod gamma. Seperti dalam mod gamma, data terbuka, dibahagikan kepada blok 64-bit T(i) (i=1, 2,..., m, di mana m ditentukan oleh volum data yang disulitkan), disulitkan dengan modulo penambahan bitwise 2 dengan sifir gamma G sh, yang dihasilkan dalam blok 64 bit:

G w = (G(1),G(2),...,G(i),...,G(m)).

Bilangan digit binari dalam blok T(m) boleh kurang daripada 64, manakala bahagian gamut sifir yang tidak digunakan untuk penyulitan daripada blok G(m) dibuang.

Persamaan penyulitan data dalam mod gamma gelung tertutup boleh dibentangkan seperti berikut:

Di sini Ш(i) ialah blok 64-bit teks sifir,
A - fungsi penyulitan dalam mod gantian mudah. Argumen fungsi pada langkah pertama algoritma lelaran ialah mesej penyegerakan 64-bit, dan pada semua langkah berikutnya ia adalah blok sebelumnya data yang disulitkan Ш(i-1).

Perkembangan sisipan tiruan

Proses pengeluaran imitovstaki adalah seragam untuk mana-mana mod penyulitan data.

Sisipan tiruan ialah blok bit p (sisipan tiruan Ir), yang dihasilkan sama ada sebelum menyulitkan keseluruhan mesej, atau selari dengan penyulitan blok demi blok. Blok pertama data terbuka yang mengambil bahagian dalam penjanaan sisipan tiruan mungkin mengandungi maklumat perkhidmatan (contohnya, bahagian alamat, masa, mesej penyegerakan) dan tidak disulitkan. Nilai parameter p (bilangan bit binari dalam sisipan simulasi) ditentukan oleh keperluan kriptografi, dengan mengambil kira fakta bahawa kebarangkalian mengenakan gangguan palsu adalah sama dengan 1/2^p.

Untuk mendapatkan sisipan simulasi, data terbuka dibentangkan dalam bentuk blok 64-bit T(i) (i = 1, 2,..., m, di mana m ditentukan oleh jumlah data yang disulitkan). Blok pertama data biasa T(1) mengalami transformasi yang sepadan dengan 16 kitaran pertama algoritma penyulitan dalam mod gantian mudah. Selain itu, kunci yang digunakan untuk menyulitkan data digunakan sebagai kunci untuk menjana sisipan tiruan.

Nombor 64-bit yang diperoleh selepas 16 kitaran operasi dijumlahkan modulo 2 dengan blok kedua data terbuka T(2). Hasil penjumlahan sekali lagi tertakluk kepada transformasi yang sepadan dengan 16 kitaran pertama algoritma penyulitan dalam mod gantian mudah. Nombor 64-bit yang terhasil dijumlahkan modulo 2 dengan blok ketiga data terbuka T(3), dsb. Blok terakhir T(m), jika perlu, berlapik pada blok 64-bit penuh dengan sifar, dijumlahkan modulo 2 dengan hasil kerja pada langkah m-1, selepas itu ia disulitkan dalam mod penggantian mudah pada yang pertama 16 kitaran algoritma. Daripada nombor 64-bit yang terhasil, segmen Ip dengan panjang p bit dipilih.

Sisipan tiruan Ir dihantar melalui saluran komunikasi atau ke dalam memori komputer selepas data yang disulitkan. Data yang disulitkan yang diterima dinyahsulit, dan daripada blok data terbuka T(i) yang diterima, sisipan simulasi terhasil, yang kemudiannya dibandingkan dengan sisipan simulasi yang diterima daripada saluran komunikasi atau daripada memori komputer sisipan tidak sepadan, semua data yang disulitkan dianggap palsu.

Algoritma penyulitan GOST 28147-89, penggunaannya dan pelaksanaan perisian untuk komputer pada platform Intel x86.

Andrey Vinokurov

Penerangan tentang algoritma.

Terma dan sebutan.

Penerangan mengenai standard penyulitan Persekutuan Rusia terkandung dalam dokumen yang sangat menarik bertajuk "Algoritma penukaran kriptografi GOST 28147-89". Hakikat bahawa dalam namanya dan bukannya istilah "penyulitan" terdapat konsep yang lebih umum " penukaran kriptografi ", sama sekali tidak sengaja. Sebagai tambahan kepada beberapa prosedur penyulitan yang berkait rapat, dokumen itu menerangkan satu algoritma untuk penjanaan sisipan tiruan . Yang terakhir ini tidak lebih daripada gabungan kawalan kriptografi, iaitu, kod yang dihasilkan daripada data asal menggunakan kunci rahsia untuk tujuan perlindungan tiruan , atau melindungi data daripada perubahan yang tidak dibenarkan.

Pada langkah algoritma GOST yang berbeza, data yang mereka kendalikan ditafsir dan digunakan dalam cara yang berbeza. Dalam sesetengah kes, elemen data dianggap sebagai tatasusunan bit bebas, dalam kes lain sebagai integer tidak bertanda, dalam kes lain sebagai elemen kompleks berstruktur yang terdiri daripada beberapa elemen yang lebih mudah. Oleh itu, untuk mengelakkan kekeliruan, adalah penting untuk bersetuju dengan notasi yang digunakan.

Elemen data dalam artikel ini ditetapkan dengan huruf besar dengan gaya condong (contohnya, X). Melalui | X| menandakan saiz elemen data X dalam bit. Oleh itu, jika kita mentafsir elemen data X Sebagai integer bukan negatif, kita boleh menulis ketaksamaan berikut:.

Jika elemen data terdiri daripada beberapa elemen yang lebih kecil, maka fakta ini ditunjukkan seperti berikut: X=(X 0 ,X 1 ,…,Xn –1)=X 0 ||X 1 ||…||Xn-1 . Proses menggabungkan beberapa elemen data menjadi satu dipanggil penyatuan data dan ditunjukkan dengan simbol “||”. Sememangnya, hubungan berikut mesti dipenuhi untuk saiz elemen data: | X|=|X 0 |+|X 1 |+…+|Xn-1 |. Apabila menentukan elemen data kompleks dan operasi penggabungan, elemen data konstituen disenaraikan dalam urutan keutamaan menaik. Dalam erti kata lain, jika kita mentafsirkan elemen komposit dan semua elemen datanya sebagai integer tidak bertanda, maka kita boleh menulis kesamaan berikut:

Dalam algoritma, elemen data boleh ditafsirkan sebagai tatasusunan bit individu, dalam hal ini bit dilambangkan dengan huruf yang sama seperti tatasusunan, tetapi dalam versi huruf kecil, seperti yang ditunjukkan dalam contoh berikut:

X=(x 0 ,x 1 ,…,x n –1)=x 0 +2 1 · x 1 +…+2 n-1 · x n –1 .

Oleh itu, jika anda perasan, apa yang dipanggil GOST telah diterima pakai. penomboran digit "little-endian", i.e. Dalam perkataan data berbilang bit, bit individu dan kumpulan bit bernombor lebih rendah adalah kurang ketara. Ini dinyatakan secara langsung dalam perenggan 1.3 standard: "Apabila menambah dan mengalihkan vektor binari secara kitaran, bit yang paling ketara dianggap sebagai bit pemacu dengan bilangan yang besar." Selanjutnya, klausa standard 1.4, 2.1.1 dan lain-lain memerlukan mula mengisi daftar storan peranti penyulitan maya dengan data daripada yang paling rendah, i.e. kategori kurang penting. Susunan penomboran yang sama digunakan dalam seni bina mikropemproses Intel x86, itulah sebabnya apabila melaksanakan sifir dalam perisian pada seni bina ini, tiada pilih atur tambahan bit dalam perkataan data diperlukan.

Jika beberapa operasi yang mempunyai makna logik dilakukan pada elemen data, maka diandaikan bahawa operasi ini dilakukan pada bit unsur yang sepadan. Dalam kata lain A B=(a 0 b 0 ,a 1 b 1 ,…,a n –1 b n-1), di mana n=|A|=|B|, dan simbol “ ” menandakan operasi logik binari sewenang-wenangnya; sebagai peraturan, ini bermakna pembedahan eksklusif atau , yang juga merupakan pengendalian modulo penjumlahan 2:

Logik membina sifir dan struktur maklumat utama GOST.

Jika anda mengkaji dengan teliti GOST 28147–89 asal, anda akan melihat bahawa ia mengandungi penerangan tentang algoritma pada beberapa peringkat. Di bahagian paling atas terdapat algoritma praktikal yang direka untuk menyulitkan tatasusunan data dan membangunkan sisipan tiruan untuknya. Kesemuanya adalah berdasarkan tiga algoritma peringkat rendah, dipanggil dalam teks GOST kitaran . Algoritma asas ini dirujuk dalam artikel ini sebagai kitaran asas untuk membezakannya daripada semua kitaran lain. Mereka mempunyai nama dan simbol berikut, yang terakhir diberikan dalam kurungan dan maknanya akan dijelaskan kemudian:

• kitaran penyulitan (32-З);
• kitaran penyahsulitan (32-P);
• kitaran pengeluaran sisipan tiruan (16-З).

Sebaliknya, setiap kitaran asas adalah pengulangan berganda bagi satu prosedur tunggal, yang memerlukan kepastian lebih lanjut dalam kerja ini langkah utama penukaran kripto .

Oleh itu, untuk memahami GOST, anda perlu memahami tiga perkara berikut:

• apa dah jadi langkah asas penukaran kripto;
• bagaimana kitaran asas terbentuk daripada langkah asas;
• setakat tiga kitaran asas semua algoritma GOST praktikal ditambah.

Sebelum meneruskan untuk mengkaji isu ini, kita harus bercakap tentang maklumat utama yang digunakan oleh algoritma GOST. Selaras dengan prinsip Kirchhoff, yang berpuas hati oleh semua sifir moden yang diketahui umum, kerahsiaannyalah yang memastikan kerahsiaan mesej yang disulitkan. Dalam GOST, maklumat utama terdiri daripada dua struktur data. Selain yang sebenarnya kunci , perlu untuk semua sifir, ia juga mengandungi jadual penggantian . Berikut adalah ciri-ciri utama struktur utama GOST.

Langkah utama penukaran kripto.

Langkah penukaran kripto asas pada dasarnya adalah pernyataan yang menentukan penukaran blok data 64-bit. Parameter tambahan pengendali ini ialah blok 32-bit, yang digunakan sebagai elemen utama. Rajah algoritma langkah utama ditunjukkan dalam Rajah 1.

Rajah 1. Skim langkah utama penukaran kripto algoritma GOST 28147-89.

Berikut adalah penjelasan tentang algoritma langkah utama:

Langkah 0

• N– blok data 64-bit yang ditukar, semasa pelaksanaan langkah kecilnya ( N 1) dan senior ( N 2) bahagian-bahagian itu dianggap sebagai integer 32-bit yang tidak bertanda yang berasingan. Dengan itu, kita boleh menulis N=(N 1 ,N 2).
• X– Elemen kunci 32-bit;

Langkah 1

Tambahan dengan kunci. Bahagian bawah blok yang ditukar ditambah modulo 2 32 dengan elemen utama yang digunakan pada langkah, hasilnya dipindahkan ke langkah seterusnya;

Langkah 2

Penggantian blok. Nilai 32-bit yang diperoleh dalam langkah sebelumnya ditafsirkan sebagai tatasusunan lapan blok kod 4-bit: S=(S 0 , S 1 , S 2 , S 3 , S 4 , S 5 , S 6 , S 7), dan S 0 mengandungi 4 yang bongsu, dan S 7 – 4 bit paling ketara S.

Seterusnya, nilai setiap lapan blok digantikan dengan yang baru, yang dipilih daripada jadual penggantian seperti berikut: nilai blok S i perubahan kepada S i-elemen ke dalam tertib (penomboran dari sifar) i-nod gantian itu (iaitu i-baris ke- bagi jadual gantian, penomboran juga dari awal). Dalam erti kata lain, elemen daripada jadual gantian dengan nombor baris yang sama dengan bilangan blok yang diganti dan nombor lajur yang sama dengan nilai blok yang diganti sebagai integer bukan negatif 4-bit dipilih sebagai pengganti. untuk nilai blok. Ini menjadikan saiz jadual gantian jelas: bilangan baris di dalamnya adalah sama dengan bilangan elemen 4-bit dalam blok data 32-bit, iaitu, lapan, dan bilangan lajur adalah sama dengan bilangan nilai yang berbeza bagi blok data 4-bit, yang dikenali sebagai 2 4, enam belas.

Langkah 3

Putar 11 bit ke kiri. Hasil daripada langkah sebelumnya dianjakkan secara kitaran sebanyak 11 bit ke arah bit yang paling ketara dan dihantar ke langkah seterusnya. Dalam rajah algoritma, simbol menunjukkan fungsi kitaran mengalihkan hujahnya 11 bit ke kiri, i.e. terhadap pangkat yang lebih tinggi.

Langkah 4

Penambahan bitwise: Nilai yang diperoleh dalam langkah 3 ditambah modulo 2 bitwise dengan separuh lebih tinggi daripada blok ditukar.

Langkah 5

Beralih sepanjang rantai: bahagian bawah blok yang ditukar dialihkan ke tempat yang lebih lama, dan hasil langkah sebelumnya diletakkan di tempatnya.

Langkah 6

Nilai yang terhasil daripada blok yang ditukar dikembalikan sebagai hasil daripada melaksanakan algoritma langkah utama penukaran kripto.

Kitaran asas transformasi kriptografi.

Seperti yang dinyatakan pada permulaan artikel ini, GOST tergolong dalam kelas sifir blok, iaitu, unit pemprosesan maklumat di dalamnya adalah blok data. Oleh itu, agak logik untuk menjangkakan bahawa ia akan mentakrifkan algoritma untuk transformasi kriptografi, iaitu, untuk menyulitkan, menyahsulit dan "perakaunan" untuk gabungan kawalan satu blok data. Algoritma ini dipanggil kitaran asas GOST, yang menekankan kepentingan asas mereka untuk pembinaan sifir ini.

Gelung asas dibina daripada langkah utama transformasi kriptografi yang dibincangkan dalam bahagian sebelumnya. Semasa langkah utama, hanya satu elemen kunci 32-bit digunakan, manakala kunci GOST mengandungi lapan elemen tersebut. Oleh itu, agar kunci dapat digunakan sepenuhnya, setiap gelung asas mesti berulang kali melaksanakan langkah utama dengan pelbagai elemennya. Pada masa yang sama, nampaknya wajar bahawa dalam setiap kitaran asas semua elemen utama harus digunakan bilangan kali yang sama atas sebab kekuatan sifir, nombor ini harus lebih daripada satu.

Semua andaian yang dibuat di atas, berdasarkan akal sehat, ternyata betul. Gelung asas terdiri daripada pelaksanaan berulang langkah utama menggunakan elemen utama yang berbeza dan berbeza antara satu sama lain hanya dalam bilangan ulangan langkah dan susunan elemen utama digunakan. Di bawah ialah pesanan ini untuk kitaran yang berbeza.

Kitaran penyulitan 32-Z:

K 0 ,K 1 ,K 2 ,K 3 ,K 4 ,K 5 ,K 6 ,K 7 ,K 0 ,K 1 ,K 2 ,K 3 ,K 4 ,K 5 ,K 6 ,K 7 ,K 0 ,K 1 ,K 2 ,K 3 ,K 4 ,K 5 ,K 6 ,K 7 ,K 7 ,K 6 ,K 5 ,K 4 ,K 3 ,K 2 ,K 1 ,K 0 .

Rajah 2a. Skim kitaran penyulitan 32-З

Kitaran penyahsulitan 32-P:

K 0 ,K 1 ,K 2 ,K 3 ,K 4 ,K 5 ,K 6 ,K 7 ,K 7 ,K 6 ,K 5 ,K 4 ,K 3 ,K 2 ,K 1 ,K 0 ,K 7 ,K 6 ,K 5 ,K 4 ,K 3 ,K 2 ,K 1 ,K 0 ,K 7 ,K 6 ,K 5 ,K 4 ,K 3 ,K 2 ,K 1 ,K 0 .

Rajah 2b. Skim kitaran penyahsulitan 32-P

Kitaran pengeluaran sisipan tiruan 16-Z:

K 0 ,K 1 ,K 2 ,K 3 ,K 4 ,K 5 ,K 6 ,K 7 ,K 0 ,K 1 ,K 2 ,K 3 ,K 4 ,K 5 ,K 6 ,K 7 .

Rajah 2c. Skim kitaran pengeluaran sisipan tiruan 16-Z.

Setiap kitaran mempunyai sebutan alfanumerik sendiri yang sepadan dengan corak " n-X", di mana elemen pertama penetapan ( n), menentukan bilangan ulangan langkah utama dalam kitaran, dan elemen kedua penetapan ( X), huruf, menentukan susunan penyulitan (“Z”) atau penyahsulitan (“P”) dalam penggunaan elemen utama. Perintah ini memerlukan penjelasan lanjut:

Kitaran penyahsulitan mestilah songsang daripada kitaran penyulitan, iaitu, aplikasi berurutan kedua-dua kitaran ini kepada blok sewenang-wenang akhirnya mesti menghasilkan blok asal, yang ditunjukkan dalam hubungan berikut: C 32-Р ( C 32-З ( T))=T, Di mana T– blok data 64-bit sewenang-wenangnya, C X ( T) – hasil pelaksanaan gelung X di atas blok data T. Untuk memenuhi syarat ini untuk algoritma yang serupa dengan GOST, adalah perlu dan mencukupi bahawa susunan penggunaan elemen utama oleh kitaran yang sepadan adalah saling songsang. Adalah mudah untuk mengesahkan kesahihan syarat bertulis untuk kes yang sedang dipertimbangkan dengan membandingkan urutan di atas untuk kitaran 32-З dan 32-Р. Satu akibat yang menarik berikut daripada perkara di atas: sifat kitaran yang songsang kepada kitaran lain adalah timbal balik, iaitu kitaran 32-Z adalah songsang kepada kitaran 32-P. Dalam erti kata lain, penyulitan blok data secara teorinya boleh dilakukan menggunakan kitaran penyahsulitan, di mana penyahsulitan blok data mesti dilakukan oleh kitaran penyulitan. Daripada dua kitaran saling songsang, sama ada satu boleh digunakan untuk penyulitan, maka yang kedua mesti digunakan untuk menyahsulit data, bagaimanapun, standard GOST 28147-89 memberikan peranan kepada kitaran dan tidak memberi pengguna hak untuk memilih dalam perkara ini. .

Kitaran untuk menghasilkan sisipan tiruan adalah separuh panjang daripada kitaran penyulitan, susunan penggunaan elemen utama di dalamnya adalah sama seperti dalam 16 langkah pertama kitaran penyulitan, yang mudah untuk disahkan dengan mempertimbangkan urutan di atas, oleh itu susunan ini dalam penetapan kitaran dikodkan oleh huruf "Z" yang sama.

Skim kitaran asas ditunjukkan dalam Rajah 2a-c. Setiap daripada mereka mengambil sebagai hujah dan mengembalikan sebagai hasilnya blok data 64-bit, ditunjukkan dalam rajah N. Langkah Simbol( N,X) menandakan pelaksanaan langkah transformasi kripto utama untuk blok data N menggunakan elemen utama X. Terdapat satu lagi perbezaan antara kitaran pengiraan penyulitan dan sisipan tiruan, yang tidak disebutkan di atas: pada penghujung kitaran penyulitan asas, bahagian tinggi dan rendah blok hasil ditukar, ini perlu untuk kebolehbalikan bersama mereka.

Mod penyulitan asas.

GOST 28147-89 menyediakan tiga mod penyulitan data berikut:

• penggantian mudah,
• permainan,
• bermain permainan dengan maklum balas,

dan satu mod tambahan untuk menjana sisipan tiruan.

Dalam mana-mana mod ini, data diproses dalam blok 64 bit, di mana tatasusunan dibahagikan dan tertakluk kepada transformasi kriptografi, itulah sebabnya GOST merujuk kepada sifir blok. Walau bagaimanapun, dalam dua mod gamma adalah mungkin untuk memproses blok data yang tidak lengkap bersaiz kurang daripada 8 bait, yang penting apabila menyulitkan tatasusunan data saiz sewenang-wenangnya, yang mungkin bukan gandaan 8 bait.

Sebelum beralih kepada perbincangan tentang algoritma transformasi kriptografi tertentu, adalah perlu untuk menjelaskan tatatanda yang digunakan dalam rajah dalam bahagian berikut:

T O, T w – tatasusunan data terbuka dan disulitkan, masing-masing;

, – i- blok 64-bit berurutan bagi data terbuka dan disulitkan, masing-masing: , , blok terakhir mungkin tidak lengkap: ;

n– bilangan blok 64-bit dalam tatasusunan data;

C X – fungsi menukar blok data 64-bit menggunakan algoritma "X" kitaran asas.

Sekarang kami akan menerangkan mod penyulitan utama:

Penggantian yang mudah.

Penyulitan dalam mod ini terdiri daripada menggunakan kitaran 32-З pada blok data terbuka, penyahsulitan - kitaran 32-Р kepada blok data yang disulitkan. Ini adalah mod yang paling mudah; blok data 64-bit diproses secara berasingan antara satu sama lain. Skim penyulitan dan algoritma penyahsulitan dalam mod penggantian mudah ditunjukkan dalam Rajah 3a dan b, masing-masing adalah remeh dan tidak memerlukan ulasan.

Melukis. 3a. Algoritma penyulitan data dalam mod gantian mudah

Melukis. 3b. Algoritma penyahsulitan data dalam mod gantian mudah

Saiz tatasusunan data terbuka atau disulitkan, tertakluk kepada penyulitan atau penyahsulitan, masing-masing, mestilah gandaan 64 bit: | T o |=| T w |=64· n , selepas menjalankan operasi, saiz tatasusunan data yang terhasil tidak berubah.

Mod penyulitan gantian mudah mempunyai ciri berikut:

• Memandangkan blok data disulitkan secara berasingan antara satu sama lain dan kedudukannya dalam tatasusunan data, menyulitkan dua blok plaintext yang serupa menghasilkan blok siferteks yang sama dan sebaliknya. Sifat yang dinyatakan akan membolehkan cryptanalyst membuat kesimpulan tentang identiti blok data asal jika dia menemui blok yang sama dalam tatasusunan data yang disulitkan, yang tidak boleh diterima untuk sifir yang serius.
• Jika panjang tatasusunan data yang disulitkan bukan gandaan 8 bait atau 64 bit, masalah timbul tentang cara dan cara menambah blok data terakhir yang tidak lengkap tatasusunan kepada 64 bit penuh. Tugas ini tidak semudah yang kelihatan pada pandangan pertama. Penyelesaian yang jelas seperti "tambah blok yang tidak lengkap dengan bit sifar" atau, lebih umum, "tambah blok yang tidak lengkap dengan gabungan tetap sifar dan satu bit" boleh, dalam keadaan tertentu, memberi peluang kepada cryptanalyst untuk menggunakan kaedah kekerasan untuk menentukan kandungan blok yang sangat tidak lengkap ini, dan fakta ini bermakna penurunan dalam sifir keselamatan. Di samping itu, panjang teks sifir akan berubah, meningkat kepada gandaan integer terdekat 64 bit, yang selalunya tidak diingini.

Pada pandangan pertama, ciri-ciri di atas menjadikannya hampir mustahil untuk menggunakan mod penggantian mudah, kerana ia hanya boleh digunakan untuk menyulitkan tatasusunan data dengan saiz berganda 64 bit dan tidak mengandungi blok 64-bit berulang. Nampaknya untuk sebarang data sebenar adalah mustahil untuk menjamin pemenuhan syarat-syarat ini. Ini hampir benar, tetapi terdapat satu pengecualian yang sangat penting: ingat bahawa saiz kunci ialah 32 bait, dan saiz jadual ganti ialah 64 bait. Di samping itu, kehadiran blok 8-bait berulang dalam kekunci atau jadual gantian akan menunjukkan kualitinya yang sangat buruk, jadi pengulangan sedemikian tidak boleh wujud dalam elemen utama sebenar. Oleh itu, kami mendapati bahawa mod penggantian mudah agak sesuai untuk menyulitkan maklumat utama, terutamanya kerana mod lain kurang sesuai untuk tujuan ini, kerana ia memerlukan elemen data penyegerakan tambahan - mesej penyegerakan (lihat bahagian seterusnya). Tekaan kami betul; GOST menetapkan penggunaan mod penggantian mudah secara eksklusif untuk menyulitkan data utama.

Bergetah.

Bagaimanakah anda boleh menghilangkan kekurangan mod penggantian mudah? Untuk melakukan ini, adalah perlu untuk memungkinkan untuk menyulitkan blok dengan saiz kurang daripada 64 bit dan memastikan bahawa blok ciphertext bergantung pada nombornya, dengan kata lain, rawak proses penyulitan. Dalam GOST ini dicapai dalam dua cara berbeza dalam dua mod penyulitan, menyediakan perjudian . Bergetah - ini ialah pengenaan (penyingkiran) skala kriptografi pada data terbuka (disulitkan), iaitu, jujukan elemen data yang dijana menggunakan beberapa algoritma kriptografi untuk mendapatkan data yang disulitkan (terbuka). Untuk menggunakan gamma semasa penyulitan dan mengalih keluarnya semasa penyahsulitan, operasi binari saling songsang mesti digunakan, contohnya, penambahan dan penolakan modulo 2 64 untuk blok data 64-bit. Dalam GOST, untuk tujuan ini, operasi penambahan bitwise modulo 2 digunakan, kerana ia adalah songsang dari dirinya sendiri dan, lebih-lebih lagi, paling mudah dilaksanakan dalam perkakasan. Gamma menyelesaikan kedua-dua masalah yang disebutkan: pertama, semua elemen gamma adalah berbeza untuk tatasusunan yang disulitkan sebenar dan, oleh itu, hasil penyulitan walaupun dua blok yang sama dalam satu tatasusunan data akan berbeza. Kedua, walaupun elemen gamma dijana dalam bahagian yang sama 64 bit, sebahagian daripada blok sedemikian dengan saiz yang sama dengan saiz blok yang disulitkan boleh digunakan.

Sekarang mari kita beralih terus ke penerangan mod gamma. Gamma untuk mod ini diperoleh seperti berikut: dengan bantuan beberapa penjana jujukan nombor berulang algoritma (RNGN), blok data 64-bit dijana, yang kemudiannya ditukar menggunakan kitaran 32-3, iaitu, disulitkan dalam mudah. mod penggantian, menghasilkan blok gamma. Disebabkan fakta bahawa aplikasi dan penyingkiran gamma dijalankan menggunakan eksklusif atau operasi bitwise yang sama, algoritma penyulitan dan penyahsulitan dalam mod gamma adalah sama, skema umum mereka ditunjukkan dalam Rajah 4.

RGPG yang digunakan untuk menjana skala ialah fungsi berulang: – elemen urutan berulang, f– fungsi transformasi. Akibatnya, persoalan pasti timbul tentang permulaannya, iaitu, mengenai elemen Sebenarnya, elemen data ini adalah parameter algoritma untuk mod gamma dalam rajah yang ditetapkan sebagai S, dan dipanggil dalam kriptografi hantaran segerak , dan dalam GOST kami – pengisian awal salah satu daftar pengekod. Atas sebab tertentu, pembangun GOST memutuskan untuk tidak menggunakan mesej penyegerakan secara langsung untuk memulakan RGFC, tetapi hasil penukarannya mengikut kitaran 32-Z: . Urutan unsur yang dijana oleh RGHR bergantung sepenuhnya pada pengisian awalnya, iaitu unsur-unsur jujukan ini adalah fungsi nombor mereka dan pengisian awal RGHR: di mana f i(X)=f(f i –1 (X)), f 0 (X)=X. Dengan mengambil kira transformasi menggunakan algoritma penggantian mudah, pergantungan pada kunci juga ditambah:

di mana Г i– i-elemen skala ke-, K- kunci.

Oleh itu, jujukan unsur gamma yang akan digunakan dalam mod gamma ditentukan secara unik oleh data utama dan mesej penyegerakan. Sememangnya, untuk prosedur penyulitan boleh diterbalikkan, mesej penyegerakan yang sama mesti digunakan dalam proses penyulitan dan penyahsulitan. Daripada keperluan keunikan gamma, kegagalan untuk mematuhi yang membawa kepada pengurangan bencana dalam kekuatan sifir, ia berikutan bahawa untuk menyulitkan dua tatasusunan data yang berbeza pada kunci yang sama, adalah perlu untuk memastikan penggunaan mesej penyegerakan yang berbeza. Ini membawa kepada keperluan untuk menyimpan atau menghantar mesej penyegerakan di sepanjang saluran komunikasi bersama-sama dengan data yang disulitkan, walaupun dalam beberapa kes khas ia boleh ditetapkan atau dikira dengan cara yang istimewa jika menyulitkan dua tatasusunan dengan kunci yang sama dikecualikan.

Sekarang mari kita lihat lebih dekat pada RGPC yang digunakan dalam GOST untuk menjana elemen gamut. Pertama sekali, perlu diingatkan bahawa ia tidak perlu menyediakan sebarang ciri statistik bagi urutan nombor yang dijana. RGHR telah direka oleh pemaju GOST berdasarkan keperluan untuk memenuhi syarat berikut:

• tempoh ulangan jujukan nombor yang dijana oleh RGPC seharusnya tidak jauh berbeza (dalam segi peratusan) daripada nilai maksimum yang mungkin untuk saiz blok tertentu 2 64;
• nilai bersebelahan yang dihasilkan oleh RGPG mesti berbeza antara satu sama lain dalam setiap bait, jika tidak, tugas cryptanalyst akan dipermudahkan;
• RGPC sepatutnya agak mudah untuk dilaksanakan dalam perkakasan dan perisian pada jenis pemproses yang paling biasa, yang kebanyakannya diketahui 32-bit.

Berdasarkan prinsip yang disenaraikan, pencipta GOST mereka bentuk RGHR yang sangat berjaya, yang mempunyai ciri-ciri berikut:

di mana C 0 =1010101 16 ;

di mana C 1 =1010104 16 ;

Subskrip dalam nombor menunjukkan sistem nombornya, jadi pemalar yang digunakan dalam langkah ini ditulis dalam perenambelasan.

Ungkapan kedua memerlukan ulasan, kerana teks GOST mengandungi sesuatu yang lain: , dengan nilai pemalar yang sama C 1 . Tetapi lebih jauh dalam teks standard komen diberikan bahawa, ternyata, di bawah operasi mengambil baki modulo 2 32 –1 di sana tidak difahami dengan cara yang sama seperti dalam matematik. Perbezaannya ialah mengikut GOST (2 32 –1) mod(2 32 –1)=(2 32 –1), bukan 0. Malah, ini memudahkan pelaksanaan formula, dan ungkapan yang betul secara matematik untuknya diberikan di atas.

• tempoh ulangan urutan untuk bahagian bawah ialah 2 32, untuk bahagian yang lebih lama 2 32 –1, untuk keseluruhan urutan tempohnya ialah 2 32 (2 32 –1), bukti fakta ini sangat mudah, dapatkannya diri sendiri. Yang pertama daripada dua formula dilaksanakan dalam satu arahan, yang kedua, walaupun kelihatan rumit, dalam dua arahan pada semua pemproses 32-bit moden - arahan pertama ialah modulo tambahan biasa 2 32 dengan menyimpan bit pembawa, dan yang kedua arahan menambah bit pembawa kepada makna yang terhasil.

Gambar rajah algoritma penyulitan dalam mod gamma ditunjukkan dalam Rajah 4 di bawah adalah penjelasan untuk skema:

Rajah 4. Algoritma untuk menyulitkan (menyahsulit) data dalam mod gamma.

Langkah 0

Mentakrifkan data input untuk langkah penukaran crypto utama:

• T o(w) – tatasusunan data terbuka (disulitkan) dengan saiz sewenang-wenangnya, tertakluk kepada prosedur penyulitan (penyahsulitan) semasa prosedur, tatasusunan ditukar dalam bahagian 64-bit;
• S – mesej segerak , elemen data 64-bit yang diperlukan untuk memulakan penjana gamma;

Langkah 1

Transformasi awal mesej penyegerakan, dilakukan untuk "merawakkan" ia, iaitu, untuk menghapuskan corak statistik yang terdapat di dalamnya, hasilnya digunakan sebagai pengisian awal RGPC;

Langkah 2

Satu langkah operasi RGPC, melaksanakan algoritma berulangnya. Semasa langkah ini, anak sulung ( S 1) dan junior ( S 0) bahagian urutan data dijana secara bebas antara satu sama lain;

Langkah 3

Bergetah. Elemen 64-bit seterusnya yang dihasilkan oleh RGPC tertakluk kepada prosedur penyulitan menggunakan kitaran 32-3, hasilnya digunakan sebagai elemen gamma untuk menyulitkan (menyahsulit) blok seterusnya data terbuka (disulitkan) dengan saiz yang sama.

Langkah 4

Hasil daripada algoritma ialah tatasusunan data yang disulitkan (dinyahsulit).

Berikut ialah ciri gamma sebagai mod penyulitan:

1. Blok yang sama dalam tatasusunan data terbuka akan menghasilkan blok teks sifir yang berbeza apabila disulitkan, yang akan memungkinkan untuk menyembunyikan fakta identiti mereka.
2. Oleh kerana tindanan gamma dilakukan secara bitwise, penyulitan blok separa data mudah dicapai dengan menyulitkan bit blok separa itu dengan menggunakan bit blok gamma yang sepadan. Oleh itu, untuk menyulitkan blok tidak lengkap 1 bit, mengikut piawaian, bit paling tidak ketara daripada blok gamma harus digunakan.
3. Mesej penyegerakan yang digunakan untuk penyulitan entah bagaimana mesti dihantar untuk digunakan dalam penyahsulitan. Ini boleh dicapai dengan cara berikut:

• menyimpan atau menghantar mesej penyegerakan bersama-sama dengan tatasusunan data yang disulitkan, yang akan membawa kepada peningkatan dalam saiz tatasusunan data apabila disulitkan mengikut saiz mesej penyegerakan, iaitu sebanyak 8 bait;
• gunakan nilai yang telah ditetapkan bagi mesej penyegerakan atau jananya secara serentak oleh sumber dan penerima mengikut undang-undang tertentu, dalam kes ini tidak ada perubahan dalam saiz tatasusunan data yang dihantar atau disimpan;

Kedua-dua kaedah saling melengkapi, dan dalam kes-kes yang jarang berlaku di mana yang pertama, yang paling biasa tidak berfungsi, yang kedua, yang lebih eksotik boleh digunakan. Kaedah kedua mempunyai aplikasi yang lebih sedikit, kerana adalah mungkin untuk membuat mesej penyegerakan ditetapkan hanya jika tidak lebih daripada satu tatasusunan data disulitkan pada set maklumat utama yang diberikan, yang tidak berlaku dengan kerap. Ia juga tidak selalu mungkin untuk menjana mesej penyegerakan secara serentak pada sumber dan penerima tatasusunan data, kerana ia memerlukan sambungan yang ketat kepada sesuatu dalam sistem. Oleh itu, idea yang kelihatan kukuh untuk menggunakan nombor mesej yang dihantar sebagai mesej penyegerakan dalam sistem untuk menghantar mesej yang disulitkan adalah tidak sesuai, kerana mesej itu mungkin hilang dan tidak sampai kepada penerima, dalam hal ini sistem penyulitan sumber dan penerima akan menjadi tidak segerak. Oleh itu, dalam kes yang dipertimbangkan, tiada alternatif untuk menghantar mesej penyegerakan bersama dengan mesej yang disulitkan.

Sebaliknya, contoh yang bertentangan boleh diberikan. Katakan penyulitan data digunakan untuk melindungi maklumat pada cakera, dan ia dilaksanakan pada tahap yang rendah untuk memastikan akses bebas, data disulitkan mengikut sektor; Dalam kes ini, adalah mustahil untuk menyimpan mesej penyegerakan bersama-sama dengan data yang disulitkan, kerana saiz sektor tidak boleh diubah, tetapi ia boleh dikira sebagai beberapa fungsi nombor kepala baca cakera, nombor trek (silinder) dan nombor sektor di atas trek. Dalam kes ini, mesej penyegerakan terikat pada kedudukan sektor pada cakera, yang tidak mungkin berubah tanpa memformat semula cakera, iaitu, tanpa memusnahkan data di atasnya.

Mod gamma mempunyai satu lagi ciri menarik. Dalam mod ini, bit tatasusunan data disulitkan secara berasingan antara satu sama lain. Oleh itu, setiap bit teks sifir bergantung pada bit plaintext yang sepadan dan, sudah tentu, nombor jujukan bit dalam tatasusunan: . Ini menunjukkan bahawa menukar bit siferteks kepada nilai bertentangan akan menghasilkan perubahan yang serupa kepada nilai bertentangan bit teks biasa:

di mana menandakan songsang berkenaan dengan t nilai bit().

Sifat ini memberi peluang kepada penyerang, dengan mempengaruhi bit teks sifir, untuk membuat perubahan yang boleh diramal dan juga disasarkan pada teks biasa sepadan yang diperoleh selepas penyahsulitan, tanpa memiliki kunci rahsia. Ini menggambarkan fakta yang terkenal dalam kriptologi bahawa kerahsiaan dan keaslian adalah sifat yang berbeza sistem kriptografi . Dalam erti kata lain, sifat sistem kripto untuk memberikan perlindungan terhadap akses tanpa kebenaran kepada kandungan mesej dan terhadap perubahan tanpa kebenaran pada mesej adalah bebas dan hanya boleh bertindih dalam kes tertentu. Ini bermakna terdapat algoritma kriptografi yang memberikan kerahsiaan tertentu data yang disulitkan dan pada masa yang sama tidak melindungi daripada perubahan dalam apa jua cara, dan sebaliknya, memastikan keaslian data dan sama sekali tidak mengehadkan keupayaan untuk membiasakan diri dengan mereka. Atas sebab ini, sifat yang dipertimbangkan bagi mod gamma tidak boleh dianggap sebagai kelemahannya.

Gamma dengan maklum balas.

Mod ini sangat serupa dengan mod gamma dan berbeza daripadanya hanya dalam cara unsur gamma dijana - unsur gamma seterusnya dijana hasil daripada transformasi 32-3 kitaran blok sebelumnya data yang disulitkan, dan untuk menyulitkan blok pertama tatasusunan data, unsur gamma dijana hasil daripada kitaran penyegerakan transformasi yang sama. Ini mencapai rantaian blok—setiap blok teks sifir dalam mod ini bergantung pada blok plaintext yang sepadan dan sebelumnya. Oleh itu, mod ini kadangkala dipanggil permainan dengan blok saling mengunci . Fakta bahawa blok dipautkan tidak mempunyai kesan ke atas kekuatan sifir.

Gambar rajah algoritma penyulitan dan penyahsulitan dalam mod gamma dengan maklum balas ditunjukkan dalam Rajah 5 dan, kerana kesederhanaannya, tidak memerlukan sebarang ulasan.

Rajah 5. Algoritma untuk menyulitkan (menyahsulit) data dalam mod gamma dengan maklum balas.

Penyulitan gamma gelung tertutup mempunyai ciri yang sama seperti penyulitan gamma biasa, kecuali untuk kesan rasuah teks sifir pada plaintext yang sepadan. Sebagai perbandingan, mari tuliskan fungsi penyahsulitan blok untuk kedua-dua mod yang disebutkan:

Gumming;

Gamma dengan maklum balas;

Jika dalam mod gamma biasa, perubahan dalam bit tertentu bagi teks sifir hanya mempengaruhi bit teks biasa yang sepadan, maka dalam mod gamma maklum balas gambarnya agak rumit. Seperti yang dapat dilihat daripada persamaan yang sepadan, apabila menyahsulit blok data dalam mod gamma gelung tertutup, blok data terbuka bergantung pada blok data yang disulitkan yang sepadan dan sebelumnya. Oleh itu, jika anda memperkenalkan herotan ke dalam blok yang disulitkan, maka selepas penyahsulitan dua blok data terbuka akan diputarbelitkan - yang sepadan dan yang mengikutinya, dan herotan dalam kes pertama akan menjadi sifat yang sama seperti dalam mod gamma , dan dalam kes kedua - seperti dalam penggantian mudah. Dalam erti kata lain, dalam blok data terbuka yang sepadan, bit yang sama akan rosak seperti dalam blok data yang disulitkan, dan dalam blok data terbuka seterusnya semua bit adalah bebas antara satu sama lain dengan kebarangkalian 1 / 2 akan mengubah nilai mereka.

Pembangunan sisipan simulasi untuk tatasusunan data.

Dalam bahagian sebelumnya, kami membincangkan kesan rasuah data yang disulitkan pada data biasa yang sepadan. Kami telah menetapkan bahawa apabila menyahsulit dalam mod gantian mudah, blok data terbuka yang sepadan ternyata diputarbelitkan dengan cara yang tidak dapat diramalkan, dan apabila menyahsulit blok dalam mod gamma, perubahan boleh diramalkan. Dalam mod gamma gelung tertutup, dua blok menjadi herot, satu dalam cara yang boleh diramal dan satu lagi dalam cara yang tidak dapat diramalkan. Adakah ini bermakna bahawa dari sudut pandangan perlindungan terhadap pengenaan data palsu, mod gamma adalah buruk, dan penggantian mudah dan mod gamma maklum balas adalah baik? - Walau apa pun. Apabila menganalisis keadaan ini, adalah perlu untuk mengambil kira bahawa perubahan yang tidak dapat diramalkan dalam blok data yang dinyahsulit hanya boleh dikesan jika data yang sama ini berlebihan, dan semakin besar tahap redundansi, semakin besar kemungkinan pengesanan herotan. Lebihan yang sangat besar berlaku, sebagai contoh, untuk teks dalam bahasa semula jadi dan buatan, dalam kes ini fakta herotan dikesan hampir tidak dapat dielakkan. Walau bagaimanapun, dalam kes lain, sebagai contoh, apabila imej bunyi yang didigitalkan dimampatkan diherotkan, kita hanya akan mendapat imej yang berbeza yang boleh dilihat oleh telinga kita. Herotan dalam kes ini akan kekal tidak dapat dikesan, melainkan, sudah tentu, terdapat maklumat apriori tentang sifat bunyi. Kesimpulannya di sini adalah ini: memandangkan keupayaan beberapa mod penyulitan untuk mengesan herotan yang diperkenalkan ke dalam data yang disulitkan bergantung dengan ketara pada kehadiran dan tahap redundansi data yang disulitkan, kebolehan ini bukanlah sifat yang wujud dalam mod yang sepadan dan tidak boleh dianggap sebagai kelebihan mereka.

Untuk menyelesaikan masalah mengesan herotan dalam tatasusunan data yang disulitkan dengan kebarangkalian tertentu, GOST menyediakan mod tambahan transformasi kriptografi - pembangunan sisipan tiruan. Sisipan tiruan ialah gabungan kawalan yang bergantung pada data terbuka dan maklumat kunci rahsia. Tujuan menggunakan sisipan tiruan adalah untuk mengesan semua perubahan yang tidak disengajakan atau disengajakan dalam tatasusunan maklumat. Masalah yang diterangkan dalam perenggan sebelumnya boleh berjaya diselesaikan dengan menambahkan sisipan tiruan pada data yang disulitkan. Bagi bakal penyerang, dua tugas berikut hampir mustahil untuk diselesaikan jika dia tidak mempunyai kunci:

• pengiraan sisipan tiruan untuk susunan maklumat terbuka yang diberikan;
• pemilihan data terbuka untuk sisipan simulasi yang diberikan;

Gambar rajah algoritma untuk membangunkan sisipan simulasi ditunjukkan dalam Rajah 6.

Rajah 6. Algoritma untuk membangunkan sisipan simulasi untuk tatasusunan data.

Sebahagian daripada blok yang diterima pada output diambil sebagai sisipan simulasi, biasanya 32 bit paling tidak ketara. Apabila memilih saiz sisipan palsu, seseorang mesti mengambil kira bahawa kebarangkalian berjaya mengenakan data palsu adalah sama dengan 2 –| saya | setiap percubaan pemilihan, melainkan penyerang mempunyai kaedah pemilihan yang lebih berkesan daripada meneka mudah. Apabila menggunakan sisipan simulasi 32-bit, kebarangkalian ini adalah sama dengan

Perbincangan algoritma kriptografi GOST.

Kekuatan kriptografi GOST.

Apabila memilih algoritma kriptografi untuk digunakan dalam pembangunan tertentu, salah satu faktor penentu adalah kekuatannya, iaitu rintangan terhadap percubaan musuh untuk mendedahkannya. Apabila diteliti lebih dekat, persoalan tentang kekuatan sifir datang kepada dua soalan yang saling berkaitan:

• Adakah mungkin untuk memecahkan sifir ini sama sekali?
• jika ya, betapa sukarnya untuk dilakukan secara praktikal;

Sifir yang tidak boleh dipecahkan sama sekali dipanggil kuat secara mutlak atau secara teori. Kewujudan sifir sedemikian dibuktikan oleh teorem Shannon, tetapi harga kekuatan ini adalah keperluan untuk menggunakan kunci untuk menyulitkan setiap mesej yang tidak lebih kecil saiznya daripada mesej itu sendiri. Dalam semua kes, kecuali beberapa kes khas, harga ini adalah berlebihan, jadi dalam amalan, sifir yang tidak benar-benar selamat digunakan terutamanya. Oleh itu, skim penyulitan yang paling biasa boleh dipecahkan dalam masa yang terhad, atau, lebih tepat lagi, dalam bilangan langkah yang terhad, setiap satunya adalah beberapa jenis operasi pada nombor. Bagi mereka, konsep yang paling penting ialah kegigihan praktikal, yang menyatakan kesukaran praktikal penemuan mereka. Ukuran kuantitatif kesukaran ini boleh menjadi bilangan operasi aritmetik dan logik asas yang mesti dilakukan untuk membuka sifir, iaitu, untuk menentukan plaintext yang sepadan untuk teks sifir tertentu dengan kebarangkalian tidak kurang daripada nilai tertentu. Pada masa yang sama, sebagai tambahan kepada tatasusunan data yang dinyahsulit, penganalisis mungkin mempunyai blok data terbuka dan data yang disulitkan yang sepadan, atau bahkan keupayaan untuk mendapatkan data yang disulitkan yang sepadan untuk mana-mana data terbuka yang dia pilih - bergantung pada senarai dan banyak lagi yang tidak ditentukan. keadaan, jenis kriptanalisis yang berasingan dibezakan.

Semua sistem kripto moden dibina berdasarkan prinsip Kirchhoff, iaitu, kerahsiaan mesej yang disulitkan ditentukan oleh kerahsiaan kunci. Ini bermakna walaupun algoritma penyulitan itu sendiri diketahui oleh cryptanalyst, dia, bagaimanapun, tidak dapat menyahsulit mesej jika dia tidak mempunyai kunci yang sesuai. Sifir dianggap direka dengan baik jika tiada cara untuk memecahkannya dengan lebih cekap daripada dengan kekerasan ke atas keseluruhan ruang utama, i.e. atas semua nilai utama yang mungkin. GOST mungkin sepadan dengan prinsip ini - selama bertahun-tahun penyelidikan intensif, tiada satu kaedah berkesan kriptanalisisnya telah dicadangkan. Dari segi kekuatan, ia adalah banyak pesanan magnitud yang lebih tinggi daripada standard penyulitan Amerika sebelumnya, DES.

GOST menggunakan kekunci 256-bit dan kelantangan ruang kekunci ialah 2,256. Tiada satu pun daripada peranti elektronik yang sedia ada atau dijangka akan dilaksanakan dalam masa terdekat boleh digunakan untuk mengambil kunci dalam masa kurang daripada beratus-ratus tahun. Nilai ini telah menjadi standard saiz kunci de facto untuk algoritma kriptografi simetri hari ini, dan standard penyulitan AS baharu turut menyokongnya. Bekas piawaian Amerika, DES, dengan saiz kunci sebenar 56 bit dan volum ruang kunci hanya 2 56 tidak lagi cukup stabil berdasarkan keupayaan alat pengkomputeran moden. Ini telah ditunjukkan pada akhir 90-an oleh beberapa percubaan kekerasan yang berjaya untuk memecahkan DES. Di samping itu, DES terdedah kepada teknik kriptanalisis khas seperti pembezaan dan linear. Dalam hal ini, DES mungkin mempunyai kepentingan penyelidikan atau saintifik dan bukannya kepentingan praktikal. Pada tahun 1998, kelemahan kriptografinya diiktiraf secara rasmi - Institut Piawaian Kebangsaan AS mengesyorkan penggunaan penyulitan DES tiga kali ganda. Dan pada penghujung tahun 2001, piawaian penyulitan AS yang baharu, AES, telah diluluskan secara rasmi, dibina berdasarkan prinsip yang berbeza dan bebas daripada kelemahan pendahulunya.

Nota mengenai seni bina GOST.

Adalah diketahui umum bahawa piawaian penyulitan domestik adalah mewakili seluruh keluarga sifir yang dibina berdasarkan prinsip yang sama. "Saudara"nya yang paling terkenal ialah standard penyulitan Amerika dahulu, algoritma DES. Semua sifir ini, seperti GOST, mengandungi algoritma tiga peringkat. Pada teras sentiasa ada "langkah asas" tertentu, berdasarkan "kitaran asas" dibina dengan cara yang sama, dan berdasarkan prosedur praktikal untuk penyulitan dan pembangunan sisipan tiruan dibina. Oleh itu, kekhususan setiap sifir keluarga ini terletak tepat pada langkah utamanya, atau lebih tepat lagi pada bahagiannya. Walaupun seni bina sifir blok klasik, yang mana GOST merujuk, terletak jauh di luar skop artikel ini, ia masih bernilai mengatakan beberapa perkataan mengenainya.

Algoritma untuk "langkah utama transformasi kripto" untuk sifir seperti GOST dibina dengan cara yang sama, dan seni bina ini dipanggil rangkaian Feistel yang seimbang (rangkaian Feistel seimbang) selepas nama orang yang mula-mula mencadangkannya. Skim penukaran data pada satu kitaran, atau, seperti yang biasa dipanggil, bulat , ditunjukkan dalam Rajah 7.

Rajah 7. Kandungan langkah utama kripto-transformasi untuk sifir blok serupa dengan GOST.

Satu blok bersaiz genap dibekalkan kepada input langkah utama, bahagian yang lebih tinggi dan bahagian bawah diproses secara berasingan antara satu sama lain. Semasa penukaran, bahagian bawah blok diletakkan di tempat separuh yang lebih lama, dan separuh yang lebih tua, digabungkan menggunakan operasi bitwise eksklusif atau ” dengan hasil pengiraan fungsi tertentu, menggantikan fungsi yang paling muda. Fungsi ini mengambil sebagai hujah separuh rendah blok dan elemen maklumat utama ( X), ialah bahagian kandungan sifir dan dipanggil fungsi penyulitan . Atas pelbagai sebab, ternyata berfaedah untuk membahagikan blok yang disulitkan kepada dua bahagian yang sama saiz: | N 1 |=|N 2 | – fakta ini dicerminkan oleh perkataan "seimbang" dalam nama seni bina. Walau bagaimanapun, menyulitkan rangkaian tidak seimbang juga digunakan dari semasa ke semasa, walaupun tidak sekerap yang seimbang. Di samping itu, pertimbangan kekuatan sifir memerlukan saiz elemen utama tidak boleh kurang daripada saiz separuh blok: dalam GOST, ketiga-tiga saiz adalah sama dengan 32 bit .

Jika kita menggunakan perkara di atas pada rajah langkah utama algoritma GOST, ia akan menjadi jelas bahawa blok 1,2,3 algoritma (lihat Rajah 1) menentukan pengiraan fungsi penyulitannya, dan blok 4 dan 5 nyatakan pembentukan blok keluaran langkah utama berdasarkan kandungan blok input dan nilai fungsi penyulitan. Butiran lanjut tentang seni bina sifir blok moden dengan kunci rahsia boleh didapati dalam karya klasik, atau, dalam bentuk yang disesuaikan, dalam karya saya.

Dalam bahagian sebelumnya, kami telah membandingkan DES dan GOST dari segi ketahanan, kini kami akan membandingkannya dari segi kandungan berfungsi dan kemudahan pelaksanaan. Dalam kitaran penyulitan GOST, langkah utama diulang sebanyak 32 kali, untuk DES nilai ini ialah 16. Walau bagaimanapun, fungsi penyulitan GOST itu sendiri adalah lebih mudah daripada fungsi DES yang serupa, yang mengandungi banyak pilih atur bit tidak teratur. Operasi ini sangat tidak cekap pada pemproses bukan khusus moden. GOST tidak mengandungi operasi sedemikian, jadi ia lebih mudah untuk pelaksanaan perisian.

Tiada satu pun pelaksanaan DES untuk platform Intel x86 yang disemak oleh pengarang mencapai separuh prestasi pelaksanaan GOST yang dicadangkan dalam artikel ini, walaupun kitaran dua kali lebih pendek. Semua perkara di atas menunjukkan bahawa pemaju GOST mengambil kira kedua-dua aspek positif dan negatif DES, dan juga secara lebih realistik menilai keupayaan kriptanalisis semasa dan masa depan. Walau bagaimanapun, mengambil DES sebagai asas apabila membandingkan prestasi pelaksanaan sifir tidak lagi relevan. Piawaian penyulitan AS baharu melakukan lebih baik dengan kecekapan - dengan saiz kunci yang sama seperti GOST (256 bit), AES berfungsi kira-kira 14% lebih pantas - ini jika dibandingkan dari segi bilangan "operasi asas". Di samping itu, GOST secara praktikal tidak boleh disejajarkan, manakala AES mempunyai lebih banyak kemungkinan dalam hal ini. Pada sesetengah seni bina kelebihan AES ini mungkin kurang, pada yang lain mungkin lebih besar. Jadi, pada pemproses Intel Pentium ia mencapai 28%. Butiran boleh didapati di.

Keperluan untuk kualiti maklumat utama dan sumber kunci.

Tidak semua kekunci dan jadual gantian memberikan kekuatan sifir maksimum. Setiap algoritma penyulitan mempunyai kriteria tersendiri untuk menilai maklumat penting. Oleh itu, untuk algoritma DES diketahui bahawa terdapat apa yang dipanggil " kunci yang lemah ", apabila digunakan, sambungan antara data terbuka dan yang disulitkan tidak bertopeng secukupnya, dan sifir agak mudah dipecahkan.

Sekiranya jawapan komprehensif kepada soalan mengenai kriteria kualiti kunci GOST dan jadual penggantian boleh diperolehi di mana-mana sahaja, ia hanya boleh dari pemaju algoritma. Data yang berkaitan tidak diterbitkan dalam akhbar terbuka. Walau bagaimanapun, mengikut prosedur yang ditetapkan, untuk menyulitkan maklumat terperingkat, data utama yang diterima daripada organisasi yang diberi kuasa mesti digunakan. Secara tidak langsung, ini mungkin menunjukkan adanya kaedah untuk menyemak data utama untuk kutu. Jika kehadiran kunci lemah dalam GOST adalah isu yang boleh dipertikaikan, maka kehadiran unit penggantian yang lemah tidak dapat diragui. Jelas sekali, jadual penggantian "remeh", mengikut mana mana-mana nilai diganti dengan sendirinya, sangat lemah sehingga apabila menggunakannya, sifir boleh dipecahkan dengan mudah, tidak kira apa kuncinya.

Seperti yang dinyatakan di atas, kriteria untuk menilai maklumat penting tidak tersedia, tetapi beberapa pertimbangan umum masih boleh dibuat mengenainya.

kunci

Kunci mestilah susunan bit bebas statistik yang mengambil nilai 0 dan 1 dengan kebarangkalian yang sama Ia tidak boleh diketepikan sepenuhnya bahawa beberapa nilai kunci tertentu mungkin menjadi "lemah", iaitu sifir mungkin tidak memberikan tahap kekuatan yang ditentukan jika digunakan. Walau bagaimanapun, mungkin, perkadaran nilai sedemikian dalam jumlah jisim semua kunci yang mungkin adalah kecil. Sekurang-kurangnya, penyelidikan intensif ke dalam sifir belum lagi mendedahkan satu kunci sedemikian untuk mana-mana jadual penggantian yang diketahui (iaitu, dicadangkan oleh FAPSI). Oleh itu, kunci yang dijana menggunakan beberapa penderia nombor yang benar-benar rawak akan berkualiti tinggi dengan kebarangkalian yang berbeza daripada perpaduan dengan jumlah yang sangat kecil. Jika kunci dijana menggunakan penjana nombor pseudo-rawak, maka penjana yang digunakan mesti menyediakan ciri statistik di atas, dan, sebagai tambahan, mempunyai kekuatan kriptografi yang tinggi - tidak kurang daripada GOST itu sendiri. Dalam erti kata lain, tugas menentukan anggota yang hilang bagi urutan unsur yang dihasilkan oleh penjana tidak seharusnya lebih mudah daripada tugas memecahkan sifir. Di samping itu, pelbagai kriteria statistik boleh digunakan untuk menolak kunci dengan ciri statistik yang lemah. Dalam praktiknya, dua kriteria biasanya mencukupi: untuk memeriksa pengedaran bit kunci yang sama antara nilai 0 dan 1, ujian Pearson (chi square) biasanya digunakan, dan untuk memeriksa kebebasan bit kunci, ujian larian digunakan. . Anda boleh membaca tentang kriteria yang disebutkan dalam buku teks atau buku rujukan tentang statistik matematik.

Pendekatan terbaik untuk menjana kunci ialah menggunakan penderia julat pertengahan perkakasan, tetapi ini tidak selalu boleh diterima atas sebab ekonomi. Apabila menjana susunan kecil maklumat penting, alternatif yang munasabah untuk menggunakan penderia sedemikian ialah kaedah "rolet elektronik", yang digunakan secara meluas dalam amalan, apabila bahagian bit rawak yang dijana seterusnya bergantung pada saat dalam masa operator menekan a kekunci tertentu pada papan kekunci komputer. Dalam skema ini, sumber data rawak ialah pengguna komputer, atau lebih tepat lagi, ciri masa tindak balasnya. Dalam kes ini, hanya beberapa bit data rawak boleh dijana setiap ketukan kekunci, jadi kelajuan keseluruhan menjana maklumat utama adalah rendah - sehingga beberapa bit sesaat. Jelas sekali, pendekatan ini tidak sesuai untuk mendapatkan tatasusunan kunci yang besar.

Dalam kes apabila perlu untuk menjana pelbagai maklumat penting, penggunaan pelbagai perisian penderia nombor pseudo-rawak adalah mungkin dan sangat meluas. Memandangkan sensor sedemikian memerlukan tahap kekuatan kriptografi yang tinggi, adalah wajar untuk menggunakan penjana gamma sifir itu sendiri kerana ia - kami hanya "memotong" gamma yang dihasilkan oleh sifir menjadi "kepingan" saiz yang diperlukan, untuk GOST - 32 bait. Sudah tentu, untuk pendekatan ini kita memerlukan "kunci induk", yang boleh kita peroleh menggunakan kaedah rolet elektronik yang diterangkan di atas, dan dengan bantuannya, menggunakan sifir dalam mod penjana gamma, kita memperoleh pelbagai maklumat penting dengan saiz kita perlu. Jadi kedua-dua kaedah menjana kunci ini - "manual" dan "algoritma" - berfungsi seiring, saling melengkapi. Skim penjanaan utama dalam sistem perlindungan kriptografi maklumat "bajet rendah" hampir selalu dibina berdasarkan prinsip ini.

Jadual penggantian

Jadual gantian ialah elemen kunci jangka panjang, iaitu, ia sah untuk tempoh yang lebih lama daripada satu kunci. Diandaikan bahawa ia adalah perkara biasa kepada semua nod penyulitan dalam sistem perlindungan kriptografi yang sama. Walaupun kerahsiaan jadual penggantian dilanggar, kekuatan sifir kekal sangat tinggi dan tidak berkurangan di bawah had yang dibenarkan. Oleh itu, tidak ada keperluan khusus untuk merahsiakan jadual, dan dalam kebanyakan aplikasi komersial GOST ini dilakukan. Sebaliknya, jadual penggantian adalah elemen kritikal untuk memastikan kekuatan keseluruhan sifir. Memilih jadual yang salah boleh menyebabkan sifir mudah dipecahkan oleh teknik analisis kriptografi yang diketahui. Kriteria untuk membangunkan unit gantian adalah rahsia yang dijaga rapi dan FAPSI tidak mungkin akan berkongsinya dengan orang ramai dalam masa terdekat. Akhirnya, memberitahu sama ada jadual penggantian yang diberikan adalah baik atau buruk memerlukan sejumlah besar kerja—beribu-ribu jam kerja dan mesin. Setelah dipilih dan digunakan, jadual mesti diganti jika dan hanya jika sifir yang menggunakannya ternyata terdedah kepada satu atau lain jenis analisis kriptografi. Oleh itu, pilihan terbaik untuk pengguna sifir biasa ialah mengambil salah satu daripada beberapa jadual yang telah menjadi umum. Contohnya, daripada standard untuk fungsi cincang, juga dikenali sebagai fungsi "perbankan pusat"; maklumat mengenai jadual ini boleh didapati di akhbar terbuka dan juga di Internet, jika anda melihat dengan cukup keras.

Bagi mereka yang tidak biasa mengambil jalan mudah, di bawah ialah skema umum untuk mendapatkan jadual berkualiti tinggi:

1. Menggunakan satu atau teknik lain, anda membangunkan satu set lapan unit gantian dengan ciri-ciri tidak linear yang dijamin. Terdapat beberapa teknik sedemikian, salah satunya ialah penggunaan fungsi bengkok yang dipanggil.
2. Anda menyemak pemenuhan "kriteria kualiti" yang paling mudah - contohnya, yang diterbitkan untuk nod penggantian DES. Berikut adalah beberapa lagi pertimbangan umum dalam hal ini: Setiap nod penggantian boleh diterangkan oleh empat fungsi logik daripada empat hujah logik. Jika fungsi ini ditulis dalam bentuk minimum(iaitu, dengan panjang ungkapan yang mungkin minimum) tidak akan cukup kompleks, nod penggantian sedemikian ditolak. Selain itu, fungsi individu dalam keseluruhan jadual penggantian mestilah cukup berbeza antara satu sama lain. Pada peringkat ini, banyak jadual jelas berkualiti rendah dihapuskan.
3. Untuk sifir dengan jadual pilihan anda, bina model bulat berbeza yang sepadan dengan jenis analisis kriptografi yang berbeza dan ukur ciri "profil" yang sepadan. Oleh itu, untuk analisis kriptografi linear, bina analog statistik linear bagi pusingan penyulitan dan hitung ciri "profil" - penunjuk tidak linear. Jika tidak mencukupi, jadual gantian ditolak.
4. Akhir sekali, dengan menggunakan keputusan perenggan sebelumnya, anda tertakluk kepada sifir dengan jadual yang telah anda pilih untuk penyelidikan intensif - percubaan pada analisis kriptografi menggunakan semua kaedah yang diketahui. Peringkat ini adalah yang paling sukar dan memakan masa. Tetapi jika ia dibuat dengan kualiti yang tinggi, maka dengan kebarangkalian yang tinggi boleh dinyatakan bahawa sifir dengan jadual yang telah anda pilih tidak akan dipecahkan oleh manusia semata-mata, dan, mungkin, akan terlalu sukar untuk kecerdasan perkhidmatan.

Walau bagaimanapun, anda boleh melakukannya dengan lebih mudah. Masalahnya ialah semakin banyak pusingan dalam sifir, semakin kurang pengaruh ciri kekuatan satu pusingan terhadap kekuatan keseluruhan sifir. GOST mempunyai sebanyak 32 pusingan - lebih banyak daripada hampir semua sifir dengan seni bina yang serupa. Oleh itu, untuk kebanyakan aplikasi domestik dan komersil adalah mencukupi untuk mendapatkan nod penggantian sebagai pilih atur rawak bebas bagi nombor dari 0 hingga 15. Ini boleh dilaksanakan secara praktikal, sebagai contoh, dengan mengocok dek enam belas kad, setiap satunya diberikan satu daripada nilai julat yang ditentukan.

Mengenai jadual penggantian, satu lagi fakta menarik harus diperhatikan. Untuk keterbalikan kitaran penyulitan "32-З" dan "32-Р", nod gantian tidak diperlukan menjadi pilih atur nombor dari 0 hingga 15. Semuanya berfungsi walaupun nod gantian mempunyai elemen pendua, dan penggantian ditentukan oleh nod sedemikian, tidak boleh diterbalikkan, tetapi dalam kes ini kekuatan sifir dikurangkan. Mengapa ini sebenarnya tidak dibincangkan dalam artikel ini, tetapi tidak sukar untuk mengesahkan fakta itu sendiri. Untuk melakukan ini, cukup untuk mula-mula cuba menyulitkan dan kemudian menyahsulit blok data menggunakan jadual penggantian "tidak lengkap", yang nodnya mengandungi nilai pendua.

Variasi pada tema GOST

Selalunya, untuk digunakan dalam sistem perlindungan data kriptografi, algoritma dengan kelajuan pelaksanaan yang lebih pantas daripada GOST diperlukan, dan kekuatan kriptografi yang tinggi tidak diperlukan. Contoh tipikal tugas sedemikian ialah pelbagai jenis sistem perdagangan saham elektronik yang menguruskan sesi dagangan dalam masa nyata. Di sini, algoritma penyulitan yang digunakan diperlukan untuk menjadikannya mustahil untuk menyahsulit data operasi sistem semasa sesi (data mengenai pesanan yang diserahkan, transaksi yang disimpulkan, dll.), Selepas tamat tempohnya, data ini, sebagai peraturan, tidak lagi tidak berguna untuk penyerang. Dalam erti kata lain, jaminan ketahanan hanya beberapa jam diperlukan - ini adalah tempoh biasa sesi dagangan. Adalah jelas bahawa menggunakan GOST sepenuhnya dalam situasi ini akan menembak burung pipit dengan meriam.

Apa yang perlu dilakukan dalam kes ini dan yang serupa untuk meningkatkan kelajuan penyulitan? Jawapannya terletak pada permukaan - gunakan pengubahsuaian sifir dengan lebih sedikit langkah utama (pusingan) dalam kitaran asas. Masa kami mengurangkan bilangan pusingan penyulitan, prestasi meningkat dengan jumlah yang sama. Perubahan ini boleh dicapai dalam dua cara - dengan mengurangkan panjang kunci dan mengurangkan bilangan "kitaran semakan" kunci. Ingat bahawa bilangan langkah asas dalam kitaran penyulitan asas ialah N=n·m, Di mana n– bilangan elemen 32-bit dalam kunci, m– bilangan kitaran penggunaan elemen utama, dalam standard n=8, m=4. Anda boleh mengurangkan mana-mana nombor ini, tetapi pilihan paling mudah ialah mengurangkan panjang kekunci tanpa menjejaskan cara ia digunakan.

Adalah jelas bahawa harga untuk mempercepatkan kerja akan menjadi penurunan kekuatan sifir. Kesukaran utama adalah agak sukar untuk menganggarkan secara lebih kurang tepat magnitud pengurangan ini. Jelas sekali, satu-satunya cara yang mungkin untuk melakukan ini adalah dengan menjalankan kajian skala penuh varian sifir dengan kitaran penukaran kriptografi yang dikurangkan. Adalah jelas bahawa, pertama, ini memerlukan penggunaan maklumat terperingkat, yang hanya dimiliki oleh pemaju GOST, dan, kedua, ia sangat intensif buruh. Oleh itu, kami kini akan cuba memberikan penilaian yang sangat, sangat kasar, hanya berdasarkan corak umum.

Bagi rintangan sifir untuk retak dengan kaedah "luas", iaitu, kepada serangan "kekerasan", semuanya lebih kurang jelas di sini: kunci 64 bit berada di suatu tempat di ambang boleh diakses oleh jenis ini serangan, sifir dengan kunci 96 bit atau lebih tinggi ( ingat bahawa kunci mesti mengandungi nombor integer unsur 32-bit) agak tahan terhadapnya. Malah, beberapa tahun yang lalu, piawaian penyulitan AS sebelumnya, DES, telah berulang kali digodam oleh kaedah kekerasan - mula-mula ia digodam oleh rangkaian komputer yang dianjurkan berdasarkan Internet global, dan kemudian oleh rangkaian khusus, i.e. komputer yang direka khusus untuk tujuan ini. Mari kita anggap bahawa versi standard GOST, apabila dilaksanakan dalam perisian pada pemproses moden, berfungsi empat kali lebih cepat daripada DES. Kemudian "GOST dikurangkan" 8 pusingan akan berfungsi 16 kali lebih cepat daripada DES. Mari kita anggap juga bahawa pada masa sejak penggodaman DES, prestasi pengkomputeran telah meningkat empat kali ganda mengikut Undang-undang Moore. Akibatnya, kami mendapat bahawa sekarang menyemak satu kunci 64-bit untuk "GOST yang dikurangkan" dengan lapan kitaran adalah 64 kali lebih pantas daripada menyemak satu kunci DES pada satu masa. Oleh itu, kelebihan versi GOST ini berbanding DES dari segi kerumitan serangan kekerasan dikurangkan daripada 2 64–56 = 2 8 = 256 kepada 256 / 64 = 4 kali. Setuju, ini adalah perbezaan yang sangat ilusi, hampir tiada apa-apa.

Adalah lebih sukar untuk menilai rintangan pengubahsuaian GOST yang lemah kepada kaedah kriptanalisis "intensif". Walau bagaimanapun, corak umum boleh dikesan di sini juga. Hakikatnya ialah ciri "profil" kebanyakan jenis kriptanalisis yang paling berkuasa hari ini bergantung secara eksponen pada bilangan pusingan penyulitan. Jadi, untuk kriptanalisis linear (LCA) ini akan menjadi ciri lineariti L :

di mana C dan adalah pemalar, R ialah bilangan pusingan. Hubungan serupa wujud untuk analisis kriptografi pembezaan. Dalam "makna fizikal" mereka, semua ciri jenis ini adalah kebarangkalian. Biasanya, jumlah data awal yang diperlukan untuk kriptanalisis dan kerumitannya adalah berkadar songsang dengan ciri-ciri tersebut. Ini berikutan bahawa penunjuk intensiti buruh ini berkembang dengan pesat dengan bilangan langkah penyulitan asas. Oleh itu, apabila bilangan pusingan dikurangkan beberapa kali, kerumitan jenis analisis yang paling terkenal akan berubah sebagai, lebih kurang dan lebih kurang, punca kuasa ini daripada kuantiti asal. Ini adalah penurunan ketahanan yang sangat besar.

Sebaliknya, GOST direka dengan margin keselamatan yang besar dan hari ini tahan terhadap semua jenis analisis kriptografi yang diketahui, termasuk pembezaan dan linear. Berhubung dengan LCA, ini bermakna bahawa untuk pelaksanaannya yang berjaya, lebih banyak pasangan "blok terbuka - blok disulitkan" diperlukan daripada "wujud dalam alam semula jadi," iaitu, lebih daripada 2 64 . Dengan mengambil kira perkara di atas, ini bermakna untuk LCA yang berjaya bagi GOST 16 pusingan, sekurang-kurangnya blok atau 2 35 bait atau 32 GB data akan diperlukan dan untuk 8 pusingan, sekurang-kurangnya blok atau 2 19 bait atau 0.5 MB.

Kesimpulan dari semua perkara di atas diberikan dalam jadual berikut, yang meringkaskan ciri-ciri versi GOST yang dikurangkan.

Bilangan pusingan	Saiz kunci, bit	Indeks prestasi	Ciri-ciri kemungkinan sifir (anggaran sangat kasar)
24	192	1,33	Tahan kepada jenis CA yang paling terkenal, atau di ambang rintangan. Pelaksanaan praktikal CA adalah mustahil kerana keperluan yang tinggi untuk data awal dan intensiti buruh.
16	128	2	Secara teorinya, ia tidak stabil untuk beberapa jenis kriptanalisis, tetapi pelaksanaan praktikalnya dalam kebanyakan kes adalah sukar kerana keperluan yang tinggi untuk data sumber dan intensiti buruh.
12	95	2,67	Ia tidak tahan kepada beberapa jenis analisis kriptografi yang diketahui, tetapi sesuai untuk memastikan kerahsiaan sejumlah kecil data (sehingga puluhan atau ratusan kilobait) untuk tempoh masa yang singkat.
8	64	4	Ia tidak tahan kepada beberapa jenis analisis kriptografi yang diketahui, tetapi sesuai untuk memastikan kerahsiaan sejumlah kecil data (sehingga berpuluh-puluh kilobait) untuk jangka masa yang singkat.

Dua pilihan terakhir, dengan 12 dan 8 pusingan, mampu memberikan perlindungan masa yang sangat terhad. Penggunaannya adalah wajar hanya dalam tugasan di mana hanya kerahsiaan jangka pendek data yang dilindungi diperlukan, mengikut urutan beberapa jam. Kawasan yang mungkin digunakan untuk varian sifir yang lemah ini adalah untuk menyekat trafik UDP daripada sistem perdagangan pertukaran elektronik. Dalam kes ini, setiap paket data (datagram, tengah "D" daripada singkatan UDP) disulitkan menggunakan kunci 64-bit yang berasingan, dan kunci itu sendiri disulitkan menggunakan kunci sesi (kunci yang skopnya adalah satu sesi komunikasi antara dua komputer) dan dihantar bersama data.

Sebelum menamatkan versi GOST yang dikurangkan, saya akan mengatakan bahawa semua pertimbangan di atas adalah sangat spekulatif. Standard ini menyediakan ketahanan untuk hanya satu, varian 32 pusingan. Dan tiada siapa yang boleh memberi anda jaminan bahawa rintangan versi sifir yang dikurangkan kepada retak akan berubah mengikut cara yang ditunjukkan di atas. Walau bagaimanapun, jika anda memutuskan untuk menggunakannya dalam perkembangan anda, ingat bahawa anda telah memijak tanah yang sangat goyah, yang boleh tergelincir dari bawah kaki anda pada bila-bila masa. Memandangkan kelajuan penyulitan adalah isu kritikal untuk anda, mungkin anda perlu mempertimbangkan untuk menggunakan sifir yang lebih pantas atau komputer yang lebih berkuasa? Pertimbangan lain mengapa ini patut dilakukan ialah versi GOST yang lemah akan menjadi paling sensitif terhadap kualiti unit gantian yang digunakan.

Isu yang sedang dipertimbangkan juga mempunyai kelemahan. Bagaimana jika kelajuan penyulitan tidak kritikal, tetapi keperluan kekuatan sangat ketat? Rintangan GOST boleh ditingkatkan dalam dua cara - mari kita panggil mereka "luas" dan "intensif". Yang pertama daripada mereka tidak lebih daripada peningkatan mudah dalam bilangan pusingan penyulitan. Ia tidak sepenuhnya jelas kepada saya mengapa ini sebenarnya diperlukan, kerana piawaian domestik sudah menyediakan ketahanan yang diperlukan tanpa ini. Walau bagaimanapun, jika anda mengalami paranoia lebih daripada tahap yang diperlukan (dan semua "pembela maklumat" hanya diwajibkan untuk mengalaminya, ini adalah syarat kesesuaian profesional, satu-satunya persoalan ialah keterukan kes:), ini akan membantu awak tenang sikit. Jika anda tidak pasti tentang sifir KGB ini atau jadual penggantian yang anda gunakan, hanya dua kali ganda, empat kali ganda, dsb. bilangan pusingan – pilih kepelbagaian berdasarkan keterukan kes anda. Pendekatan ini membolehkan anda benar-benar meningkatkan kekuatan sifir - jika analisis kriptografi awal adalah mustahil, kini mustahil kuasa dua!

Soalan yang lebih rumit dan menarik ialah sama ada mungkin untuk meningkatkan kekuatan sifir tanpa mengubah nombor dan struktur langkah penyulitan utama. Anehnya, jawapan untuk ini adalah positif, walaupun kita sekali lagi melangkah di atas tanah spekulasi yang goyah. Hakikatnya ialah dalam GOST, pada langkah penukaran utama, ia sepatutnya menggantikan 4 hingga 4 bit, tetapi dalam praktiknya (kita akan membincangkannya kemudian) semua pelaksanaan perisian melakukan penggantian bait demi bait, i.e. 8 hingga 8 bit - ini dilakukan atas sebab kecekapan. Jika kami segera mereka bentuk penggantian seperti 8-bit, kami akan meningkatkan prestasi satu pusingan dengan ketara. Pertama, ciri "penyebaran" atau penunjuk "avalanche" akan meningkat - satu bit data sumber dan/atau kunci akan mempengaruhi lebih banyak bit hasil. Kedua, untuk nod penggantian yang lebih besar, ciri pembezaan dan linear yang lebih rendah boleh diperolehi, dengan itu mengurangkan kerentanan sifir kepada jenis kriptanalisis yang serupa. Ini benar terutamanya untuk kitaran GOST yang dikurangkan, dan untuk pilihan 8 dan 12 pusingan, langkah sedemikian hanya perlu. Ini sedikit sebanyak akan mengimbangi kehilangan ketahanan di dalamnya daripada pengurangan bilangan pusingan. Apa yang menyukarkan penggunaan teknik ini ialah anda perlu mereka bentuk unit gantian yang "diperbesarkan" itu sendiri. Dan juga hakikat bahawa unit yang lebih besar biasanya lebih sukar untuk dibina daripada yang lebih kecil.

Penggunaan standard yang tidak standard.

Sudah tentu, tujuan utama algoritma kriptografi GOST ialah penyulitan dan perlindungan data. Walau bagaimanapun, mereka juga boleh mencari aplikasi lain yang berkaitan, secara semula jadi, dengan keselamatan maklumat. Mari kita bercakap secara ringkas tentang mereka:

1. Untuk penyulitan dalam mod gamma, GOST menyediakan untuk pembangunan gamma kriptografi - urutan bit dengan ciri statistik yang baik dan kekuatan kriptografi yang tinggi. Gamma ini kemudiannya digunakan untuk mengubah suai data terbuka, menghasilkan data yang disulitkan. Walau bagaimanapun, ini bukan satu-satunya penggunaan gamma kriptografi yang mungkin. Hakikatnya ialah algoritma untuk penjanaannya ialah penjana jujukan nombor rawak (PRNG) dengan ciri-ciri cemerlang. Sudah tentu, menggunakan PRNG sedemikian di mana hanya ciri statistik bagi jujukan yang dijana diperlukan, tetapi kekuatan kriptografi tidak diperlukan, tidak begitu munasabah - untuk kes ini terdapat penjana yang lebih cekap. Tetapi untuk pelbagai aplikasi yang berkaitan dengan keselamatan maklumat, sumber sedemikian akan sangat berguna:

• Seperti yang dinyatakan di atas, gamma boleh digunakan sebagai "bahan mentah" untuk menjana kunci. Untuk melakukan ini, anda hanya perlu mendapatkan segmen gamma dengan panjang yang diperlukan - 32 bait. Dengan cara ini, kunci boleh dibuat mengikut keperluan dan ia tidak perlu disimpan - jika kunci sedemikian diperlukan sekali lagi, agak mudah untuk menjananya semula. Anda hanya perlu mengingati kekunci yang asalnya dijana, mesej penyegerakan yang digunakan, dan bait gamma yang dijana yang dimulakan oleh kunci itu. Semua maklumat kecuali kunci yang digunakan tidak dikelaskan. Pendekatan ini akan memudahkan untuk mengawal sistem kunci yang agak kompleks dan bercabang menggunakan hanya satu "kunci induk".
• Sama seperti yang sebelumnya, gamma boleh digunakan sebagai "bahan mentah" awal untuk menjana kata laluan. Di sini persoalan mungkin timbul: mengapa perlu untuk menjananya sama sekali bukankah lebih mudah untuk menciptanya mengikut keperluan? Kegagalan pendekatan ini jelas ditunjukkan oleh beberapa siri insiden dalam rangkaian komputer, yang terbesar adalah kelumpuhan harian Internet pada November 1988 yang disebabkan oleh cacing Morris. Salah satu cara program berniat jahat menembusi komputer adalah dengan meneka kata laluan: program itu cuba memasuki sistem dengan mencuba kata laluan secara berurutan daripada senarai dalaman beberapa ratus, dan dalam sebahagian besar kes ia berjaya. Imaginasi manusia untuk mencipta kata laluan ternyata sangat lemah. Itulah sebabnya dalam organisasi yang keselamatan diberi perhatian sewajarnya, kata laluan dijana dan diedarkan kepada pengguna oleh pentadbir keselamatan sistem. Menjana kata laluan adalah sedikit lebih rumit daripada menjana kunci, kerana dalam kes ini gamma binari "mentah" mesti ditukar kepada bentuk simbolik, dan bukan hanya "dipotong" menjadi kepingan. Selain itu, nilai individu mungkin perlu dibuang untuk memastikan semua aksara abjad berkemungkinan sama muncul dalam kata laluan.
• Satu lagi cara untuk menggunakan gamma kriptografi adalah jaminan pemadaman data pada media magnetik. Hakikatnya ialah walaupun maklumat ditulis semula pada medium magnet, kesan data terdahulu kekal, yang boleh dipulihkan melalui pemeriksaan yang sesuai. Untuk memusnahkan kesan ini, penindasan sedemikian mesti dilakukan berkali-kali. Ternyata adalah perlu untuk menulis semula maklumat ke media lebih sedikit kali jika prosedur sedemikian menggunakan data rawak atau pseudo-rawak yang akan kekal tidak diketahui oleh pakar yang cuba memulihkan maklumat yang dipadamkan. Sifir gamma akan berguna di sini.

2. Bukan sahaja gamma kriptografi, tetapi juga transformasi kriptografi itu sendiri boleh digunakan untuk keperluan yang tidak berkaitan secara langsung dengan penyulitan:

• Kami tahu bahawa salah satu pilihan untuk menggunakan GOST ini ialah pembangunan sisipan simulasi untuk tatasusunan data. Walau bagaimanapun, berdasarkan mana-mana sifir blok, termasuk GOST, agak mudah untuk membina skema untuk mengira fungsi cincang sehala, juga dipanggil dalam kesusasteraan MDC, yang dalam sumber yang berbeza bermaksud tukar kod pengesanan / manipulasi (M pengubahsuaian/ M anapulasi D etection C ode) atau ringkasan mesej (M karangan D igest C ode). Penyahkodan pertama muncul dalam kesusasteraan lebih awal, yang kedua, yang lebih pendek, saya fikir, dicipta oleh mereka yang tidak dapat mengingati yang pertama :), - ia adalah jenaka. MDC boleh digunakan secara langsung dalam sistem perlindungan tiruan sebagai analog pemasukan tiruan, yang bagaimanapun, tidak bergantung pada kunci rahsia. Di samping itu, MDC digunakan secara meluas dalam skim tandatangan digital elektronik (EDS), kerana kebanyakan skim sedemikian direka sedemikian rupa sehingga mudah untuk menandatangani blok data dengan saiz tetap. Seperti yang anda ketahui, berdasarkan piawaian GOST 28147-89 yang dibincangkan, piawaian Persekutuan Rusia untuk mengira fungsi hash sehala GOST R34.11-94 telah dibina.
• Kurang diketahui bahawa berdasarkan mana-mana sifir blok, termasuk GOST, skim tandatangan digital berfungsi sepenuhnya boleh dibina, dengan kunci tandatangan rahsia dan gabungan pengesahan terbuka. Atas beberapa sebab, skim ini tidak menerima pengedaran praktikal yang meluas, namun, dalam beberapa kes ia masih boleh dianggap sebagai alternatif yang sangat menarik kepada skim tandatangan digital "matematik" yang kini dominan di dunia.

kesusasteraan

Sistem pemprosesan maklumat. Perlindungan kriptografi. Algoritma transformasi kriptografi GOST 28147-89. negeri Com. USSR mengikut piawaian, M., 1989. ftp://ftp.wtc-ural.ru/pub/ru.crypt/GOST-28147
Shannon Claude. Teori matematik sistem rahsia. Dalam koleksi "Works on information theory and cybernetics", M., IL, 1963, hlm. 333-369. http://www.enlight.ru/crypto/articles/shannon/shann__i.htm
Mengumumkan Kelulusan Piawaian Pemprosesan Maklumat Persekutuan (FIPS) 197, Piawaian Penyulitan Lanjutan (AES), Daftar Persekutuan Vol. 66, No. 235 / Khamis, 6 Disember 2001 / Notis, ms 63369–63371. http://csrc.nist.gov/encryption/aes/
Feistel Horst. Kriptografi dan keselamatan komputer. Terjemahan oleh A. Vinokurov menurut penerbitan Horst Feistel. Kriptografi dan Privasi Komputer, Scientific American, Mei 1973, Vol. 228, No. 5, hlm. 15-23. http://www.enlight.ru/crypto/articles/feistel/feist_i.htm
Schneier Bruce. kriptografi gunaan. ed ke-2. Protokol, algoritma dan teks sumber dalam bahasa C., M., “Triumph”, 2002 http://www.ssl.stu.neva.ru/psw/crypto/appl_rus/appl_cryp.htm
Menezes Alfred, van Oorschot Paul, Vanstone Scott. Buku panduan kriptografi gunaan. ttp://www.cacr.math.uwaterloo.ca/hac/
Vinokurov Andrey. Bagaimanakah sifir blok berfungsi? Manuskrip. http://www.enlight.ru/crypto/articles/vinokurov/blcyph_i.htm
Vinokurov Andrey. Isu mengenai kriptografi untuk jurnal elektronik INFUSED BYTES dalam talian. http://www.enlight.ru/crypto/articles/ib/ib.htm
Vinokurov Andrey, Primenko Eduard. Teks laporan "Mengenai pelaksanaan perisian piawaian penyulitan di Persekutuan Rusia dan Amerika Syarikat," persidangan mengenai maklumat, Moscow, MEPhI, 28-29 Januari 2001. Diterbitkan dalam prosiding persidangan.
Teknologi maklumat. Perlindungan maklumat kriptografi. Fungsi hash GOST R34.11-94, Standard Negeri Persekutuan Rusia, M., 1994.

Algoritma ini wajib digunakan sebagai algoritma penyulitan dalam organisasi kerajaan Persekutuan Rusia dan beberapa organisasi komersial.

Penerangan tentang algoritma

Rajah algoritma ditunjukkan dalam Rajah. 3.1. Seperti yang anda lihat, reka bentuk algoritma ini agak mudah, yang jelas memudahkan pelaksanaan perisian atau perkakasannya.

Algoritma GOST 28147-89 menyulitkan maklumat dalam blok 64 bit, yang dibahagikan kepada dua subblok 32 bit (N1 dan N2). Subblock N1 diproses dengan cara tertentu, selepas itu nilainya ditambah

dengan nilai subblok N2 (penambahan dilakukan modulo 2), maka subblok ditukar. Transformasi ini dilakukan dalam bilangan pusingan tertentu: 16 atau 32, bergantung pada mod operasi algoritma (diterangkan di bawah). Operasi berikut dilakukan dalam setiap pusingan:

1. Aplikasi utama. Kandungan subblok /VI ditambah modulo 2 32 dengan sebahagian daripada kekunci Kx.

Kunci penyulitan algoritma GOST 28147-89 mempunyai dimensi 256 bit, dan Kx ialah bahagian 32-bitnya, iaitu kunci penyulitan 256-bit diwakili sebagai gabungan subkunci 32-bit (Gamb. 3.2):

Shch ATI, AG2, Yu, AG4, K5, Kb, K7.

Semasa proses penyulitan, salah satu daripada subkunci ini digunakan, bergantung pada nombor bulat dan mod operasi algoritma.

nasi. 3.1. Gambar rajah algoritma GOST 28147-

nasi. 3.2. Kunci penyulitan algoritma GOST 28147-89

2. Penggantian meja. Selepas mengekunci, subblok /VI dibahagikan kepada 8 bahagian 4 bit, nilai setiap satunya diganti secara individu mengikut jadual penggantian untuk bahagian subblok ini. Penggantian jadual (Kotak penggantian, S-box) sering digunakan dalam algoritma penyulitan moden, jadi ia patut dipertimbangkan dengan lebih terperinci.

Penggantian jadual digunakan dengan cara ini: satu blok data saiz tertentu (dalam kes ini, 4-bit) dibekalkan kepada input, perwakilan berangka yang menentukan bilangan nilai output. Sebagai contoh, kami mempunyai kotak-S dalam bentuk berikut:

4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9, 7, 5, 10, 6, 1.

Biarkan blok 4-bit "0100" datang ke input, iaitu nilai 4. Menurut jadual, nilai output akan sama dengan 15, i.e. “1111” (0 digantikan dengan 4, 1 dengan 11, nilai 2 kekal tidak berubah, dsb.).

Seperti yang anda lihat, reka bentuk algoritma adalah sangat mudah, yang bermaksud bahawa beban penyulitan data yang paling besar jatuh pada jadual gantian. Malangnya, algoritma mempunyai sifat bahawa terdapat jadual penggantian "lemah", yang menggunakan algoritma itu boleh diselesaikan dengan kaedah cryptanalytic. Yang lemah termasuk, sebagai contoh, jadual yang outputnya sama dengan input:

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15.

3. Anjakan kitaran bitwise ke kiri sebanyak 11 bit.

Mod operasi algoritma

Algoritma GOST 28147-89 mempunyai 4 mod operasi:

□ mod penggantian mudah;

□ mod gamma;

Mod P gamma dengan maklum balas;

□ cara pembangunan lampiran tiruan.

Mod ini agak berbeza daripada yang diterima umum (diterangkan dalam Bahagian 1.4), jadi ia patut dipertimbangkan dengan lebih terperinci.

Mod ini mempunyai tujuan yang berbeza, tetapi menggunakan transformasi penyulitan yang sama yang diterangkan di atas.

Mod penggantian mudah

Dalam mod gantian mudah, setiap blok maklumat 64-bit hanya disulitkan menggunakan 32 pusingan yang diterangkan di atas. Subkunci 32-bit digunakan dalam urutan berikut:

□ KO, Kl, K2, KZ, K4, K5, KB, AG7, KO, ATI, dsb. - dalam pusingan 1 hingga 24;

□ K1, Kb, K5, K4, KZ, K2, K\, KO - dalam pusingan dari 25 hingga 32.

Penyahsulitan dalam mod penggantian mudah dilakukan dengan cara yang sama, tetapi dengan urutan penggunaan subkunci yang sedikit berbeza:

□ KO, K\, K2, KZ, K4, K5, Kb, KP - dalam pusingan 1 hingga 8;

□ KP, Kb, K5, K4, KZ, K2, K\, KO, K1, Kb, dsb. - dalam pusingan dari 9 hingga 32.

Sama seperti mod ECB standard, disebabkan penyulitan blok yang berasingan, mod penggantian mudah tidak disyorkan sama sekali untuk menyulitkan data itu sendiri; ia hanya boleh digunakan untuk menyulitkan kunci penyulitan lain dalam skema berbilang kunci.

Mod gamma

Dalam mod gamma (Rajah 3.3), setiap blok teks biasa ditambah sedikit demi sedikit modulo 2 kepada blok gamma sifir 64-bit. Sifir gamma ialah jujukan khas yang dijana menggunakan transformasi yang diterangkan di atas seperti berikut:

1. Pengisian awal mereka ditulis untuk mendaftar N1 dan N2 - nilai 64-bit yang dipanggil "mesej penyegerakan" (mesej penyegerakan secara praktikalnya adalah analog bagi vektor permulaan dalam mod CBC, CFB dan OFB).

2. Kandungan daftar /VI dan N2 (dalam kes ini, mesej penyegerakan) disulitkan dalam mod gantian mudah.

3. Kandungan N1 ditambah modulo (2 32 – 1) dengan pemalar CI = 2 24 + 2 16 + 2 8 + 4, hasil penambahan ditulis pada daftar /VI.

4. Kandungan N2 ditambah modulo 2 dengan pemalar C2 = 2 24 + 2 16 + 2 8 +1, hasil penambahan ditulis untuk mendaftarkan N2.

5. Kandungan daftar /VI dan N2 dikeluarkan sebagai blok gamma sifir 64-bit (iaitu, dalam kes ini, /VI dan N2 membentuk blok gamma pertama).

6. Jika blok gamma seterusnya diperlukan (iaitu, penyulitan atau penyahsulitan selanjutnya perlu dilakukan), kembali ke langkah 2.

Untuk penyahsulitan, gamma dijana dengan cara yang sama, kemudian teks sifir dan bit gamma sekali lagi di-XOR.

Untuk menjana julat sifir yang sama, pengguna yang menyahsulit kriptogram mesti mempunyai kunci yang sama dan nilai mesej penyegerakan yang sama yang digunakan semasa menyulitkan maklumat. Jika tidak, teks asal tidak akan dapat diperoleh daripada teks yang disulitkan.

Dalam kebanyakan pelaksanaan algoritma GOST 28147-89, mesej penyegerakan bukanlah elemen rahsia, namun, mesej penyegerakan boleh menjadi rahsia seperti kunci penyulitan. Dalam kes ini, kita boleh menganggap bahawa panjang kunci berkesan algoritma (256 bit) meningkat sebanyak 64 bit lagi mesej penyegerakan, yang boleh dianggap sebagai elemen utama tambahan.

Mod gamma dengan maklum balas

Dalam mod gamma dengan maklum balas, hasil penyulitan blok plaintext sebelumnya digunakan untuk mengisi daftar /VI dan L/2, bermula dari blok ke-2, bukan blok gamma sebelumnya, tetapi hasil penyulitan blok plaintext sebelumnya. (Gamb. 3.4). Blok pertama dalam mod ini dijana sepenuhnya sama dengan yang sebelumnya.

nasi. 3.4. Menjana sifir gamma dalam mod gamma dengan maklum balas

Mod penjanaan lampiran tiruan

Awalan ialah jumlah semak kriptografi yang dikira menggunakan kunci penyulitan dan direka bentuk untuk mengesahkan integriti mesej. Untuk mengiranya, terdapat mod khas algoritma GOST 28147-89.

Menjana awalan tiruan dilakukan seperti berikut:

1. Blok maklumat 64-bit pertama yang mana awalan tiruan dikira ditulis untuk mendaftar N1 dan N2 dan disulitkan dalam mod penggantian ringkas yang dikurangkan, di mana 16 pusingan pertama daripada 32 dilakukan.

2. Hasil yang diperoleh dijumlahkan modulo 2 dengan blok maklumat seterusnya, menyimpan keputusan dalam N1 dan N2.

3. M dan N2 disulitkan semula dalam mod penggantian ringkas yang dipendekkan, dsb. sehingga blok maklumat terakhir.

Awalan tiruan dianggap sebagai kandungan terhasil 64-bit daftar N1 dan N2 atau sebahagian daripadanya. Selalunya, awalan tiruan 32-bit digunakan, iaitu separuh daripada kandungan daftar. Ini sudah cukup, kerana, seperti mana-mana checksum, lampiran tiruan bertujuan, pertama sekali, untuk melindungi daripada penyelewengan maklumat yang tidak disengajakan. Untuk melindungi daripada pengubahsuaian data yang disengajakan, kaedah kriptografi lain digunakan - terutamanya tandatangan digital elektronik (lihat Bahagian 1.1).

Awalan tiruan digunakan seperti berikut:

1. Apabila menyulitkan sebarang maklumat, awalan tiruan teks biasa dikira dan dihantar bersama teks sifir.

2. Selepas penyahsulitan, awalan tiruan sekali lagi dikira dan dibandingkan dengan yang dihantar.

3. Jika awalan tiruan yang dikira dan dihantar tidak sepadan, teks sifir telah diherotkan semasa penghantaran atau kekunci yang salah digunakan semasa penyahsulitan.

Awalan tiruan amat berguna untuk menyemak penyahsulitan maklumat kunci yang betul apabila menggunakan skema berbilang kunci.

Awalan tiruan adalah beberapa analog kod pengesahan mesej MAC, dikira dalam mod CBC; Perbezaannya ialah apabila mengira awalan tiruan, mesej penyegerakan tidak digunakan, manakala apabila mengira MAC, vektor permulaan digunakan.

Kekuatan kriptografi algoritma

Pada tahun 1994, perihalan algoritma GOST 28147-89 telah diterjemahkan ke dalam bahasa Inggeris dan diterbitkan; selepas ini hasil analisisnya, yang dijalankan oleh pakar asing, mula muncul; walau bagaimanapun, tiada serangan yang menghampiri kemungkinan ditemui untuk tempoh yang agak lama.

□ panjang kunci besar - 256 bit; bersama-sama dengan mesej penyegerakan rahsia, panjang kunci berkesan meningkat kepada 320 bit;

□ 32 pusingan transformasi; sudah selepas 8 pusingan kesan penuh penyebaran data input dicapai: menukar satu bit blok teks biasa akan menjejaskan semua bit blok teks sifir, dan sebaliknya, iaitu terdapat margin kekuatan berganda.

Mari kita pertimbangkan keputusan kriptanalisis algoritma GOST 28147-89.

Analisis jadual penggantian

Memandangkan jadual gantian tidak disediakan dalam standard, beberapa kerja (contohnya, dalam) mencadangkan bahawa "organisasi yang cekap" boleh mengeluarkan kedua-dua jadual gantian "baik" dan "buruk". Walau bagaimanapun, pakar terkenal Bruce Schneier memanggil andaian sedemikian "khabar angin." Adalah jelas bahawa kekuatan kriptografi algoritma sebahagian besarnya bergantung pada sifat jadual gantian yang digunakan dengan sewajarnya, terdapat jadual penggantian yang lemah (lihat contoh di atas), penggunaannya boleh memudahkan serangan algoritma. Walau bagaimanapun, kemungkinan menggunakan jadual gantian yang berbeza kelihatan seperti idea yang sangat berbaloi, yang memihak kepada dua fakta berikut dari sejarah piawaian penyulitan DES boleh dipetik (untuk butiran, lihat Bahagian 3.15):

□ serangan menggunakan kedua-dua analisis kriptografi linear dan pembezaan algoritma DES menggunakan ciri khusus jadual gantian; apabila menggunakan jadual lain, kriptanalisis perlu dimulakan semula;

□ percubaan telah dibuat untuk mengukuhkan DES terhadap analisis kriptografi linear dan pembezaan dengan menggunakan jadual penggantian yang lebih mantap; jadual sedemikian, yang sememangnya lebih teguh, telah dicadangkan, sebagai contoh, dalam algoritma s 5 DES; tetapi, malangnya, adalah mustahil untuk menggantikan DES dengan s 5 DES, kerana jadual gantian ditakrifkan dengan ketat dalam standard, dan oleh itu, pelaksanaan algoritma mungkin tidak menyokong keupayaan untuk menukar jadual kepada yang lain.

Sebilangan kerja (contohnya, , dan ) tersilap membuat kesimpulan bahawa jadual penggantian rahsia algoritma GOST 28147-89 boleh menjadi sebahagian daripada kunci dan meningkatkan panjang berkesannya (yang tidak penting, kerana algoritma mempunyai 256 yang sangat besar. -kunci bit). Walau bagaimanapun, kerja itu membuktikan bahawa jadual penggantian rahsia boleh dikira menggunakan serangan berikut, yang boleh digunakan secara praktikal:

1. Kekunci sifar ditetapkan dan carian untuk "vektor sifar" dilakukan, iaitu nilai z = /(0), dengan /() ialah fungsi bulat bagi algoritma. Peringkat ini mengambil masa kira-kira 2 operasi penyulitan.

2. Menggunakan vektor sifar, nilai jadual gantian dikira, yang mengambil masa tidak lebih daripada 2 11 operasi.

Pengubahsuaian algoritma dan analisisnya

Kerja itu menjalankan analisis kriptografi pengubahsuaian algoritma GOST 28147-89:

□ Algoritma GOST-H, di mana, berbanding dengan algoritma asal, susunan penggunaan subkunci telah diubah, iaitu dalam pusingan daripada 25 hingga 32 subkunci digunakan dalam susunan langsung, iaitu betul-betul sama seperti pusingan sebelumnya bagi algoritma ;

□ Algoritma GOST® 20 pusingan, di mana pusingan menggunakan XOR dan bukannya tambahan modulo-2 untuk menindih kekunci.

Berdasarkan keputusan analisis, disimpulkan bahawa GOST-H dan GOST© adalah lebih lemah daripada algoritma GOST 28147-89 asal, kerana kedua-duanya mempunyai kelas kunci yang lemah. Perlu diingat bahawa dari segi kriptanalisis GOST©, kerja itu mengulangi perkataan demi perkataan bahagian yang dikhaskan untuk analisis kriptografi algoritma GOST 28147-89, sebuah karya terkenal yang diterbitkan pada tahun 2000 (tanpa rujukan kepada yang asal). Ini mempersoalkan profesionalisme pengarang karya dan hasil lain.

Pengubahsuaian algoritma yang sangat menarik telah dicadangkan dalam kerja: jadual S\…Ss semestinya berbeza; dalam setiap pusingan algoritma mereka mesti disusun semula mengikut undang-undang tertentu. Pilih atur ini mungkin bergantung pada kunci penyulitan, atau mungkin juga rahsia (iaitu, menjadi sebahagian daripada kunci penyulitan yang lebih besar daripada kunci 256-bit asal). Kedua-dua pilihan ini, menurut pengarang mereka, dengan ketara meningkatkan rintangan algoritma terhadap kriptanalisis linear dan pembezaan.

Dan satu lagi pengubahsuaian yang berkaitan dengan jadual penggantian diberikan dalam kerja, yang menganalisis salah satu kaedah yang mungkin untuk mengira jadual penggantian berdasarkan kunci penyulitan. Pengarang kerja menyimpulkan bahawa pergantungan sedemikian melemahkan algoritma, kerana ia membawa kepada kehadiran kunci yang lemah dan kepada beberapa potensi kelemahan algoritma.

Analisis Algoritma Pusingan Penuh

Terdapat juga serangan pada GOST 28147-89 pusingan penuh tanpa sebarang pengubahsuaian. Salah satu kerja awam pertama yang menganalisis algoritma, kerja yang terkenal, ditumpukan kepada serangan yang mengeksploitasi kelemahan dalam prosedur pengembangan utama beberapa algoritma penyulitan yang terkenal. Khususnya, algoritma pusingan penuh GOST 28147-89 boleh dipecahkan menggunakan analisis kriptografi pembezaan pada kunci berkaitan, tetapi hanya jika jadual penggantian yang lemah digunakan. Versi 24 pusingan algoritma (yang mana 8 pusingan pertama tiada) dibuka dengan cara yang sama dengan mana-mana jadual gantian, tetapi jadual gantian yang kuat (contohnya, yang diberikan dalam) menjadikan serangan sedemikian tidak praktikal sama sekali.

Para saintis domestik A. G. Rostovtsev dan E. B. Makhovenko pada tahun 2001 mencadangkan kaedah kriptanalisis yang pada asasnya baru (menurut pengarang, jauh lebih berkesan daripada kriptanalisis linear dan pembezaan) dengan membentuk fungsi objektif daripada teks biasa yang diketahui sepadan dengannya ciphertext dan nilai kunci yang dikehendaki dan mencari ekstremnya sepadan dengan nilai kunci sebenar. Mereka juga menemui kelas besar kekunci lemah algoritma GOST 28147-89, yang memungkinkan untuk membuka algoritma hanya menggunakan 4 teks biasa yang dipilih dan teks sifir yang sepadan dengan kerumitan yang agak rendah. Kriptanalisis algoritma diteruskan dalam kerja.

Pada tahun 2004, sekumpulan pakar dari Korea mencadangkan serangan yang, menggunakan analisis kriptografi pembezaan pada kunci berkaitan, boleh memperoleh 12 bit kunci rahsia dengan kebarangkalian 91.7%. Serangan memerlukan 2 35 teks biasa yang dipilih dan 2 36 operasi penyulitan. Seperti yang anda lihat, serangan ini boleh dikatakan tidak berguna untuk benar-benar memecahkan algoritma.