Nama : Evi Nurmala
NIM : 17.01.071.029
Mata Kuliah : KRIPTOGRAFI
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.3 Algoritma Saringan Quadratic
Algoritma
Pollard rho berjalan dalam waktu eksponensial dalam panjang angka N yang akan
diperhitungkan. Algoritma kuadratik berjalan dalam waktu sub-eksponensial. Ini
adalah algoritma anjak piutang yang paling cepat diketahui hingga awal tahun
90-an, dan tetap merupakan algoritma anjak pilihan untuk angka hingga sekitar
300 bit. Pada bagian ini, kami menjelaskan prinsip-prinsip umum yang mendasari
algoritma ayakan kuadratik tetapi mengingatkan pembaca bahwa banyak detail penting
dihilangkan. Ingatlah bahwa
elemen z ∈ Z ∗ N adalah modulo residu kuadratik jika ada.ada
x ∈
Z ∗
p sehingga x2 = z mod N; kita katakan x adalah akar kuadrat dari z dalam kasus
ini. Pengamatan berikut, digunakan juga dalam Bab 11, berfungsi sebagai titik
awal kami:
•
Jika N = pq adalah produk dari dua bilangan prima yang berbeda, maka setiap
modulo kuadrat residu memiliki tepat empat akar kuadrat. Lihat Bagian 11.1.2
untuk bukti.
•
Diberikan x, y dengan x2 = y2 mod N dan x 6 = ± y mod N, dimungkinkan untuk
menghitung dalam waktu polinomial faktor non-sepele dari N. Ini berdasarkan
fakta bahwa x2 = y2 mod N menyiratkan
0 = x2 −y2 = (x−y)(x + y) mod N,
dan begitu N | (x − y) (x + y). Di
sisi lain, N6 | (x − y) dan N6 | (x + y) karena x 6 = ± y mod N. Jadi itu harus
menjadi kasus yang gcd (x − y, N) sama dengan salah satu faktor utama N. Lihat
juga Lemma 11.20.
Algoritma
kuadratik mencoba menghasilkan sepasang nilai x, y yang kuadratnya sama dengan
modulo N; harapannya adalah bahwa dengan probabilitas konstan juga akan
menyatakan bahwa x 6 = ± y mod N. Ini mencari x dan y melalui proses dua
langkah sebagai berikut:
Langkah
1. Perbaiki himpunan B = {p1, ..., pk} dari bilangan prima kecil. Temukan `>
k nilai yang berbeda x1, ..., x` ∈
Z ∗
N yang qi def = [x2 i mod N] adalah" kecil ", sehingga qi dapat
difaktorkan ke bilangan bulat (menggunakan, misalnya, pembagian percobaan ) dan
sedemikian rupa sehingga semua faktor utama qi terletak pada B. (Diperlukan
pula xi> √n, jadi x2i> n dan reduksi modular x2i tidak sepele.) Kami
mengabaikan detail bagaimana ini { xi} ditemukan.
Mengikuti langkah ini, kami memiliki seperangkat persamaan bentuk:
Melihat
hanya pada eksponen dari masing-masing modulo pi 2, kita memperoleh matriks
Tujuannya
adalah untuk memiliki `> k dengan tidak ada deretan Γ semua 0. Setelah ini
selesai, lanjutkan ke langkah berikutnya.
Langkah
2. Matriks Γ yang dibangun pada langkah sebelumnya memiliki lebih banyak baris
daripada kolom. Oleh karena itu, beberapa bagian dari baris harus dijumlahkan
ke semua-0 modulo 2. (Selanjutnya, dengan konstruksi, Γ tidak memiliki semua-0
baris.) Satu set baris
yang
tepat dapat ditemukan secara efisien menggunakan aljabar linier. Demi
ilustrasi, ucapkan baris `1,` 2, `3 jumlah ke semua-0 baris; itu adalah,
di mana
penambahan adalah modulo 2. Mengambil persamaan yang sesuai dari Persamaan
(8.3), kita miliki
Selain
itu, dengan pilihan `1,` 2, `3 kita tahu bahwa e`1, i + e`2, i + e`3, i bahkan
untuk semua i. Ini artinya kita bisa menulis
dan
kami telah menemukan dua elemen yang kotaknya sama modulo N. Meskipun
tidak
ada jaminan bahwa x`1 · x`2 · x`3 6 = ± Qk i = 1 p
(e`1,
i + e`2, i + e`3, i) / 2 i mod N, kita setidaknya dapat secara heuristik
berharap bahwa ini akan menjadi kasus dengan probabilitas sekitar 1/2 (karena X
memiliki empat akar kuadrat ).
Contoh 8.4
Ambil
N = 377753. Kami memiliki 6647 = [6202 mod N], dan kami dapat memfaktorkan 6647
(lebih dari bilangan bulat, tanpa pengurangan modular) sebagai
6647 = 172 ·23
Dengan
demikian, 6202 = 172 · 23 mod N. Demikian pula,
6212
= 24 ·17·29 mod N
6452 = 27 ·13·23 mod N
6552 = 23 ·13·17·29 mod N.
Jadi,
6202
·6212 ·6452 ·6552 = 214 ·132 ·174 ·232 ·292 mod N
⇒ (620·621·645·655 mod N)2 =27
·13·172 ·23·29 mod N2 mod N
⇒ 1271942 =
453352 mod N,
dengan 127194 6 = ± 45335 mod N.
Computing gcd (127194−45335, 377753) = 751 menghasilkan faktor non-sepele N.
Durasi.
Kami telah menghilangkan banyak
detail dalam diskusi kami tentang algoritma di atas. Akan tetapi, dapat diperlihatkan
bahwa dengan optimasi yang tepat, algoritma ayakan kuadrat berjalan dalam waktu
2O (·n · log n) untuk memasukkan faktor sejumlah N lengthO (n). Poin penting
adalah bahwa waktu berjalan ini adalah sub-eksponensial dalam panjang N.
