Materi Kriptografi

Pengantar Kriptografi Modern

Nama : Elga Ramdani

Nim 17.01.071.027

Mata Kuliah : Kriptografi
Prodi : Teknik Informatika (A)
Link : http://www.uts.ac.id

ALGORITMA 8.5
Algoritma langkah kecil / langkah besar Input: Elemen g ∈ G dan y ∈(g);  urutan q dari g Output: loggy t: = [√q] untuk i = 0 hingga [q / t]: hitung gi: = gi.t urutkan pasangan (i, gi) dengan komponen kedua untuk i = 0 hingga t: hitung yi: = y · gi jika yi = gk untuk beberapa k, kembalikan [kt - i mod q]
(Kami menghilangkan "mod 29" karena dapat dipahami bahwa operasi ada dalam  grup Z∗29.) Kemudian hitung  17·20 = 17, 17·21 = 5, 17·22 = 10, 17·23 = 20, 17·24 = 11, 17·25 = 22, dan perhatikan bahwa 225 = 11 = 17 · 24 .  Dengan demikian kita memiliki log2 17 = 25 - 4 = 21.

Algoritma Pohlig-Hellman

Algoritma Pohlig-Hellman dapat digunakan untuk mempercepat perhitungan logaritma diskrit ketika  faktor non-sepele dari urutan grup q adalah dikenal.  Ingat bahwa urutan elemen g, yang kami  tunjukkan di sini oleh ord (g), adalah i positif terkecil yang  i = 1. Kita perlu lemma berikut:

LEMMA 8.7 Biarkan ord (g) = q, dan ucapkan p |  q.  Kemudian ord (gp ) = q / p.

BUKTI Sejak (gp ) q / p = gq= 1, urutan gp tentu paling banyak q / p. Biarkan saya> 0 sedemikian rupa  sehingga (gp ) i = 1. Lalu gpi = 1 dan, karena q adalah urutannya dari g, itu harus menjadi kasus yang pi  ≥ q atau i ≥ q / p.  Urutan gp oleh karena itu persis q / p. Kami juga akan menggunakan generalisasi dari sisa teorema Cina: jika q =πki = 1 qi dan {qi} relatif berpasangan (mis., gcd (qi , qj) = 1 untuk i 6 = j), lalu Zq 'Zq1 × · · · × Zqk dan Z∗q 'Z∗q1 × · · · × Z∗qk . (Ini dapat dibuktikan dengan induksi pada k, menggunakan sisa dasar bahasa Cina teorema sebagai kasus dasar.) Selain itu, dengan perpanjangan algoritma di Bagian 7.1.5 dimungkinkan untuk mengkonversi secara efisien antara representasi elemen sebagai elemen Zq dan perwakilannya sebagai elemen Zq1 × · · · × Zqk .

• pemfaktoran dan Menghitung Logaritma Diskrit 295

Kami sekarang menggambarkan pendekatan Pohlig-Hellman.  Kita diberi g dan y dan tertarik untuk menemukan x sehingga g x = y.  Biarkan ord (g) = q, dan ucapkan a faktorisasi q = Y k i = 1qi  dikenal dengan {qi} berpasangan relatif prima.  (Perhatikan bahwa ini tidak perlu faktorisasi utama lengkap q.) Kita tahu itu g q / qi x = (g x ) q / qi = y q / qi untuk i = 1,.  .  .  , k.  (8.4) Membiarkan gi def = g q / qi, dengan demikian kami memiliki contoh k dari masalah logaritma diskrit dalam k kelompok yang lebih kecil, masing-masing ukuran ord (gi) = qi (oleh Lemma 8.7). Kita dapat menyelesaikan setiap instance k yang dihasilkan menggunakan algoritma lain untuk memecahkan masalah logaritma diskrit;  untuk konkret, mari kita asumsikan itu algoritmababy-step / giant-step pada bagian sebelumnya digunakan.  Memecahkan contoh-contoh ini memberikan satu set jawaban {xi} k i = 1 untuk yang g xi i = y q / qi = g x saya .

(Kesetaraan kedua mengikuti dari Persamaan (8.4).) Proposisi 7.50 menyiratkan bahwa x = xi modqi untuk semua saya.  Dengan teorema sisa Tiongkok yang umum dibahas sebelumnya, kendala x = x1 mod q1 ... x = xk mod qk tentukan secara unik x modulo q.  (Ini tentu saja yang terbaik yang bisa kita harapkan, sejak persamaan g x = y hanya secara unik menentukan x modulo q.) Jawabannya x sendiri dapat direkonstruksi secara efisien dari x1,.  .  .  , xk.

Contoh 8.8

Kami sekali lagi menerapkan gagasan yang diperkenalkan di sini untuk menghitung logaritma diskrit di Z∗p.  Di sini, ambil p = 31 dengan urutan Z∗ 31 menjadi q = 31 ∞ 1 = 30 = 5 · 3 · 2. Katakan g = 3 dan y = 26 = g x .  Kita punya (g x ) 30/5 = y 30/5 ⇒ (36 ) x = 16x = 266 = 1 (g x ) 30/3 = y 30/3 ⇒ (310) x = 25x = 2610 = 5 (g x ) 30/2 = y 30/2 ⇒ (315) x = 30x = 2615 = 30. (Sekali lagi, kami menghilangkan "mod 31" karena ini dipahami.) Memecahkan masing-masing persamaan, kita dapatkan x = 0 mod 5, x = 2 mod 3, x = 1 mod 2, dan begitu x = 5 mod 30. Memang, 3 5 = 26 mod 31.

Pengantar Kriptografi Modern

Dengan asumsi q dengan faktorisasi seperti di atas, dan dengan asumsi algoritma langkah kecil / langkah besar digunakan untuk menyelesaikan masing-masing contoh yang lebih kecil dari masalah logaritma diskrit, waktu berjalan seluruh algoritma akan menjadi O (polylog (q) ·Pk i = 1 √qi).  Karena q dapat memiliki paling banyak faktor log q, ini menyederhanakan fiesto O (polylog (q) · maxi { √qi}).  Tergantung pada ukuran terbesar yang diketahui faktor q, ini bisa menjadi peningkatan yang nyata atas O ( √q) algoritma diberikan di bagian sebelumnya.  Secara khusus, jika q memiliki banyak faktor kecil maka masalah logaritma diskrit dalam kelompok pesanan q akan relatif mudah selesaikan melalui pendekatan ini.  Seperti dibahas dalam Bagian 7.3.2, ini memotivasi pemilihan q menjadi prima untuk aplikasi kriptografi. Jika q memiliki faktorisasi utama q =Qk i = 1 pei saya , algoritmaPohlig-Hellman sebagai dijelaskan di atas memecahkan logaritma diskrit dalam kelompok urutan q dalam waktu HAIpolylog (q) · maxi { hal halei saya } .