Algoritma untuk Anjak piutang dan Komputasi Logaritma Diskrit (Algorithms for Factoring and Computing Discrete Logarithms)

Nama : Eva Rahmiati

NIM : 17.01.071.028

Mata Kuliah : KRIPTOGRAFI

Prodi : Teknik Informatika
Link : http://www.uts.ac.id

Seperti dibahas dalam Bab 7, saat ini tidak ada algoritma waktu polinomial yang dikenal untuk anjak piutang atau untuk menghitung logaritma diskrit di Z ∗ p. Tetapi ini tidak berarti bahwa pencarian dengan kekerasan adalah metode terbaik yang tersedia untuk menyerang masalah ini! Di sini, kami mensurvei beberapa algoritma yang lebih baik untuk masalah ini. Selain menarik dalam hak mereka sendiri, dan berfungsi sebagai aplikasi yang bagus dari beberapa teori bilangan yang telah kita pelajari, memahami keefektifan algoritma ini sangat penting untuk memilih parameter kriptografi dalam praktik: jika skema kriptografi berdasarkan anjak seharusnya tahan musuh yang memasang serangan berdedikasi selama 5 tahun, lalu - minimal! - modulus N yang digunakan oleh skema harus cukup lama sehingga algoritma anjak piutang paling terkenal akan membutuhkan waktu (setidaknya) 5 tahun untuk berhasil faktor N.

8.1 Algoritma untuk Anjak Piutang (Algorithms for Factoring)

            Sepanjang bagian ini, kami mengasumsikan bahwa N = pq adalah produk dari dua bilangan prima yang berbeda. Kami juga akan sangat tertarik pada kasus ketika p dan q masing-masing memiliki panjang n yang sama (diketahui), dan juga n = Θ (logN). Ada algoritma anjak piutang lain yang dirancang untuk bekerja untuk N dari bentuk yang berbeda (mis., Ketika N = prq untuk p, q prime dan integer r> 1, atau ketika p dan q memiliki panjang yang berbeda secara signifikan), tetapi kami tidak membahasnya di sini.

Kita akan sering menggunakan teorema sisa Cina bersama dengan beberapa notasi yang dikembangkan di Bagian 7.1.4 dan 7.1.5. Teorema sisa Cina menyatakan itu.

Z∗ N ' Z∗ p ×Z∗ q,

Dengan isomorfisme yang diberikan oleh f (x) def = ([x mod p], [x mod q]) untuk x ∈ Z ∗ N. Fakta bahwa f adalah isomorfisme berarti secara khusus bahwa ia memberikan pemetaan satu-satu antara elemen-elemen x ∈ Z ∗ N dan pasang (xp, xq) ∈ Z ∗ p × Z Z q. Kami menulis x ↔ (xp, xq), dengan xp = [x mod p] dan xq = [x mod q], untuk menunjukkan bijih ini.

Ingatlah dari Bagian 7.2 bahwa pembagian percobaan, metode pemfaktoran sepele, brute-force, menemukan faktor dari angka N yang diberikan dengan probabilitas 1 dalam waktu O (√N). Algoritma pemfaktoran yang lebih canggih karenanya hanya menarik jika waktu operasinya kurang asimtotik dari ini. Kami membahas tiga algoritma pemfaktoran yang berbeda dengan waktu berjalan yang lebih baik:

Ø  Metode p − 1 Pollard efektif jika p − 1 memiliki faktor prima “kecil”.

Ø  Metode Pollard rho berlaku untuk N. sewenang-wenang (Dengan demikian, itu disebut algoritma pemfaktoran tujuan umum). Waktu berjalannya untuk N dari formulir yang dibahas pada awal bagian ini adalah O (N1 / 4 · polylog (N)) . Karena N = 2Θ (n) ini eksponensial dalam n, panjang N.

Ø  Algoritma kuadratik adalah algoritma pemfaktoran tujuan umum yang berjalan dalam waktu sub-eksponensial dalam panjang N.1 Kami memberikan gambaran tingkat tinggi tentang cara kerja algoritma ini, tetapi detailnya agak rumit dan berada di luar cakupan buku ini .

Saat ini, algoritma pemfaktoran tujuan umum yang paling terkenal (dalam hal waktu berjalan asimptotik) adalah ayakan bidang angka umum. Secara heuristik, 2 algoritma ini berjalan dalam waktu 2O (n1 / 3 · (logn) 2/3) rata-rata untuk faktor sejumlah N panjang O (n).

8.1.1 Metode Pollard p – 1

Bagian ini bergantung pada beberapa bahan dari Bagian B.3.1. Algoritma karena Pollard dapat digunakan untuk faktor integer N = pq ketika p - 1 hanya memiliki faktor "kecil". Kunci dari pendekatan ini adalah observasi berikut: Katakanlah kita dapat menemukan elemen y ∈ Z ∗ N yang mana y ↔ (1, yq) andy q 6 = 1. Yaitu:

y = 1 mod p but y 6= 1 mod q (8.1)

or, equivalently,

y−1 = 0 mod p but y−16= 0 mod q.

Di atas berarti bahwa p | (y −1) tetapi q6 | (y −1), yang pada gilirannya menyiratkan bahwa gcd (y − 1, N) = p. Dengan demikian, perhitungan gcd sederhana (yang dapat dilakukan secara efisien seperti yang dijelaskan dalam Bagian B.1.2) menghasilkan faktor non-sepele dari N. Dengan demikian, masalah anjak piutang N telah dikurangi untuk menemukan nilai y dengan properti yang disebutkan. Kami sekarang menjelaskan bagaimana menemukan y. Katakanlah kita memiliki bilangan bulat B untuk itu:

(p−1)|B but (q−1)6|B

Dengan catatan :

1.      Jika f (n) = 2Ω (n), maka f adalah eksponensial dalam n. Jika f (n) = 2o (n), maka f adalah sub-eksponensial dalam n. Polinomial dalam n memiliki bentuk f (n) = 2O (log n) = nO (1).

2.       Tetap terbuka untuk menganalisis secara ketat waktu berjalan dari algoritma ini.

Tulis B = γ · (p - 1) untuk beberapa bilangan bulat γ. Mengambil elemen sewenang-wenang x ∈ Z ∗ N dan pengaturan y = [xB mod N] (perhatikan bahwa y dapat dihitung dengan menggunakan algoritma eksponensial efisien dari Bagian B.2.3), kami memiliki:

y = [xB mod N] ↔ (xp,xq)B = (xB p mod p, xB q mod q) = ((xp−1 p )γ mod p, xB q mod q) = (1, xB q mod q)

Menggunakan Teorema 7.14 dan fakta bahwa urutan Z ∗ p adalah p − 1. Nilai y dengan y ↔ (1, xB q) karenanya memenuhi persamaan (8.1) selama xB q 6 = 1 mod q. Kita sekarang menunjukkan bahwa yang terakhir terjadi dengan probabilitas yang cukup tinggi. Karena Z ∗ q adalah siklik, grup Z ∗ q berisi persis φ (q − 1) masing-masing generator yang urutannya (menurut definisi) q − 1. Kami mengklaim bahwa jika xq adalah generator Z ∗ q dan (q − 1) 6 | B, maka xB q 6 = 1 mod q. Untuk melihat ini, gunakan pembagian-dengan-sisa (Proposisi 7.1) untuk menulis B = α · (q − 1) + β dengan 1≤ β <(q − 1). Kemudian:

Menggunakan Teorema 7.14. Tapi xβ q 6 = 1 mod q karena urutan xq benar-benar lebih besar dari .

Jika x dipilih secara seragam secara acak dari Z ∗ N, maka xq def = [x mod q] didistribusikan secara seragam dalam Zq. (Ini adalah konsekuensi dari fakta bahwa teorema sisa Cina memberikan sebuah penipisan antara Z ∗ N dan Z ∗ p × Z ∗ q.) Menggunakan Teorema B.16, kami menyimpulkan bahwa dengan probabilitas setidaknya φ (q − 1) q −1 = Ω (1 / logq) kita memilih x sehingga xB q 6 = 1 mod q.Kode semu untuk algoritma p − 1 Pollard berikut. Diskusi dalam paragraf sebelumnya menyiratkan bahwa algoritma berhasil menemukan faktor non-sepele N dengan probabilitas Ω (1 / logq) = Ω (1 / n), dengan asumsi B memuaskan persamaan (8.2) diketahui.

ALGORITHM 8.1 Pollard’s p−1 algorithm for factoring

Input: Integer N Output: A non-trivial factor of Nx← Z∗ N y := [xB mod N] p := gcd(y−1,N)  if p 6∈{1,N} return p

 

 

Tetap memilih nilai untuk B. Satu kemungkinan adalah memilih.

                        B =k Y i=1pbn/log pic

Di mana pi menunjukkan ith prima (yaitu, p1 = 2, p2 = 3, p3 = 5, ...) dan k adalah batas yang pilihannya memengaruhi waktu berjalan dan probabilitas keberhasilan algoritma. Perhatikan bahwa pbn / log pic i adalah kekuatan pi terbesar yang dapat membagi p − 1, bilangan bulat panjang paling banyak n. Dengan demikian, selama p − 1 dapat ditulis kami with  (yaitu, selama p − 1 tidak memiliki faktor prima lebih besar dari pk), itu akan menjadi kasus yang (p − 1) | B. Sebaliknya, jika q −1 faktor hasan y prima lebih besar dari pk maka (q − 1) 6 | B.

Memilih nilai yang lebih besar untuk k meningkatkan B dan juga meningkatkan waktu berjalan algoritma (yang melakukan eksponensial modular dengan daya B). Nilai k yang lebih besar juga membuatnya lebih mungkin bahwa (p − 1) | B tetapi pada saat yang sama membuatnya lebih kecil kemungkinannya bahwa (q −1) | B. Tentu saja dimungkinkan untuk menjalankan algoritma berulang kali menggunakan beberapa pilihan untuk k. Cara lain untuk memilih B juga dimungkinkan.

 Metode p − 1 Pollard digagalkan jika p − 1 dan q − 1 memiliki faktor prima yang besar. Untuk alasan ini, ketika menghasilkan modulus N = pq untuk aplikasi kriptografi, p dan q kadang-kadang dipilih sebagai bilangan prima yang kuat (ingat bahwa p adalah bilangan prima yang kuat jika (p −1) / 2 juga prima). Memilih p dan q dengan cara ini sangat kurang efisien daripada hanya memilih p dan q sebagai bilangan prima acak (acak). Karena algoritma pemfaktoran yang lebih baik tersedia, seperti yang akan kita lihat di bawah, konsensus saat ini adalah bahwa biaya komputasi tambahan untuk menghasilkan p dan q sebagai bilangan prima yang kuat tidak diatur oleh keuntungan keamanan yang cukup besar. Namun, kami berkomentar bahwa skema kriptografi tertentu (yang tidak akan kita lihat dalam buku ini) memerlukan p dan q untuk menjadi bilangan prima yang kuat karena alasan teknis terkait dengan struktur grup Z ∗ N.

 

8.1.2 Metode Rhard Pollard

Berbeda dengan algoritme dari bagian sebelumnya, metode Pollard rho dapat digunakan untuk menemukan faktor non-sepele dari bilangan bulat sembarang N tanpa asumsi tentang p atau q yaitu, itu adalah algoritma pemfaktoran tujuan umum. Membuktikan batas-batas yang ketat pada waktu berjalan / probabilitas keberhasilan algoritma masih merupakan pertanyaan terbuka, heuristically, faktor algoritma N dengan probabilitas konstan dalam O (. Polylog (N))steps. peningkatan atas pembagian sidang.

Gagasan metode rho adalah untuk menemukan dua nilai yang berbeda x, x0 ∈ Z ∗ N yang setara modulo p (yaitu, x = x0 mod p); mari kita sebut sepasang nilai yang baik. Demikian pula dengan bagian sebelumnya, kita dapat mengamati bahwa x − x0 = 0 mod p tetapi x − x0 6 = 0 mod N, dan juga p | (x − x0) tetapi N6 | (x − x0). Tetapi ini berarti bahwa gcd (x − x0, N) = p, merupakan faktor non-sepele dari N.

Bagaimana kita dapat menemukan pasangan yang baik? Katakanlah kita memilih nilai x1, ..., xk secara independen dan seragam secara acak dari , dimana k==O(. Perhatikan itu :

·         Dengan aplikasi langsung dari Lemma A.9, probabilitas yang ada

Beda i, j dengan xi = xj paling banyak ==0()

yang dapat diabaikan dalam n.

·         Sebagai konsekuensi dari bijektivitas antara  dan x dijamin oleh teorema sisa Cina nilai{[mod p]}m = 1 didistribusikan secara independen dan seragam dalam Z ∗ p Menggunakan Lemma A.10, probabilitas bahwa ada i, j dengan [mod p] adalah kira-kira 1/4.

Menggabungkan di atas, kita melihat bahwa dengan probabilitas kira-kira 1/4 akan ada i, j dengan xi, xj pasangan yang baik yaitu,

xi = xj mod p but xi 6= xj mod N.

Pasangan ini kemudian dapat digunakan untuk menemukan faktor N non-sepele seperti yang dibahas sebelumnya. Kita dapat menghasilkan k=0( elemen acak dari  di 0(  waktu. Akan tetapi, menguji semua pasangan elemen untuk menemukan pasangan yang baik (0 ()=0(p)=0() waktu. Tanpa optimasi lebih lanjut, ini tidak akan lebih baik dari pembagian percobaan.

Pollard'sidea adalah untuk memilih x1, ..., xk, ..., x2k secara rekursif, memilih x1 ∈ Z ∗ N secara acak dan kemudian menghitung xm = F (xm − 1) mod N untuk beberapa fungsi yang sesuai F (Pilihan F dibahas di bawah ini.) Daripada menguji setiap pasangan xi, xj (untuk semua i, j ≤ k) untuk menemukan pasangan yang baik, sekarang cukup untuk menguji xi dan x2i untuk semua i ≤ k seperti dijelaskan dalam mengikuti klaim.

PERSOALAN 8.2Misalkan x1, ... menjadi urutan nilai dengan xm = F (xm − 1) mod N. Katakan xi = xj mod p dengan i <j ≤ k. Lalu ada i0 <j ≤ k sedemikian sehingga xi0 = x2i0 mod p.

BUKTI : Jika xi = xj mod p, maka urutan [xi mod p], [xi + 1 mod p], ... berulang dengan periode j −i. (Untuk melihat ini, amati bahwa xm = F (xm − 1) mod p untuk semua m. Jadi xi + δ = xj + δ mod p untuk semua δ ≥ 0 dan kemudian xi = xj = xi + (j − i) = xj + (j − i) mod p.) Ambil i0 menjadi kelipatan terkecil dari j −i yang lebih besar dari atau sama dengan i; yaitu, i0 def = (j −i) · di / (j − i) e. Kita harus memiliki i0 <j karena ini i, i + 1, ... i + (j − i − 1) berisi kelipatan j − i. Karena 2i0 − i0 = i0 adalah kelipatan dari periode dan i0 ≥i, maka xi0 = x2i0 mod p.

(Bukti klaim adalah alasan algoritma disebut "rho," karena urutan berulang menyarankan huruf Yunani ρ seperti yang ditunjukkan pada Gambar ??.) Dengan klaim di atas, jika ada pasangan yang baik xi, xj di urutan x1, ..., xk maka ada pasangan xi0 yang baik, x2i0 dalam urutan x1, ..., x2k. Namun, jumlah pasangan yang perlu diuji dikurangi darik2 menjadi k = O (√p) = O (N1 / 4). Deskripsi keseluruhan algoritma berikut :

 

ALGORITHM 8.3 Algoritma rho Pollard untuk anjak piutang

Input: Integer N Output: A non-trivial factor of x0 ← Z∗ N  for i = 1 to 2n/2:  xi := [F(xi−1) mod N] x2i := [F(F(x2i−2)) mod N]  p := gcd(x2i −xi,N) if p 6∈{1,N} return p

 

Pilihan Pollard tentang x1, ... mengarah pada peningkatan waktu berjalan algoritme. Sayangnya, karena nilai-nilai dalam urutan tidak lagi dipilih secara independen secara acak, analisis yang diberikan sebelumnya (menunjukkan bahwa pasangan yang baik ada dengan probabilitas kira-kira 1/4) tidak lagi berlaku. Namun secara heuristik, jika urutan "berperilaku secara acak" maka kami berharap bahwa pasangan yang baik masih akan ditemukan dengan probabilitas sekitar 1/4. (Kami menekankan bahwa urutannya tentu saja bukan pseudorandom dalam arti Bab 3. Namun, pseudorandomness kriptografis bukanlah syarat yang diperlukan untuk algoritma rho Pollard untuk berhasil.) Mengambil F dari bentuk F (x) = x2 + b, di mana b 6 = 0, mod2 mod N, memberikan F yang efisien untuk dihitung dan tampaknya bekerja dengan baik dalam latihan. (Lihat [127, Bagian 10.2] untuk beberapa alasan untuk pilihan F. ini.) Masih merupakan pertanyaan terbuka yang menarik untuk memberikan analisis yang ketat dan teliti tentang algoritma r Pollard's Polling untuk setiap F. beton.