PENGANTAR KIRTOGRAFI MODERN - Algoritma untuk Komputasi Discrete Logaritma dan Bayi-Raksasa Langkah Algoritma.

www.uts.ac.id

FEBRIANSAH_17.01.071.035

TEKNIK INFORMATIKA
KRIPTOGRAFI
UNIVERSITAS TEKNOLOGI SUMBAWA

 8.2 Algoritma untuk Komputasi Discrete Logaritma

     Membiarkan G menjadi kelompok yang operasi kelompok dapat dilakukan dengan efisien.        Dengan hasil Bagian B.2.3, ini berarti bahwa eksponensial di G juga bisa dilakukan dengan efisien. Sebuah contoh dari masalah logaritma diskret mengambil bentuk berikut (lihat Bagian 7.3.2): diberikan g ∈ G dan y ∈ < g >, fi nd x seperti yang _{x =} y. ₄ Jawaban ini dilambangkan dengan log _g y, dan unik de fi ned modulo urutan g. Kita kadang-kadang mengacu g di sebuah instance dari masalah logaritma diskret sebagai mendasarkan.

Algoritma untuk menyerang diskrit masalah logaritma jatuh ke dalam dua kategori:

    ·  mereka yang bekerja untuk sewenang-wenang kelompok (algoritma tersebut kadang-kadang disebut umum) dan orang-orang yang bekerja untuk beberapa spesifik kelompok.

      ·    Untuk algoritma mantan jenis, kita sering bisa saja juga mengambil kelompok untuk menjadi < g > itu sendiri (sehingga mengabaikan unsur di G \ < g > kapan g bukan generator G). Ketika melakukan itu, kami akan membiarkan q menunjukkan urutan < g > dan menganggap bahwa q dikenal. Perhatikan bahwa pencarian brute-force untuk logaritma diskrit dapat dilakukan dalam waktu HAI( q) dan jadi kita hanya akan tertarik algoritma yang waktu berjalan lebih baik dari ini.

Kita akan membahas algoritma berikut yang bekerja dalam kelompok sewenang-wenang:

• Bayi-langkah / raksasa-langkah metode, karena Shanks, menghitung logaritma diskrit dalam kelompok agar q pada waktunya O (√ q · polylog ( q)).

• Pohlig-Hellman algoritma dapat digunakan ketika faktorisasi dari urutan kelompok q dikenal. Kapan q memiliki faktor kecil, teknik ini mengurangi logaritma contoh diskrit yang diberikan kepada beberapa contoh dari masalah logaritma diskrit dalam kelompok agar lebih kecil. Solusi untuk masing-masing yang terakhir dapat dikombinasikan untuk memberikan solusi yang diinginkan untuk masalah asli.

Pengantar modern Kriptografi

Kami melihat ke depan di komputasi logaritma diskrit dalam beberapa spesifik kelompok. Sebagai contoh ilustratif tapi sederhana, kita pertama melihat pertama pada masalah di (aditif) kelompok Z _N dan menunjukkan bahwa logaritma diskrit dapat dihitung dalam waktu polinomial dalam kasus ini.

   Inti dari latihan ini adalah untuk menunjukkan bahwa meskipun kelompok siklik pesanan q isomorfis untuk Z _{q (} cf. Contoh 7.58 di Bab 7), dan karenanya semua kelompok siklik dari urutan yang sama, dalam arti tertentu, “sama”,kekerasan masalah logaritma diskrit tergantung dengan cara penting pada khususnya perwakilan yang digunakan untuk grup.

      Memang, algoritma untuk menghitung logaritma diskrit dalam bahan tambahan kelompok Z_N akan bergantung pada fakta bahwa perkalian modulo N juga didefinisikan. pernyataan seperti tidak masuk akal dalam beberapa kelompok sewenang-wenang yang didefinisikan tanpa mengacu aritmatika modular.

      Algoritma bayi-langkah / raksasa-langkah diketahui optimal ( dalam hal waktu yang berjalan asymptotic) sejauh algoritma generik pergi. (Kami berkomentar, bagaimanapun, bahwa lebih banyak ruang-e FFI efisien algoritma generik dengan waktu berjalan sama diketahui.) Terbukti batas bawah pada kompleksitas fi nding logaritma diskrit ketika kelompok diperlakukan secara umum, bagaimanapun, mengatakan apa-apa tentang kekerasan fi nding diskrit logaritma dalam kelompok tertentu.

   Saat ini, algoritma paling terkenal untuk komputasi logaritma diskrit dalam Z ^*_{p (} untuk p Perdana) adalah Nomor umum lapangan saringan. ₅ Heuristik, algoritma ini berjalan dalam waktu 2 _HAI( n ^1/3 · ( catatan n) _2/3) rata-rata untuk menghitung logaritma diskrit dalam Z ^* _p kapan p memiliki panjang ‖ p ‖ = O ( n). Yang penting, pada dasarnya tidak ada non-generik algoritma yang saat ini dikenal untuk menghitung logaritma diskrit dalam kelompok-kelompok tertentu khusus dibangun elliptic curve (cf. Bagian 7.3.4). Ini berarti bahwa untuk kelompok-kelompok seperti, selama urutan kelompok perdana (sehingga menghalangi Pohlig-Hellman algoritma), hanya eksponensial-waktu algoritma untuk menghitung logaritma diskrit dikenal.

Anjak piutang dan Komputasi Discrete Logaritma 

logaritma di Z*_p di sekitar 2 ^{512 1/3}  · 9 ^2/3 ≈ 2 ^{8 · 4} ₌ 2 ³² Langkah. Hal ini sesuai dengan waktu yang dibutuhkan untuk menghitung logaritma diskrit menggunakan yang terbaik algoritma generik dalam grup kurva eliptik pesanan q, dimana q adalah 64-bit perdana, sejak saat itu √q ≈ 2^64/2 = 2^{32 .} 

Kami melihat bahwa grup kurva eliptik fi signi cantly lebih kecil, dengan bersamaan cepat operasi kelompok, dapat digunakan tanpa mengurangi di FFI culty dari masalah logaritma diskrit (setidaknya sehubungan dengan terbaik teknik saat ini dikenal). Secara kasar, kemudian, dengan menggunakan kelompok kurva eliptik di tempat Z _{* p} kita memperoleh skema kriptografi yang lebih e FFI efisien bagi para pemain yang jujur, tapi itu sama-sama sulit bagi musuh untuk istirahat.

8.2.1  The Baby-Langkah / Raksasa-Langkah Algoritma

        Algoritma bayi-langkah / raksasa-langkah, karena Shanks, menghitung logaritma diskrit dalam kelompok agar q pada waktunya O (√ q · polylog ( q)). Idenya sederhana. Diberikan sebagai masukan g dan y ∈ < g >, kita bisa membayangkan unsur-unsur < g > ditata dalam lingkaran sebagai
1 = g ⁰, g ¹, g ²,....... g ^{q - 2}, g ^{q - 1}, g ^q = 1,

dan kita tahu bahwa y harus berbaring di suatu tempat di lingkaran ini. Komputasi dan menuliskan semua titik pada lingkaran ini akan mengambil setidaknya Ω ( q) waktu. Sebaliknya, kita “mark off” lingkaran pada interval   ukuran t=^def[√q]  menghitung dan merekam [q/t] + 1 = O (√ q) elemen

                                     g⁰, g^t, g^2t,…………..,g^[q/t].t

  

(Ini adalah “langkah raksasa”.) Perhatikan bahwa “kesenjangan” antara setiap “tanda” berturut-turut pada lingkaran yang paling banyak t. Selanjutnya, kita tahu bahwa y = g^x kebohongan di salah satu kesenjangan ini. Kami dengan demikian dijamin bahwa salah satu t elemen

y · g ⁰ = g ^x, y · g ¹ = g  ^{x +1} ,          y · g ^t = g ^{x + t},

akan sama dengan salah satu poin kami telah ditandai o ff. (Ini adalah “langkah-langkah bayi”.) Say y · gⁱ₌ g^k.t _. Kita bisa dengan mudah memecahkan ini untuk mendapatkan y = g^kt-i atau login _g y = [kt - i mod q]. Psuedocode untuk algoritma ini diberikan berikutnya.

        Algoritma memerlukan O (√ q) eksponensial dan perkalian di G dan masing-masing eksponensial dapat dilakukan dalam waktu HAI( polylog ( q)) menggunakan e FFI efisien algoritma eksponensial. (Sebenarnya, selain fi nilai rst g_{1 =} g ^t_, setiap nilai g _saya dapat dihitung dengan menggunakan perkalian tunggal sebagai

      

                              g_{i =} g_{i - 1} · g_1.).

menyortir O (√ q) pasang ( IG _saya) dapat dilakukan dalam waktu O (√ q · catatan q), dan kita kemudian dapat menggunakan pencarian biner untuk memeriksa apakah y _saya sama dengan beberapa g _k pada waktunya

HAI( catatan q). Algoritma keseluruhan sehingga berjalan dalam waktu O (√ q · polylog ( q)).

contoh 8.6

Kami menunjukkan aplikasi dari algoritma dalam kelompok siklik Z _{* 29} order

q = 29 - 1 = 28. Mengambil g = 2 dan y = 17. Kami set t = 5 dan menghitung

2 ⁰ ₌ 1, 2 ⁵ ₌ 3, 2 ¹⁰ ₌ 9, 2 ¹⁵ ₌ 27, 2 ²⁰ ₌ 23, 2 ²⁵ ₌ 11.

Pengantar modern Kriptografi

ALGORITMA 8.5

Bayi-langkah / raksasa-langkah algoritma

Memasukkan: elemen g ∈ G dan y ∈ < g >; pesanan q dari g

Keluaran: log_g y

t= [ √q]

untuk i = 0 untuk [q/t]:

menghitung g _i :₌ g^i-t

menyortir pasangan ( i,gi) oleh komponen kedua mereka

untuk i = 0 untuk t:

menghitung y _{i: =} y · g _saya

jika y_{i =} g _k untuk beberapa k, kembali [ kt - i mod q]

(Kami menghilangkan “mod 29” karena dipahami bahwa operasi adalah dalam kelompok Z _* 29.) kemudian menghitung

17 · 2 ⁰ = 17, 17 · 2 ¹ = 5, 17 · 2 ² = 10, 17 · 2 ³ = 20, 17 · 2 ⁴ = 11, 17 · 2 ⁵ = 22,

dan pemberitahuan bahwa 2²⁵ ₌ 11 = 17 · 2⁴_. Dengan demikian kita memiliki log ₂ 17 = 25 - 4 = 21.