• tutorial

Halo %nama pengguna%!
Banyak orang mengetahui standar bawaan di lapangan enkripsi simetris untuk waktu yang lama dipertimbangkan Algoritma DES. Serangan pertama yang berhasil terhadap algoritma yang tidak dapat dibunuh ini diterbitkan pada tahun 1993, 16 tahun setelah diadopsi sebagai standar. Metode yang penulis sebut kriptanalisis linier, dengan adanya 2 47 pasang teks biasa/tersandi, memungkinkan terjadinya crack kunci rahasia Sandi DES dalam 2 43 operasi.
Di bawah ini saya akan mencoba menguraikan secara singkat poin-poin utama serangan ini.

Kriptanalisis linier

Secara umum, serangan berdasarkan kriptanalisis linier bermuara pada kondisi berikut. Penyerang telah melakukannya sejumlah besar pasangan plaintext/ciphertext diperoleh dengan menggunakan kunci enkripsi K yang sama. Tujuan penyerang adalah memulihkan sebagian atau seluruh kunci K.

Pertama-tama, penyerang memeriksa sandi dan menemukan apa yang disebut analog statistik, yaitu persamaan tipe berikut, yang dijalankan dengan probabilitas P ≠ 1/2 untuk pasangan teks publik/pribadi sembarang dan kunci tetap:
P I1 ⊕ P I2 ⊕… ⊕ P Ia ⊕ C I1 ⊕ C I2 ⊕… ⊕ C Ib = K I1 ⊕ K I2 ⊕… ⊕ K Ic (1) ,
dimana P n, C n, K n adalah bit ke-n dari teks, ciphertext dan kunci.
Setelah persamaan tersebut ditemukan, penyerang dapat memulihkan 1 bit informasi penting menggunakan algoritma berikut

Algoritma 1
Misalkan T adalah jumlah teks yang mana sisi kiri persamaan (1) sama dengan 0, maka
Jika T>N/2, dimana N adalah jumlah plaintext yang diketahui.
Asumsikan K I1 ⊕ K I2 ⊕… ⊕ K Ic = 0 (bila P>1/2) atau 1 (bila P<1/2).
Jika tidak
Asumsikan K I1 ⊕ K I2 ⊕… ⊕ K Ic = 1 (bila P>1/2) atau 0 (bila P<1/2).
Jelas bahwa keberhasilan algoritma secara langsung bergantung pada nilai |P-1/2| dan pada jumlah pasangan teks terbuka/tertutup yang tersedia N. Semakin besar probabilitas P persamaan (1) berbeda dari 1/2, semakin sedikit jumlah teks jelas N yang dibutuhkan untuk menyerang.

Ada dua masalah yang perlu diselesaikan agar serangan berhasil:

• Cara mencari persamaan efektif yang berbentuk (1).
• Cara menggunakan persamaan ini untuk mendapatkan lebih dari satu bit informasi tentang kunci.

Deskripsi DES

Jadi, DES adalah block cipher yang berbasis pada jaringan Feistel. Cipher mempunyai ukuran blok 64 bit dan ukuran kunci 56 bit. Mari kita pertimbangkan skema enkripsi algoritma DES.

Seperti dapat dilihat dari gambar, saat mengenkripsi teks, operasi berikut dilakukan:

1. Permutasi bit awal. Pada tahap ini, bit-bit blok masukan dikocok dalam urutan tertentu.
2. Setelah ini, bit campuran dipecah menjadi dua bagian, yang diumpankan ke input fungsi Feistel. Untuk DES standar, jaringan Feistel mencakup 16 putaran, tetapi ada varian algoritma lain.
3. Dua blok yang diperoleh pada putaran transformasi terakhir digabungkan dan permutasi lain dilakukan pada blok yang dihasilkan.

Di setiap putaran jaringan Feistel, 32 bit pesan yang paling tidak signifikan dilewatkan melalui fungsi f:

Mari kita lihat operasi yang dilakukan pada tahap ini:

1. Blok masukan dilewatkan melalui fungsi ekstensi E, yang mengubah blok 32-bit menjadi blok 48-bit.
2. Blok yang dihasilkan ditambahkan ke kunci bulat K i .
3. Hasil dari langkah sebelumnya dibagi menjadi 8 blok yang masing-masing terdiri dari 6 bit.
4. Masing-masing blok B i yang diterima dilewatkan melalui fungsi substitusi S-Box i , yang menggantikan urutan 6-bit dengan blok 4-bit.
5. Blok 32-bit yang dihasilkan dilewatkan melalui permutasi P dan dikembalikan sebagai hasil fungsi f.

Yang paling menarik bagi kami, dari sudut pandang kriptanalisis sandi, adalah blok S, yang dirancang untuk menyembunyikan hubungan antara data input dan output dari fungsi f. Agar berhasil menyerang DES, pertama-tama kita akan membuat analog statistik untuk masing-masing S-box, dan kemudian memperluasnya ke seluruh cipher.

Analisis blok S

Mari kita pertimbangkan bagaimana kita dapat menemukan analog statistik dari S-box dalam kasus umum.

Untuk S-box S a , 1 ≤ α ≤ 63 dan 1 ≤ β ≤ 15, nilai NS a (α, β) menjelaskan berapa kali dari 64 kemungkinan bit input XOR S a yang ditumpangkan pada bit α sama dengan bit keluaran XOR ditumpangkan pada bit α β, yaitu:
dimana simbolnya logis DAN.
Nilai α dan β yang NS a (α, β) paling berbeda dari 32 menggambarkan analog statistik paling efisien dari S-box S a .

Analog yang paling efektif ditemukan pada S-box ke-5 dari cipher DES untuk α = 16 dan β = 15 NS 5 (16, 15) = 12. Artinya persamaan berikut berlaku: Z=Y ⊕ Y ⊕ Y ⊕ Y, dimana Z adalah rangkaian masukan dari S-box dan Y adalah rangkaian keluaran.
Atau mengingat pada algoritma DES, sebelum masuk ke S-box, data ditambahkan modulo 2 dengan kunci bulat, yaitu. Z = X ⊕ K kita dapatkan
X ⊕ Y ⊕ Y ⊕ Y ⊕ Y = K, dimana X dan Y adalah data masukan dan keluaran fungsi f tanpa memperhitungkan permutasi.
Persamaan yang dihasilkan dieksekusi pada semua putaran algoritma DES dengan probabilitas yang sama P=12/64.
Tabel berikut menunjukkan daftar yang efektif, yaitu. memiliki deviasi terbesar dari P=1/2, analog statistik untuk setiap blok s dari algoritma DES.

Membangun analog statistik untuk beberapa putaran DES

Mari kita temukan ekspresi serupa menggunakan putaran terakhir. Kali ini kita punya persamaannya
X(3) ⊕ K3 = Y(3) ⊕ Y(3) ⊕ Y(3) ⊕ Y(3).
Karena
X(2) ⊕ X(2) ⊕ X(2) ⊕ X(2) = CL ⊕ CL ⊕ CL ⊕ CL ⊕ Y(3) ⊕ Y(3) ⊕ Y(3) ⊕ Y(3)
kita mengerti itu
X(2) ⊕ X(2) ⊕ X(2) ⊕ X(2) = CL ⊕ CL ⊕ CL ⊕ CL ⊕ X(3) ⊕ K3(4) dengan probabilitas 12/64.

Menyamakan ruas kanan persamaan (3) dan (4) kita peroleh
CL ⊕ CL ⊕ CL ⊕ CL ⊕ X(3) ⊕ K3 = PL ⊕ PL ⊕ PL ⊕ PL ⊕ X(1) ⊕ K1 dengan probabilitas (12/64) 2 +(1-12/64) 2.
Dengan mempertimbangkan fakta bahwa X(1) = PR dan X(3) = CR kita memperoleh analog statistik
CL ⊕ CR ⊕ PL ⊕ PR = K1 ⊕ K3 (5) ,
yang dieksekusi dengan probabilitas (12/64) 2 + (1-12/64) 2 =0.7.
Analog statistik yang dijelaskan di atas dapat direpresentasikan secara grafis sebagai berikut (bit pada gambar diberi nomor dari kanan ke kiri dan dimulai dari nol):

Semua bit di sisi kiri persamaan diketahui oleh penyerang, sehingga ia dapat menerapkan Algoritma 1 dan mengetahui nilai K1 ⊕ K3. Mari kita tunjukkan bagaimana dengan menggunakan analog statistik ini Anda tidak dapat membuka 1, tetapi 12 bit kunci enkripsi K.

Serangan Plaintext yang Diketahui pada DES

Di atas sudah kita tentukan bahwa nilai F1(PR,K1) dipengaruhi oleh bit-bit masukan S-box ke-5 yaitu bit kunci K1 dan bit-bit blok PR. Mari kita tunjukkan bagaimana, dengan hanya memiliki satu set teks terbuka/tertutup, Anda dapat mengembalikan nilai K1. Untuk melakukan ini, kita akan menggunakan Algoritma 2.

Algoritma 2
Misalkan N adalah jumlah pasangan teks terbuka/tertutup yang diketahui sebelum serangan. Kemudian untuk membuka kunci Anda perlu melakukan langkah-langkah berikut.
Untuk (saya=0; saya<64; i++) do
{
Untuk(j=0; j {
jika(СL j ⊕ CR j ⊕ PL j ⊕ F1(PR j , i)=0) maka
T saya =T saya +1
}
}
Sebagai barisan probabilitas K1, diambil nilai i sedemikian sehingga ekspresi |T i -N/2| mempunyai nilai maksimum.

Mengingat jumlah teks biasa yang diketahui mencukupi, algoritme akan memiliki probabilitas tinggi untuk mengembalikan nilai yang benar dari enam bit subkunci putaran pertama K1. Hal ini dijelaskan oleh fakta bahwa jika variabel i tidak sama dengan K1, maka nilai fungsi F1(PR j, K) akan acak dan banyaknya persamaan untuk nilai i yang ruas kirinya adalah sama dengan nol akan cenderung N/2. Jika subkunci ditebak dengan benar, ruas kiri akan sama dengan bit tetap K3 dengan probabilitas 12/64. Itu. akan ada penyimpangan yang signifikan dari N/2.

Setelah menerima 6 bit subkunci K1, Anda juga dapat membuka 6 bit subkunci K3. Yang perlu Anda lakukan hanyalah mengganti C dengan P dan K1 dengan K3 pada persamaan (6):
PL ⊕ PR ⊕ CL ⊕ F3(CR, K3) = K1.
Algoritma 2 akan mengembalikan nilai K3 yang benar karena proses dekripsi pada algoritma DES sama dengan proses enkripsi, hanya saja urutan kuncinya dibalik. Jadi pada dekripsi putaran pertama digunakan kunci K3, dan pada putaran terakhir digunakan kunci K1.

Setelah menerima 6 bit subkunci K1 dan K3, penyerang memulihkan 12 bit kunci umum dari cipher K, karena kunci bulat adalah permutasi biasa dari kunci K. Jumlah teks biasa yang diperlukan agar serangan berhasil bergantung pada probabilitas analog statistik. Untuk memecahkan kunci DES 3 putaran 12-bit, 100 pasangan teks publik/pribadi sudah cukup. Untuk memecahkan 12 bit kunci DES 16 putaran, diperlukan sekitar 2 44 pasang teks. 44 bit kunci yang tersisa dibuka menggunakan kekerasan normal.

Modifikasi proyek yang diusulkan IBM, yang disebut Lucifer, diadopsi sebagai DES. DES diterbitkan dalam bentuk draft di Daftar Federal pada bulan Maret 1975 sebagai Standar Pemrosesan Informasi Federal (FIPS – Standar Pemrosesan Informasi Federal).

Setelah dipublikasikan, sketsa itu mendapat kritik keras karena dua alasan. Pertama, ada kritik terhadap panjang kunci yang terlalu kecil (hanya 56 bit), yang dapat membuat sandi rentan terhadap serangan brute force.

Mereka menduga bahwa beberapa bagian dari struktur (S-box) mungkin memiliki pintu belakang tersembunyi yang memungkinkan pesan didekripsi tanpa kunci. Perancang IBM kemudian melaporkan bahwa struktur internal telah dimodifikasi untuk mencegah pembacaan sandi.

DES akhirnya diterbitkan sebagai FIPS 46 di Federal Register pada Januari 1977. Namun FIPS telah menyatakan DES sebagai standar untuk digunakan dalam aplikasi tidak resmi. DES adalah cipher blok yang paling banyak digunakan kunci simetris, mulai dari penerbitannya. NIST kemudian mengusulkan standar baru (FIPS 46-3) yang merekomendasikan penggunaan triple DES (triple DES cipher) untuk aplikasi masa depan. Seperti yang akan kita lihat nanti di kuliah 9-10, standar AES yang lebih baru diharapkan menggantikan DES.

Ketentuan umum

Seperti yang ditunjukkan pada Gambar. 8.1. DES - sandi blok.

Beras. 8.1.

Di sisi enkripsi, DES mengambil teks biasa 64-bit dan menghasilkan teks tersandi 64-bit; Di sisi dekripsi, DES mengambil ciphertext 64-bit dan menghasilkan plaintext 64-bit. Kedua belah pihak menggunakan kunci 56-bit yang sama untuk enkripsi dan dekripsi.

8.2. struktur DES

Mari kita lihat enkripsi terlebih dahulu dan kemudian dekripsi. Proses enkripsi terdiri dari dua permutasi (blok P) – disebut permutasi awal dan akhir – dan enam belas putaran Feistel. Setiap putaran menggunakan kunci 48-bit berbeda yang dihasilkan. Algoritma pembangkitan akan dibahas nanti dalam kuliah ini. Gambar 8.2 menunjukkan elemen cipher DES pada sisi enkripsi.

Permutasi awal dan akhir

Gambar 8.3 menunjukkan permutasi awal dan akhir (blok P). Masing-masing permutasi mengambil input 64-bit dan menyusun ulang elemen-elemennya sesuai aturan yang diberikan. Kami hanya menunjukkan sejumlah kecil port masukan dan port keluaran yang sesuai. Permutasi ini merupakan permutasi langsung tanpa kunci yang merupakan invers satu sama lain. Misalnya, pada permutasi awal, bit masukan ke-58 masuk ke bit pertama keluaran. Demikian pula, pada permutasi akhir, bit masukan pertama menuju bit keluaran ke-58. Dengan kata lain, jika tidak ada putaran di antara kedua permutasi ini, bit ke-58 yang disuplai ke masukan perangkat permutasi awal akan dikirimkan ke keluaran ke-58 melalui permutasi akhir.

Aturan permutasi untuk P-box ini ditunjukkan pada Tabel 8.1. Tabel dapat direpresentasikan sebagai array 64 elemen. Perhatikan bahwa kita telah membahas bekerja dengan tabel; nilai setiap elemen menentukan nomor port masukan, dan nomor seri (indeks) elemen menentukan nomor port keluaran.

Permutasi terbatas

Kedua permutasi ini tidak memiliki arti bagi kriptografi

Standar DES dirancang untuk melindungi terhadap akses tidak sah terhadap informasi sensitif namun tidak rahasia di pemerintahan AS dan organisasi komersial. Algoritme yang mendasari standar ini menyebar cukup cepat, dan sudah pada tahun 1980 disetujui oleh Institut Standar dan Teknologi Nasional AS. Mulai saat ini, DES menjadi standar tidak hanya dalam nama, tetapi juga faktanya. Perangkat lunak dan mikrokomputer khusus muncul yang dirancang untuk mengenkripsi dan mendekripsi informasi dalam jaringan transmisi data.

Saat ini, DES adalah algoritma yang paling umum digunakan dalam sistem keamanan informasi komersial. Selain itu, penerapan algoritma DES pada sistem seperti itu menjadi pertanda baik.

Keuntungan utama dari algoritma DES:

· hanya satu kunci dengan panjang 56 bit yang digunakan;

· setelah mengenkripsi pesan menggunakan satu paket, Anda dapat menggunakan paket lain untuk mendekripsinya;

· kesederhanaan relatif dari algoritma memastikan kecepatan pemrosesan informasi yang tinggi;

· stabilitas algoritma yang cukup tinggi.

DES mengenkripsi blok data 64-bit menggunakan kunci 56-bit. Dekripsi dalam DES adalah operasi kebalikan dari enkripsi dan dilakukan dengan mengulangi operasi enkripsi dalam urutan terbalik (meskipun terlihat jelas, hal ini tidak selalu dilakukan. Nanti kita akan melihat sandi di mana enkripsi dan dekripsi dilakukan menggunakan algoritma yang berbeda) .

Proses enkripsi terdiri dari permutasi bit awal dari blok 64-bit, enam belas siklus enkripsi, dan terakhir permutasi bit terbalik (Gambar 1).

Perlu segera dicatat bahwa SEMUA tabel yang diberikan dalam artikel ini adalah STANDAR, dan oleh karena itu harus disertakan dalam implementasi algoritme Anda tanpa perubahan. Semua permutasi dan kode dalam tabel dipilih oleh pengembang sedemikian rupa untuk membuat proses dekripsi sesulit mungkin dengan memilih kunci. Struktur algoritma DES ditunjukkan pada Gambar. 2.

Biarkan blok T 8-byte berikutnya dibaca dari file, yang ditransformasikan menggunakan IP matriks permutasi awal (Tabel 1) sebagai berikut: bit 58 dari blok T menjadi bit 1, bit 50 menjadi bit 2, dst., yang akan hasilnya : T(0) = IP(T).

Urutan bit yang dihasilkan T(0) dibagi menjadi dua urutan yang masing-masing terdiri dari 32 bit: L(0) - bit tingkat kiri atau tinggi, R(0) - bit tingkat kanan atau rendah.

Tabel 1: Matriks Permutasi Awal IP

58 50 42 34 26 18 10 02

60 52 44 36 28 20 12 04

62 54 46 38 30 22 14 06

64 56 48 40 32 24 16 08

57 49 41 33 25 17 09 01

59 51 43 35 27 19 11 03

61 53 45 37 29 21 13 05

63 55 47 39 31 23 15 07

Kemudian dilakukan enkripsi yang terdiri dari 16 iterasi. Hasil iterasi ke-i digambarkan dengan rumus sebagai berikut:

R(i) = L (i-1) xor f (R(i-1), K(i)),

di mana xor adalah operasi EKSKLUSIF ATAU.

Fungsi f disebut fungsi enkripsi. Argumennya adalah urutan 32-bit R(i-1), yang diperoleh pada iterasi ke-(i-1), dan kunci 48-bit K(i), yang merupakan hasil konversi kunci 64-bit K. Secara rinci fungsi enkripsi dan algoritma untuk memperoleh kunci K(i) dijelaskan di bawah ini.

Pada iterasi ke-16 diperoleh sequence R(16) dan L(16) (tanpa permutasi), yang digabungkan menjadi sequence 64-bit R(16) L(16).

Kemudian posisi bit urutan ini disusun ulang sesuai dengan matriks IP -1 (Tabel 2).

Tabel 2: Matriks permutasi terbalik IP -1

40 08 48 16 56 24 64 32

39 07 47 15 55 23 63 31

38 06 46 14 54 22 62 30

37 05 45 13 53 21 61 29

36 04 44 12 52 20 60 28

35 03 43 11 51 19 59 27

34 02 42 10 50 18 58 26

33 01 41 09 49 17 57 25

Hubungan matriks IP -1 dan IP adalah sebagai berikut: nilai elemen ke-1 matriks IP -1 adalah 40, dan nilai elemen ke-40 matriks IP adalah 1, nilai elemen ke-2 elemen matriks IP -1 adalah 8, dan nilai elemen matriks IP ke-8 sama dengan 2, dst.

Proses dekripsi data merupakan kebalikan dari proses enkripsi. Semua langkah harus dilakukan dalam urutan terbalik. Artinya, data yang didekripsi terlebih dahulu disusun ulang sesuai dengan matriks IP-1, kemudian tindakan yang sama dilakukan pada urutan bit R(16) L(16) seperti pada proses enkripsi, tetapi dalam urutan terbalik.

Proses dekripsi berulang dapat dijelaskan dengan rumus berikut:

R (i-1) = L(i), i = 1, 2,…, 16;

L (i-1) = R(i) xor f (L(i), K(i)), i = 1, 2,…, 16.

Pada iterasi ke-16 diperoleh sequence L(0) dan R(0) yang digabungkan menjadi sequence 64-bit L(0) R(0).

Posisi bit dari urutan ini kemudian disusun ulang sesuai dengan matriks IP. Hasil permutasi tersebut adalah urutan 64-bit asli.

Sekarang perhatikan fungsi enkripsi f (R(i-1), K(i)). Hal ini ditunjukkan secara skematis pada Gambar. 3.

Beras. 3.

Untuk menghitung nilai fungsi f digunakan fungsi matriks sebagai berikut:

E - perpanjangan urutan 32-bit ke 48-bit,

S1, S2,…, S8 - konversi blok 6-bit menjadi blok 4-bit,

P - permutasi bit dalam urutan 32-bit.

Fungsi ekspansi E ditentukan oleh tabel. 3. Berdasarkan tabel ini, 3 bit pertama E (R(i-1)) adalah bit 32, 1 dan 2, dan yang terakhir adalah 31, 32 dan 1.

Tabel 3: Fungsi ekstensi E

32 01 02 03 04 05

04 05 06 07 08 09

08 09 10 11 12 13

12 13 14 15 16 17

16 17 18 19 20 21

20 21 22 23 24 25

24 25 26 27 28 29

28 29 30 31 32 01

Hasil dari fungsi E (R(i-1)) adalah barisan 48-bit yang ditambahkan modulo 2 (operasi xor) dengan kunci 48-bit K(i). Urutan 48-bit yang dihasilkan dibagi menjadi delapan blok 6-bit B(1) B(2) B(3) B(4) B(5) B(6) B(7) B(8). Yaitu:

E (R(i-1)) xor K(i) = B(1) B(2)… B(8).

Fungsi S1, S2,…, S8 didefinisikan dalam tabel. 4.

Tabel 4

Ke meja 4. Klarifikasi tambahan diperlukan. Misalkan input fungsi matriks Sj berupa blok 6-bit B(j) = b1b2b3b4b5b6, maka dua bit bilangan b1b6 menunjukkan nomor baris matriks, dan b2b3b4b5 nomor kolom. Hasil dari Sj (B(j)) akan berupa elemen 4-bit yang terletak pada perpotongan baris dan kolom yang ditentukan.

Misalnya, B(1)=011011. Maka S1 (B(1)) terletak pada perpotongan baris 1 dan kolom 13. Pada kolom 13 baris 1 nilainya 5. Artinya S1 (011011)=0101.

Menerapkan operasi pemilihan ke masing-masing blok 6-bit B(1), B(2),…, B(8), kita memperoleh urutan 32-bit S1 (B(1)) S2 (B(2)) S3 (B( 3))... S8 (B(8)).

Terakhir, untuk mendapatkan hasil fungsi enkripsi, bit-bit rangkaian ini harus disusun ulang. Untuk tujuan ini, digunakan fungsi permutasi P (Tabel 5). Pada urutan masukan, bit-bit tersebut disusun ulang sehingga bit 16 menjadi bit 1, bit 7 menjadi bit 2, dan seterusnya.

Tabel 5: Fungsi permutasi P

Dengan demikian,

f (R(i-1), K(i)) = P (S1 (B(1)),… S8 (B(8)))

Untuk melengkapi uraian algoritma enkripsi data, tetap disajikan algoritma untuk memperoleh kunci 48-bit K(i), i=1...16. Pada setiap iterasi digunakan nilai kunci baru K(i) yang dihitung dari kunci awal K. K merupakan blok 64-bit dengan delapan bit paritas yang terletak pada posisi 8,16,24,32,40,48, 56.64.

Untuk menghapus bit kontrol dan mengatur ulang sisanya, fungsi G dari persiapan kunci awal digunakan (Tabel 6).

Tabel 6

Matriks G persiapan kunci awal

57 49 41 33 25 17 09

01 58 50 42 34 26 18

10 02 59 51 43 35 27

19 11 03 60 52 44 36

63 55 47 39 31 23 15

07 62 54 46 38 30 22

14 06 61 53 45 37 29

21 13 05 28 20 12 04

Hasil transformasi G(K) dibagi menjadi dua blok 28-bit C(0) dan D(0), dan C(0) akan terdiri dari bit 57, 49, ..., 44, 36 kunci K, dan D(0) akan terdiri dari bit 63, 55,…, 12, 4 kunci K. Setelah menentukan C(0) dan D(0), C(i) dan D(i), i=1… 16, ditentukan secara rekursif. Untuk melakukan ini, terapkan pergeseran siklik ke kiri sebanyak satu atau dua bit, bergantung pada nomor iterasi, seperti yang ditunjukkan pada tabel. 7.

Tabel 7. Tabel shift untuk penghitungan kunci

Nilai yang dihasilkan kembali “dicampur” sesuai dengan matriks H (Tabel 8).

Tabel 8: Matriks Penyelesaian Kunci H

14 17 11 24 01 05

03 28 15 06 21 10

23 19 12 04 26 08

16 07 27 20 13 02

41 52 31 37 47 55

30 40 51 45 33 48

44 49 39 56 34 53

46 42 50 36 29 32

Kunci K(i) akan terdiri dari bit 14, 17,…, 29, 32 dari urutan C(i) D(i). Dengan demikian:

K(saya) = H (C(saya) D(saya))

Diagram blok algoritma perhitungan kunci ditunjukkan pada Gambar. 4.

Beras. 4.

Pemulihan teks asli dilakukan menggunakan algoritma ini, tetapi pertama-tama Anda menggunakan kunci K(15), lalu K(14) dan seterusnya. Sekarang Anda harus memahami mengapa penulis sangat merekomendasikan penggunaan matriks yang diberikan. Jika Anda nakal, Anda mungkin akan mendapatkan kode yang sangat rahasia, tetapi Anda tidak akan bisa memecahkannya sendiri!

Konversi mudah antar bagian blok. Karena konversi dilakukan blok demi blok, langkah terpisah memerlukan pembagian data sumber menjadi blok-blok dengan ukuran yang diperlukan. Selain itu, apapun format data sumbernya, baik itu dokumen teks, gambar, atau file lainnya, mereka harus diinterpretasikan ke dalam bentuk biner dan baru kemudian dibagi menjadi blok-blok. Semua hal di atas dapat dilakukan dengan perangkat lunak atau perangkat keras.

Transformasi oleh Feistel Network

Ini adalah transformasi vektor (blok) yang mewakili bagian kiri dan kanan register geser. Algoritma DES menggunakan transformasi jaringan Feistel maju dalam enkripsi (lihat Gambar 1) dan transformasi jaringan Feistel terbalik dalam dekripsi (lihat Gambar 2).

Skema enkripsi algoritma DES

Teks sumber adalah blok 64-bit.
Teks sandi adalah blok 64-bit.

Proses enkripsi terdiri dari permutasi awal, 16 siklus enkripsi, dan permutasi akhir.
Mari kita lihat diagram detail algoritma DES:
L i R i =1,2\ldots.bagian kiri dan kanan blok 64-bit L i R i
k i - kunci 48 bit
f - fungsi enkripsi
IP - permutasi awal
IP -1 - permutasi akhir. Berdasarkan tabel, 3 bit pertama dari blok IP(T) yang dihasilkan setelah permutasi awal IP adalah bit 58, 50, 42 dari blok masukan T, dan 3 bit terakhirnya adalah bit 23, 15, 7 dari blok masukan T. blok masukan. Selanjutnya, blok IP(T) 64-bit berpartisipasi dalam 16 siklus transformasi Feistel.

16 siklus transformasi Feistel:

Pisahkan IP(T) menjadi dua bagian L 0 ,R 0 , dengan L 0 ,R 0 masing-masing adalah 32 bit paling signifikan dan 32 bit paling tidak signifikan dari blok T0 IP(T)= L 0 R 0 .

Misalkan T i -1 = L i -1 R i -1 hasil iterasi (i-1), maka hasil iterasi ke i T i = L i R i ditentukan:

L saya = R saya - 1 Separuh kiri L i sama dengan separuh kanan vektor sebelumnya L i - 1 R i - 1 . Dan separuh kanan R i merupakan penambahan bit dari L i - 1 dan f(R i - 1, k i) modulo 2.

Dalam transformasi Feistel 16 siklus, fungsi f berperan sebagai enkripsi. Mari kita lihat fungsi f secara detail.

Argumen untuk fungsi f adalah vektor 32-bit R i - 1 , kunci 48-bit k i , yang merupakan hasil konversi kunci sandi asli 56-bit k.

Untuk menghitung fungsi f digunakan fungsi muai E, transformasi S yang terdiri dari 8 transformasi kotak S, dan permutasi P.

Fungsi E memperluas vektor 32-bit R i - 1 ke vektor 48-bit E(R i - 1) dengan menduplikasi beberapa bit dari R i - 1, sedangkan urutan bit-bit dari vektor E(R i - 1 ) ditunjukkan pada Tabel 2. Tiga bit pertama dari vektor E(R i - 1) adalah bit 32, 1, 2 dari vektor R i -1. Tabel 2 menunjukkan bahwa bit 1, 4, 5, 8, 9, 12, 13, 16, 17, 20, 21, 24, 25, 28, 29, 32 diduplikasi. 3 bit terakhir dari vektor E(Ri - 1) adalah bit 31, 32, 1 dari vektor Ri - 1. Blok E(R i -1) yang diperoleh setelah penataan ulang ditambahkan modulo 2 dengan kunci k i dan kemudian disajikan dalam bentuk delapan blok berturut-turut B 1 , B 2 ,...B 8 .
E(R saya - 1) = B 1 B 2 ...B 8
Setiap Bj adalah blok 6-bit. Selanjutnya masing-masing blok B j ditransformasikan menjadi blok 4-bit B" j menggunakan transformasi S j. Transformasi S j ditentukan oleh Tabel 3. Misalkan B 3 = 101111 dan kita ingin mencari B" 3. Bit pertama dan terakhir dari B 3 merupakan representasi biner dari bilangan a, 0. Nilai fungsi f(R i - 1,k i) (32 bit) diperoleh dengan permutasi P yang diterapkan pada blok 32-bit B " 1 B" 2 ...B" 8. Permutasi P diberikan oleh Tabel 4.
f(R saya - 1 ,k saya) = P(B" 1 B" 2 ...B" 8)
Menurut Tabel 4, empat bit pertama dari vektor yang dihasilkan setelah aksi fungsi f adalah bit 16, 7, 20, 21 dari vektor B" 1 B" 2 ...B" 8

Menghasilkan kunci k i .
Kunci k i diperoleh dari kunci awal k (56 bit = 7 byte atau 7 karakter ASCII) dengan cara ini. Delapan bit, terletak pada posisi 8, 16, 24, 32, 40, 48, 56, 64, ditambahkan ke kunci k sehingga setiap byte berisi bilangan ganjil. Ini digunakan untuk mendeteksi kesalahan dalam pertukaran kunci dan penyimpanan. Kemudian dilakukan permutasi untuk kunci yang diperluas (kecuali untuk bit tambahan 8, 16, 24, 32, 40, 48, 56, 64). Permutasi ini didefinisikan seperti pada Tabel 5.

Permutasi ini ditentukan oleh dua blok C 0 dan D 0 masing-masing 28 bit. 3 bit pertama C0 adalah bit 57, 49, 41 dari kunci yang diperluas. Dan tiga bit pertama D 0 adalah bit 63, 55, 47 dari kunci yang diperluas. C i ,D i i=1,2,3…diperoleh dari C i - 1 ,D i - 1 dengan satu atau dua pergeseran siklik ke kiri sesuai Tabel 6.

Kunci k i , i=1,…16 terdiri dari 48 bit yang dipilih dari bit-bit vektor C i D i (56 bit) sesuai Tabel 7. Bit pertama dan kedua k i adalah bit 14, 17 dari vektor C i D saya

Permutasi terakhir IP - 1 bekerja pada T 16 dan digunakan untuk mengembalikan posisi. Ini adalah kebalikan dari permutasi IP. Permutasi akhir ditentukan oleh Tabel 8.
Mode penggunaan DES DES dapat digunakan dalam empat mode.

Mode Buku Kode Elektronik (ECB): penggunaan DES yang biasa sebagai cipher blok (lihat Gambar 7).

Mode rantai blok (CBC - Cipher Block Chaining) (lihat Gambar 8). Setiap blok berikutnya C i i>=1, sebelum enkripsi, ditambahkan modulo 2 dengan blok teks biasa berikutnya M i + 1. Vektor C 0 merupakan vektor awal, berubah setiap hari dan dirahasiakan.

Mode Umpan Balik Sandi (CFB - Umpan Balik Sandi) (lihat Gambar 9). Dalam mode CFB, blok “gamma” dihasilkan Z 0 ,Z 1 ,...Z i = DEsk(C i - 1) . Vektor awal C 0 dirahasiakan.

Mode umpan balik keluaran (OFB - Umpan Balik Keluaran) (lihat Gambar 10). Dalam mode OFB, blok “gamma” Z 0 ,Z 1 ,... , i>=1 dihasilkan

Standar Enkripsi Data (DES) adalah standar enkripsi data yang ditemukan di Amerika Serikat pada tahun 1980an. Di antara para sandi, ia dianggap sebagai "pensiun", namun tetap menjadi pekerja keras kriptografi. DES tidak lagi cocok di lingkungan dengan teknologi ultra-cepat dan volume data besar karena keterbatasan 56 bit per kunci dan 64 bit per data. Namun, masih digunakan.

Apa itu cipher blok?

DES adalah algoritma enkripsi blok. Banyak cipher blok telah dibuat selama 20-30 tahun terakhir, namun menciptakan cipher yang baik dan aman adalah tugas yang sulit. Sandi harus memiliki karakteristik yang memungkinkannya berfungsi di banyak bidang dan industri.

Block cipher terdiri dari beberapa iterasi penggunaan cipher secara bergantian. Setiap iterasi disebut putaran. Seperti yang ditunjukkan oleh praktik, bahkan beberapa algoritme primitif, bila digunakan secara konsisten, mampu menghasilkan sandi yang andal. Algoritma DES adalah contoh yang tetap dapat diandalkan dan tidak dapat dipecahkan selama 20 tahun.

Pendekatan pengembangan sandi ini sangat menyederhanakan proses dan menyederhanakan analisis keamanan. Misalnya, serangan uji coba pada cipher blok dimulai dengan jumlah putaran minimum dan secara metodis dilanjutkan dengan peningkatan jumlah putaran.

Menggunakan DES

Meskipun DES dianggap ketinggalan jaman dan tidak memenuhi persyaratan modern, namun dapat digunakan, misalnya dalam bentuk 3DES, bila sandi digunakan tiga kali berturut-turut. Pendekatan ini menghilangkan batasan ukuran kunci, namun blok data terenkripsi tetap sama. Pada suatu waktu, DES merupakan sandi yang cukup cepat dan aman. Sekarang tidak demikian, dan 3DES bekerja tiga kali lebih lambat. Meskipun demikian, DES masih digunakan di sejumlah sistem, namun penggunaannya dalam proyek baru dilarang.

Secara resmi, algoritma cipher DES menjadi standar di Amerika Serikat hingga tahun 1998. Pada tahun 1997, pembuatan standar baru dimulai, yang disebut Sistem), dan meskipun kriptanalisis menunjukkan bahwa upaya untuk memecahkan DES mengarah ke banyak sistem persamaan nonlinier, metode analisis tidak dapat membantu memecahkan masalah - titik lemahnya adalah sekumpulan kecil kunci yang mungkin. Jumlahnya 2 56 dan semua pilihan dapat diselesaikan dengan menggunakan teknologi modern dalam waktu yang relatif singkat.

Satu putaran dalam algoritma

Untuk kejelasan penyajian dan deskripsi algoritma DES, kami menggunakan Gambar 4.1 yang menunjukkan struktur satu putaran.

Setiap persegi panjang dalam diagram garis mewakili beberapa jenis perhitungan, dan panah yang berasal darinya menunjukkan ke mana hasil blok akan ditransfer. Tanda plus yang dilingkari menunjukkan operasi "eksklusif atau", yang disebut XOR dalam pemrograman. Operasi ini juga disebut “penambahan bitwise” atau “penambahan tanpa carry”. Anda dapat menemukan algoritma DES di C online dan mempelajarinya untuk pemahaman yang lebih baik.

DES menerima blok teks berukuran 64 bit. Ia melewati permutasi awal menurut prinsip tertentu. Saat menganalisis algoritma, ternyata permutasi ini tidak masuk akal, karena tidak memberikan efek kriptografi apa pun. Blok teks dibagi menjadi 2 bagian yang sama: kanan (R) dan kiri (L). Bagian yang dienkripsi kemudian ditukar dan digabungkan, dan di akhir putaran, blok data 64-bit diperoleh, hanya dienkripsi.

Algoritma umum

Algoritma DES mencakup 16 putaran, dilakukan sesuai dengan skema yang dijelaskan di atas. Semua putaran diberi nomor melalui i, dimana i = (1; 16). Setiap putaran ke-i dari pasangan (Li-1, Ri-1) menerima pasangan baru (Li, Ri), dengan menggunakan kunci Ki. Transformasi utama terjadi di dalam fungsi F.

Algoritma operasi fungsi F

Seperti yang Anda lihat pada Gambar 4.1, R menjalani operasi Perluas. Blok ini menduplikasi sejumlah bit dari R dan melengkapinya, menghasilkan nilai 48-bit. Hasil yang dihasilkan dilewatkan melalui penambahan bitwise dengan kunci Ki 48-bit. Dan hasil operasi ini diteruskan ke blok S. Blok S berisi 8 matriks substitusi kecil, yang dipilih dengan cara khusus.

Setiap matriks menerima 6 bit informasi sebagai masukan dan menghasilkan nilai 4 bit. Hasilnya, blok S menerima data 48-bit pada masukan dan menyajikan hasilnya sebagai nilai 32-bit pada keluaran.

Nilai 32-bit ini dilewatkan melalui operasi permutasi lain dan kemudian di-xor dengan L. Terakhir, sisi kanan dan kiri ditukar dan putaran selesai. Seperti disebutkan sebelumnya, algoritme melakukan 16 putaran seperti itu.

Di sini kami tidak akan membebani artikel dengan contoh-contoh yang memakan banyak ruang. Karya DES dan contohnya dapat dilihat secara online.

Sandi Feistel

Algoritma DES didasarkan pada sandi Feistel. Idenya cukup elegan. Pada setiap putaran, bagian L ditambahkan ke nilai F(R, Ki) dan L ditukar dengan R. Fitur utama dari algoritma Feistel adalah bahwa dekripsi dan enkripsi terdiri dari langkah-langkah yang sama: bagian L dan R ditukar, dan kemudian L ditambahkan dan F (R, Ki). Hal ini membuat prosedur enkripsi dan dekripsi menjadi sederhana dan mudah.

Salah satu perubahan menarik yang sering dilakukan pada cipher Feistel adalah penghapusan permutasi L dan R pada iterasi terakhir. Hal ini membuat algoritma enkripsi dan dekripsi sepenuhnya simetris. Satu-satunya perbedaan adalah urutan penggunaan tombol Ki. Prinsip ini ternyata sangat nyaman untuk digunakan pada tingkat perangkat lunak, karena enkripsi dan dekripsi dilakukan menggunakan fungsi yang sama. Misalnya, implementasi singkat dari algoritma enkripsi DES di C.

Kunci enkripsi

DES menggunakan enam belas kunci 48-bit untuk mengenkripsi data. Satu kunci per putaran. Setiap kunci dibuat dengan mengambil sampel 48 bit dari kunci master 56-bit. Pembuatan kunci untuk putaran tertentu ditentukan oleh mekanisme yang dijelaskan secara rinci dalam dokumentasi DES.

Secara singkat algoritma pemilihan kunci i adalah sebagai berikut. Bit ditambahkan ke kunci utama pada posisi 8, 16, 24, 32, 40, 48, 56, 64. Hal ini dilakukan sedemikian rupa sehingga setiap byte berisi bilangan ganjil. Mengikuti aturan membantu mendeteksi kesalahan dalam pertukaran kunci. Setelah itu, dengan menggunakan tabel khusus, kunci yang diperbesar mengalami permutasi dan pergeseran, tidak termasuk bit yang ditambahkan. Dengan cara ini kunci yang diperlukan diperoleh.

komponen DES

Setiap komponen algoritma DES memecahkan masalah tertentu:

1. Algoritme Feistel menyederhanakan enkripsi dan dekripsi sekaligus memastikan bahwa kedua bagian teks tercampur.
2. Penjumlahan bitwise dari bagian teks dengan kunci menggabungkan teks biasa dengan kunci dan mengenkripsinya.
3. S-box dan tabel korespondensi membuat algoritma menjadi nonlinier, meningkatkan ketahanannya terhadap berbagai serangan.
4. Ekspansi, S-box, dan permutasi memberikan difusi algoritma - efek longsoran salju. Dengan kata lain, jika terjadi perubahan minimal 1 bit pada data masukan fungsi F, hal ini akan menyebabkan perubahan banyak bit sekaligus. Jika tidak ada efek longsoran pada cipher, maka perubahan pada data terbuka akan menyebabkan perubahan setara dalam bentuk terenkripsi, yang dapat dilacak dan digunakan untuk cracking. Dalam kriptografi terdapat kriteria efek longsoran salju. Algoritme memenuhinya jika mengubah 1 bit data biasa mengubah setidaknya setengah dari data terenkripsi. Algoritma DES memenuhinya mulai dari putaran ke-4. Hasilnya jika Anda mengubah 1 bit data biasa di cipher DES, 29 bit akan berubah.

Masalah Keamanan di DES

Masalah yang jelas dengan DES adalah pemilihan kunci enkripsi dari kunci bersama. Apa yang terjadi jika Anda memilih nilai nol sebagai kunci (semua bit kunci adalah 0)? Hal ini akan mengarah pada fakta bahwa pemilihan semua kunci enkripsi di setiap putaran akan sama, dan semua kunci akan sama dengan nol. 16 enkripsi tidak hanya akan bekerja dengan satu kunci, tetapi karena algoritma enkripsi dan dekripsi DES hanya berbeda dalam urutan penggunaan kunci, maka keduanya akan sama persis. Inti dari enkripsi akan hilang.

DES memiliki 4 kunci, yang disebut lemah, yang mengarah ke efek yang dijelaskan. DES memiliki 12 kunci semi-lemah dan 48 kunci pseudo-lemah, yang mengakibatkan terbatasnya variasi kunci yang dihasilkan di seluruh putaran. Dengan kata lain, ada kemungkinan selama 16 putaran enkripsi, bukan 16 kunci berbeda yang akan digunakan, melainkan 8, 4 atau bahkan 2.

Kerugian yang kurang jelas dari DES adalah sifatnya yang saling melengkapi. Artinya, jika Anda menggunakan komplemen plaintext dan komplemen kunci untuk mengenkripsi, Anda akan mendapatkan nilai yang merupakan komplemen dari ciphertext. Properti aneh ini dapat menyebabkan serangan berhasil terhadap proyek yang menggunakan DES untuk keamanan.

Masalah kunci enkripsi

Hal ini mendasar bagi DES dan dianggap sebagai alasan utama mengapa algoritma ini harus ditinggalkan. Karena ukuran kunci dalam DES adalah 56 bit, untuk menghitung semua kunci Anda perlu melihat 2 56 opsi. Apakah sebanyak itu?

Jika Anda melakukan 10 juta pemeriksaan kunci per detik, maka verifikasinya akan memakan waktu sekitar 2000 tahun. Algoritmenya tampaknya cukup kuat. Hal ini terjadi pada abad terakhir, ketika menciptakan komputer dengan kekuatan sebesar itu merupakan tugas yang hampir mustahil baik dari sudut pandang teknis maupun finansial.

Jika Anda membuat komputer dengan sejuta chip, pencarian seluruh rangkaian kunci DES akan memakan waktu 20 jam. Komputer pertama untuk dekripsi menggunakan algoritma DES muncul kembali pada tahun 1998, yang menyelesaikan tugas dalam 56 jam. Teknologi jaringan modern dan proses paralel dapat mengurangi waktu ini lebih jauh lagi.

Kriptanalisis dan DES

Dapat dikatakan tanpa berlebihan bahwa DES menjadi alasan munculnya ilmu terapan yang disebut “Analisis Kriptografi”. Sejak awal kemunculan DES, upaya telah dilakukan untuk memecahkannya, dan karya ilmiah telah dilakukan untuk mempelajarinya. Semua ini menyebabkan munculnya bidang matematika seperti:

• kriptanalisis linier - studi dan identifikasi ketergantungan antara teks biasa dan teks tersandi;
• kriptanalisis diferensial - studi dan analisis ketergantungan antara beberapa teks biasa dan versi terenkripsinya;
• kriptanalisis pada kunci terkait - studi tentang ketergantungan antara teks tersandi yang diperoleh pada kunci utama dan kunci yang terkait dengan kunci utama dalam beberapa cara.

DES telah bertahan selama 20 tahun dari kriptanalisis dan serangan di seluruh dunia, namun tetap menjadi sandi yang kuat. Namun siapa yang mencari akan selalu menemukan...

1. Biham dan Shamir, ilmuwan dari Israel, menunjukkan pada tahun 1991 dengan menggunakan kriptanalisis diferensial bahwa serangan dapat dilakukan terhadap DES di mana kuncinya dihitung asalkan penyerang memiliki 2.47 pasangan teks biasa dan teks tersandi yang dipilih secara khusus.
2. Ilmuwan Jepang Mitsuru Matsui menunjukkan pada tahun 1993 bahwa kunci dapat dihitung menggunakan kriptanalisis linier. Untuk melakukan ini, Anda hanya perlu mengetahui 2 47 pasang teks biasa dan versi terenkripsi yang sesuai.

Selanjutnya, metode peretasan ini sedikit disempurnakan, ditingkatkan, dan disederhanakan, dan sejumlah metode peretasan baru juga bermunculan. Namun hal tersebut masih terlalu rumit; dengan latar belakang tersebut, pencarian lengkap terhadap semua opsi utama tampaknya merupakan serangan yang paling memadai terhadap DES.