kriptografi - Asumsi dalam Grup Siklik

KRIPTOGRAFI

Nama               : Fikri Nuryansah

NIM                : 17.01.071.037
kelas               : Teknik Informatika A 2017
Prodi              : Teknik Informatika
Link                : www.uts.ac.id

Kelompok 7

Asumsi dalam Grup Siklik

Pada bagian ini kami memperkenalkan kelas asumsi kekerasan kriptografi dalam kelompok siklik. Pertama-tama kita akan mendiskusikan latar belakang yang diperlukan.

Grup dan Generator Siklik

G adalah merupakan anggota daroi group  m. Untuk g  G , pertimbangan set

Dengan Teorema 7.14, kita memiliki gm = 1. Biarkan aku menjadi bilangan bulat positif terkecil untuk mana gi = 1. Kemudian urutan di atas berulang setelah istilah i (mis., gi = g0, gi + 1 = g1, dll.), dan sebagainya hgi =

g0; :::; gi  1:

Kita melihat bahwa hgi mengandung paling banyak elemen i. Bahkan, isinya persis ielemen karena jika gj = gk dengan 0 j <k <i maka gk  j = 1 dan 0 <k   j <i, bertentangan dengan pilihan kami tentang i. Tidak terlalu sulit untuk memverifikasi bahwa hgi adalah subkelompok G untuk setiap g (lihat Latihan 7.3); hgi disebut subkelompok yang dihasilkan oleh g. Jika urutan subkelompok hgi adalah i, maka saya disebut urutan g; itu adalah:

DEFINISI 7.48 Misalkan G adalah grup nite dan g 2 G. Urutan g adalah bilangan bulat positif terkecil saya dengan gi = 1. Berikut ini adalah analog yang berguna dari Corollary 7.15 (buktinya identik): PROPOSISI 7.49 Misalkan G adalah grup nite, dan g 2 G elemen memesan saya. Kemudian untuk sembarang bilangan bulat x, kita memiliki gx = g [x mod i]. Kami benar-benar dapat membuktikan sesuatu yang lebih kuat.

PROPOSISI 7.50 Misalkan G adalah grup nite, dan g 2 G elemen memesan saya. Kemudian gx = gy jika dan hanya jika x = y mod i.

BUKTI Jika x = y mod i maka [x mod i] = [y mod i] dan proposisi sebelumnya mengatakan itu gx = g [x mod i] = g [y mod i] = gy:

Untuk arah yang lebih menarik, ucapkan gx = gy. Biarkan x0 = [x mod i] dan y0 = [y mod i]; proposisi sebelumnya memberitahu kita bahwa gx0 = gy0 atau, secara setara, gx0 (Gy0 )   1 = 1. Jika x0 6 = y0, kita dapat mengasumsikan tanpa kehilangan generalitas itu x0> y0; karena x0 dan y0 lebih kecil dari i, maka perbedaan x0    y0 adalah bilangan bulat bukan nol yang lebih kecil dari I.

1 = gx0__gy0_􀀀1= gx0􀀀y0;

bertentangan dengan fakta bahwa saya adalah urutan g.

Elemen identitas dari setiap grup G memiliki urutan 1, menghasilkan grup h1i = f1g, dan merupakan satu-satunya elemen urutan 1. Pada ekstrem yang lain, if

ada elemen g 2 G yang memiliki urutan m (di mana m adalah urutan G), lalu hgi = G. Dalam hal ini, kami menyebut G sebagai grup siklik dan mengatakan bahwa g adalah generator G. (Perhatikan bahwa grup siklik akan memiliki beberapa generator, dan jadi kita tidak dapat berbicara tentang generator.) Jika g adalah generator dari G maka, oleh definisi, setiap elemen h 2 G sama dengan gx untuk beberapa x 2 f0; :::; m   1g, a titik kita akan kembali ke pada bagian selanjutnya. Elemen yang berbeda dari grup G yang sama mungkin memiliki pesanan yang berbeda. Kita dapat, namun, berikan beberapa batasan pada kemungkinan pesanan ini.

PROPOSISI 7.51 Misalkan G adalah grup n dari urutan m, dan katakanlah g 2 G telah memesan saya. Lalu aku jm.

BUKTI Menurut Teorema 7.14 kita tahu bahwa gm = 1. Karena g memiliki urutan i, kami memiliki gm = g [m mod i] dengan Proposisi 7.49. Jika saya tidak membagi m, maka i0 def = [m mod i] adalah bilangan bulat positif yang lebih kecil dari i untuk yang gi0 = 1. Sejak saya adalah urutan g, ini tidak mungkin. Akibat wajar berikutnya menggambarkan kekuatan hasil ini:

COROLLARY 7.52 Jika G adalah sekelompok orde prima p, maka G adalah siklik.

Lebih lanjut, semua elemen G kecuali identitasnya adalah generator G.

BUKTI Dengan Proposisi 7.51, satu-satunya urutan unsur yang mungkin ada di G 1 dan p. Hanya identitas yang memiliki urutan 1, dan semua elemen lainnya memilikinya memesan p dan menghasilkan G.

Kelompok orde utama membentuk satu kelas kelompok siklik. Grup aditif ZN, untuk N> 1, memberikan contoh lain dari grup siklik (elemen 1 adalah selalu generator). Teorema berikutnya memberikan kelas tambahan penting kelompok siklik; bukti di luar ruang lingkup kami, tetapi dapat ditemukan dalam standar apa pun teks aljabar abstrak.

THEOREM 7.53 Jika p adalah prima maka Z p adalah siklik.

Untuk p> 3 prime, Zp tidak memiliki pesanan utama dan jadi di atas tidak ikuti dari akibat wajar sebelumnya. Beberapa contoh akan membantu menggambarkan diskusi sebelumnya.

Contoh 7.54

Pertimbangkan grup Z15. Seperti yang telah kita catat, Z15 adalah siklik dan elemennya `1 'adalah generator karena 15 1 = 0 mod 15 dan i0 1 = i0 6 = 0 mod 15 untuk semua 0 <i0 <15. Z15 memiliki generator lain. E.g., h2i = f0; 2; 4; . . . , 14; 1; 3; 5,. . . , 13g dan jadi 2 juga generator.

Tidak setiap elemen menghasilkan Z15. Misalnya, elemen `3 'memiliki urutan 5 karena 5 3 = 0 mod 15, dan 3 tidak menghasilkan Z15. Subkelompok h3i terdiri dari 5 elemen f0; 3; 6; 9; 12g, dan ini memang merupakan subkelompok di bawah Selain modulo 15. Elemen `10 'memiliki urutan 3 sejak 3 10 = 0 mod 15, dan h10i subkelompok terdiri dari 3 elemen f0; 10; 20g. Perhatikan bahwa 5 dan 3 keduanya bagikan jZ15j = 15 seperti yang dipersyaratkan oleh Proposisi 7.51. }

Contoh 7.55

Pertimbangkan grup Z 15 dengan urutan (5  1) (3  1) = 8. Kami memiliki h2i = f1; 2; 4; 8g, dan urutan 2 adalah 4. Sebagaimana disyaratkan oleh Proposisi 7.51, 4 membagi 8.

Contoh 7.56

Pertimbangkan grup Zp pesanan utama h. Kami tahu grup ini adalah siklik, tetapi Konsekuensi 7,52 memberi tahu kita lebih banyak: yaitu, bahwa setiap elemen kecuali 0 adalah generator.

Memang, untuk elemen g2 f1; :::; p    1g dan integer i> 0 yang kita miliki ig = 0 mod p i p j ig. Tetapi kemudian Proposisi 7.3 mengatakan bahwa p j g atau p j i.

Yang pertama tidak dapat terjadi (karena g <p), dan bilangan bulat positif terkecil untuk yang terakhir dapat terjadi adalah i = p. Dengan demikian kami telah menunjukkan bahwa setiap non-nol

elemen g memiliki urutan p (dan menghasilkan Zp), sesuai dengan Corollary 7.52.}

Contoh 7.57

Pertimbangkan grup Z 7, yang merupakan siklus menurut Teorema 7.53. Kami memiliki h2i = f1; 2; 4g, dan 2 bukan generator. Namun, h3i = f1; 3; 2; 6; 4; 5g = Z 7; dan 3 adalah generator Z 7. }

Berikut ini menunjukkan bahwa semua kelompok siklik dari urutan yang sama, dalam beberapa akal, sama.

Contoh 7.58

Biarkan G menjadi kelompok siklik dari urutan n, dan biarkan g menjadi generator G. Kemudian pemetaan f: Zn! G yang diberikan oleh f (a) = ga adalah isomorfisme antara Zn dan G. Memang, untuk; a0 2 Zn yang kita miliki f (a + a0) = g [a + a0 mod n] = ga + a0 = ga ga0 = f (a) f (a0):

Bijektivitas f dapat dibuktikan dengan menggunakan fakta bahwa n adalah urutan g. }

Kami menekankan bahwa sementara hal di atas benar dalam pengertian teori-kelompok, itu tidak benar dalam arti komputasi. Artinya, meskipun (misalnya) Zp , untuk p prime, adalah isomorfik ke grup Zp  1, kompleksitas komputasi operasi di dua kelompok ini mungkin sangat berbeda.

7.3.2 Logaritma Terpisah dan Asumsi Di e-Hellman- tions

Kami sekarang memperkenalkan sejumlah masalah komputasi yang dapat didefinisikan untuk setiap kelas kelompok siklik. Kami akan menyimpan diskusi di bagian ini abstrak, dan pertimbangkan contoh spesifik kelompok di mana masalah ini diyakini sulit di Bagian 7.3.3 dan 7.3.4. Jika G adalah grup siklik dari orde q, maka ada generator g 2 G tersebut bahwa fg0, g1,:::, gq  1g = G. Setara, untuk setiap jam 2 G ada yang unik x 2 Zq sedemikian rupa sehingga gx = h. Dengan cara notasi, ketika kelompok yang mendasarinya G dipahami dari konteks yang kita sebut ini x logaritma diskrit dari h dengan menghormati g dan menulis x = logg h.5 Perhatikan bahwa jika gx0 = h untuk beberapa arbitrer integer x0, lalu logg h = [x0 mod q]. Logaritma diskrit mematuhi banyak aturan yang sama dengan logaritma \ standar ".

Misalnya, logg 1 = 0 (di mana `1 'adalah identitas G) dan logg (h1 h2) = [(logg h1 + logg h2) mod q].

Masalah logaritma diskrit dalam kelompok siklik G dengan generator yang diberikan g adalah untuk menghitung logg h diberikan elemen acak h 2 G sebagai input. Secara formal, biarkan G menjadi algoritma waktu polinomial yang, pada input 1n, menghasilkan a (deskripsi dari a) grup siklik G, urutannya q (dengan kqk = n), dan generator g 2 G.

Kami juga mensyaratkan bahwa operasi grup di G dapat dihitung secara efisien (yaitu, dalam polinomial waktu dalam n). Pertimbangkan eksperimen berikut untuk a diberikan algoritma A dan parameter n:

Eksperimen logaritma diskrit DLogA; G (n)

1. Jalankan G (1n) untuk mendapatkan output (G; q; g), di mana G adalah siklik kelompok pesanan q (dengan kqk = n) dan g adalah generator G.

2. Pilih h G. (Perhatikan bahwa ini dapat dilakukan dengan memilih x0 Zq dan pengaturan h: = gx0 .)

3. A diberikan G; q; g; h, dan output x 2 Zq.

4. Output percobaan didefinisikan menjadi 1 jika gx = h, dan 0 sebaliknya.