Tiga protokol lulus

Teks ini akan menjadi salah satu bab yang ditulis ulang untuk manual tentang perlindungan informasi dari Departemen Teknik Radio dan Sistem Kontrol, serta, dari kode pelatihan ini, Departemen Perlindungan Informasi MIPT (GU). Tutorial lengkap tersedia di github (lihat juga draft rilis ). Pada Habrir saya berencana untuk membuat potongan-potongan "besar" yang baru, pertama, untuk mengumpulkan komentar dan pengamatan yang bermanfaat, dan kedua, untuk memberi masyarakat lebih banyak bahan ikhtisar tentang topik yang berguna dan menarik.

Topik sebelumnya:

• Protokol kriptografi: definisi, catatan, properti, klasifikasi, serangan
• Protokol distribusi utama pada cipher simetris

Jika ada saluran komunikasi antara Alice dan Bob yang tidak dapat diakses untuk modifikasi oleh penyerang (yaitu, ketika hanya model cryptanalyst pasif yang berlaku), maka bahkan tanpa pertukaran awal kunci rahasia atau informasi lain, Anda dapat menggunakan ide yang digunakan sebelumnya dalam kriptografi kunci publik. Setelah menggambarkan RSA pada 1978, pada 1980 Adi Shamir mengusulkan penggunaan cryptosystems berdasarkan operasi komutatif untuk mengirimkan informasi tanpa terlebih dahulu bertukar kunci rahasia. Jika kami berasumsi bahwa informasi yang dikirimkan adalah kunci sesi rahasia yang dihasilkan oleh salah satu pihak, maka secara umum kami mendapatkan protokol tiga-pass berikut.

Pendahuluan:

• Alice dan Bob terhubung oleh saluran komunikasi yang tidak aman, terbuka untuk mendengarkan (tetapi tidak untuk modifikasi) oleh penyerang.
• Masing-masing pihak memiliki sepasang kunci publik dan pribadi $$$K_A$ , $$$k_A$ , $$$K_B$ , $$$k_B$ sesuai.
• Para pihak telah memilih dan menggunakan fungsi enkripsi komutatif:
  

  $$

  $$\ begin {array} {lll} D_ {A} \ kiri (E_ {A} \ kiri (X \ kanan) \ kanan) = X & \ untuksemua X, \ kiri \ {K_A, k_a \ kanan \}; \\ E_ {A} \ kiri (E_ {B} \ kiri (X \ kanan) \ kanan) = E_B \ kiri (E_A \ kiri (X \ kanan) \ kanan) & \ forall ~ K_A, K_B, X. \ end {array}$$

Protokol terdiri dari tiga lintasan dengan transmisi pesan (maka namanya) dan satu yang terakhir, di mana Bob menerima kuncinya.

1. Alice memilih kunci sesi baru $$$K$
   
   $$$Alice \ to \ left \ {E_A \ left (K \ right) \ right \} \ to Bob$
2. $$$Bob \ ke \ kiri \ {E_B \ kiri (E_A \ kiri (K \ kanan) \ kanan) \ kanan \} \ ke Alice$
3. Alice, menggunakan komutatifitas fungsi enkripsi,
   

   $$

   $$D_A \ kiri (E_B \ kiri (E_A \ kiri (K \ kanan) \ kanan) \ kanan) = D_A \ kiri (E_A \ kiri (E_B \ kiri (K \ kanan) \ kanan) \ kanan) = E_B \ kiri (K \ benar).$$
   $$$Alice \ to \ left \ {E_B \ left (K \ right) \ right \} \ to Bob$
4. Bob mendekripsi $$$D_B \ kiri (E_B \ kiri (K \ kanan) \ kanan) = K$

Akibatnya, para pihak menerima kunci rahasia bersama. $$$K$ .

Kelemahan umum dari semua protokol tersebut adalah kurangnya otentikasi para pihak. Tentu saja, dalam kasus cryptanalyst pasif, ini tidak diperlukan, tetapi dalam kehidupan nyata Anda masih perlu mempertimbangkan semua model yang mungkin (termasuk cryptanalyst aktif) dan menggunakan protokol yang melibatkan otentikasi timbal balik para pihak. Juga, tidak seperti skema Diffie - Hellman, kunci baru dipilih oleh pemrakarsa sesi, yang memungkinkan pemrakarsa, bukan dengan niat baik, untuk memaksa peserta kedua menggunakan kunci sesi yang sudah ketinggalan zaman.

Berbicara dalam hal sifat keamanan , maka semua perwakilan dari kelas protokol ini hanya menyatakan otentikasi kunci (G7). Berbeda dengan skema Diffie - Hellman, protokol tiga-pass tidak memerlukan pemilihan kunci "master" baru untuk setiap sesi protokol, yang mengapa tidak ada kerahasiaan langsung sempurna (G9) maupun pembentukan kunci baru (G10) yang dapat dijamin.

Opsi sepele

Mari kita beri contoh protokol yang didasarkan pada fungsi XOR (penambahan bito modulo 2). Meskipun fungsi ini dapat digunakan sebagai dasar untuk membangun sistem dengan kekuatan kriptografi yang sempurna, untuk protokol tiga langkah ini adalah pilihan yang buruk.

Sebelum memulai protokol, kedua belah pihak memiliki kunci rahasia mereka. $$$K_A$ dan $$$K_B$ mewakili urutan biner acak dengan distribusi karakter yang seragam. Fungsi enkripsi didefinisikan sebagai $$$E_i (X) = X \ oplus K_i$ dimana $$$X$ pesan ini juga $$$K_i$ - kunci rahasia. Jelas:

$$

$$\ forall i, j, X: E_i \ kiri (E_j \ kiri (X \ kanan) \ kanan) = X \ oplus K_j \ oplus K_i = X \ oplus K_i \ oplus K_j = E_j \ kiri (E_i \ kiri (X \ benar) \ benar)$$

1. Alice memilih kunci sesi baru $$$K$
   
   $$$Alice \ to \ left \ {E_A \ left (K \ right) = K \ oplus K_A \ right \} \ to Bob$
2. $$$Bob \ ke \ kiri \ {E_B \ kiri (E_A \ kiri (K \ kanan) \ kanan) = K \ oplus K_A \ oplus K_B \ kanan \} \ ke Alice$
3. Alice, menggunakan komutatifitas fungsi enkripsi,
   

   $$

   $$D_A \ kiri (E_B \ kiri (E_A \ kiri (K \ kanan) \ kanan) \ kanan) = K \ oplus K_A \ oplus K_B \ oplus K_A = K \ oplus K_B = E_B \ kiri (K \ kanan).$$
   $$$Alice \ to \ left \ {E_B \ left (K \ right) = K \ oplus K_B \ right \} \ to Bob$
4. Bob mendekripsi $$$D_B \ kiri (E_B \ kiri (K \ kanan) \ kanan) = K \ oplus K_B \ oplus K_B = K$

Pada akhir sesi protokol, Alice dan Bob mengetahui kunci sesi umum $$$K$ .

Pilihan yang diusulkan dari fungsi enkripsi komutatif kerahasiaan sempurna tidak berhasil, karena ada situasi di mana seorang cryptanalyst dapat menentukan kunci $$$K$ . Misalkan seorang cryptanalyst mencegat ketiga pesan:

$$

$$K \ oplus K_A, ~~ K \ oplus K_A \ oplus K_B, ~~ K \ oplus K_B.$$

Modulo 2 tambahan dari ketiga pesan memberi kunci $$$K$ . Karena itu, sistem enkripsi seperti itu tidak digunakan.

Sekarang kami menyajikan protokol untuk transfer kunci rahasia yang andal, berdasarkan pada fungsi enkripsi eksponensial (komutatif). Stabilitas protokol ini dikaitkan dengan kesulitan tugas menghitung logaritma diskrit: untuk nilai yang diketahui $$$y, g, p$ temukan $$$x$ dari persamaan $$$y = g ^ x \ bmod p$ .

Keyless Protocol Shamir

Pihak-pihak secara tentatif menyetujui suatu penawaran besar $$$p \ sim 2 ^ {1024}$ . Masing-masing pihak memilih kunci rahasia. $$$a$ dan $$$b$ . Kunci-kunci ini lebih kecil dan saling sederhana. $$$p-1$ . Juga, para pihak disiapkan sesuai dengan nomor khusus $$$a '$ dan $$$b '$ yang memungkinkan mereka untuk mendekripsi pesan yang dienkripsi dengan kunci mereka:

$$

$$\ begin {array} {l} a '= a {-1} \ mod (p-1), \\ a \ kali a' = 1 \ mod (p-1), \\ \ forall X: (X ^ a) ^ {a '} = X. \\ \ end {array}$$

Ungkapan terakhir benar oleh akibat wajar dari teorema \ indeks kecil {teorema! Pertanian itu kecil}. Operasi enkripsi dan dekripsi didefinisikan sebagai berikut:

$$

$$\ begin {array} {lll} \ forall M <p: & C = E (M) = M ^ {a} & \ mod p, \\ & D (C) = C ^ {a '} & \ mod p, \\ & D_A (E_A (M)) = M ^ {aa '} = M & \ mod p. \\ \ end {array}$$

1. Alice memilih kunci sesi baru $$$K <p$
   
   $$$Alice \ to \ left \ {E_A \ left (K \ right) = K ^ a \ bmod p \ right \} \ to Bob$
2. $$$Bob \ ke \ kiri \ {E_B \ kiri (E_A \ kiri (K \ kanan) \ kanan) = K ^ {ab} \ bmod p \ kanan \} \ untuk Alice$
3. Alice, menggunakan komutatifitas fungsi enkripsi,
   

   $$

   $$D_A \ kiri (E_B \ kiri (E_A \ kiri (K \ kanan) \ kanan) \ kanan) = K ^ {aba '} = K ^ b = E_B \ kiri (K \ kanan) \ mod p.$$
   
   $$$Alice \ to \ left \ {E_B \ left (K \ right) = K ^ b \ right \} \ to Bob$
4. Bob mendekripsi $$$D_B \ kiri (E_B \ kiri (K \ kanan) \ kanan) = K ^ {bb '} \ bmod p = K$

Pada akhir sesi protokol, Alice dan Bob mengetahui kunci sesi umum $$$K$ .

Misalkan seorang cryptanalyst dicegat tiga pesan:

$$

$$\ begin {array} {l} y_1 = K ^ a \ bmod p, \\ y_2 = K ^ {ab} \ bmod p, \\ y_3 = K ^ b \ bmod p. \\ \ end {array}$$

Untuk menemukan kuncinya $$$K$ , seorang cryptanalyst perlu menyelesaikan suatu sistem dari ketiga persamaan ini, yang memiliki kompleksitas komputasi yang sangat besar, tidak dapat diterima dari sudut pandang praktis, jika ketiga angka tersebut $$$a, b, ab$ cukup besar. Asumsikan itu $$$a$ (atau $$$b$ ) tidak cukup. Kemudian, komputasi derajat berurutan $$$y_3$ (atau $$$y_1$ ), dapat ditemukan $$$a$ (atau $$$b$ ), membandingkan hasilnya dengan $$$y_2$ . Tahu $$$a$ mudah ditemukan $$$a ^ {- 1} \ bmod (p-1)$ dan $$$K = (y_1) ^ {a ^ {- 1}} \ bmod p$ .

Cryptosystem Massey-Omura

Pada tahun 1982, James Massey dan Jim Omura mengajukan paten (James Massey, Jim K. Omura), meningkatkan (menurut pendapat mereka) protokol tanpa kunci dari Shamir. Sebagai operasi enkripsi bukannya eksponensial dalam kelompok multiplikasi $$$\ mathbb {Z} _p ^ *$ mereka menyarankan menggunakan eksponensial di bidang Galois $$$\ mathbb {GF} {2 ^ n}$ . Kunci rahasia masing-masing pihak (untuk Alice - $$$a$ ) harus memenuhi ketentuan:

$$

$$\ begin {array} {l} a \ in \ mathbb {GF} {2 ^ n}, \\ gfd \ kiri (a, x ^ {n-1} + x ^ {n-2} + ... + x + 1 \ kanan) = 1. \\ \ end {array}$$

Kalau tidak, protokolnya terlihat mirip.

Kata penutup

Penulis akan berterima kasih atas komentar faktual dan lainnya pada teks.