Algoritma enkripsi GOST 28147-89. Metode penggantian sederhana. - Arsip WASM.RU

“Selagi kamu hidup, jangan mati, lihatlah dunia ini.
Banyak di sini memiliki jiwa yang mati - mereka mati di dalam.
Tapi mereka berjalan dan tertawa, tidak tahu bahwa mereka tidak,
Jangan terburu-buru saat kematianmu, ”katanya padaku.

Aria, "Tinggi Di Atas sana"

2.1 jaringan Feistel.
2.2 Blok cipher GOST 28147-89

3.1 Informasi kunci
3.2 Langkah utama dari transformasi kripto

3.3 Siklus dasar:“ 32-Z” , “ 32-R” .

4.1 Implementasi langkah utama transformasi kripto
4.2 Meningkatkan kecepatan algoritma
5. Persyaratan informasi utama
6. Daftar literatur yang digunakan
7. Ucapan terima kasih.

Pengantar.

Dokumen ini adalah upaya saya untuk menjelaskan metode untuk hanya mengganti algoritma enkripsi GOST 28147-89 dengan bahasa yang paling sederhana, tetapi, bagaimanapun, secara teknis kompeten. Setelah membaca enam poin pertama, pembaca akan memberikan pendapatnya tentang bagaimana saya melakukannya.

Agar karya saya lebih bermanfaat, saya sarankan Anda mempersenjatai diri dengan karya-karya penulis yang tercantum dalam daftar literatur bekas. Kalkulator juga disarankan memiliki fungsi untuk menghitung operasi. XOR sejak membaca artikel mengasumsikan bahwa pembaca bermaksud mempelajari algoritma enkripsi ini. Walaupun cocok juga sebagai referensi, tapi saya menulis artikel ini justru sebagai salah satu pelatihan.

Informasi awal tentang cipher blok.

Sebelum kita mulai melihat algoritma, kita perlu membiasakan diri dengan sejarah penciptaan cipher semacam ini. Algoritme termasuk dalam kategori cipher blok, dalam arsitektur di mana informasi dibagi menjadi sejumlah blok yang terbatas, yang terakhir secara alami mungkin tidak lengkap. Proses enkripsi berlangsung di atas blok lengkap, yang membentuk cipher. Blok terakhir, jika tidak lengkap, dilengkapi dengan sesuatu (saya akan mengatakan tentang nuansa menyelesaikannya di bawah) dan dienkripsi dengan cara yang sama seperti blok penuh. Dengan cipher, maksud saya hasil dari fungsi enkripsi yang bekerja pada sejumlah data tertentu yang dikirimkan pengguna untuk enkripsi. Dengan kata lain, cipher adalah hasil akhir dari enkripsi.

Sejarah pengembangan cipher blok dikaitkan dengan awal tahun 70-an, ketika IBM, menyadari kebutuhan untuk melindungi informasi saat mentransmisikan data melalui saluran komunikasi komputer, memulai program penelitiannya sendiri yang ditujukan untuk perlindungan informasi dalam jaringan elektronik, termasuk kriptografi.

Sekelompok peneliti – pengembang dari IBM, yang mulai meneliti sistem enkripsi dengan skema penggunaan kunci simetris, dipimpin oleh Dr. Horst Feistel.

2.1 Jaringan Feistel

Arsitektur metode enkripsi baru yang diusulkan oleh Feistel dalam literatur klasik disebut "Arsitektur Feistel", tetapi saat ini dalam literatur Rusia dan asing istilah yang lebih mapan digunakan - "jaringan Feistel" atau Jaringan Feistel. Selanjutnya, sandi "Lucifer" dibangun di atas arsitektur ini - yang kemudian diterbitkan dan menyebabkan gelombang minat baru dalam kriptografi secara umum.

Gagasan arsitektur "jaringan Feistel" adalah sebagai berikut: aliran informasi yang masuk dibagi menjadi blok-blok berukuran n bit, di mana n adalah bilangan genap. Setiap blok dibagi menjadi dua bagian - L dan R, kemudian bagian-bagian ini dimasukkan ke dalam cipher blok berulang, di mana hasil dari tahap ke-j ditentukan oleh hasil tahap sebelumnya j-1! Hal ini dapat diilustrasikan dengan sebuah contoh:

Beras. 1

Dimana, fungsi A adalah aksi utama dari block cipher. Ini bisa berupa tindakan sederhana, seperti operasi XOR, atau dapat memiliki bentuk yang lebih kompleks sebagai urutan dari serangkaian tindakan sederhana - penambahan modulo, shift kiri, penggantian elemen, dll., Secara bersama-sama, bentuk tindakan sederhana ini yang disebut - langkah utama transformasi kripto.

Perlu dicatat bahwa elemen kunci dari operasi fungsi adalah pasokan elemen kunci dan operasi XOR, dan dari seberapa baik pekerjaan operasi ini dipikirkan, ini berbicara tentang kekuatan kriptografi cipher secara keseluruhan.

Agar gagasan jaringan Feistel menjadi jelas, pertimbangkan kasus paling sederhana yang ditunjukkan di Nasi. 1, di mana dalam fungsi A - akan ada operasi "mod 2" ("xor"), tetapi ini paling sederhana kasus, dalam situasi yang lebih serius, misalnya, menyembunyikan informasi penting negara, fungsi A mungkin lebih kompleks (sejauh yang saya lihat, fungsi A benar-benar sangat kompleks):

Data awal:

L = 1110b, R = 0101, K = 1111b

Dapatkan sandi

1. (R + K) mod 2 4 = Smod, Smod = 0100b

2. (Smod + L) mod 2 = Sxor, Sxor = 1010b

3.L = R, R = Sxor

L = 0101b, R = 1010b

Mari kita jelaskan tindakan kita:

1. Operasi ini adalah penambahan mod 2 4. Dalam praktiknya, operasi semacam itu direduksi menjadi penjumlahan sederhana, di mana kita harus menambahkan dua angka dan mengabaikan transfer ke digit ke-5. Karena, jika kita meletakkan eksponen di atas digit representasi biner dari suatu angka, akan ada eksponen empat di atas digit kelima, mari kita lihat gambar di bawah ini, yang menunjukkan tindakan operasi kita:

Beras. 2

Di sini saya menunjuk ke eksponen dengan panah, seperti yang Anda lihat, hasilnya seharusnya 10100, tetapi karena transfer diabaikan selama operasi mod 2 4, kami mendapatkan 0100.

2. Operasi ini dalam literatur disebut mod 2, dalam bahasa assembly diimplementasikan dengan perintah XOR... Tapi nama yang lebih tepat adalah mod 2 1. Tanpa operasi unik ini, hampir tidak mungkin untuk membangun algoritma enkripsi yang cepat dan mudah diterapkan, dan pada saat yang sama, sehingga masih cukup kuat secara kriptografis. Keunikan dari operasi ini terletak pada kenyataan bahwa itu sendiri adalah kebalikannya! Misal angka A di XOR dengan angka B maka kita akan mendapatkan B, ke depannya cukup meng-XOR angka B dan C antara satu sama lain untuk mendapatkan nilai A sebelumnya!

Dalam operasi ini, kami mendapatkan 1010 yang memiliki angka 1110 dan 0100, untuk mendapatkan kembali 1110, cukup dengan melakukan reXOR antara angka 0100 dan 1010! Rincian lebih lanjut tentang operasi ini dapat ditemukan di artikel, yang dilampirkan ke situs. www.wasm.ru, « Panduan dasar untukAlgoritma deteksi kesalahan CRC_»Penulis yang Ross N. Williams... Ada gunanya dalam pekerjaan ini - “ 5. Aritmatika biner tanpa tanda hubung". Dalam artikel ini operasi dijelaskan. xor! Saya berseru karena dalam artikel ini operasi ini sangat terjadwal sehingga pembaca tidak hanya mengerti bagaimana operasi ini bekerja, dia bahkan memulainya. lihat, dengar, dan rasakan!

3. Tindakan ini diperlukan agar nilai awal dapat diperoleh dari enkripsi saat dekripsi.

2.2 Blok cipher GOST 28147-89

Algoritma enkripsi GOST 28147 - 89 termasuk dalam kategori cipher blok yang beroperasi sesuai dengan arsitektur jaringan Feistel yang seimbang, di mana dua bagian dari blok informasi yang dipilih berukuran sama. Algoritma ini dikembangkan di kedalaman departemen kedelapan KGB, sekarang diubah menjadi FAPSI dan diabadikan sebagai standar enkripsi Federasi Rusia pada tahun 1989 di bawah Uni Soviet.

Agar metode algoritme ini berfungsi, perlu untuk membagi informasi menjadi blok-blok berukuran 64 bit. Hasilkan atau masukkan ke dalam sistem enkripsi informasi kunci berikut: kunci dan tabel substitusi. Pemilihan kunci dan tabel substitusi untuk enkripsi harus diperhatikan dengan sangat serius, karena ini adalah dasar dari keamanan informasi Anda. Untuk informasi tentang persyaratan apa yang dikenakan pada kunci, dan tabel substitusi, lihat item "Persyaratan untuk informasi kunci".

Saat mempertimbangkan metodenya, kami tidak akan fokus pada ini, karena artikel ini, seperti yang saya katakan di atas, ditulis dengan tujuan mengajari pembaca cara mengenkripsi data dengan metode penggantian sederhana dari algoritma enkripsi ini, tetapi kami pasti akan menyentuh masalah ini di akhir artikel.

Minimum teoritis.

3.1 Informasi kunci

Seperti yang saya katakan di atas, berikut ini secara aktif terlibat dalam enkripsi data:

3.1.1. Kunci adalah urutan delapan elemen, masing-masing 32 bit. Berikut ini, kita akan dilambangkan dengan simbol K, dan unsur-unsurnya adalah k1, k2, k3, k4, k5, k6, k7, k8.

3.1.2 Tabel Substitusi - matriks delapan baris dan enam belas kolom, selanjutnya - Hij. Setiap elemen pada perpotongan baris i dan kolom j menempati 4 bit.

3.2 Langkah dasar transformasi kripto

Langkah utama dalam proses enkripsi adalah – langkah utama dari transformasi kripto. Ini tidak lebih dari tindakan untuk mengenkripsi data sesuai dengan algoritma tertentu, hanya pengembang yang memperkenalkan nama yang terlalu rumit.

Sebelum mulai mengenkripsi, blok dibagi menjadi dua bagian L dan R, masing-masing 32 bit. Elemen kunci dipilih dan hanya kemudian dua bagian blok ini, elemen kunci, tabel substitusi, dimasukkan ke dalam fungsi langkah utama, hasil dari langkah utama adalah satu iterasi dari siklus dasar, yang akan dibahas dalam paragraf berikutnya. Langkah utama terdiri dari berikut ini:

1. Bagian tambahan dari blok R dijumlahkan dengan elemen kunci K mod 2 32. Saya menggambarkan operasi serupa di atas, di sini hal yang sama hanya eksponennya bukan "4", tetapi "32" - hasil dari operasi ini akan dilambangkan Smod di masa depan.
2. Bagilah hasil Smod yang diperoleh sebelumnya menjadi elemen empat bit s7, s6, s5, s4, s3, s2, s1, s0 dan masukkan ke fungsi pengganti. Penggantiannya adalah sebagai berikut: elemen Smod - si dipilih, kita mulai dari awal dengan elemen terendah, dan mengganti dengan nilai dari tabel penggantian dengan i - baris dan kolom yang ditunjukkan oleh nilai elemen s Saya. Kami meneruskan ke elemen s i +1 dan melanjutkan dengan cara yang sama dan melanjutkan hingga kami mengubah nilai elemen terakhir Smod - hasil dari operasi ini akan dilambangkan sebagai, Sederhana.
3. Dalam operasi ini, kami menggeser nilai Ssimple secara siklis ke kiri sebanyak 11 bit dan mendapatkan Srol.
4. Kami memilih bagian kedua dari blok L dan menambahkannya mod 2 dengan Srol, sebagai hasilnya kami memiliki Sxor.
5. Pada tahap ini, bagian dari blok L menjadi sama dengan nilai bagian R, dan bagian R, pada gilirannya, diinisialisasi dengan hasil Sxor, dan pada tahap ini fungsi dari langkah utama selesai!

3.3 Siklus dasar: "32-З", "32-Р".

Untuk mengenkripsi informasi, perlu untuk membaginya menjadi blok-blok berukuran 64 bit, tentu saja blok terakhir bisa kurang dari 64 bit. Fakta ini adalah kelemahan dari metode "penggantian mudah" ini. Karena penambahannya ke 64 bit adalah tugas yang sangat penting untuk meningkatkan kekuatan kriptografi program cipher dan ke tempat sensitif ini, jika ada dalam array informasi, dan mungkin tidak ada (misalnya, file 512 byte! ), Seseorang harus memperlakukan dengan tanggung jawab yang besar!

Setelah Anda membagi informasi menjadi blok, Anda harus membagi kunci menjadi elemen:

K = k1, k2, k3, k4, k5, k6, k7, k8

Enkripsi itu sendiri terdiri dari penggunaan yang disebut siklus dasar. Yang, pada gilirannya, termasuk jumlah ke-n dari langkah-langkah dasar transformasi kripto.

Siklus dasar diberi label, cara mengatakannya: n - m. Di mana n adalah jumlah langkah dasar transformasi kripto dalam siklus dasar, dan m adalah "tipe" dari siklus dasar, mis. tentang apa, tentang enkripsi "Z" atau enkripsi data "R".

Siklus enkripsi dasar 32-З terdiri dari 32 langkah dasar transformasi kripto. Blok N dan elemen kunci K dimasukkan ke dalam fungsi yang mengimplementasikan tindakan langkah, dan langkah pertama terjadi dengan k1, yang kedua di atas hasil yang diperoleh dengan elemen k2, dll. sesuai skema berikut:

k1, k2, k3, k4, k5, k6, k7, k8, k1, k2, k3, k4, k5, k6, k7, k8, k1, k2, k3, k4, k5, k6, k7, k8k8, k7, k6, k5, k4, k3, k2, k1

Proses dekripsi untuk 32-P terjadi dengan cara yang sama, tetapi elemen kunci diberikan dalam urutan terbalik:

k1, k2, k3, k4, k5, k6, k7, k8, k8, k7, k6, k5, k4, k3, k2, k1, k8, k7, k6, k5, k4, k3, k2, k1, k8, k7, k6, k5, k4, k3, k2, k1

Praktek.

4.1 Implementasi langkah utama transformasi kripto

Setelah kami berkenalan dengan teori tentang cara mengenkripsi informasi, sekarang saatnya untuk melihat bagaimana enkripsi bekerja dalam praktiknya.

Data awal:

Ambil blok informasi N = 0102030405060708h, di sini bagian L dan R sama:

L = 01020304h, R = 05060708h, mari kita ambil kuncinya:

K = ‘ sebagai28 zw37 q839 7342ui23 8e2t wqm2 ewp1 '(ini adalah kode ASCII, untuk melihat representasi heksadesimal, Anda dapat membuka file ini dalam mode tampilan di Total Commander dengan menekan tombol F3"Lalu kuncinya" 3 "). Dalam kunci ini, nilai elemen akan menjadi:

k1 = ‘as28’, k2 = ‘zw37’, k3 = ‘q839’, k4 = ‘7342’

k5 = ‘ui23’, k6 = ‘8e2t’, k7 = ‘wqm2’, k8 = ‘ewp1’

Ambil juga tabel substitusi berikut:

Beras. 3

Di sini, baris diberi nomor dari 0 hingga 7, kolom dari 0 hingga F.

Sebuah peringatan: Semua informasi, termasuk kunci dengan tabel substitusi, diambil sebagai contoh untuk mempertimbangkan algoritma!

Menggunakan "Data awal", perlu untuk mendapatkan hasil dari tindakan langkah utama transformasi kripto.

1. Pilih bagian R = 05060708h dan elemen kunci k1 = 'as28', dalam bentuk heksadesimal elemen kunci akan terlihat seperti ini: 61733238h. Sekarang kita melakukan operasi penjumlahan mod 2 32:

Beras. 4

Seperti yang Anda lihat pada gambar, kami tidak memiliki transfer dalam 33 bit yang ditandai dengan warna merah dan dengan eksponen “ 32 ". Dan jika kita memiliki nilai lain dari R dan elemen kunci, ini bisa saja terjadi, dan kemudian kita akan mengabaikannya, dan selanjutnya hanya menggunakan bit yang ditandai dengan warna kuning.

Saya melakukan operasi ini dengan perintah assembler Menambahkan:

; eax = R, ebx = 'as28'

Hasil dari operasi ini Smod = 66793940h

2. Sekarang operasi yang paling rumit, tetapi jika Anda melihat lebih dekat, itu tidak lagi menakutkan seperti yang terlihat pada awalnya. Mari kita bayangkan Smod sebagai berikut:

Beras. 5

Saya mencoba memvisualisasikan elemen Smod pada gambar, tetapi saya akan tetap menjelaskan:

s0 = 0, s1 = 4, s2 = 9, dst.

Sekarang, mulai dari elemen terendah s0, kami melakukan penggantian. Mengingat paragraf “ 3.2 Langkah dasar transformasi kripto»I - baris, s i - kolom, cari nilai pada baris nol dan kolom nol:

Gambar 6

Jadi nilai Smod saat ini bukan 6679394 0 h, dan 6679394 5 H.

Kami melanjutkan untuk mengganti s1, mis. empat. Menggunakan baris pertama dan kolom keempat (s1 = 4!). Kita lihat gambarnya:

Beras. 7

Sekarang sudah nilai Smod, bukan 667939 4 5 jam, 667939 2 5 jam Saya berasumsi bahwa sekarang algoritma penggantian jelas bagi pembaca, dan saya dapat mengatakan bahwa setelah hasil akhir Ssimple akan memiliki nilai berikut - 11e10325h.

Saya akan berbicara tentang bagaimana ini paling mudah diimplementasikan dalam bentuk perintah assembler nanti di paragraf berikutnya, setelah saya berbicara tentang tabel yang diperluas.

1. Kita harus menggeser nilai Simple yang dihasilkan 11 bit ke kiri.

Beras. delapan

Seperti yang Anda lihat, tindakan ini cukup sederhana, dan diimplementasikan oleh satu perintah bahasa rakitan - peran dan hasil dari operasi Srol ini adalah 0819288Fh.

4. Sekarang bagian L dari blok informasi kita akan di-XOR dengan nilai Srol. Saya mengambil kalkulator dari w2k sp4 dan mendapatkan Sxor = 091b2b8bh.

5. Tindakan ini final dan kita cukup menetapkan, membersihkan R, nilai bagian L, dan menginisialisasi bagian L dengan nilai Sxor.

Hasil akhir:

L = 091b2b8bh, R = 01020304h

4.2 Meningkatkan kecepatan algoritma

Sekarang mari kita bicara tentang mengoptimalkan algoritma untuk kecepatan. Dalam proses pelaksanaan proyek, kita harus memperhitungkan bahwa program yang bekerja dengan register lebih sering daripada dengan memori bekerja paling cepat, dan di sini penilaian ini juga sangat penting, karena lebih dari satu blok informasi sebanyak 32 tindakan enkripsi!

Ketika saya menerapkan algoritma enkripsi dalam program saya, saya melakukan hal berikut:

1. Memilih bagian dari blok L ke register eax, dan R ke edx.

2. Dalam register esi, diinisialisasi dengan alamat kunci yang diperluas, lebih lanjut di bawah ini.

3. Dalam register ebx diberikan nilai alamat tabel substitusi yang diperluas, lebih lanjut tentang ini di bawah ini

4. Mentransfer informasi butir 1, 2, 3 ke fungsi siklus dasar 32 - atau 32 - , tergantung situasi.

Jika Anda melihat diagram alir dari elemen-elemen kunci dalam paragraf " Siklus dasar: "32-З", "32-Р"", Maka kunci kita untuk siklus dasar 32 - 3 dapat direpresentasikan sebagai berikut:

K 32-Z =

'As28', 'zw37', 'q839', '7342', 'ui23', '8e2t', 'wqm2', 'ewp1',

'As28', 'zw37', 'q839', '7342', 'ui23', '8e2t', 'wqm2', 'ewp1',

'Ewp1', 'wqm2', '8e2t', 'ui23', '7342', 'q839', 'zw37', 'as28'

Itu. dari awal ada k1, k2, k3, k4, k5, k6, k7, k8 - ‘ sebagai28','zw37 ','q839 ',' 7342 ','ui23 ',' 8e2T ','wqm2','epp1 ' urutan ini diulang tiga kali. Kemudian elemen berjalan dalam urutan terbalik, yaitu .: k8, k7, k6, k5, k4, k3, k2, k1 - 'Ewp1', 'wqm2', '8e2t', 'ui23', '7342', 'q839', 'zw37', 'as28'.

Saya mengatur elemen dalam array terlebih dahulu dalam urutan yang harus dimasukkan dalam 32 - Z. Jadi, saya meningkatkan memori yang diperlukan secara turnkey, tetapi menyelamatkan diri dari beberapa proses berpikir yang tidak saya butuhkan, dan meningkatkan kecepatan dari algoritma, karena dengan mengurangi waktu akses memori! Di sini saya hanya menjelaskan kunci untuk 32 - , untuk siklus 32 - Saya melakukan hal yang sama, tetapi menggunakan skema pemasokan elemen yang berbeda, yang juga saya jelaskan dalam paragraf " Siklus dasar: “32-Z”, “32-P».

Sekarang saatnya menjelaskan implementasi fungsi pengganti, seperti yang saya janjikan di atas. Saya tidak bisa menjelaskan sebelumnya, karena ini membutuhkan pengenalan konsep baru - tabel substitusi yang diperluas. Saya tidak bisa menjelaskan kepada Anda apa itu. Sebagai gantinya, saya akan menunjukkannya kepada Anda, dan Anda sendiri yang merumuskan sendiri, apa itu - tabel substitusi yang diperluas?

Jadi, untuk memahami apa itu tabel substitusi yang diperluas, kita memerlukan tabel substitusi, misalnya, saya akan mengambil yang ditunjukkan pada Gambar. 3.

Misalnya, kami perlu mengganti nomor 66793940h. Saya akan menyajikannya sebagai berikut:

Beras. sembilan

Sekarang jika kita mengambil elemen s1, s0, yaitu. byte paling signifikan, hasil dari fungsi penggantian akan menjadi 25 jam! Setelah membaca artikel oleh Andrey Vinokurov, yang saya kutip dalam paragraf " Daftar literatur yang digunakan", Anda benar-benar menemukan bahwa jika Anda mengambil dua baris, Anda bisa mendapatkan array, memungkinkan Anda menemukan elemen pengganti dengan cepat menggunakan perintah assembler xlat. Mereka mengatakan itu dapat dilakukan dengan cara lain lebih cepat, tetapi Andrey Vinokurov menghabiskan sekitar empat tahun untuk meneliti algoritma cepat untuk implementasi GOST! Saya tidak berpikir Anda harus menemukan kembali roda ketika Anda sudah memilikinya.

Jadi, tentang array:

Mari kita ambil dua baris pertama nol dan yang pertama, buat array 256 byte. Sekarang kami mengamati satu keanehan bahwa jika perlu untuk mengubah 00h, maka hasilnya akan menjadi 75h (berdasarkan Gambar 3) - kami menempatkan nilai ini ke dalam array pada offset 00h. Kami mengambil nilai 01h, hasil dari fungsi substitusi 79h, memasukkannya ke dalam array pada offset 01, dan seterusnya hingga 0FFh, yang akan memberi kami 0FCh, yang akan kami masukkan ke dalam array pada offset 0FFh. Jadi kami mendapat tabel substitusi yang diperluas untuk grup baris pertama: yang pertama dan nol. Tapi masih ada tiga kelompok: halaman kedua 2, halaman 3, halaman ketiga 4, halaman 5, halaman keempat 6, halaman 7. Kami menangani ketiga kelompok ini dengan cara yang sama seperti yang pertama. Hasilnya adalah tabel substitusi yang diperpanjang!

Sekarang kita dapat mengimplementasikan algoritma yang akan melakukan penggantian. Untuk melakukan ini, kami mengambil kode sumber yang diposting Andrei Vinokurov di halamannya, lihat " Bibliografi».

lea ebx, extended_table_simple

mov eax, [masukkan nomor yang akan diganti]

tambahkan ebx, 100h; lompat ke dua node berikutnya

sub ebx, 300 jam; sehingga di masa depan ebx menunjuk ke tabel

Sekarang satu fitur lagi, dengan tindakan sebelumnya kami tidak hanya mengganti, tetapi juga menggeser angka sebanyak 8 bit ke kiri! Kita hanya perlu menggeser angka 3 bit lagi ke kiri:

dan kita mendapatkan hasil dari operasi rol eax, 11!

Saya tidak dapat menambahkan apa-apa lagi tentang pengoptimalan, satu-satunya hal yang dapat saya tekankan adalah apa yang saya katakan di atas - gunakan register lebih sering daripada akses memori. Saya pikir kata-kata ini hanya untuk pemula, berpengalaman dan tanpa kata-kata saya memahaminya dengan sempurna.

Persyaratan untuk informasi kunci.

Seperti yang dinyatakan dalam artikel oleh Andrey Vinokurov, kuncinya dipilih berdasarkan dua kriteria:

Kriteria untuk distribusi bit yang setara antara nilai 1 dan 0. Biasanya, kriteria untuk distribusi bit yang setara adalah kriteria Pearson ("chi-kuadrat").

Ini berarti kunci, pada prinsipnya, nomor berapa pun bisa. Artinya, ketika bit kunci berikutnya terbentuk, kemungkinan inisialisasinya dengan satu atau nol adalah 50/50!

Harap dicatat bahwa kunci terdiri dari delapan elemen, masing-masing 32 bit, jadi hanya ada 32 * 8 = 256 bit dalam kunci dan jumlah kemungkinan kunci adalah 2 256! Tidakkah itu mengejutkan Anda?

Kriteria seri.

Jika kita melihat kunci kita, yang saya berikan di paragraf " 4.1 Implementasi langkah utama transformasi kripto», Maka Anda akan melihat bahwa notasi berikut ini valid:

Beras. sepuluh

Dalam satu frase, nilai k 1 tidak boleh diulang tidak di k 2, tidak di elemen kunci lainnya.

Artinya, kunci yang kita pilih sebagai pertimbangan algoritma enkripsi konsisten dengan dua kriteria di atas.

Sekarang tentang pilihan tabel substitusi:

Sekarang mari kita bicara tentang bagaimana memilih tabel substitusi yang tepat. Persyaratan utama untuk pemilihan tabel pengganti adalah fenomena elemen "non-repeatability", yang masing-masing berukuran 4 bit. Seperti yang Anda lihat di atas, setiap baris tabel substitusi terdiri dari nilai 0h, 1h, 2h, 3h,…, 0fh. Jadi syarat utamanya adalah setiap baris berisi nilai 0h, 1h, 2h, ..., 0fh dan masing-masing nilai tersebut dalam satu salinan. Misalnya, urutannya:

1 2 3 4 5 6 7 8 9 A B C D E F

Ini sepenuhnya sesuai dengan persyaratan ini, tapi tetap saja! Tidak disarankan untuk memilih urutan ini sebagai string. Karena jika Anda memasukkan nilai ke input fungsi yang bergantung pada string seperti itu, maka Anda akan mendapatkan nilai yang sama pada output! Tidak percaya padaku? Kemudian ambil angka 332DA43Fh dan delapan baris seperti tabel substitusi. Lakukan operasi penggantian, dan saya jamin, hasilnya akan menjadi angka 332DA43Fh! Artinya, sama dengan yang Anda kirimkan ke input operasi! Dan ini bukan pertanda baik dalam enkripsi, dan bukan?

Ini adalah salah satu persyaratan, kriteria berikutnya mengatakan bahwa - setiap bit dari blok output harus secara statistik independen dari setiap bit dari blok input!

Bagaimana tampilannya lebih sederhana? Dan inilah caranya, misalnya, kita telah memilih dari angka di atas elemen s0 = 0Fh, 01111b. Probabilitas bahwa kita sekarang akan mengganti bit pertama dengan satu atau nol adalah 0,5! Probabilitas penggantian bit kedua, ketiga dan keempat, setiap bit, kami pertimbangkan secara terpisah, dengan satu atau nol juga 0, 5. Saat memilih s1 = 0Eh, probabilitas bahwa kami adalah bit nol, dan ini adalah "0" , akan diganti dengan nol atau satu juga sama dengan - 0,5! Jadi, menurut kriteria ini, tidak ada keteraturan antara penggantian bit nol elemen s0, s1! Ya, Anda bisa mengganti satu, tetapi Anda juga bisa mengganti nol.

Untuk mengevaluasi tabel dengan kriteria ini, Anda dapat membuat tabel koefisien korelasi yang dihitung dengan rumus:

Jika p = 1, maka nilai bit j pada keluaran sama dengan nilai bit i pada masukan untuk setiap kombinasi bit pada masukan;

Jika p = -1, maka nilai bit j pada keluaran selalu merupakan kebalikan dari bit masukan i;

Jika p = 0, maka bit keluaran j dengan probabilitas yang sama mengambil nilai 0 dan 1 untuk setiap nilai tetap dari bit masukan i.

Mari kita ambil satu contoh baris:

Mari kita memecahnya menjadi "komponen":

Mari kita hitung satu koefisien sesuai dengan rumus di atas. Agar lebih mudah memahami bagaimana hal ini dilakukan, saya akan menjelaskan lebih detail:

Kami mengambil bit ke-0 dari angka 0 (0) pada input dan bit ke-0 dari angka 0 pada output (1) kami melakukan operasi 0 XOR 1 = 1.

Kami mengambil bit ke-0 dari angka 1 (1) pada input dan bit ke-0 dari angka 1 pada output (1) kami melakukan operasi 1 XOR 1 = 0.

Kami mengambil bit ke-0 dari angka ke-2 (0) pada input dan bit ke-0 dari angka ke-2 pada output (0), kami melakukan operasi 0 XOR 0 = 0.

Kami mengambil bit ke-0 dari angka ke-3 (1) pada input dan bit ke-0 dari angka ke-3 pada output (1) kami melakukan operasi 1 XOR 1 = 0.

Melakukan operasi XOR berturut-turut dalam urutan ini, kami menghitung jumlah semua nilai bukan nol, kami mendapatkan nilai 6. Oleh karena itu P 00 = 1- (6/2 4-1) = 0,25. Jadi, ternyata nilai bit 0 pada output sama dengan nilai bit 0 pada input dalam 4 kasus dari 16;

Tabel peluang akhir:

Seperti dapat dilihat dari tabel koefisien korelasi, bit 3 pada input terbalik relatif terhadap bit 0 pada output dalam 14 kasus dari 16, yaitu 87,5%.Ini tidak lagi dapat diterima untuk sistem enkripsi normal. Mari kita ambil contoh lain untuk perubahan:

Tabel koefisien adalah sebagai berikut (kepada siapa tidak malas untuk menghitung ulang)

Nah, di tabel ini, keadaannya bahkan lebih buruk - bit 1 dan 2 dari grup tetap tidak berubah! Cryptanalyst memiliki tempat untuk berbalik Mempertimbangkan semua persyaratan ini, pencarian sederhana ("langsung") menemukan tabel permutasi yang sesuai dengan teori yang ditunjukkan (hari ini - 1276 kombinasi) Berikut adalah beberapa di antaranya:

09 0D 03 0E-06 02 05 08-0A 07 00 04-0C 01 0F 0B

00 05 0A 07-03 08 0F 0C-0E 0B 04 09-0D 06 01 02

06 0B 0F 00-0C 01 02 0D-08 07 09 04-05 0A 03 0E

04 0E 00 09-0B 01 0F 06-03 0D 07 0A-0C 02 08 05

04 02 08 0E-05 0F 03 09-0B 01 0D 07-0A 0C 06 00

07 03 09 0C-08 00 06 0F-0E 04 01 0A-0D 0B 02 05

06 0F 03 08-0D 04 0A 01-09 02 05 0C-00 0B 0E 07

0C 06 08 01-03 09 07 0E-0B 05 0F 02-04 0A 00 0D

04 0B 09 06-0E 01 00 0F-0A 05 03 0C-0D 02 07 08

00 0E 0F 01-07 08 09 06-04 0B 0A 05-03 0D 0C 02

0F 09 01 07-04 0A 08 06-0E 00 02 0C-05 03 0B 0D

0A 03 04 01-05 0C 0B 0E-08 06 0F 0D-07 09 00 02

0B 06 0F 01-04 0A 08 05-00 0D 0C 02-07 09 03 0E

0C 03 02 08-0D 06 0B 05-07 09 04 0F-0A 00 01 0E

02 0B 0F 04-09 00 06 0D-05 0E 01 08-0C 07 0A 03

Daftar literatur yang digunakan.

1. Artikel oleh Andrey Vinokurov:

Algoritma enkripsi GOST 28147-89, penggunaan dan implementasinya

untuk komputer platform Intel x86.

Ada juga kode sumber untuk implementasi algoritma enkripsi.

1. Artikel Horst Feistel:

Kriptografi dan Keamanan Komputer.

(dapat ditemukan di alamat yang sama dengan artikel sebelumnya)

1. Ross N. Williams:

Panduan Dasar untuk Algoritma Deteksi Kesalahan CRC

Diposting di situs www.wasm.ru.

Ucapan terima kasih.

Saya ingin mengucapkan terima kasih kepada semua pengunjung forum www.wasm.ru. Namun secara khusus saya ingin mengucapkan terima kasih kepada ChS, yang saat ini dikenal sebagai SteelRat, dia membantu saya memahami hal-hal yang mungkin tidak akan pernah saya pahami, serta membantu dalam menulis paragraf: “ Persyaratan informasi utama”, Bagian utama dari paragraf ini ditulis olehnya. Saya juga sangat berterima kasih kepada karyawan KSTU yang dinamai NS. Tupolev Anikin Igor Vyacheslavovich dan itu akan menjadi dosa untuk tidak menyebutkan Chris Kaspersky untuk fakta bahwa dia dan Volodya / wasm.ru untuk instruksinya. Oh, dan saya mendapatkannya dari dia. Saya juga ingin mencatat Sega-Zero / Callipso, tetapi itu membawa beberapa hutan matematis ke pikiran saya.

Mungkin ini saja yang ingin saya ceritakan kepada Anda.

Saya akan berterima kasih atas kritik atau pertanyaan terkait artikel ini atau hanya saran. Detail kontak saya: [dilindungi email], ICQ - 337310594.

Salam Hormat, Evil's Interrupt.

P.S.: Dengan artikel ini, saya tidak mencoba untuk mengalahkan siapa pun. Itu ditulis dengan niat, untuk memfasilitasi studi GOST, dan jika Anda mengalami kesulitan, ini tidak berarti bahwa saya bersalah dalam hal ini. Bersikaplah masuk akal dan bersabarlah, semua yang terbaik untuk Anda!

“Selagi kamu hidup, jangan mati, lihatlah dunia ini.
Banyak di sini memiliki jiwa yang mati - mereka mati di dalam.
Tapi mereka berjalan dan tertawa, tidak tahu bahwa mereka tidak,
Jangan terburu-buru saat kematianmu, ”katanya padaku.

Aria, "Tinggi Di Atas sana"

1. pengantar

1. Informasi awal tentang cipher blok

2.1 jaringan Feistel.
2.2 Blok cipher GOST 28147-89

1. Minimum teoretis

3.1 Informasi kunci
3.2 Langkah utama dari transformasi kripto

3.3 Siklus dasar:“ 32-Z” , “ 32-R” .

1. Praktek

4.1 Implementasi langkah utama transformasi kripto
4.2 Meningkatkan kecepatan algoritma
5.
6. Daftar literatur yang digunakan
7. Ucapan terima kasih.

Pengantar.

Dokumen ini adalah upaya saya untuk menjelaskan metode untuk hanya mengganti algoritma enkripsi GOST 28147-89 dengan bahasa yang paling sederhana, tetapi, bagaimanapun, secara teknis kompeten. Setelah membaca enam poin pertama, pembaca akan memberikan pendapatnya tentang bagaimana saya melakukannya.

Agar karya saya lebih bermanfaat, saya sarankan Anda mempersenjatai diri dengan karya-karya penulis yang tercantum dalam daftar literatur bekas. Kalkulator juga disarankan memiliki fungsi untuk menghitung operasi. XOR sejak membaca artikel mengasumsikan bahwa pembaca bermaksud mempelajari algoritma enkripsi ini. Walaupun cocok juga sebagai referensi, tapi saya menulis artikel ini justru sebagai salah satu pelatihan.

Informasi awal tentang cipher blok.

Sebelum kita mulai melihat algoritma, kita perlu membiasakan diri dengan sejarah penciptaan cipher semacam ini. Algoritme termasuk dalam kategori cipher blok, dalam arsitektur di mana informasi dibagi menjadi sejumlah blok yang terbatas, yang terakhir secara alami mungkin tidak lengkap. Proses enkripsi berlangsung di atas blok lengkap, yang membentuk cipher. Blok terakhir, jika tidak lengkap, dilengkapi dengan sesuatu (saya akan mengatakan tentang nuansa menyelesaikannya di bawah) dan dienkripsi dengan cara yang sama seperti blok penuh. Dengan cipher, maksud saya hasil dari fungsi enkripsi yang bekerja pada sejumlah data tertentu yang dikirimkan pengguna untuk enkripsi. Dengan kata lain, cipher adalah hasil akhir dari enkripsi.

Sejarah pengembangan cipher blok dikaitkan dengan awal tahun 70-an, ketika IBM, menyadari kebutuhan untuk melindungi informasi saat mentransmisikan data melalui saluran komunikasi komputer, memulai program penelitiannya sendiri yang ditujukan untuk perlindungan informasi dalam jaringan elektronik, termasuk kriptografi.

Sekelompok peneliti – pengembang dari IBM, yang mulai meneliti sistem enkripsi dengan skema penggunaan kunci simetris, dipimpin oleh Dr. Horst Feistel.

2.1 Jaringan Feistel

Arsitektur metode enkripsi baru yang diusulkan oleh Feistel dalam literatur klasik disebut "Arsitektur Feistel", tetapi saat ini dalam literatur Rusia dan asing istilah yang lebih mapan digunakan - "jaringan Feistel" atau Jaringan Feistel. Selanjutnya, sandi "Lucifer" dibangun di atas arsitektur ini - yang kemudian diterbitkan dan menyebabkan gelombang minat baru dalam kriptografi secara umum.

Gagasan arsitektur "jaringan Feistel" adalah sebagai berikut: aliran informasi yang masuk dibagi menjadi blok-blok berukuran n bit, di mana n adalah bilangan genap. Setiap blok dibagi menjadi dua bagian - L dan R, kemudian bagian-bagian ini dimasukkan ke dalam cipher blok berulang, di mana hasil dari tahap ke-j ditentukan oleh hasil tahap sebelumnya j-1! Hal ini dapat diilustrasikan dengan sebuah contoh:

Beras. 1

Dimana, fungsi A adalah aksi utama dari block cipher. Ini bisa berupa tindakan sederhana, seperti operasi XOR, atau dapat memiliki bentuk yang lebih kompleks sebagai urutan dari serangkaian tindakan sederhana - penambahan modulo, shift kiri, penggantian elemen, dll., Secara bersama-sama, bentuk tindakan sederhana ini yang disebut - langkah utama transformasi kripto.

Perlu dicatat bahwa elemen kunci dari operasi fungsi adalah pasokan elemen kunci dan operasi XOR, dan dari seberapa baik pekerjaan operasi ini dipikirkan, ini berbicara tentang kekuatan kriptografi cipher secara keseluruhan.

Agar gagasan jaringan Feistel menjadi jelas, pertimbangkan kasus paling sederhana yang ditunjukkan di Nasi. 1, di mana dalam fungsi A - akan ada operasi "mod 2" ("xor"), tetapi ini paling sederhana kasus, dalam situasi yang lebih serius, misalnya, menyembunyikan informasi penting negara, fungsi A mungkin lebih kompleks (sejauh yang saya lihat, fungsi A benar-benar sangat kompleks):

Data awal:

L = 1110b, R = 0101, K = 1111b

Dapatkan sandi

1. (R + K) mod 2 4 = Smod, Smod = 0100b
2. (Smod + L) mod 2 = Sxor, Sxor = 1010b
3. L = R, R = Sxor

L = 0101b, R = 1010b

Mari kita jelaskan tindakan kita:

1. Operasi ini adalah mod 2 4 tambahan. Dalam praktiknya, operasi semacam itu direduksi menjadi penjumlahan sederhana, di mana kita harus menambahkan dua angka dan mengabaikan transfer ke digit ke-5. Karena, jika kita meletakkan eksponen di atas digit representasi biner dari suatu angka, akan ada eksponen empat di atas digit kelima, mari kita lihat gambar di bawah ini, yang menunjukkan tindakan operasi kita:

Beras. 2

Di sini saya menunjuk ke eksponen dengan panah, seperti yang Anda lihat, hasilnya seharusnya 10100, tetapi karena transfer diabaikan selama operasi mod 2 4, kami mendapatkan 0100.

1. Operasi ini dalam literatur disebut mod 2, dalam bahasa assembly diimplementasikan oleh perintah XOR... Tapi nama yang lebih tepat adalah mod 2 1. Tanpa operasi unik ini, hampir tidak mungkin untuk membangun algoritma enkripsi yang cepat dan mudah diterapkan, dan pada saat yang sama, sehingga masih cukup kuat secara kriptografis. Keunikan dari operasi ini terletak pada kenyataan bahwa itu sendiri adalah kebalikannya! Misal angka A di XOR dengan angka B maka kita akan mendapatkan B, ke depannya cukup meng-XOR angka B dan C antara satu sama lain untuk mendapatkan nilai A sebelumnya!

Dalam operasi ini, kami mendapatkan 1010 yang memiliki angka 1110 dan 0100, untuk mendapatkan kembali 1110, cukup dengan melakukan reXOR antara angka 0100 dan 1010! Rincian lebih lanjut tentang operasi ini dapat ditemukan di artikel, yang dilampirkan ke situs. www.wasm.ru, « Panduan dasar untukAlgoritma deteksi kesalahan CRC_»Penulis yang Ross N. Williams... Ada gunanya dalam pekerjaan ini - “ 5. Aritmatika biner tanpa tanda hubung". Dalam artikel ini operasi dijelaskan. xor! Saya berseru karena dalam artikel ini operasi ini sangat terjadwal sehingga pembaca tidak hanya mengerti bagaimana operasi ini bekerja, dia bahkan memulainya. lihat, dengar, dan rasakan!

1. Tindakan ini diperlukan agar selama dekripsi, nilai awal dapat diperoleh dari cipher.

2.2 Blok cipher GOST 28147-89

Algoritma enkripsi GOST 28147 - 89 termasuk dalam kategori cipher blok yang beroperasi sesuai dengan arsitektur jaringan Feistel yang seimbang, di mana dua bagian dari blok informasi yang dipilih berukuran sama. Algoritma ini dikembangkan di kedalaman departemen kedelapan KGB, sekarang diubah menjadi FAPSI dan diabadikan sebagai standar enkripsi Federasi Rusia pada tahun 1989 di bawah Uni Soviet.

Agar metode algoritme ini berfungsi, perlu untuk membagi informasi menjadi blok-blok berukuran 64 bit. Hasilkan atau masukkan ke dalam sistem enkripsi informasi kunci berikut: kunci dan tabel substitusi. Pemilihan kunci dan tabel substitusi untuk enkripsi harus diperhatikan dengan sangat serius, karena ini adalah dasar dari keamanan informasi Anda. Untuk informasi tentang persyaratan apa yang dikenakan pada kunci, dan tabel substitusi, lihat item "Persyaratan untuk informasi kunci".

Saat mempertimbangkan metodenya, kami tidak akan fokus pada ini, karena artikel ini, seperti yang saya katakan di atas, ditulis dengan tujuan mengajari pembaca cara mengenkripsi data dengan metode penggantian sederhana dari algoritma enkripsi ini, tetapi kami pasti akan menyentuh masalah ini di akhir artikel.

Minimum teoritis.

3.1 Informasi kunci

Seperti yang saya katakan di atas, berikut ini secara aktif terlibat dalam enkripsi data:

3.1.1. Kunci adalah urutan delapan elemen, masing-masing 32 bit. Berikut ini, kita akan dilambangkan dengan simbol K, dan unsur-unsurnya adalah k1, k2, k3, k4, k5, k6, k7, k8.

3.1.2 Tabel Substitusi - matriks delapan baris dan enam belas kolom, selanjutnya - Hij. Setiap elemen pada perpotongan baris i dan kolom j menempati 4 bit.

Langkah utama dalam proses enkripsi adalah – langkah utama dari transformasi kripto. Ini tidak lebih dari tindakan untuk mengenkripsi data sesuai dengan algoritma tertentu, hanya pengembang yang memperkenalkan nama terlalu rumit :).

Sebelum mulai mengenkripsi, blok dibagi menjadi dua bagian L dan R, masing-masing 32 bit. Elemen kunci dipilih dan hanya kemudian dua bagian blok ini, elemen kunci, tabel substitusi, dimasukkan ke dalam fungsi langkah utama, hasil dari langkah utama adalah satu iterasi dari siklus dasar, yang akan dibahas dalam paragraf berikutnya. Langkah utama terdiri dari berikut ini:

1. Bagian tambahan dari blok R dijumlahkan dengan elemen kunci K mod 2 32. Saya menggambarkan operasi serupa di atas, di sini hal yang sama hanya eksponennya bukan "4", tetapi "32" - hasil dari operasi ini akan dilambangkan Smod di masa depan.
2. Bagilah hasil Smod yang diperoleh sebelumnya menjadi elemen empat bit s7, s6, s5, s4, s3, s2, s1, s0 dan masukkan ke fungsi pengganti. Penggantiannya adalah sebagai berikut: elemen Smod - si dipilih, kita mulai dari awal dengan elemen terendah, dan mengganti dengan nilai dari tabel penggantian dengan i - baris dan kolom yang ditunjukkan oleh nilai elemen s Saya. Kami meneruskan ke elemen s i +1 dan melanjutkan dengan cara yang sama dan melanjutkan hingga kami mengubah nilai elemen terakhir Smod - hasil dari operasi ini akan dilambangkan sebagai, Sederhana.
3. Dalam operasi ini, kami menggeser nilai Ssimple secara siklis ke kiri sebanyak 11 bit dan mendapatkan Srol.
4. Kami memilih bagian kedua dari blok L dan menambahkannya mod 2 dengan Srol, sebagai hasilnya kami memiliki Sxor.
5. Pada tahap ini, bagian dari blok L menjadi sama dengan nilai bagian R, dan bagian R, pada gilirannya, diinisialisasi dengan hasil Sxor, dan pada tahap ini fungsi dari langkah utama selesai!

3.3 Siklus dasar: "32-З", "32-Р".

Untuk mengenkripsi informasi, perlu untuk membaginya menjadi blok-blok berukuran 64 bit, tentu saja blok terakhir bisa kurang dari 64 bit. Fakta ini adalah kelemahan dari metode "penggantian mudah" ini. Karena penambahannya ke 64 bit adalah tugas yang sangat penting untuk meningkatkan kekuatan kriptografi program cipher dan ke tempat sensitif ini, jika ada dalam array informasi, dan mungkin tidak ada (misalnya, file 512 byte! ), Seseorang harus memperlakukan dengan tanggung jawab yang besar!

Setelah Anda membagi informasi menjadi blok, Anda harus membagi kunci menjadi elemen:

K = k1, k2, k3, k4, k5, k6, k7, k8

Enkripsi itu sendiri terdiri dari penggunaan yang disebut siklus dasar. Yang, pada gilirannya, termasuk jumlah ke-n dari langkah-langkah dasar transformasi kripto.

Siklus dasar diberi label, cara mengatakannya: n - m. Di mana n adalah jumlah langkah dasar transformasi kripto dalam siklus dasar, dan m adalah "tipe" dari siklus dasar, mis. tentang apa, tentang enkripsi "Z" atau enkripsi data "R".

Siklus enkripsi dasar 32-З terdiri dari 32 langkah dasar transformasi kripto. Blok N dan elemen kunci K dimasukkan ke dalam fungsi yang mengimplementasikan tindakan langkah, dan langkah pertama terjadi dengan k1, yang kedua di atas hasil yang diperoleh dengan elemen k2, dll. sesuai skema berikut:

k1, k2, k3, k4, k5, k6, k7, k8, k1, k2, k3, k4, k5, k6, k7, k8, k1, k2, k3, k4, k5, k6, k7, k8k8, k7, k6, k5, k4, k3, k2, k1

Proses dekripsi untuk 32-P terjadi dengan cara yang sama, tetapi elemen kunci diberikan dalam urutan terbalik:

k1, k2, k3, k4, k5, k6, k7, k8, k8, k7, k6, k5, k4, k3, k2, k1, k8, k7, k6, k5, k4, k3, k2, k1, k8, k7, k6, k5, k4, k3, k2, k1

Praktek.

Setelah kami berkenalan dengan teori tentang cara mengenkripsi informasi, sekarang saatnya untuk melihat bagaimana enkripsi bekerja dalam praktiknya.

Data awal:

Ambil blok informasi N = 0102030405060708h, di sini bagian L dan R sama:

L = 01020304h, R = 05060708h, mari kita ambil kuncinya:

K = ‘ sebagai28 zw37 q839 7342ui23 8e2t wqm2 ewp1 '(ini adalah kode ASCII, untuk melihat representasi heksadesimal, Anda dapat membuka file ini dalam mode tampilan di Total Commander dengan menekan tombol F3"Lalu kuncinya" 3 "). Dalam kunci ini, nilai elemen akan menjadi:

k1 = ‘as28’, k2 = ‘zw37’, k3 = ‘q839’, k4 = ‘7342’

k5 = ‘ui23’, k6 = ‘8e2t’, k7 = ‘wqm2’, k8 = ‘ewp1’

Ambil juga tabel substitusi berikut:

Beras. 3

Di sini, baris diberi nomor dari 0 hingga 7, kolom dari 0 hingga F.

Sebuah peringatan: Semua informasi, termasuk kunci dengan tabel substitusi, diambil sebagai contoh untuk mempertimbangkan algoritma!

Menggunakan "Data awal", perlu untuk mendapatkan hasil dari tindakan langkah utama transformasi kripto.

1. Kami memilih bagian R = 05060708h dan elemen kunci k1 = 'as28', dalam bentuk heksadesimal elemen kunci akan terlihat seperti ini: 61733238h. Sekarang kita melakukan operasi penjumlahan mod 2 32:

Beras. 4

Seperti yang Anda lihat pada gambar, kami tidak memiliki transfer dalam 33 bit yang ditandai dengan warna merah dan dengan eksponen “ 32 ". Dan jika kita memiliki nilai lain dari R dan elemen kunci, ini bisa saja terjadi, dan kemudian kita akan mengabaikannya, dan selanjutnya hanya menggunakan bit yang ditandai dengan warna kuning.

Saya melakukan operasi ini dengan perintah assembler Menambahkan:

; eax = R, ebx = 'as28'

Hasil dari operasi ini Smod = 66793940h

1. Sekarang operasi yang paling rumit, tetapi jika Anda melihat lebih dekat, itu tidak lagi seburuk kelihatannya pada awalnya. Mari kita bayangkan Smod sebagai berikut:

GAMBAR TIDAK TERSIMPAN

Beras. 5

Saya mencoba memvisualisasikan elemen Smod pada gambar, tetapi saya akan tetap menjelaskan:

s0 = 0, s1 = 4, s2 = 9, dst.

Sekarang, mulai dari elemen terendah s0, kami melakukan penggantian. Mengingat paragraf “ 3.2 Langkah dasar transformasi kripto»I - baris, s i - kolom, cari nilai pada baris nol dan kolom nol:

Gambar 6

Jadi nilai Smod saat ini bukan 6679394 0 h, dan 6679394 5 H.

Kami melanjutkan untuk mengganti s1, mis. empat. Menggunakan baris pertama dan kolom keempat (s1 = 4!). Kita lihat gambarnya:

Beras. 7

Sekarang sudah nilai Smod, bukan 667939 4 5 jam, 667939 2 5 jam Saya berasumsi bahwa sekarang algoritma penggantian jelas bagi pembaca, dan saya dapat mengatakan bahwa setelah hasil akhir Ssimple akan memiliki nilai berikut - 11e10325h.

Saya akan berbicara tentang bagaimana ini paling mudah diimplementasikan dalam bentuk perintah assembler nanti di paragraf berikutnya, setelah saya berbicara tentang tabel yang diperluas.

1. Kita harus menggeser nilai Simple yang dihasilkan 11 bit ke kiri.

Beras. delapan

Seperti yang Anda lihat, tindakan ini cukup sederhana, dan diimplementasikan oleh satu perintah bahasa rakitan - peran dan hasil dari operasi Srol ini adalah 0819288Fh.

1. Sekarang tetap menjadi bagian L dari blok informasi kita untuk di-XOR dengan nilai Srol. Saya mengambil kalkulator dari w2k sp4 dan mendapatkan Sxor = 091b2b8bh.
2. Tindakan ini final dan kami hanya menetapkan, membersihkan R, nilai bagian L, dan menginisialisasi bagian L dengan nilai Sxor.

Hasil akhir:

L = 091b2b8bh, R = 01020304h

4.2 Meningkatkan kecepatan algoritma

Sekarang mari kita bicara tentang mengoptimalkan algoritma untuk kecepatan. Dalam proses pelaksanaan proyek, kita harus memperhitungkan bahwa program yang bekerja dengan register lebih sering daripada dengan memori bekerja paling cepat, dan di sini penilaian ini juga sangat penting, karena lebih dari satu blok informasi sebanyak 32 tindakan enkripsi!

Ketika saya menerapkan algoritma enkripsi dalam program saya, saya melakukan hal berikut:

1. Bagian yang dipilih dari blok L ke register eax, dan R ke edx.
2. Dalam register esi, diinisialisasi dengan alamat kunci yang diperluas, lebih lanjut di bawah ini.
3. Dalam register ebx diberikan nilai alamat dari tabel substitusi yang diperluas, lebih lanjut tentang ini di bawah ini
4. Mentransfer informasi item 1, 2, 3 ke fungsi siklus dasar 32 - atau 32 - , tergantung pada situasinya.

Jika Anda melihat diagram alir dari elemen-elemen kunci dalam paragraf " Siklus dasar: "32-З", "32-Р"", Maka kunci kita untuk siklus dasar 32 - 3 dapat direpresentasikan sebagai berikut:

K 32-Z =

'As28', 'zw37', 'q839', '7342', 'ui23', '8e2t', 'wqm2', 'ewp1',

'As28', 'zw37', 'q839', '7342', 'ui23', '8e2t', 'wqm2', 'ewp1',

'Ewp1', 'wqm2', '8e2t', 'ui23', '7342', 'q839', 'zw37', 'as28'

Itu. dari awal ada k1, k2, k3, k4, k5, k6, k7, k8 - ‘ sebagai28','zw37 ','q839 ',' 7342 ','ui23 ',' 8e2T ','wqm2','epp1 ' urutan ini diulang tiga kali. Kemudian elemen berjalan dalam urutan terbalik, yaitu .: k8, k7, k6, k5, k4, k3, k2, k1 - 'Ewp1', 'wqm2', '8e2t', 'ui23', '7342', 'q839', 'zw37', 'as28'.

Saya mengatur elemen dalam array terlebih dahulu dalam urutan yang harus dimasukkan dalam 32 - Z. Jadi, saya meningkatkan memori yang diperlukan secara turnkey, tetapi menyelamatkan diri dari beberapa proses berpikir yang tidak saya butuhkan, dan meningkatkan kecepatan dari algoritma, karena dengan mengurangi waktu akses memori! Di sini saya hanya menjelaskan kunci untuk 32 - , untuk siklus 32 - Saya melakukan hal yang sama, tetapi menggunakan skema pemasokan elemen yang berbeda, yang juga saya jelaskan dalam paragraf " Siklus dasar: “32-Z”, “32-P».

Sekarang saatnya menjelaskan implementasi fungsi pengganti, seperti yang saya janjikan di atas. Saya tidak bisa menjelaskan sebelumnya, karena ini membutuhkan pengenalan konsep baru - tabel substitusi yang diperluas. Saya tidak bisa menjelaskan kepada Anda apa itu. Sebagai gantinya, saya akan menunjukkannya kepada Anda, dan Anda sendiri yang merumuskan sendiri, apa itu - tabel substitusi yang diperluas?

Jadi, untuk memahami apa itu tabel substitusi yang diperluas, kita memerlukan tabel substitusi, misalnya, saya akan mengambil yang ditunjukkan pada Gambar. 3.

Misalnya, kami perlu mengganti nomor 66793940h. Saya akan menyajikannya sebagai berikut:

GAMBAR TIDAK TERSIMPAN

Beras. sembilan

Sekarang jika kita mengambil elemen s1, s0, yaitu. byte paling signifikan, hasil dari fungsi penggantian akan menjadi 25 jam! Setelah membaca artikel oleh Andrey Vinokurov, yang saya kutip dalam paragraf " Daftar literatur yang digunakan", Anda benar-benar menemukan bahwa jika Anda mengambil dua baris, Anda bisa mendapatkan array, memungkinkan Anda menemukan elemen pengganti dengan cepat menggunakan perintah assembler xlat. Mereka mengatakan itu dapat dilakukan dengan cara lain lebih cepat, tetapi Andrey Vinokurov menghabiskan sekitar empat tahun untuk meneliti algoritma cepat untuk implementasi GOST! Saya tidak berpikir Anda harus menemukan kembali roda ketika Anda sudah memilikinya.

Jadi, tentang array:

Mari kita ambil dua baris pertama nol dan yang pertama, buat array 256 byte. Sekarang kami mengamati satu keanehan bahwa jika perlu untuk mengubah 00h, maka hasilnya akan menjadi 75h (berdasarkan Gambar 3) - kami menempatkan nilai ini ke dalam array pada offset 00h. Kami mengambil nilai 01h, hasil dari fungsi substitusi 79h, memasukkannya ke dalam array pada offset 01, dan seterusnya hingga 0FFh, yang akan memberi kami 0FCh, yang akan kami masukkan ke dalam array pada offset 0FFh. Jadi kami mendapat tabel substitusi yang diperluas untuk grup baris pertama: yang pertama dan nol. Tapi masih ada tiga kelompok: halaman kedua 2, halaman 3, halaman ketiga 4, halaman 5, halaman keempat 6, halaman 7. Kami menangani ketiga kelompok ini dengan cara yang sama seperti yang pertama. Hasilnya adalah tabel substitusi yang diperpanjang!

Sekarang kita dapat mengimplementasikan algoritma yang akan melakukan penggantian. Untuk melakukan ini, kami mengambil kode sumber yang diposting Andrei Vinokurov di halamannya, lihat " Bibliografi».

lea ebx, extended_table_simple

mov eax, [masukkan nomor yang akan diganti]

tambahkan ebx, 100h; lompat ke dua node berikutnya

sub ebx, 300 jam; sehingga di masa depan ebx menunjuk ke tabel

Sekarang satu fitur lagi, dengan tindakan sebelumnya kami tidak hanya mengganti, tetapi juga menggeser angka sebanyak 8 bit ke kiri! Kita hanya perlu menggeser angka 3 bit lagi ke kiri:

dan kita mendapatkan hasil dari operasi rol eax, 11!

Saya tidak dapat menambahkan apa-apa lagi tentang pengoptimalan, satu-satunya hal yang dapat saya tekankan adalah apa yang saya katakan di atas - gunakan register lebih sering daripada akses memori. Saya pikir kata-kata ini hanya untuk pemula, yang berpengalaman dan tanpa kata-kata saya memahami ini dengan sempurna :).

Persyaratan untuk informasi kunci.

Seperti yang dinyatakan dalam artikel oleh Andrey Vinokurov, kuncinya dipilih berdasarkan dua kriteria:

- kriteria untuk distribusi bit yang setara antara nilai 1 dan 0. Biasanya, kriteria untuk distribusi bit yang setara adalah kriteria Pearson ("chi-kuadrat").

Ini berarti kunci, pada prinsipnya, nomor berapa pun bisa. Artinya, ketika bit kunci berikutnya terbentuk, kemungkinan inisialisasinya dengan satu atau nol adalah 50/50!

Harap dicatat bahwa kunci terdiri dari delapan elemen, masing-masing 32 bit, jadi hanya ada 32 * 8 = 256 bit dalam kunci dan jumlah kemungkinan kunci adalah 2 256! Tidakkah itu mengejutkan Anda? 🙂

- kriteria seri.

Jika kita melihat kunci kita, yang saya berikan di paragraf " 4.1 Implementasi langkah utama transformasi kripto», Maka Anda akan melihat bahwa notasi berikut ini valid:

Beras. sepuluh

Dalam satu frase, nilai k 1 tidak boleh diulang tidak di k 2, tidak di elemen kunci lainnya.

Artinya, kunci yang kita pilih sebagai pertimbangan algoritma enkripsi konsisten dengan dua kriteria di atas.

Sekarang tentang pilihan tabel substitusi:

Sekarang mari kita bicara tentang bagaimana memilih tabel substitusi yang tepat. Persyaratan utama untuk pemilihan tabel pengganti adalah fenomena elemen "non-repeatability", yang masing-masing berukuran 4 bit. Seperti yang Anda lihat di atas, setiap baris tabel substitusi terdiri dari nilai 0h, 1h, 2h, 3h,…, 0fh. Jadi syarat utamanya adalah setiap baris berisi nilai 0h, 1h, 2h, ..., 0fh dan masing-masing nilai tersebut dalam satu salinan. Misalnya, urutannya:

1 2 3 4 5 6 7 8 9 A B C D E F

Ini sepenuhnya sesuai dengan persyaratan ini, tapi tetap saja! Tidak disarankan untuk memilih urutan ini sebagai string. Karena jika Anda memasukkan nilai ke input fungsi yang bergantung pada string seperti itu, maka Anda akan mendapatkan nilai yang sama pada output! Tidak percaya padaku? Kemudian ambil angka 332DA43Fh dan delapan baris seperti tabel substitusi. Lakukan operasi penggantian, dan saya jamin, hasilnya akan menjadi angka 332DA43Fh! Artinya, sama dengan yang Anda kirimkan ke input operasi! Dan ini bukan pertanda baik dalam enkripsi, dan bukan? 🙂

Ini adalah salah satu persyaratan, kriteria berikutnya mengatakan bahwa - setiap bit dari blok output harus secara statistik independen dari setiap bit dari blok input!

Bagaimana tampilannya lebih sederhana? Dan inilah caranya, misalnya, kita telah memilih dari angka di atas elemen s0 = 0Fh, 01111b. Probabilitas bahwa kita sekarang akan mengganti bit pertama dengan satu atau nol adalah 0,5! Probabilitas penggantian bit kedua, ketiga dan keempat, setiap bit, kami pertimbangkan secara terpisah, dengan satu atau nol juga 0, 5. Saat memilih s1 = 0Eh, probabilitas bahwa kami adalah bit nol, dan ini adalah "0" , akan diganti dengan nol atau satu juga sama dengan - 0,5! Jadi, menurut kriteria ini, tidak ada keteraturan antara penggantian bit nol elemen s0, s1! Ya, Anda bisa mengganti satu, tetapi Anda juga bisa mengganti nol. 🙂

Untuk mengevaluasi tabel dengan kriteria ini, Anda dapat membuat tabel koefisien korelasi yang dihitung dengan rumus:

- jika p = 1, maka nilai bit j pada keluaran sama dengan nilai bit i pada masukan untuk setiap kombinasi bit pada masukan;

- jika p = -1, maka nilai bit j pada keluaran selalu kebalikan dari bit masukan i;

- jika p = 0, maka bit keluaran j dengan probabilitas yang sama mengambil nilai 0 dan 1 untuk setiap nilai tetap dari bit masukan i.

Mari kita ambil satu contoh baris:

D	B	4	1	3	F	5	9	0	A	E	7	6	8	2	C

Mari kita memecahnya menjadi "komponen":

Mari kita hitung satu koefisien sesuai dengan rumus di atas. Agar lebih mudah memahami bagaimana hal ini dilakukan, saya akan menjelaskan lebih detail:

- kami mengambil bit ke-0 dari angka 0 (0) pada input dan bit ke-0 dari angka 0 pada output (1) kami melakukan operasi 0 XOR 1 = 1.

- kami mengambil bit ke-0 dari angka 1 (1) pada input dan bit ke-0 dari angka 1 pada output (1) kami melakukan operasi 1 XOR 1 = 0.

- kami mengambil bit ke-0 dari angka ke-2 (0) pada input dan bit ke-0 dari angka ke-2 pada output (0) kami melakukan operasi 0 XOR 0 = 0.

- kami mengambil bit ke-0 dari angka ke-3 (1) pada input dan bit ke-0 dari angka ke-3 pada output (1) kami melakukan operasi 1 XOR 1 = 0.

Melakukan operasi XOR berturut-turut dalam urutan ini, kami menghitung jumlah semua nilai bukan nol, kami mendapatkan nilai 6. Oleh karena itu P 00 = 1- (6/2 4-1) = 0,25. Jadi, ternyata nilai bit 0 pada output sama dengan nilai bit 0 pada input dalam 4 kasus dari 16;

Tabel peluang akhir:

Tabel koefisien adalah sebagai berikut (kepada siapa tidak malas untuk menghitung ulang)

	pintu masuk
Keluaran		0	1	2	3
	0	-0,25	0,00	0,00	0,00
	1	0,00	1,00	0,00	0,00
	2	0,00	0,00	1,00	0,00
	3	0,00	0,00	0,00	-0,50

Nah, di tabel ini, keadaannya bahkan lebih buruk - bit 1 dan 2 dari grup tetap tidak berubah! Kriptanalisis memiliki tempat untuk berpaling Mempertimbangkan semua persyaratan ini, dengan pencarian sederhana ("langsung"), tabel permutasi yang sesuai dengan teori yang ditunjukkan ditemukan (hari ini - 1276 kombinasi) Berikut adalah beberapa di antaranya:

09 0D 03 0E-06 02 05 08-0A 07 00 04-0C 01 0F 0B

00 05 0A 07-03 08 0F 0C-0E 0B 04 09-0D 06 01 02

06 0B 0F 00-0C 01 02 0D-08 07 09 04-05 0A 03 0E

04 0E 00 09-0B 01 0F 06-03 0D 07 0A-0C 02 08 05

04 02 08 0E-05 0F 03 09-0B 01 0D 07-0A 0C 06 00

07 03 09 0C-08 00 06 0F-0E 04 01 0A-0D 0B 02 05

06 0F 03 08-0D 04 0A 01-09 02 05 0C-00 0B 0E 07

0C 06 08 01-03 09 07 0E-0B 05 0F 02-04 0A 00 0D

04 0B 09 06-0E 01 00 0F-0A 05 03 0C-0D 02 07 08

00 0E 0F 01-07 08 09 06-04 0B 0A 05-03 0D 0C 02

0F 09 01 07-04 0A 08 06-0E 00 02 0C-05 03 0B 0D

0A 03 04 01-05 0C 0B 0E-08 06 0F 0D-07 09 00 02

0B 06 0F 01-04 0A 08 05-00 0D 0C 02-07 09 03 0E

0C 03 02 08-0D 06 0B 05-07 09 04 0F-0A 00 01 0E

02 0B 0F 04-09 00 06 0D-05 0E 01 08-0C 07 0A 03

Daftar literatur yang digunakan.

1. Artikel oleh Andrey Vinokurov:

Algoritma enkripsi GOST 28147-89, penggunaan dan implementasinya

untuk komputer platform Intel x86.

(dapat ditemukan di: http://www.enlight.ru/crypto/frame.htm).

Ada juga kode sumber untuk implementasi algoritma enkripsi.

1. Artikel Horst Feistel:

Kriptografi dan Keamanan Komputer.

(dapat ditemukan di alamat yang sama dengan artikel sebelumnya)

1. Ross N. Williams:

Panduan Dasar untuk Algoritma Deteksi Kesalahan CRC

Diposting di situs www.wasm.ru.

Ucapan terima kasih.

Saya ingin mengucapkan terima kasih kepada semua pengunjung forum www.wasm.ru. Namun secara khusus saya ingin mengucapkan terima kasih kepada ChS, yang saat ini dikenal sebagai SteelRat, dia membantu saya memahami hal-hal yang mungkin tidak akan pernah saya pahami, serta membantu dalam menulis paragraf: “ Persyaratan informasi utama”, Bagian utama dari paragraf ini ditulis olehnya. Saya juga sangat berterima kasih kepada karyawan KSTU yang dinamai NS. Tupolev Anikin Igor Vyacheslavovich dan itu akan menjadi dosa untuk tidak menyebutkan Chris Kaspersky untuk fakta bahwa dia dan Volodya / wasm.ru untuk instruksinya. Oh, dan saya mendapatkannya dari dia :). Saya juga ingin mencatat Sega-Zero / Callipso, tetapi itu membawa beberapa hutan matematis ke pikiran saya.

Mungkin ini saja yang ingin saya ceritakan kepada Anda.

Saya akan berterima kasih atas kritik atau pertanyaan terkait artikel ini atau hanya saran. Detail kontak saya: [dilindungi email], ICQ - 337310594.

Salam Hormat, Evil's Interrupt.

P.S.: Dengan artikel ini, saya tidak mencoba untuk mengalahkan siapa pun. Itu ditulis dengan niat, untuk memfasilitasi studi GOST, dan jika Anda mengalami kesulitan, ini tidak berarti bahwa saya bersalah dalam hal ini. Bersikaplah masuk akal dan bersabarlah, semua yang terbaik untuk Anda!

Algoritma ini wajib digunakan sebagai algoritma enkripsi di organisasi negara Federasi Rusia dan sejumlah organisasi komersial.

Deskripsi algoritma

Diagram algoritma ditunjukkan pada Gambar. 3.1. Seperti yang Anda lihat, skema algoritma ini cukup sederhana, yang jelas menyederhanakan implementasi perangkat lunak atau perangkat kerasnya.

Algoritma GOST 28147-89 mengenkripsi informasi dalam blok 64 bit, yang dibagi menjadi dua subblok 32 bit (N1 dan N2). Subblock N1 diproses dengan cara tertentu, setelah itu nilainya ditambahkan

dengan nilai sub-blok N2 (penambahan dilakukan modulo 2), maka sub-blok tersebut ditukar. Transformasi semacam itu dilakukan untuk sejumlah putaran tertentu: 16 atau 32, tergantung pada mode operasi algoritma (dijelaskan di bawah). Di setiap putaran, operasi berikut dilakukan:

1. Hamparan kunci. Isi dari sub-blok / VI ditambahkan modulo 2 32 dengan bagian dari kunci Kx.

Kunci enkripsi dari algoritma GOST 28147-89 memiliki dimensi 256 bit, dan Kx adalah bagian 32-bitnya, yaitu, kunci enkripsi 256-bit direpresentasikan sebagai rangkaian subkunci 32-bit (Gbr. 3.2) :

SH ATI, AG2, YU, AG4, K5, KB, K7.

Dalam proses enkripsi, salah satu subkunci ini digunakan, tergantung pada bilangan bulat dan mode operasi algoritma.

Beras. 3.1. Skema algoritma GOST 28147-

Beras. 3.2. Kunci enkripsi algoritma GOST 28147-89

2. Penggantian tabel. Setelah kunci dikenakan, sub-blok / VI dibagi menjadi 8 bagian dari 4 bit, yang nilainya masing-masing diganti secara individual sesuai dengan tabel penggantian untuk bagian sub-blok ini. Kotak substitusi (S-box) sering digunakan dalam algoritma enkripsi modern, jadi ada baiknya mempertimbangkannya secara lebih rinci.

Penggantian tabel digunakan dengan cara ini: blok data dari dimensi tertentu (dalam hal ini, 4-bit) diumpankan ke input, representasi numerik yang menentukan jumlah nilai output. Misalnya, kami memiliki kotak-S dengan bentuk berikut:

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

Biarkan blok 4-bit "0100" masuk ke input, yaitu nilainya 4. Menurut tabel, nilai outputnya adalah 15, yaitu. "1111" (0 diganti dengan 4, 1 diganti dengan 11, nilai 2 tidak berubah, dll.).

Seperti yang Anda lihat, skema algoritmenya sangat sederhana, yang berarti bahwa beban enkripsi data terbesar jatuh pada tabel pengganti. Sayangnya, algoritme memiliki properti bahwa ada tabel substitusi "lemah", ketika menggunakan algoritme yang dapat diungkapkan dengan metode cryptanalytic. Yang lemah termasuk, misalnya, tabel di mana output sama dengan input:

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

3. Pergeseran kiri siklik bitwise sebesar 11 bit.

Mode operasi algoritma

Algoritma GOST 28147-89 memiliki 4 mode operasi:

modus penggantian sederhana;

modus gama;

Mode gamma P dengan umpan balik;

mode produksi simulator.

Mode ini agak berbeda dari yang diterima secara umum (dijelaskan di Bagian 1.4), jadi ada baiknya mempertimbangkannya secara lebih rinci.

Mode ini memiliki tujuan yang berbeda, tetapi menggunakan transformasi enkripsi yang sama yang dijelaskan di atas.

Modus penggantian mudah

Dalam mode penggantian sederhana, 32 putaran yang dijelaskan di atas hanya dilakukan untuk mengenkripsi setiap blok informasi 64-bit. Subkunci 32-bit digunakan dalam urutan berikut:

KO, Kl, K2, KZ, K4, K5, Kb, AG7, KO, ATI, dll. - dalam ronde 1 hingga 24;

K1, Kb, K5, K4, KZ, K2, K \, KO — dalam ronde dari tanggal 25 hingga ke-32.

Dekripsi dalam mode penggantian sederhana dilakukan dengan cara yang persis sama, tetapi dengan urutan subkunci yang sedikit berbeda:

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

KP, Kb, K5, K4, KZ, K2, K \, KO, K1, Kb, dll. - dalam putaran dari tanggal 9 hingga 32.

Mirip dengan mode ECB standar, karena enkripsi blok yang terpisah, mode penggantian sederhana sangat tidak disarankan untuk mengenkripsi data itu sendiri; itu hanya boleh digunakan untuk mengenkripsi kunci enkripsi lain dalam skema multi-kunci.

Modus gamma

Dalam mode gamma (Gbr. 3.3), setiap blok plaintext ditambahkan modulo 2 bitwise dengan blok gamma cipher 64-bit. Gamma cipher adalah urutan khusus yang dihasilkan menggunakan transformasi yang dijelaskan di atas sebagai berikut:

1. Dalam register N1 dan N2 pengisian awalnya ditulis - nilai 64-bit, yang disebut "synchro-burst" (sinkronisasi-burst, pada kenyataannya, adalah analog dari vektor inisialisasi dalam mode CBC, CFB dan OFB).

2. Enkripsi isi register / VI dan N2 (dalam hal ini - pesan sinkronisasi) dilakukan dalam mode penggantian sederhana.

3. Isi N1 ditambahkan modulo (2 32 - 1) dengan konstanta CI = 2 24 + 2 16 + 2 8 + 4, hasil penjumlahan tersebut ditulis ke register / VI.

4. Isi N2 dijumlahkan modulo 2 dengan konstanta C2 = 2 24 + 2 16 + 2 8 +1, hasil penjumlahan tersebut ditulis ke register N2.

5. Isi register / VI dan N2 adalah output sebagai blok gamma cipher 64-bit (yaitu, dalam hal ini / VI dan N2 membentuk blok gamma pertama).

6. Jika blok gamma berikutnya diperlukan (yaitu, Anda perlu melanjutkan enkripsi atau dekripsi), Anda kembali ke langkah 2.

Untuk dekripsi, gamma dibangkitkan dengan cara yang sama, kemudian operasi XOR diterapkan lagi pada ciphertext dan bit gamma.

Untuk menghasilkan gamut cipher yang sama, pengguna yang mendekripsi kriptogram harus memiliki kunci yang sama dan nilai pesan sinkronisasi yang sama yang digunakan untuk mengenkripsi informasi. Jika tidak, tidak akan mungkin untuk mendapatkan teks asli dari yang dienkripsi.

Dalam sebagian besar implementasi algoritme GOST 28147-89, pesan sinkronisasi bukanlah elemen rahasia, namun, pesan sinkronisasi bisa sama rahasianya dengan kunci enkripsi. Dalam hal ini, kita dapat mengasumsikan bahwa panjang efektif kunci algoritme (256 bit) bertambah 64 bit lagi dari pesan sinkronisasi, yang dapat dianggap sebagai elemen kunci tambahan.

Mode gamma dengan umpan balik

Pada mode gamma dengan umpan balik, sebagai pengisian register / VI dan L / 2, mulai dari blok ke-2, bukan blok gamma sebelumnya yang digunakan, tetapi hasil enkripsi blok teks biasa (Gbr. 3.4) . Blok pertama dalam mode ini dibuat sangat mirip dengan yang sebelumnya.

Beras. 3.4. Generasi cipher gamma dalam mode gamma dengan umpan balik

Mode produksi simulator

Awalan adalah checksum kriptografi yang dihitung menggunakan kunci enkripsi untuk memverifikasi integritas pesan. Untuk menghitungnya, ada mode khusus dari algoritma GOST 28147-89.

Pembuatan simulator dilakukan sebagai berikut:

1. Blok informasi 64-bit pertama, yang awalannya dihitung, ditulis ke dalam register N1 dan N2 dan dienkripsi dalam mode penggantian sederhana yang dikurangi, di mana 16 putaran pertama dari 32 dilakukan.

2. Hasil yang diperoleh dijumlahkan modulo 2 dengan blok informasi berikutnya, menyimpan hasilnya dalam N1 dan N2.

3. M dan N2 dienkripsi lagi dalam mode pengurangan penggantian sederhana, dan seterusnya sampai blok informasi terakhir.

Peniru adalah hasil 64-bit dari register N1 dan N2, atau bagian darinya. Awalan 32-bit yang paling umum digunakan digunakan, yaitu setengah dari isi register. Ini sudah cukup, karena, seperti checksum lainnya, simulator dirancang terutama untuk melindungi dari distorsi informasi yang tidak disengaja. Untuk melindungi dari modifikasi data yang disengaja, metode kriptografi lainnya digunakan - pertama-tama, tanda tangan digital elektronik (lihat bagian 1.1).

Peniru digunakan sebagai berikut:

1. Saat mengenkripsi informasi apa pun, awalan plaintext dihitung dan dikirim bersama dengan ciphertext.

2. Setelah dekripsi, awalan dihitung kembali dan dibandingkan dengan yang dikirim.

3. Jika awalan yang dihitung dan dikirim tidak cocok - teks sandi terdistorsi selama transmisi atau kunci yang salah digunakan selama dekripsi.

Awalan sangat berguna untuk memverifikasi dekripsi yang benar dari informasi kunci saat menggunakan skema multi-kunci.

Peniru adalah beberapa analog dari kode otentikasi pesan MAC yang dihitung dalam mode CBC; perbedaannya adalah pesan sinkronisasi tidak digunakan dalam perhitungan awalan, sedangkan vektor inisialisasi digunakan dalam perhitungan MAC.

Kekuatan kriptografi dari algoritma

Pada tahun 1994, deskripsi algoritma GOST 28147-89 diterjemahkan ke dalam bahasa Inggris dan diterbitkan; barulah setelah itu hasil analisisnya yang dilakukan oleh para ahli asing mulai terlihat; namun, untuk jangka waktu yang cukup lama, tidak ada serangan yang ditemukan mendekati layak.

panjang kunci besar - 256 bit; bersama dengan pesan sinkronisasi rahasia, panjang kunci efektif ditingkatkan menjadi 320 bit;

32 putaran transformasi; setelah 8 putaran, efek penuh dari dispersi data input tercapai: perubahan dalam satu bit dari blok plaintext akan mempengaruhi semua bit dari blok ciphertext, dan sebaliknya, yaitu, ada margin keamanan ganda.

Pertimbangkan hasil kriptanalisis dari algoritma GOST 28147-89.

Analisis tabel pengganti

Karena tabel substitusi tidak diberikan dalam standar, sejumlah karya (misalnya, c) menyarankan bahwa "organisasi yang kompeten" dapat menghasilkan tabel substitusi "baik" dan "buruk". Namun, ahli terkenal Bruce Schneier menyebut asumsi seperti itu "rumor". Jelas bahwa kekuatan kriptografi dari algoritme sangat tergantung pada properti tabel pengganti yang digunakan; oleh karena itu, ada tabel pengganti yang lemah (lihat contoh di atas), yang penggunaannya dapat menyederhanakan serangan terhadap algoritma. Namun demikian, kemungkinan menggunakan tabel pengganti yang berbeda tampaknya merupakan ide yang sangat berharga, yang mendukung dua fakta dari sejarah standar enkripsi DES yang dapat dikutip (lihat bagian 3.15 untuk detailnya):

serangan menggunakan kriptanalisis linier dan diferensial dari algoritma DES menggunakan fitur khusus dari tabel pengganti; saat menggunakan tabel lain, kriptanalisis harus memulai dari awal;

upaya telah dilakukan untuk memperkuat DES terhadap kriptanalisis linier dan diferensial dengan menggunakan tabel substitusi yang lebih kuat; tabel tersebut, yang memang lebih kuat, diusulkan, misalnya, dalam algoritma DES 5 s; tetapi, sayangnya, tidak mungkin untuk mengganti DES dengan s 5 DES, karena tabel pengganti didefinisikan secara kaku dalam standar, masing-masing, implementasi algoritma mungkin tidak mendukung kemampuan untuk mengubah tabel ke tabel lain.

Sejumlah karya (misalnya, dan) secara keliru menyimpulkan bahwa tabel rahasia substitusi dari algoritma GOST 28147-89 dapat menjadi bagian dari kunci dan meningkatkan panjang efektifnya (yang tidak signifikan, karena algoritma memiliki 256- yang sangat besar). kunci bit). Namun, pekerjaan tersebut membuktikan bahwa tabel substitusi rahasia dapat dihitung menggunakan serangan berikut, yang dapat diterapkan dalam praktik:

1. Kunci nol diatur dan pencarian "vektor nol" dilakukan, yaitu nilai z = / (0), di mana / () adalah fungsi putaran algoritma. Tahap ini memakan waktu sekitar 2 operasi enkripsi.

2. Menggunakan vektor nol, nilai tabel substitusi dihitung, yang membutuhkan tidak lebih dari 2 11 operasi.

Modifikasi algoritma dan analisisnya

Pekerjaan melakukan kriptanalisis modifikasi algoritma GOST 28147-89:

algoritma GOST-H, di mana, relatif terhadap algoritma asli, urutan penggunaan subkunci diubah, yaitu, dalam putaran 25 hingga 32, subkunci digunakan dalam urutan langsung, yaitu, dengan cara yang sama seperti pada putaran algoritma sebelumnya;

Algoritma GOST® 20 putaran, yang menggunakan XOR untuk menerapkan kunci alih-alih penambahan modulo 32.

Berdasarkan hasil analisis, disimpulkan bahwa GOST-H dan GOST © lebih lemah dari algoritma GOST 28147-89 yang asli, karena keduanya memiliki kelas kunci yang lemah. Perlu dicatat bahwa di bagian kriptanalisis GOST ©, pekerjaan mengulangi kata demi kata bagian yang dikhususkan untuk kriptanalisis algoritma GOST 28147-89, diterbitkan pada tahun 2000 oleh karya terkenal (tanpa referensi ke aslinya) . Hal ini menimbulkan keraguan pada profesionalisme penulis karya dan hasil lainnya.

Modifikasi algoritma yang sangat menarik diusulkan dalam pekerjaan: tabel S \… Ss harus berbeda; di setiap putaran algoritma, mereka harus diatur ulang menurut hukum tertentu. Permutasi ini dapat bergantung pada kunci enkripsi, atau dapat rahasia (yaitu, dapat menjadi bagian dari kunci enkripsi yang lebih besar dari kunci 256-bit asli). Kedua opsi ini, menurut penulisnya, secara signifikan meningkatkan ketahanan algoritma terhadap kriptanalisis linier dan diferensial.

Dan satu lagi modifikasi terkait dengan tabel substitusi diberikan dalam pekerjaan, yang menganalisis salah satu metode yang mungkin untuk menghitung tabel substitusi berdasarkan kunci enkripsi. Penulis karya menyimpulkan bahwa ketergantungan seperti itu melemahkan algoritme, karena ini mengarah pada keberadaan kunci yang lemah dan beberapa potensi kerentanan algoritme.

Analisis algoritme putaran penuh

Ada serangan pada GOST 28147-89 full-round tanpa modifikasi apa pun. Salah satu makalah terbuka pertama yang menganalisis algoritme, makalah terkenal, dikhususkan untuk serangan yang mengeksploitasi kelemahan prosedur perluasan kunci dari sejumlah algoritme enkripsi terkenal. Secara khusus, algoritma GOST 28147-89 putaran penuh dapat dipecah menggunakan kriptanalisis diferensial pada kunci yang ditautkan, tetapi hanya jika tabel substitusi yang lemah digunakan. Varian 24 putaran dari algoritme (yang tidak memiliki 8 putaran pertama) dibuka dengan cara yang sama untuk tabel substitusi apa pun, tetapi tabel substitusi yang kuat (misalnya, ditunjukkan dalam c) membuat serangan seperti itu sama sekali tidak praktis.

Ilmuwan dalam negeri A.G. Rostovtsev dan E.B. Makhovenko pada tahun 2001 dalam pekerjaan mereka mengusulkan metode kriptanalisis yang secara fundamental baru (menurut penulis, ini jauh lebih efektif daripada kriptanalisis linier dan diferensial) dengan membentuk fungsi objektif dari teks biasa yang dikenal yang sesuai dengannya. dan nilai kunci yang diinginkan dan menemukan ekstremnya yang sesuai dengan nilai kunci yang sebenarnya. Mereka juga menemukan kelas besar kunci lemah dari algoritma GOST 28147-89, yang memungkinkan pemecahan algoritma hanya menggunakan 4 teks biasa yang dipilih dan teks sandi yang sesuai dengan kompleksitas yang cukup rendah. Kriptanalisis algoritma dilanjutkan dalam pekerjaan.

Pada tahun 2004, sekelompok spesialis dari Korea mengusulkan serangan yang, dengan menggunakan kriptanalisis diferensial pada kunci yang terhubung, adalah mungkin untuk memperoleh, dengan probabilitas 91,7%, 12 bit dari kunci rahasia. Serangan tersebut membutuhkan 2 35 plaintext yang dipilih dan 2 36 operasi enkripsi. Seperti yang Anda lihat, serangan ini praktis tidak berguna untuk serangan nyata pada algoritma.

Algoritma GOST 28147-89 dan sandi "Magma" (GOST R 34.12-2015)

Skema umum dari algoritma. Algoritme yang dijelaskan oleh GOST 28147-89 “Sistem pemrosesan informasi. Perlindungan kriptografi. Algoritma Transformasi Kriptografi ", adalah standar domestik untuk enkripsi simetris (sebelum 1 Januari 2016) dan wajib untuk diterapkan dalam alat perlindungan informasi kriptografi bersertifikat yang digunakan dalam sistem informasi negara bagian dan, dalam beberapa kasus, dalam sistem komersial. Sertifikasi sarana perlindungan kriptografi informasi diperlukan untuk melindungi informasi yang merupakan rahasia negara Federasi Rusia, dan informasi, yang kerahasiaannya harus dijamin sesuai dengan undang-undang saat ini. Juga di Federasi Rusia, penggunaan algoritma GOST 28147-89 direkomendasikan untuk perlindungan sistem informasi perbankan.

Algoritma GOST 28147-89 (Gbr. 2.21) didasarkan pada skema Feistel dan mengenkripsi informasi dalam blok 64 bit, yang dibagi menjadi dua sub-blok 32 bit (I, dan R). Subblok R, diproses oleh fungsi transformasi bulat, setelah itu nilainya ditambahkan ke nilai subblok Lj, kemudian subblok tersebut ditukar. Algoritme memiliki 16 atau 32 putaran, tergantung pada mode enkripsi (perhitungan penyisipan imitasi atau mode enkripsi lainnya).

Beras. 2.21.

Di setiap putaran algoritma, transformasi berikut dilakukan.

1. Hamparan kunci. Konten subblok R i menambahkan modulo 2 32 dengan kunci bulat K. Kj adalah bagian 32-bit dari kunci asli yang digunakan sebagai kunci bulat. Algoritma GOST 28147-89 ns menggunakan prosedur perluasan kunci, kunci enkripsi 256-bit asli direpresentasikan sebagai rangkaian (gabungan) dari delapan subkunci 32-bit (Gbr. 2.22): K 0, K (, K t K, K A, K 5, K 6, K 7.

Proses enkripsi menggunakan salah satu subkunci tersebut. KE

Dari putaran ke-1 hingga ke-24 - dalam urutan langsung:

Dari ronde ke-25 hingga ke-32 - dalam urutan terbalik:

Beras. 2.22. Struktur kunci enkripsi dari algoritma GOST 28147-89

2. Penggantian tabel. Setelah kunci diterapkan, subblok R i dibagi menjadi delapan bagian tetapi 4 bit, nilai yang masing-masing diganti secara individual sesuai dengan tabel penggantinya (S-box). Sebanyak delapan S-box digunakan - S 0, S, S 2, S 3, S 4, S 5, S 6, S 7. Setiap S-box dari algoritma GOST 28147-89 adalah vektor (array satu dimensi) dengan elemen ^ bernomor dari 0 hingga 15. Nilai S-box adalah angka 4-bit; bilangan bulat dari 0 sampai 15.

Sebuah elemen diambil dari tabel S-box, nomor urut yang bertepatan dengan nilai yang datang ke input substitusi.

Contoh 2.6.

Misalkan ada blok-S dari bentuk berikut:

Biarkan nilai 0100 2 = 4 diberikan pada input dari kotak-S ini.Keluaran dari kotak-S akan menjadi elemen ke-4 dari tabel substitusi, yaitu. 15 = 1111 2 (penomoran elemen dimulai dari nol).

orang pengganti tidak ditentukan oleh standar, seperti yang dilakukan, misalnya, dalam sandi DES. Nilai tabel substitusi yang dapat diubah mempersulit kriptanalisis algoritma secara signifikan. Pada saat yang sama, kekokohan algoritma secara signifikan tergantung pada pilihan yang benar.

Sayangnya, algoritma GOST 28147-89 memiliki tabel substitusi "lemah", ketika menggunakan algoritma yang dapat dengan mudah diungkapkan dengan metode cryptanalytic. Di antara yang "lemah", misalnya, tabel substitusi sepele, di mana input sama dengan output (Tabel 2.16).

Tabel 2.16

Contoh S-box yang lemah

Diyakini bahwa nilai spesifik dari tabel pengganti harus dirahasiakan dan merupakan elemen kunci jangka panjang, mis. valid untuk periode yang lebih lama daripada kunci individual. Namun, nilai rahasia tabel pengganti bukan bagian dari kunci dan tidak dapat menambah panjang efektifnya.

Memang, tabel substitusi rahasia dapat dihitung menggunakan serangan berikut, yang dapat diterapkan dalam praktik:

• kunci nol diatur dan pencarian untuk "vektor nol" dilakukan, mis. arti z = F ( 0), dimana F - fungsi algoritma transformasi bulat. Ini membutuhkan sekitar 2 32 operasi enkripsi uji;
• menggunakan vektor nol, nilai tabel substitusi dihitung, yang membutuhkan tidak lebih dari 2 11 operasi.

Namun, bahkan jika kerahasiaan tabel substitusi dilanggar, kekuatan cipher tetap sangat tinggi dan tidak jatuh di bawah batas yang diizinkan.

Diasumsikan juga bahwa tabel substitusi adalah umum untuk semua node enkripsi dalam sistem proteksi kriptografi yang sama.

Memperbaiki struktur S-box adalah salah satu masalah yang paling intensif diteliti di bidang cipher blok simetris. Pada dasarnya, setiap perubahan pada input dari S-box diperlukan untuk acak tampaknya mengubah output. Di satu sisi, semakin besar S-box, semakin resisten algoritma terhadap metode kriptanalisis linier dan diferensial. Di sisi lain, meja pengganti yang besar lebih sulit untuk dirancang.

Dalam algoritma modern, S-box biasanya berupa vektor (array satu dimensi) yang berisi 2 "t- elemen bit. Input blok mendefinisikan jumlah elemen, yang nilainya berfungsi sebagai output dari blok-S.

Sejumlah kriteria telah diajukan untuk desain S-box. Tabel substitusi harus memenuhi:

• kriteria longsoran yang ketat;
• kriteria independensi bit;
• persyaratan non-linier dari nilai input.

Untuk memenuhi persyaratan terakhir, diusulkan untuk menentukan kombinasi linier Saya bit ( saya = 1, ..., T) nilai tabel substitusi fungsi bengkok(eng, membungkuk - menyimpang, dalam hal ini - dari fungsi linier). Fungsi bengkok membentuk kelas khusus fungsi Boolean yang dicirikan oleh kelas nonlinier tertinggi dan kepatuhan terhadap kriteria longsoran yang ketat.

Dalam beberapa pekerjaan, untuk S-box, diusulkan untuk memeriksa pemenuhan efek longsoran yang dijamin dari urutan y - ketika satu bit input berubah, setidaknya bit output dari S-box berubah. Properti efek longsoran yang dijamin dari urutan y dari 2 hingga 5 memberikan karakteristik difusi yang cukup baik dari S-box untuk algoritma enkripsi apa pun.

Saat merancang tabel pengganti yang cukup besar, pendekatan berikut dapat digunakan:

• pemilihan acak (untuk kotak S kecil, ini dapat menyebabkan pembuatan tabel substitusi yang lemah);
• seleksi acak diikuti dengan memeriksa kepatuhan terhadap berbagai kriteria dan penolakan terhadap S-box yang lemah;
• pemilihan manual (terlalu melelahkan untuk blok-S besar);
• pendekatan matematis, misalnya, pembangkitan menggunakan fungsi bengkok (pendekatan ini digunakan dalam algoritma CAST).

Prosedur berikut untuk merancang blok-S individu dari algoritma GOST 28147-89 dapat diusulkan:

• setiap S-box dapat dideskripsikan oleh empat fungsi logis, masing-masing fungsi harus memiliki empat argumen logis;
• fungsi-fungsi ini harus cukup canggih. Persyaratan kompleksitas ini tidak dapat dinyatakan secara formal, namun, sebagai kondisi yang diperlukan, dapat diperlukan bahwa fungsi logika yang sesuai, yang ditulis dalam bentuk minimum (yaitu, dengan panjang ekspresi minimum yang mungkin) menggunakan operasi logika dasar, tidak boleh lebih pendek dari nilai tertentu yang diperlukan;
• fungsi individu, bahkan digunakan dalam tabel substitusi yang berbeda, harus cukup berbeda satu sama lain.

Pada tahun 2011, serangan baru "pertemuan refleksif di tengah" diusulkan, yang sedikit mengurangi resistensi GOST 28147-89 (dari 2256 menjadi 2225). Hasil kriptanalisis terbaik dari algoritma pada tahun 2012 mengurangi kekuatannya menjadi 2.192, membutuhkan ukuran ciphertext yang relatif besar dan volume data yang telah dibentuk sebelumnya. Terlepas dari serangan yang diusulkan, GOST 28147-89 praktis tetap stabil pada tingkat perkembangan teknologi komputer saat ini.

Kode "Magma" (GOST R 34.12-2015). Standar GOST 28147-89 telah berlaku di Rusia selama lebih dari 25 tahun. Selama ini, ia telah menunjukkan daya tahan yang cukup dan efisiensi yang baik dari implementasi perangkat lunak dan perangkat keras, termasuk pada perangkat sumber daya rendah. Meskipun serangan cryptanalytic telah diusulkan yang mengurangi perkiraan resistensi (yang terbaik adalah 2.192), mereka jauh dari layak. Oleh karena itu, diputuskan untuk memasukkan algoritma GOST 28147-89 dalam standar enkripsi simetris yang baru dikembangkan.

Di toko 2015, dua standar kriptografi nasional baru diadopsi: GOST R 34.12-2015 “Teknologi informasi. Perlindungan informasi kriptografi. Blokir cipher "dan GOST R 34.13-2015" Teknologi informasi. Perlindungan informasi kriptografi. Mode operasi cipher blok ", yang mulai berlaku pada 1 Januari 2016.

Standar GOST R 34.12-2015 berisi deskripsi dua cipher blok dengan panjang blok 128 dan 64 bit. Cipher GOST 28147-89 dengan blok substitusi nonlinier tetap termasuk dalam GOST R 34.12-2015 baru sebagai cipher 64-bit yang disebut "Magma".

Di bawah ini adalah blok pengganti yang diperbaiki dalam standar:

Himpunan S-box yang diberikan dalam standar memberikan karakteristik terbaik yang menentukan ketahanan algoritma kripto terhadap kriptoanalisis diferensial dan linear.

Menurut komite teknis untuk standarisasi "Perlindungan informasi kriptografis" (TC 26), memperbaiki blok substitusi nonlinier akan membuat algoritma GOST 28147-89 lebih terpadu dan membantu menghilangkan penggunaan blok substitusi nonlinier "lemah". Selain itu, fiksasi dalam standar semua parameter jangka panjang cipher memenuhi praktik internasional yang diterima. Standar baru GOST R 34.12-2015 secara terminologi dan konseptual terkait dengan standar internasional ISO / IEC 10116 “Teknologi informasi. Metode Keamanan. Mode operasi untuk "-bit block cipher" (ISO / IEC 10116: 2006 Teknologi informasi - Teknik keamanan - Mode operasi untuk n-bit block cipher) dan seri ISO / IEC 18033 "Teknologi informasi. Metode dan sarana untuk memastikan keamanan. Algoritma enkripsi ": ISO / IEC 18033-1: 2005" Bagian 1. Umum "(ISO / IEC 18033-1: 2005 Teknologi informasi - Teknik keamanan - Algoritma enkripsi - Bagian 1: Umum) dan ISO / IEC 18033-3: 2010 "Bagian 3. Block cipher" (ISO / IEC 18033-3: 2010 (Teknologi informasi - Teknik keamanan - Algoritma enkripsi - Bagian 3: Block cipher)).

Standar GOST P 34.12-2015 juga mencakup cipher blok baru ("Belalang") dengan ukuran blok 128 bit. Cipher ini diharapkan kuat terhadap semua serangan block cipher yang dikenal saat ini.

Mode operasi cipher blok (penggantian sederhana, gamma, gamma dengan umpan balik keluaran, gamma dengan umpan balik ciphertext, penggantian sederhana dengan keterlibatan dan pengembangan sisipan imitasi) termasuk dalam standar terpisah GOST R 34.13-2015, yang sesuai dengan praktik internasional yang diterima. Mode ini berlaku untuk cipher Magma dan cipher Grasshopper baru.

• Pergeseran kiri melingkar bitwise sebanyak 11 bit dilakukan. Dekripsi dilakukan sesuai dengan skema yang sama, tetapi dengan jadwal penggunaan kunci yang berbeda: dari dekripsi putaran ke-1 hingga ke-8 - dalam urutan langsung: dari dekripsi putaran ke-9 hingga ke-32 - dalam urutan terbalik: Dibandingkan dengan dekripsi Cipher DES di GOST 28147-89 memiliki keuntungan sebagai berikut: kunci yang jauh lebih panjang (256 bit versus 56 untuk cipher DES), serangan yang dengan cara brute force enumerasi set kunci tampaknya tidak mungkin saat ini; jadwal sederhana untuk menggunakan kunci, yang menyederhanakan implementasi algoritma dan meningkatkan kecepatan komputasi. Desain blok-S GOST 28147-89. Jelas bahwa skema algoritma GOST 28147-89 sangat sederhana. Ini berarti bahwa beban enkripsi terbesar jatuh pada tabel substitusi. Nilai tab
• Panasepko S.P. Algoritma Enkripsi: buku referensi khusus. SPb.: BHV-Peter-burg, 2009.
• Serangan Refleksi Kara O. pada Cipher Produk. URL: http://eprint.iacr.org/2007/043.pdf
• Standar enkripsi Rusia: kekuatan berkurang. URL: http://cryptofaq.ru/index.php/2010-12-23-18-20-21/2010-12-23-18-22-09/90-2011-02-01-07-47- 27
• Achekseev E. K., Smyshlyaev S. V. GOST 28147-89: "Jangan buru-buru menguburkannya."

Peneliti terkenal, pendiri kriptanalisis aljabar, Nicolas Courtois, mengklaim bahwa cipher blok GOST, yang akan menjadi standar internasional dalam waktu dekat, sebenarnya telah rusak dan sedang menunggu banyak publikasi di masa depan yang harus mengembangkan ide-idenya tentang ketidakstabilan algoritma ini.

Berikut ini adalah kutipan singkat dari karya ini, yang dapat dianggap sebagai serangan yang mengkhawatirkan di tengah standarisasi internasional (penulis dikenal karena melebih-lebihkan yang serupa dalam kaitannya dengan AES, tetapi karyanya kemudian memiliki pengaruh teoretis yang besar pada kriptanalisis, tetapi telah tidak mengarah pada serangan praktis pada AES itu sendiri). Tapi, mungkin, ini juga merupakan peringatan nyata tentang awal dari tahap "pesawat terjun ke pusaran", yang mungkin berakhir dengan runtuhnya standar enkripsi nasional, seperti halnya dengan algoritma hashing SHA-1 dan algoritma hashing MD5 de facto.

GOST 28147-89 distandarisasi pada tahun 1989 dan menjadi standar resmi untuk perlindungan informasi rahasia untuk pertama kalinya, tetapi spesifikasi sandi tetap tertutup. Pada tahun 1994, standar tersebut dideklasifikasi, diterbitkan dan diterjemahkan ke dalam bahasa Inggris. Dengan analogi dengan AES (dan tidak seperti DES), GOST diizinkan untuk melindungi informasi rahasia tanpa batasan, sesuai dengan cara yang ditentukan dalam standar Rusia. Itu. GOST bukan analog dari DES, tetapi pesaing 3-DES dengan tiga kunci independen atau AES-256. Jelas, GOST adalah sandi yang cukup serius yang memenuhi kriteria militer, dibuat dengan harapan aplikasi yang paling serius. Setidaknya dua set GOST S-box telah diidentifikasi berdasarkan aplikasi yang digunakan oleh bank Rusia. Bank-bank ini perlu melakukan komunikasi rahasia dengan ratusan cabang dan melindungi miliaran dolar dari pencurian penipuan.

GOST adalah cipher blok dengan struktur Feistel sederhana, dengan ukuran blok 64 bit, kunci 256-bit, dan 32 putaran. Setiap putaran berisi penambahan kunci modulo 2 ^ 32, satu set delapan S-box 4-bit, dan pergeseran siklik 11-bit sederhana. Fitur GOST adalah kemampuan untuk menyimpan blok-S secara rahasia, yang dapat direpresentasikan sebagai kunci kedua yang meningkatkan materi kunci efektif menjadi 610 bit. Satu set S-box diterbitkan pada tahun 1994 sebagai bagian dari spesifikasi fungsi hash GOST-R 34.11-94 dan, seperti yang ditulis Schneier, digunakan oleh Bank Sentral Federasi Rusia. Itu juga termasuk dalam standar RFC4357 di bagian "id-GostR3411-94-CryptoProParamSet". Ada bug dalam kode sumber di akhir buku Schneier (dalam urutan S-box). Implementasi referensi paling akurat yang berasal dari bahasa Rusia asli sekarang dapat ditemukan di perpustakaan OpenSSL. Jika S-box rahasia digunakan di suatu tempat, maka mereka dapat diekstraksi dari implementasi perangkat lunak dan dari sirkuit mikro, pada kenyataannya, karya yang sesuai diterbitkan.

GOST adalah pesaing serius

Selain ukuran kunci yang sangat besar, GOST memiliki biaya eksekusi yang jauh lebih rendah dibandingkan dengan AES dan sistem enkripsi serupa lainnya. Faktanya, biayanya jauh lebih murah daripada AES, yang membutuhkan gerbang logika perangkat keras empat kali lebih banyak untuk tingkat keamanan yang diklaim jauh lebih rendah.

Tidak mengherankan bahwa GOST telah menjadi standar Internet, khususnya, termasuk dalam banyak perpustakaan crypto seperti OpenSSL dan Crypto ++, dan menjadi lebih populer di luar negara asalnya. Pada tahun 2010, GOST dinyatakan untuk standarisasi ISO sebagai standar enkripsi di seluruh dunia. Sejumlah kecil algoritma telah mampu menjadi standar internasional. ISO / IEC 18033-3: 2010 menjelaskan algoritme berikut: empat cipher 64-bit - TDEA, MISTY1, CAST-128, HIGHT - dan tiga cipher 128-bit - AES, Camellia, SEED. GOST diusulkan untuk ditambahkan ke standar ISO / IEC 18033-3 yang sama.

Untuk pertama kalinya dalam sejarah standardisasi industri, kita berhadapan dengan algoritma kompetitif seperti itu dalam hal optimalitas antara biaya dan tingkat keamanan. GOST memiliki 20 tahun upaya kriptanalisis dan hingga saat ini keamanan tingkat militernya belum dipertanyakan.

Seperti yang penulis pelajari baru-baru ini dari korespondensi pribadi, sebagian besar negara menentang GOST pada pemungutan suara ISO di Singapura, tetapi hasil pemungutan suara ini masih akan dipertimbangkan pada rapat pleno ISO SC27, sehingga GOST masih dalam proses standardisasi pada saat publikasi karya ini.

Pendapat ahli tentang GOST

Tak satu pun dari informasi dan literatur yang tersedia mengenai GOST memberikan alasan untuk percaya bahwa sandi mungkin tidak aman. Sebaliknya, ukuran kunci yang besar dan jumlah putaran yang besar membuat GOST, pada pandangan pertama, cocok untuk penggunaan selama beberapa dekade.

Siapa pun yang akrab dengan Hukum Moore menyadari bahwa, secara teori, kunci 256-bit akan tetap aman setidaknya selama 200 tahun. GOST telah diteliti secara ekstensif oleh para ahli terkemuka di bidang kriptografi, yang dikenal di bidang analisis block cipher, seperti Schneier, Biryukov, Dankelman, Wagner, banyak ilmuwan Australia, Jepang dan Rusia, ahli kriptografi dari ISO, dan semua peneliti telah menyatakan bahwa segala sesuatu terlihat seperti ini bahwa ia dapat atau harus aman. Meskipun pendapat mencapai pemahaman luas bahwa struktur GOST itu sendiri sangat lemah, misalnya, dibandingkan dengan DES, khususnya, difusi tidak begitu baik, namun, ini selalu karena fakta bahwa ini harus dikompensasi oleh sejumlah besar putaran (32), serta nonlinier tambahan dan difusi yang disediakan oleh penambahan modulus.

Biryukov dan Wagner menulis: "Banyaknya putaran (32) dan konstruksi Feistel yang dipelajari dengan baik, dikombinasikan dengan permutasi Shannon yang berurutan, memberikan dasar yang kuat untuk keamanan GOST." Dalam pekerjaan yang sama, kita membaca: "setelah investasi waktu dan usaha yang cukup besar, tidak ada kemajuan yang dibuat dalam analisis sandi standar dalam literatur terbuka." Dengan demikian, tidak ada serangan signifikan yang memungkinkan dekripsi atau pemulihan kunci dalam skenario realistis di mana GOST digunakan dalam enkripsi dengan banyak kunci acak yang berbeda. Sebaliknya, ada banyak pekerjaan yang diketahui tentang serangan terhadap kunci lemah di GOST, serangan dengan kunci terkait, serangan pada pemulihan kotak-S rahasia. Di Crypto-2008, peretasan fungsi hash berdasarkan cipher ini disajikan. Dalam semua serangan, penyerang memiliki tingkat kebebasan yang jauh lebih besar daripada biasanya. Dalam aplikasi enkripsi tradisional menggunakan kunci yang dipilih secara acak, sejauh ini tidak ada serangan kriptografi serius yang ditemukan pada GOST, yang pada tahun 2010 diungkapkan dengan frasa terakhir: "terlepas dari upaya signifikan para kriptanalis selama 20 tahun terakhir, GOST belum retak" (Axel Poschmann , San Ling, dan Huaxiong Wang: 256 Bit Standardized Crypto untuk 650 GE GOST Ditinjau Kembali, Dalam CHES 2010, LNCS 6225, hlm. 219-233, 2010).

Analisis linier dan diferensial GOST

Dalam buku terkenal Schneier, kita membaca: "Melawan kriptanalisis diferensial dan linier, GOST mungkin lebih kuat daripada DES." Penilaian utama keamanan GOST diberikan pada tahun 2000 oleh Gabidulin et al.Hasilnya sangat mengesankan: dengan tingkat keamanan 2 ^ 256 set, lima putaran sudah cukup untuk melindungi GOST dari kriptanalisis linier. Selain itu, bahkan ketika mengganti S-box dengan yang identik dan satu-satunya operasi cipher nonlinier - penambahan mod 2 ^ 32 - cipher masih tahan terhadap kriptanalisis linier setelah 6 putaran dari 32. Kriptanalisis diferensial GOST terlihat relatif lebih mudah dan menarik lebih banyak perhatian. Untuk tingkat keamanan 2 ^ 128, para peneliti (Vitaly V. Shorin, Vadim V. Jelezniakov dan Ernst M. Gabidulin: Linear and Differential Cryptanalysis of Russian GOST, Preprint diserahkan ke Elsevier Preprint, 4 April 2001) mengasumsikan daya tahan yang cukup pada 7 putaran . Menurut mereka, memecahkan GOST dalam lebih dari lima putaran adalah "sangat sulit." Selain itu, dua peneliti Jepang telah menunjukkan bahwa serangan diferensial langsung klasik dengan satu karakteristik diferensial memiliki kemungkinan yang sangat rendah untuk melewati sejumlah besar putaran. Berdasarkan fakta mempelajari karakteristik diferensial iteratif yang cukup "baik" untuk sejumlah putaran (yang dengan sendirinya memiliki probabilitas lulus tidak lebih baik dari 2-11,4 per putaran), nilai himpunan kunci yang sesuai kurang dari setengah . Untuk GOST putaran penuh, serangan seperti itu dengan karakteristik tunggal hanya akan bekerja dengan bagian kunci yang dapat diabaikan dari urutan 2-62 (dan bahkan di bagian kecil ini akan memiliki kemungkinan melewati tidak lebih dari 2-360 ).

Serangan yang lebih canggih melibatkan beberapa perbedaan yang mengikuti pola tertentu, seperti menggunakan S-box terpisah yang memiliki perbedaan nol sementara bit lain memiliki yang bukan nol. Kita berbicara tentang serangan pembeda berdasarkan sifat difusi GOST yang buruk. Yang terbaik dari serangan ini bekerja melawan 17 putaran GOST, tergantung pada kunci dan memiliki diskriminator yang sangat lemah dari data acak pada output itu sendiri, sehingga entah bagaimana dapat digunakan untuk mendapatkan informasi tentang kunci.

Slip dan menangkis serangan

Menurut Biryukov dan Wagner, struktur GOST, yang mencakup urutan terbalik dari subkunci di putaran terakhir, membuatnya tahan terhadap serangan geser (yang disebut "serangan geser"). Namun, karena adanya kesamaan diri yang besar dalam cipher, ini memungkinkan serangan inversi kunci pada kombinasi titik tetap dan properti "refleksi" (disebut "serangan reflektif") untuk kunci lemah tertentu. Kompleksitas serangan ini adalah 2 ^ 192 dan 2 ^ 32 plaintext yang cocok.

Hasil terbaru

Serangan baru juga menggunakan refleksi dan benar-benar merusak GOST, yang dipresentasikan pada konferensi FSE 2011. Serangan ini juga ditemukan secara independen oleh penulis makalah ini. Serangan itu membutuhkan 2 ^ 132 byte memori, yang sebenarnya lebih buruk daripada serangan yang lebih lambat dengan kebutuhan memori yang lebih sedikit.

Banyak serangan kesamaan diri baru bekerja terhadap semua kunci GOST dan memungkinkan Anda untuk memecahkan GOST penuh dengan kunci 256-bit, dan bukan hanya untuk kunci yang lemah, seperti sebelumnya. Semua serangan ini membutuhkan memori yang jauh lebih sedikit dan secara signifikan lebih cepat.

Serangan baru ini dapat dilihat sebagai contoh paradigma umum baru untuk kriptanalisis blok cipher yang disebut "pengurangan kompleksitas aljabar", dengan generalisasi serangan ini ke banyak kasus serangan khusus dengan titik tetap, slide, involusi, dan siklus yang diketahui. Adalah penting bahwa di antara keluarga semua serangan ini ada yang memungkinkan kriptanalisis GOST tanpa refleksi dan tanpa titik simetris yang muncul selama perhitungan. Salah satu contohnya adalah serangan peretasan GOST sederhana tanpa refleksi dalam karya ini.

Kriptanalisis Aljabar dan Serangan Kompleksitas Data Rendah pada Cipher Putaran yang Dikurangi

Serangan aljabar pada block dan stream cipher dapat direpresentasikan sebagai masalah pemecahan sistem besar persamaan aljabar Boolean yang mengikuti geometri dan struktur skema kriptografi tertentu. Idenya kembali ke Shannon. Dalam praktiknya, ini disajikan untuk DES (pertama kali disajikan oleh penulis karya ini) sebagai metode pengkodean formal dan dapat memecahkan 6 putaran hanya dalam satu teks biasa yang diketahui. Manipulasi persamaan didasarkan pada algoritma XL, basis Gröbner, metode ElimLin, pemecah SAT.

Dalam praktiknya, serangan aljabar telah diterapkan terhadap sejumlah kecil cipher blok, tetapi telah menyebabkan retaknya stream cipher, dan ada juga keberhasilan dalam memecahkan cipher ultra-ringan untuk peralatan mikro. Karena kesulitan dalam ukuran memori dan perkiraan biaya komputasi, mereka digabungkan dengan serangan lain.

Bagaimana cara meretas GOST?

Serangan aljabar pada GOST putaran penuh disajikan secara lebih rinci dalam publikasi ini. Dalam karya sebelumnya, penulis telah menguraikan 20 serangan aljabar pada GOST dan mengharapkan sejumlah besar dari mereka dalam waktu dekat. Serangan yang diusulkan dalam pekerjaan ini bukan yang terbaik dari mereka, tetapi membuka jalan yang mudah (setidaknya untuk pemahaman kriptografer) untuk pengembangan selanjutnya untuk membuat metodologi khusus untuk memecahkan GOST.

Hasil praktisnya masih sederhana: 2 ^ 64 plaintext yang diketahui dan memori 2 ^ 64 untuk menyimpan pasangan plaintext / ciphertext memungkinkan untuk memecahkan GOST 2 ^ 8 lebih cepat daripada brute force sederhana. Namun dalam hal kriptanalisis, pernyataan bahwa "GOST telah diretas" sepenuhnya adil.

kesimpulan

GOST dirancang untuk memberikan tingkat keamanan militer selama 200 tahun ke depan. Sebagian besar ahli terkemuka yang telah mempelajari GOST telah sepakat bahwa "terlepas dari upaya cryptanalytic yang signifikan selama 20 tahun, GOST belum dipecahkan." Pada tahun 2010, GOST dipromosikan menjadi ISO 18033 sebagai standar enkripsi global.

Landasan ide tentang kriptanalisis aljabar muncul lebih dari 60 tahun yang lalu. Tetapi hanya dalam 10 tahun terakhir telah dikembangkan perangkat lunak yang efektif untuk solusi (sebagian) dari banyak masalah NP-complete. Sejumlah stream cipher telah dipecahkan. Hanya satu blok cipher yang telah dipecahkan oleh metode ini - KeeLoq yang lemah itu sendiri. Dalam karya ini, penulis memecahkan sandi GOST yang penting dan benar-benar digunakan. Dia mencatat bahwa ini adalah pertama kalinya dalam sejarah bahwa sandi negara standar telah dipecahkan oleh kriptanalisis aljabar.

Serangan "MITM dengan refleksi" sederhana pada GOST telah dipresentasikan pada konferensi FSE 2011. Dalam karya yang dibahas dalam artikel ini, serangan lain disajikan hanya untuk menggambarkan fakta berapa banyak serangan terhadap GOST yang telah muncul sekarang, banyak di antaranya lebih cepat, dan serangan aljabar membutuhkan lebih sedikit memori dan membuka ruang kemungkinan yang hampir tidak ada habisnya bagi musuh untuk menyerang sandi dengan cara yang berbeda. Juga dalam makalah ini, ditunjukkan bahwa tidak perlu menggunakan properti refleksi untuk meretas.

Penulis mengklaim bahwa jelas bahwa GOST memiliki kelemahan serius dan sekarang tidak memberikan tingkat daya tahan yang diperlukan oleh ISO. Banyak serangan terhadap GOST disajikan dalam kerangka konfirmasi paradigma pengurangan kompleksitas aljabar.

Akhirnya, peneliti secara khusus mencatat beberapa fakta yang belum tersedia bagi pembaca, tetapi diketahui oleh peneliti, yang penting dalam proses standarisasi ISO. Serangan ini bukan hanya serangan "sertifikasi" pada GOST, yang lebih cepat daripada serangan brute force brute force. Faktanya, standarisasi GOST sekarang akan sangat berbahaya dan tidak bertanggung jawab. Hal ini karena beberapa serangan yang layak dalam praktek. Dalam praktiknya, beberapa kunci GOST bahkan dapat didekripsi, apakah itu kunci lemah atau kunci dari aplikasi nyata pribadi GOST. Dalam karya sebelumnya, penulis memberikan pertimbangan rinci tentang kasus-kasus kemungkinan serangan praktis. Secara signifikan, "ini adalah pertama kalinya dalam sejarah bahwa sandi blok standar serius yang dirancang untuk melindungi rahasia tingkat militer dan dirancang untuk melindungi rahasia negara bagi pemerintah, bank besar, dan organisasi lain telah dikompromikan oleh serangan matematis."