Additional Public - Key Encryption Schemes (Residu Quadratic Modulo A Composite

Nama : Ari syahwatullah
Nim :17.01.071.013
Mata kuliah : kriptografi
 
                                 
                              Rangkuman

11.1.2 Residu Quadratic Modulo a Composite
 Kita sekarang mengalihkan perhatian kita untuk residukuadrat dalam kelompok Z * N . Arang-Mengolah residukuadratik modulo N mudah jika kita menggunakan bagian sebelumnya dalam hubungannya dengan teorema sisa Cina. Kembali-menyebut bahwa teorema sisa China mengatakan bahwa Z ∗ N ≃ Z ∗ p × Z ∗ q , dan kami biar kan y ↔ (y p , y q ) menunjukkan korespondensi dijamin oleh teorema (yaitu,y p = [y mod p] dan y q = [y mod q]). Pengamatan utama adalah:
PROPOSISIB:B = pq dengan p, q bilangan prima yang berbeda, dan biarkan y ∈ Z ∗ N dengan y ↔ (y p , y q ). Maka y adalah modulo residukuadratik N jika dan hanya jika y p adalah kuadratresidu modulo p dan y q adalah modulo residukuadratik q.
BUKTI Jika y adalah modulo residukuadratik maka, menurut definisi, ada x ∈ Z ∗ N sehingga x 2 = y mod N. Misalkan x↔ (x p , x q ). Kemudian (y p , y q ) ↔ y = x 2 ↔ (x p , x q ) 2 = ([x 2 p mod p], [x 2 q mod q]), di mana (x p ,x q ) 2 hanyalah kuadrat elemen (x p , x q ) dalam grup Z ∗ p × Z ∗ q .Itu adalah ,y p = x 2 p mod p dan y q = x 2 q mod q dan y p , y q adalah kuadratresidu (sehubungan dengan modulus yang sesuai).Sebaliknya, jika y ↔ (y p , y q ) dan y p , y q adalahresidukuadratik modulo p dan q,masing-masing, makaada x p ∈ Z ∗ p dan x q ∈ Z ∗ q sedemikianrupasehinggaPersamaan (11.1)memegang. Misalkan x ∈ Z ∗ N sedemikianrupasehingga x ↔ (x p , x q ). Membalikkan  langkah-langkah di atas menunjukkan bahwa x adalah akarkuadrat dari y.Proposisi di atas mencirikan residukuadratik modulo N. Care-pemeriksaan lengkap dari bukti menghasilkan lebih banyak pada kenyataannya, setiap residukuadratik y ∈ Z ∗ N memiliki empat akar kuadrat. Untuk melihat ini, biarkan y ↔ (y p , y q ) menjadiakuadratresidu modulo N dan membiarkan x p , x q menjadi akar kuadrat dari y p dan y q modulo p dan q, masing-masing. Kemudian empat akar kuadratdari y diberikan oleh (the elemen dalam Z ∗ N terkait dengan) (x p , x q ), (−x p , x q ), (x p , −x q ), (−x p , −x q ).(11.2) Masing-masing adalah akar kuadrat dari sejak itu (± x p , ± x q ) 2 = ([(± x p ) 2 mod p], [(± x q ) 2 mod q]) = ([x 2p mod p], [x 2q mod q]) = (y p , y q ) ↔ y (di mana lagi notasi (·,·) 2 mengacu pada mengkuadratkan dalam grup Z p × Z q ). Teorema sisa Cina menjamin bahwa empat elemen dalam Equation (11.2) masing-masing sesuai dengan elemen Z ∗ N yang berbeda , karena x p dan −x p adalah modulo p unik (dan juga untuk x q dan −x q modulo q).

      Pengantar kriptografi modern
Contoh 11.7
Pertimbangkan Z ∗ 15 (korespondensi yang diberikan oleh teoremasisa China
Ditabulasikan dalam Contoh 7.25). Elemen 4 adalah residukuadratik dengan kuadrat
root 2. Sejak 2 ↔ (2, 2), akar kuadratlainnya dari 4 diberikan oleh
• (2, [−2 mod 3]) = (2, 1) ↔ 3;
• ([−2 mod 5], 2) = (3, 2) ↔ 8; dan
• ([−2 mod 5], [−2 mod 3]) = (3, 1) ↔ 13.
Seseorang dapat memverifikasi bahwa 7 2 = 8 2 = 13 2 = 4 mod 15.
♦ Karena mengkuadratkan modulo N adalah fungsi empat-ke-satu, kita langsung melihat
Bahwa persis 1/4 elemen Z ∗ N adalah residukuadratik. Bergantian,
Kita bisa mencatat bahwa sejak y ∈ Z * N adalah residukuadratik jika dan hanya jika y  p , y q adalah residukuadratik, ada korespondensi satu-ke-satu antara Q R N dan QR p × QR q . Dengan demikian, fraksi residukuadratik modulo N adalah| QR N || Z ∗ N |= | QRp | · | QR q || Z ∗ N |=p − 12· Q − 12(p - 1) (q - 1)=14, Dalam perjanjian dengan yang di atas.Pada bagian sebelumnya, kita mendefinisikan Jacobi simbol J p (x) untuk p> 2 utama. Kami memperluas definisi untuk kasus N = pq produk yang berbeda, bilangan prima ganjil sebagai berikut: untuk setiap x relatif prima ke N, J N (x) def = J p (x) · J q (x) = J p ([x mod p]) · J q ([x mod q]). Kami mendefinisikan J +1 N Sebagai himpunan elemen dalam Z ∗ N yang memiliki simbol Jacobi +1, dan tentukan J −1N secara analog.Kita tahu dari Proposisi 11.6 bahwa jika x adalah modulo residukuadratik, maka [x mod p] dan [x mod q] adalah residukuadratik modulo p dan q, masing-masing secara aktif; yaitu, J p (x) = J q (x) = 1. Jadi J N (x) = +1 dan kami melihatnya jika x adalahkuadratresidu modulo N, maka J N (x) = 1.Namun, J N (x) = +1 juga dapat terjadi ketika  J p (x) = J q (x) = −1; itu adalah, ketika keduanya [x mod p] dan [x mod q] bukan residukuadrat, modulo p dan q(dan jadi x bukan modulo residukuadratik). Ini ternyata bermanfaat untuk skema enkripsi Goldwasser-Micali, dan oleh karena itu kami memperkenalkan notasi QN R +1N untuk himpunan elemen jenis ini ; itu adalah QN R +1N def= {x ∈ Z ∗ N ∣∣∣ J n (x) = +1, tetapi x tidak modulo residukuadratik N} Sekarang mudah untuk membuktikan hal berikut:
PROPOSISI Misalkan N = pqdengan p, q berbeda, bilangan prima aneh.
1. Kemudian  Setengah elemen Z ∗ N berada di J +1N .
2. QR N terkandungdalam J +1N .
3. Tepatsetengahelemen J +1N
Berada dalam Q R N (separuh lainnya berada di QN R +1N ).
BUKTI Kita tahu bahwa J N (x) = +1 jika J p (x) = J q (x) = +1 atau J p (x) = J q (x) = −1. Kami juga tahu (dari bagian sebelumnya) bahwa tepatnya Separuh elemen Z ∗p memiliki simbol Jacobi +1, dan setengahnya memiliki simbol Jacobi−1 (dan juga untuk Z ∗ q ). Mendefinisikan J +1hal, J −1hal, J +1q, dan J −1q di dalam cara, kami memiliki: ∣+ 1J +1N ∣ = | J +1 hal× J +1q| + | J −1hal × J −1q|= | J +1hal| · | J +1q| + | J −1hal| · | J −1q|= (p - 1)2(q - 1)2+ (p - 1)2(q - 1)2=φ(N)2 Jadi∣∣J +1N ∣∣ = | Z ∗ N | / 2, membuktikan bahwa separuh elemen Z ∗ N ada di J +1N .Kami telah mencatat sebelumnya bahwa semua residukuadratik modulo N memiliki Jacobi simbol +1, menunjukkan bahwa QR N ⊆ J +1N .Sejak x ∈ QR N jika dan hanya jika J p (x) = J q (x) = 1, kita memiliki| QR N | = | J +1hal× J +1q| =(p - 1)2(q - 1)2=φ (N)4, Dan sebagainya | QR N | = ∣∣J +1N ∣∣ / 2. Karena QR N adalahbagiandari J +1N , ini membuktikan itu Setengah elemen J +1N berada di Q R N . Dua hasil selanjutnya adalah analog dari Proposisi 11.4 dan Konsekuensi 11.5.