krptografi

Additional Public-Key Encryption Schemes

(SkemaEnkripsiKunciPublikTambahan)

Disusunoleh : 

Arfan jaya

17.01.071.012

Dosen : 

Nawassyarif. S. Kom., M. Pd

PROGRAM STUDI INFORMATIKA

FAKULTAS TEKNIK

UNIVERSITAS TEKNOLOGI SUMBAWA

2020

Bab 11

11.1.4 SkemaEnkripsiGoldwasser-Micali

Bagian sebelumnya segera menyarankan skema enkripsi kunci public untuk pesan bit-tunggal berdasarkan asumsi residuositas kuadratik:

• Kunci public akan menjadi modulus N, dan kunci rahasia akan menjadi faktorisasi N.

• Enkripsi bit '0' akan menjadi residukuadratik acak, dan enkripsi bit '1' akan menjadi non-residukuadrat acak dengan Simbol Jacobi +1.

• Penerima dapat mendekripsi ciphertext c dengan kunci rahasianya dengan menggunakan

faktorisasi N untuk memutuskan apakah c adalah residukuadratik atau tidak keamanan skema ini dalam arti Definisi 10.3 mengikuti hamper sepele dari kesulitan masalah residukuadratik. Satu hal yang hilang dari uraian di atas adalah spesifikasi bagaimana pengirim, yang tidak tahu faktorisasi N, dapat memilih secara acak elemen QR N (jika ingin mengenkripsi 0) atau QN R +1N (kalau-kalau mau Pengantar Kriptografi Modern untuk mengenkripsi 1). Yang pertama ternyata mudah dilakukan, sedangkan yang kedua membutuhkan kecerdikan.Memilih residukuadratik acak. Memilih elemen acak y ∈ QR N mudah: cukup pilih acak x ← Z ∗ N (lihat Bagian B.2.4) danset y: = x 2 mod N. Jelas y ∈ QR N . Y itu acak mengikuti dari fakta bahwa mengkuadratkan modulo N adalah fungsi 4-ke-1 (lihat Bagian 11.1.2) dan x dipilih secara acak. Secara lebih rinci, perbaiki y ∈ QR N dan mari kita hitung probabilitas bahwa y = y. Nyatakan empat akar kuadrat y dengan ± x, ± x. Kemudian Pr [y = y] = Pr [x adalah akar kuadrat dari y] = Pr [x ∈ {± x, ± x}]=4| Z ∗ N |=1| QR N | karena hal di atas berlaku untuk setiap y ∈ Q R N , kita melihat bahwa y didistribusikan secara formly di QR N memilih elemen acak QN R +1N  Secara umum, itu tidak diketahui bagaimana memilih elemen acak QN R +1N jika faktorisasi N tidak dikenal. Apa yang menyelamatkan kita dalam konteks saat ini adalah bahwa penerima dapat membantu secara khusus, kami memodifikasi skema seperti yang dijelaskan di atas sehingga penerima juga akan memilih z acak ← QNR +1N dan sertakan z sebagai bagiannya kunci publik. (Ini mudah dilakukan penerima karena ia tahu faktortion dari N; lihat Latihan 11.3.) Kemudian pengirim dapat memilih elemen acakN ← QNR +1N dengan terlebih dahulu memilih x ← QR N acak (seperti di atas) lalu pengaturan  y: = [z · x mod N]. Kami meninggalkannya sebagai latihan untuk menunjukkan bahwa  Anda dipilih cara ini memang terdistribusi secara seragam di QN R +1N ; kami tidak menggunakan fakta ini langsung di bukti keamanan yang diberikan di bawah ini kami memberikan deskripsi lengkap tentang skema enkripsi Gold wasser-Micali,menerapkan ide-ide di atas, seperti Konstruksi 11.12.

THEOREM 11.13

Jika masalah residukuadratik relatif sulit Untuk Gen Modulus, maka skema enkripsi Gold wasser-Micali memiliki indistin enkripsi yang dapat dipercaya di bawah serangan plaintext yang dipilih.

BUKTI

Biarkan Π  menunjukkan skema enkripsi Gold wasser-Micali. Kami membuktikan bahwa Π memiliki enkripsi yang tidak dapat dibedakan dengan adanya penyadap oleh Teorema 10.10 ini menyiratkan bahwa itu aman untuk CPA. Biarkan A menjadi musuh probabilistik, waktu polinomial, dan definisikan ε (n) def = Pr [PubK EAVA, Π(n) = 1] Pertimbangkan musuh ppt berikut D yang mencoba menyelesaikan kuadratik masalah residuositas relatif terhadap GenPrime: SkemaEnkripsiPublik-KunciTambahan 373

KONSTRUKSI 11.12

Biarkan Gen Modulus menjadi algoritma polinomial-waktu yang, pada input 1 n ,menempatkan (N, p, q) di mana N = pq, dan p dan q adalah bilangan prima n-bit kecuali dengan probabilitas dapat diabaikan dalam n. Bangun skema enkripsi kunci public sebagai berikut:

• Gen (1 n ) menjalankan GenModulus (1 n ) untuk mendapatkan (N, p, q). Itu juga memilih acak z ← QNR +1N . Kunci public adalah pk = 〈N, z〉dan kunci pribadi adalah sk = 〈p, q〉.

• Untuk mengenkripsi pesan m ∈ {0, 1} sehubungan dengan kunci public pk = 〈N, z〉, pilih acak x ← Z ∗N dan output ciphertext  C: = [z m · x 2 mod N].

• Untuk  mendekripsi ciphertext c menggunakan kunci pribadi sk = 〈p, q〉, deter- menambang apakah c adalah modulu N residukuadratik yang menggunakan, mis Algoritma bagian 11.1.3. Jika c adalah residukuadratik, hasilkan 0 Jika tidak, output 1.Skema enkripsi Gold wasser-Micali Algoritma D: Algoritma ini diberikan N, z sebagai input.

• Atur pk = 〈N, z〉dan jalankan A (pk) untuk mendapatkan dua pesan m 0 , m 1 .

• Pilih bit acak b dan acak x ← Z ∗ N , dan set c: = [z m b · x 2 mod N].

• Berikan ciphertext c ke A dan dapatkan bit output b. Jika b = b, output 1; jikatidak, hasilkan 0. Mari kita menganalisis perilaku D. Ada dua hal yang perlu dipertimbangkan: Kasus 1: Ucapkan input ke D dihasilkan dengan menjalankan Gen Modulus (1 n ) ke dapatkan (N, p, q), lalu pilih acak z ← QNR +1N . Kemudian D menjalankan A Pada kunci publik yang di bangun persis seperti pada  Π, dan kami melihat bahwa dalam kasus ini, tampilan A saat di jalankan sebagai subrutin oleh D di distribusikan persi seperti tampilan A Dalam percobaan Pub K EAVA, Π(n). Karena D menghasilkan 1 tepat ketika keluaran b dari A sama dengan b, kita memilikinya Pr [D (N, qr) = 1] = Pr [PubK EAVA, Π (n) = 1] = ε (n),di mana q rmewakili residukua dratika cak seperti pada   Definisi 11.11. Kasus 2: Katakan input ke D dihasilkan dengan menjalankan Gen Modulus (1 n ) ke memperoleh (N, p, q), dan kemudian  memilih z acak ← QR N . Kami mengklaim bahwa  pandangan A dalam halini tidak tergantung pada bit b. Untuk meli hat ini, perhatikan bahwa ciphertext c yang diberikankepada A adalah residukuadratik acak terlepas dari apakah 0 atau 1 dienkripsi Pengantar Kriptografi Modern

• Ketika 0 dienkripsi, c = [x 2 mod N] untuk x acak ← Z ∗ N dan itu adalah Langsung bahwa c adalah residukuadratik acak.

• Ketika 1 dienkripsi, c = [z · x 2 mod N] untuk x acak ← Z * N . Membiarkan x def = [x 2 mod N], dan perhatikan bahwa x adalah elemen yang terdistribusi secara merata dari kelompok Q R N . Karena z ∈ QR N , kita dapat menerapkan Lemma 10.18 hingga menyimpulkan bahwa c terdistribusi secara seragam di QR N juga. karena pandangan A tidak tergantung pada b, probabilitas bahwa b = b dalam kasus ini adalah tepat 1 2 . Itu adalah, Pr [D (N, qnr) = 1] =12,di mana Q N R mewakili elemen acak dari QN R +1N seperti dalam

DEFINISI 11.11.

Karena masalah residukuadratik relatif sulit untuk Gen Modulus, pasti ada fungsi yang bisa begitu sajanegl (n) = ∣∣∣Pr [D (N, qr) = 1] - Pr [D (N, qnr) = 1]∣∣∣= ∣∣∣∣ε (n)-12∣∣∣∣.ini menyiratkan bahwa ε (n) ≤ 12 + negl (n), melengkapi buktinya.