Nama:HAMKA SATRIA PUTRA
Prodi :Teknik
Kelas : Informatika A 2017
NIM    :17.01.071.042
Mata Kuliah : KRIPTOGRAFI
http://www.uts.ac.id

RINGKASAN KELOPOK 7

Teori Angka dan Asumsi Kekerasan Kriptografis 239 modulo N adalah grup abelian dengan urutan N: Penutupan jelas; asosiasi dan komutatif mengikuti dari fakta bahwa bilangan bulat memenuhi sifat-sifat ini; identitasnya adalah 0; dan, karena a + (N −a) = 0 mod N, maka kebalikannya dari setiap elemen a adalah [(N - a) mod N]. Kami menunjukkan kelompok ini dengan Z N . (Kami akan sesekali gunakan Z N juga untuk menunjukkan set {0, ..., N - 1} tanpa memperhatikan operasi tertentu.)
♦
Kami mengakhiri bagian ini dengan lemma mudah yang memformalkan hukum celation ”untuk kelompok.

Misalkan G adalah grup dan a, b, c ∈ G. Jika ac = bc, maka a = b.Secara khusus, jika ac = c maka a adalah identitas dalam G.
BUKTI
Kita tahu ac = bc. Mengalikan kedua sisi dengan invers unik c −1 dari c, kita mendapatkan a = b. Dalam detail yang luar biasa: a = a · 1 = a (c · c −1 ) = (ac) c −1 = (bc) c −1 = b (c · c −1 ) = b · 1 = b. Bandingkan bukti di atas dengan pembahasan (sebelumnya Proposisi 7.7) membuat undang-undang pembatalan untuk modulo divisi N. Seperti yang ditunjukkan oleh sim- ilaritas, elemen-elemen yang dapat dibalik modulo N membentuk sebuah grup dengan multiplikasi modulo N. Kami akan segera kembali ke contoh ini secara lebih rinci. Eksponen Kelompok
Seringkali berguna untuk menggambarkan operasi kelompok yang diterapkan m kali ke elemen tetap g, di mana m adalah bilangan bulat positif. Saat menggunakan aditif notasi, kami menyatakan ini sebagai m · g atau mg; itu adalah, mg = m · g def = g + ··· + g ︸︷︷︸ m kali. Perhatikan bahwa m adalah bilangan bulat, sedangkan g adalah elemen grup. Jadi mg tidak mewakili operasi grup diterapkan ke m dan g (memang, kami bekerja dalam sebuah grup di mana operasi grup ditulis secara aditif). Untungnya, bagaimanapun, itu notasi "berperilaku sebagaimana mestinya"; jadi, misalnya, jika g ∈ G dan m, m adalahbilangan bulat lalu (mg) + (mg) = (m + m) g, m (mg) = (mm) g, dan 1 · g = g. Di kelompok abelian G dengan g, h ∈ G, (mg) + (mh) = m (g + h).Saat menggunakan notasi multiplikasi, kami menyatakan aplikasi grup operasi m kali ke elemen g oleh g m . Itu adalah  g m def = g ··· g ︸︷︷︸ m kali.


240
Pengantar Kriptografi ModernAturan akrab eksponensial terus: g m · g m = g m + m , (g m ) m = g mm ,dan g 1 = g. Juga, jika G adalah grup abelian dan g, h ∈ G maka g m · h m = (gh) m .Perhatikan bahwa semua hasil ini hanyalah "terjemahan" dari hasil yang dinyatakan dalam paragraf sebelumnya dengan pengaturan kelompok yang ditulis lebih dari satudaripada aditif.Notasi di atas diperluas ke kasus ketika m adalah nol atau negative bilangan bulat dengan cara alami. (Secara umum, kita membiarkan g r tidak terdefinisi jika r bukaninteger.) Saat menggunakan notasi aditif, kita memiliki 0 · gdef= 0 dan (−m) · gdef=m · (−g) untuk bilangan bulat positif. (Perhatikan bahwa dalam persamaan '0 · g = 0''0' di sisi kiri adalah bilangan bulat 0 sedangkan '0' di sisi kananadalah elemen identitas dalam grup.) Seperti yang diharapkan, ini dapat ditampilkanitu (−m) · g = - (mg). Saat menggunakan notasi multiplikasi, g 0 def= 1 dang defm def= (g −1 ) m . Sekali lagi, seperti yang diharapkan, orang dapat menunjukkan bahwa g −m = (g m ) −1 .Misalkan g ∈ G dan b ≥ 0 menjadi bilangan bulat. Kemudian exponentiation g b dapatdihitung menggunakan jumlah polinomial operasi grup yang mendasarinya di G.Jadi, jika operasi grup dapat dihitung dalam waktu polinomial, maka demikiandapat exponentiation. Pengamatan non-sepele ini dibahas dalam Bagian B.2.3.Kami sekarang cukup tahu untuk membuktikan hasil luar biasa berikut:
THEOREM 7.14
Biarkan G menjadi grup hingga dengan m = | G |, urutankelompok. Maka untuk setiap elemen g ∈ G, g m = 1.
BUKTI
Kami membuktikan teorema hanya ketika G adalah abelian (meskipun itu berlakuuntuk grup terbatas). Perbaiki sembarang g ∈ G, dan biarkan g 1 , ..., g m menjadi elemendari G. Kami mengklaim itug 1 · g 2 ··· g m = (gg 1 ) · (gg 2 ) ··· (gg m ).Untuk melihat ini, perhatikan bahwa gg i = gg j menyiratkan g i = g j oleh Lemma 7.13. Jadi masing-masingelemen m dalam tanda kurung di sisi kanan persamaan yang ditampilkan adalahberbeda. Karena ada elemen m dalam G, elemen m adalahdikalikan bersama di sisi kanan adalah semua elemen G di
beberapa pesanan yang diijinkan. Karena G adalah abelian urutan di mana semua elemenkelompok dikalikan tidak masalah, sehingga sisi kanan samake sisi kiri.Sekali lagi menggunakan fakta bahwa G adalah abelian, kita dapat "menarik" semua kejadiang dan dapatkang 1 · g 2 ··· g m = (gg 1 ) · (gg 2 ) ··· (gg m ) = g m · (g 1 · g 2 ··· g m ).Menarik sekali lagi untuk Lemma 7.13, ini berarti g m = 1.Sebuah konsekuensi penting dari hal di atas adalah bahwa kita dapat bekerja “modulo gruppesan dalam eksponen ”:


Teori Angka dan Asumsi Kekerasan Kriptografis
241
COROLLARY 7.15
Biarkan G menjadi grup hingga dengan m = | G | > 1. Lalu untukg ∈ G dan integer i, kami memiliki g i = g [i mod m] .
BUKTI
Katakanlah i = qm + r, di mana q, r adalah bilangan bulat dan r = [i mod m]. Menggunakan
Teorema 7.14,
g i = g qm + r = g qm · g r = (g m ) q · g r = 1 q · g r = g r ,seperti yang diklaim.
Contoh 7.16
Ditulis secara tambahan, akibat wajar di atas mengatakan bahwa jika g adalah elemen dalam grupdari pesanan m, maka i · g = [i mod m] · g. Sebagai contoh, perhatikan grup Z 15dari order m = 15, dan ambil g = 11. Konsekuensi wajarnya mengatakan itu152 · 11 = [152 mod 15] · 11 = 2 · 11 = 11 + 11 = 22 = 7 mod 15.Hal di atas persis sesuai dengan fakta (lih. Contoh 7.5) yang dapat kita “kurangidan kemudian berkembang biak "daripada harus" memperbanyak dan kemudian mengurangi. "
♦Konsekuensi lain yang akan sangat berguna untuk aplikasi kriptografitions adalah sebagai berikut:
COROLLARY 7.17
Biarkan G menjadi grup hingga dengan m = | G | > 1. Biarkane> 0 menjadi bilangan bulat, dan mendefinisikan fungsi f e : G → G dengan f e (g) = g e . Jikagcd (e, m) = 1, maka f e adalah permutasi. Selain itu, jika d = [e −1 mod m] makaf d adalah kebalikan dari f e .
BUKTI
Dengan Proposisi 7,7, gcd (e, m) = 1 menyiratkan bahwa e tidak dapat dibalikmodulo m, dan jadi e −1 mod m ada. Bagian kedua dari klaim menyiratkanyang pertama, jadi kita hanya perlu menunjukkan bahwa f d adalah kebalikan dari f e . Ini benar karenauntuk setiap g ∈ G yang kita milikif d (f e (g)) = f d (g e ) = (g e ) d = g ed = g [ed mod m] = g 1 = g,di mana kesetaraan ketiga ke terakhir mengikuti dari wajar 7.15.
7.1.4 Grup Z ∗ N dan Teorema Sisa TiongkokSeperti dibahas dalam Contoh 7.12, set Z N = {0, ..., N - 1} adalah grupdi bawah tambahan modulo N. Bisakah kita mendefinisikan struktur grup di set{0, ..., N −1} sehubungan dengan multiplikasi modulo N? Jelas, '1' akan dimilikimenjadi identitas. Kita tahu bahwa tidak setiap elemen dalam himpunan ini dapat dibalik;

Pengantar Kriptografi Modernmisalnya, '0' jelas tidak memiliki invers multiplikasi. Ini bukan satu-satunyamasalah potensial: jika N = 6, maka '3' tidak dapat dibalik seperti yang dapat dibuktikan olehsecara mendalam mencoba setiap kemungkinan.
Elemen mana a ∈ {0, ..., N - 1} yang dapat diubah modulo N? Proposal-tion 7.7 mengatakan bahwa ini terjadi jika dan hanya jika gcd (a, N) = 1. Kita juga telah melihatdi Bagian 7.1.2 bahwa setiap kali a dapat dibalik, ia memiliki kebohongan terbalik dirange {0, ..., N - 1}. Ini mengarahkan kita untuk mendefinisikan, untuk N> 1, himpunanZ ∗ N def= {a ∈ {1, ..., N - 1} | gcd (a, N) = 1}(yaitu, Z ∗ N terdiri dari bilangan bulat di set {1, ..., N −1} yang relatif primake N) dengan operasi biner terkait modulo perkalian N.Kami mengklaim bahwa Z ∗ N , sehubungan dengan operasi ini, adalah grup. Diskusidi atas menunjukkan bahwa Z ∗ N memiliki identitas, dan setiap elemen dalam himpunan ini memilikikebalikan multiplikasi dalam set yang sama. Komutatif dan asosiatifikuti dari fakta bahwa properti ini menahan bilangan bulat. Memperlihatkanbahwa penutupan memegang, biarkan a, b ∈ Z * N , biarkan c = [ab mod N], dan menganggap c ∈ Z * N .Ini berarti gcd (c, N) = 1, dan dengan demikian ada p utama yang membagi keduanyaN dan c. Karena ab = qN + c untuk beberapa integer q, kita melihat bahwa p | ab. OlehProposisi 7.3, ini berarti p | a atau p | b; tapi kemudian gcd (a, N) = 1 atauFPB (b, N) = 1, bertentangan asumsi kita bahwa a, b ∈ Z * N .
Meringkas:
PROPOSISI 7.18
Biarkan N> 1 menjadi bilangan bulat. Maka Z ∗ N adalah abeliangrup dalam modul multiplikasi N.Tentukan φ (N)def= | Z ∗ N |, urutan grup Z ∗ N (φ disebut Euler phifungsi). Berapa nilai φ (N)? Pertama-tama pertimbangkan kasus ketika N = putama. Maka semua elemen dalam {1, ..., p - 1} relatif prima untuk p, dan seterusnyaφ (p) = | Z ∗ p | = p - 1. Selanjutnya perhatikan kasus N = pq, di mana p, q berbedabilangan prima. Jika bilangan bulat a ∈ {1, ..., N - 1} relatif tidak prima dari N, makabaik p | a atau q | a (a tidak dapat dibagi oleh p dan q karena ini akan berartipq | a tetapi a <N = pq). Elemen-elemen dalam {1, ..., N - 1} dapat dibagi dengan p adalahpersis (q − 1) elemen p, 2p, 3p, ..., (q − 1) p, dan elemen-elemen dapat dibagi denganq persis elemen (p - 1) q, 2q, ..., (p - 1) q. Jumlah elementersisa (yaitu, mereka yang tidak dapat dibagi oleh p atau q) karena itu diberikan olehN - 1 - (q - 1) - (p - 1) = pq - p - q + 1 = (p - 1) (q - 1).Kami telah membuktikan bahwa φ (N) = (p - 1) (q - 1) ketika N adalah produk daridua bilangan prima berbeda p dan q.Anda diminta untuk membuktikan hasil umum berikut dalam Latihan 7.4:
THEOREM 7.19
Biarkan N = ∏ i p e I  , di mana {p i } adalah bilangan prima dan berbedae i ≥ 1. Lalu φ (N) = ∏ i p e i −1 Saya(hal i - 1).


Teori Angka dan Asumsi Kekerasan Kriptografis
243
Contoh 7.20
Ambil N = 15 = 5 · 3. Kemudian Z ∗ 15 = {1, 2, 4, 7, 8, 11, 13, 14} dan | Z ∗ N | = 8 = 4 · 2 = φ (15). Kebalikan dari 8 dalam Z ∗ N adalah 2, karena 8 · 2 = 16 = 1 mod 15.
♦
Kami telah menunjukkan bahwa Z ∗ N adalah sekelompok pesanan φ (N). Berikut ini sekarang akibat wajar mudah dari Teorema 7.14 dan Konsekuensi 7.17:
COROLLARY 7.21
Ambil sewenang-wenang N> 1 dan ∈ Z * N . Kemudian a φ (N) = 1 mod N. Untuk kasus khusus ketika N = p adalah prima dan ∈ {1, ..., p - 1}, kita milikia p − 1 = 1 mod p.
COROLLARY 7.22
Perbaiki N> 1. Untuk bilangan bulat e> 0 define f e : Z ∗ N → Z ∗ N oleh f e (x) = x e mod N. Jika e relatif prima ke φ (N) maka f e adalah permutasi. Selain itu, jika d = [e −1 mod φ (N)] maka f d adalah kebalikan dari f e . Isomorfisme Kelompok Isomorfisme suatu kelompok G memberikan cara alternatif, tetapi setara memikirkan tentang G.
DEFINISI 7.23
Biarkan G, H menjadi kelompok sehubungan dengan operasi ◦ G , ◦ H , masing-masing. Fungsi f: G → H adalah isomorfisme dari G ke H jika
(1) f adalah sebuah penambangan; (2) untuk semua g 1 , g 2 ∈ G kita memiliki f (g 1 ◦ G g 2 ) = f (g 1 ) ◦ H f (g 2 ). Jika ada isomorfisme dari G ke H maka kita katakan kelompok ini isomorfik dan tulis ini sebagai G ≃ H.Perhatikan bahwa jika G adalah terbatas dan G ≃ H, maka H harus terbatas dan memiliki yang samaukuran sebagai G. Juga, jika ada isomorfisma f dari G ke H maka f −1 adalah isomorfisme dari H ke G. Tujuan dari bagian ini adalah untuk menggunakan bahasa isomorfisma untuk lebih baik memahami struktur kelompok Z N dan Z * N ketika N = pq adalah produk dari
dua bilangan prima yang berbeda. Pertama-tama kita perlu memperkenalkan gagasan tentang produk silang kelompok. Diberikan grup G, H dengan operasi grup ◦ G , ◦ H masing-masing, kami dapat mendefinisikan grup baru G × H (produk silang dari G dan H) sebagai berikut. Itu melemen G × H adalah pasangan berurutan (g, h) dengan g ∈ G dan h ∈ H; jadi, jika G memiliki n elemen dan H memiliki n elemen, G × H memiliki nn elemen. Grup
operasi ◦ pada G × H diterapkan berdasarkan komponen; itu adalah: (g, h) ◦ (g, h) def= (g ◦ G g, h ◦ H h). Kita serahkan pada Latihan 7.5 untuk memverifikasi bahwa G × H memang sebuah kelompok.


Pengantar Kriptografi Modern
Notasi di atas dapat diperluas untuk melintasi produk lebih dari dua berkelompok dengan cara alami, meskipun kita tidak membutuhkan ini untuk apa yang mengikuti. Kita sekarang dapat menyatakan dan membuktikan teorema sisa Tiongkok. THEOREM 7.24 (Teorema Sisa Tiongkok)
Misalkan N = pq di mana p dan q relatif prima. Kemudian Z N ≃ Z p × Z qdan Z ∗ N ≃ Z ∗ p × Z ∗ q . Selain itu, misalkan f menjadi elemen pemetaan fungsi x ∈ {0, ..., N - 1} untuk berpasangan(x p , x q ) dengan x p ∈ {0, ..., p - 1} dan x q ∈ {0, ..., q - 1} didefinisikan oleh f (x) = ([x mod p], [x mod q]). Maka f adalah isomorfisme dari Z N sampai Z p × Z q serta 2 isomorfisma dari Z ∗ N ke Z ∗ p × Z ∗ q .
BUKTI
Jelas bahwa untuk setiap x ∈ Z N output f (x) adalah sepasang elemen (x p , x q ) dengan x p ∈ Z p dan x q ∈ Z q . Selanjutnya, kami mengklaim bahwa jikax ∈ Z ∗ N lalu (x p , x q ) ∈ Z ∗ p × Z ∗ q . Memang, jika (katakanlah) x p ∈ Z ∗ p maka ini berarti itu gcd ([x mod p], p) = 1. Tetapi kemudian gcd (x, p) = 1. Ini menyiratkan gcd (x, N) = 1, bertentangan dengan asumsi bahwa x ∈ Z * N . Kami sekarang menunjukkan bahwa f adalah isomorfisme dari Z N ke Z p × Z q . (Buktinya itu adalah isomorfisme dari Z ∗ N ke Z ∗ p × Z ∗ q serupa.) Mari kita mulai dengan membuktikan bahwa f adalah satu-ke-satu. Katakan f (x) = (x p , x q ) = f (x). Kemudian x = x p = x mod p dan x = x q = x mod q. Ini pada gilirannya menyiratkan bahwa (x - x) dapat dibagi oleh p dan q. Karena gcd (p, q) = 1, Proposisi 7.4 mengatakan bahwa pq = N membelah (x − x). Tapi kemudian x = x mod N. Untuk x, x ∈Z N , ini berarti bahwa x = x dan jadi f memang satu-ke-satu. Sejak | Z N | = N = p · q = | Z p | · | Z q |, ukuran Z N dan Z p × Z q adalah sama. Ini dikombinasikan dengan fakta bahwa f adalah satu-ke-satu menyiratkan bahwa f bersifat bijektif. Dalam paragraf berikut, misalkan + N , + p , + q menunjukkan penambahan modulo N, mod- ulo p, dan modulo q, masing-masing; misalkan Ш menunjukkan operasi grup dalam Z p × Z q
(yaitu, penambahan modulo p di komponen pertama dan penambahan modulo q di komponen kedua). Untuk menyimpulkan bukti bahwa f adalah isomorfisme dari Z N ke Z p × Z q , kita perlu menunjukkan bahwa untuk semua a, b ∈ Z N menyatakan demikian f (a + N b) = f (a) Ш f (b). Untuk melihat bahwa ini benar, perhatikan itu f (a + N b) = ([(a + N b) mod p], [(a + N b) mod q]) = ([(a + p b) mod p], [(a + q b) mod q]) = ([a mod p], [a mod q]) Ш ([b mod p], [b mod q]) = f (a) Ш f (b). 2 Secara teknis, di sini kami mempertimbangkan pembatasan f ke input dalam Z ∗N .