Bagaimana enkripsi dapat melibatkan keacakan?

8

Jika suatu algoritma enkripsi dimaksudkan untuk mengubah suatu string ke string lain yang kemudian dapat didekripsi kembali ke aslinya, bagaimana proses ini dapat melibatkan keacakan?

Tentunya itu harus deterministik, kalau tidak bagaimana bisa fungsi dekripsi tahu faktor apa yang terlibat dalam membuat string terenkripsi?

CJ7
sumber
3
Tolong jangan ajukan pertanyaan yang identik di beberapa situs Stack Exchange, seperti yang ini di Crypto.SE .
Paŭlo Ebermann

Jawaban:

5

Mungkin ada lebih dari satu ciphertext yang memetakan kembali ke plaintext yang sama. Dalam istilah matematika, algoritma enkripsi harus bersifat injektif sehingga Anda dapat memulihkan plaintext untuk ciphertext, tetapi ini tidak mencegah ciphertext dari menyandikan lebih banyak informasi daripada plaintext.

Sebagai contoh nyata, pertimbangkan mode operasi cipher blok seperti CBC , CTR atau OFB . Semua mode ini melibatkan IV (vektor inisialisasi) selain plaintext, algoritma cipher blok dan kuncinya. (Untuk CTR, IV disebut nonce, tetapi memainkan peran yang sama.) Fungsi enkripsi adalah deterministik untuk IV yang diberikan. IV, di sisi lain, dapat dipilih secara acak (untuk RKT, harus dipilih secara acak). Jadi, kecuali protokol menentukan metode deterministik untuk memilih IV (seperti konstanta yang disepakati), IV dikirim bersama ciphertext. Bahkan, output dari perangkat lunak enkripsi sering kali terdiri dari IV diikuti oleh teks cipher stricto sensu. IV itu sendiri dikirim dalam plaintext; itu tidak (tidak boleh) mengandung informasi rahasia apa pun.

Sebagai contoh lain, pertimbangkan mode PKCS1.5 (“skema padding”) RSA (didefinisikan dalam PKCS # 1 versi 1.5 - lihat hal.22–25 dari PKCS # 1 v2.1 ). Sederhanakan sedikit, mode ini terdiri dari menggabungkan string acak dengan pesan, kemudian menerapkan operasi eksponensial. adalah mana adalah concatenation, adalah pesan dan adalah string padding yang sebagian besar bitnya acak. Untuk memulihkan pesan dari ciphertext , terapkan operasi dekripsi mentah dan pisahkan menjadi padding (yang dibuang) dan pesan.(PM)emodnMPCCdmodnC

Gilles 'SANGAT berhenti menjadi jahat'
sumber
4

Skema enkripsi tidak hanya dapat memiliki keacakan, tetapi dalam beberapa kasus (misalnya, enkripsi kunci publik ), mereka harus diacak. Ini bukan masalah karena kami memerlukan skema enkripsi untuk menjadi benar , yaitu, untuk setiap pesan dan tombol apa saja itu menyatakan bahwa atas keacakan .mk

Pr[ DEC( ENC(k,m,R) )=m]=1
R

Alasan mengapa skema kunci publik harus acak berasal dari cara kami mendefinisikan keamanan: kami tidak ingin ciphertext membocorkan informasi apa pun tentang pesan terenkripsi. Contoh klasik adalah sebagai berikut. Asumsikan bahwa masing-masing adalah kunci publik dan rahasia, dan bahwa musuh mencegat pesan terenkripsi dikirim ke beberapa unit di lapangan. Musuh tahu bahwa pesannya "ATTACK" atau "RETREAT", tetapi tidak tahu yang mana. Satu hal yang dapat dilakukan musuh adalah mengenkripsi kedua pesan menggunakan publik . biarkan dan . Jika(pk,sk)cpkcA=ENCpk("ATTACK ")cR=ENCpk("RETREAT")ENCbersifat deterministik, musuh dapat mengetahui pesan dengan pasti dengan membandingkan ke dan .ccAcR

Cara pengertian ini didefinisikan secara formal dikenal sebagai keamanan semantik :

Skema enkripsi secara semantik aman jika ada musuh tidak bisa memenangkan permainan berikut dengan probabilitas lebih besar dari :A1/2

  1. Penantang menghasilkan kunci dan mengirimkan kunci publik ke musuh.C(pk,sk)pk
  2. A memilih dua pesan dengan panjang yang sama dan dan memberikan keduanya ke .m0m1C
  3. C secara seragam mengambil sedikit dan mengirim kembali .b{0,1}ENC(mb)
  4. A perlu mengatakan pesan mana yang dienkripsi: atau , yaitu, ia perlu menampilkan bit .m0m1b

(Saya menghilangkan parameter keamanan , yang sangat penting untuk mendefinisikan "diabaikan" atau "terlihat"; Kita perlu mengasumsikan bahwa pembuatan kunci tergantung pada , dan bahwa keuntungan telah di atas dapat diabaikan dalam , yaitu kurang dari ) κκA1/2κκω(1)

Ran G.
sumber
kita dapat menambahkan string acak ke akhir input sebelum membentuk enkripsi untuk menghindari masalah dan selalu memiliki , yaitu kondisinya dapat lebih kuat daripada yang telah Anda nyatakan di atas . DEC(ENC(k,m,R))=m
Kaveh
3

Anda belum menyatakan jenis enkripsi apa yang sedang kita diskusikan, tetapi izinkan saya menunjukkan apa yang benar-benar diperlukan untuk keamanan protokol kartografi (selain apa yang dinyatakan dalam jawaban lain).

Yang benar-benar kita butuhkan adalah ini: kunci harus dibuat secara acak (ini dapat dilakukan dalam kolaborasi seperti dalam kriptografi kunci publik seperti RSA atau oleh satu entitas seperti dalam kriptografi kunci pribadi). Keacakan kunci memastikan bahwa musuh tidak dapat memprediksi kunci (dan menggunakannya untuk melanggar protokol). Selama kunci tampak acak ke musuh protokol akan aman. Seringkali, kunci dihasilkan oleh algoritma acak dan kemudian diberikan kepada para pihak, sedangkan algoritma enkripsi dan dekripsi tidak acak tetapi deterministik.

Juga ingat bahwa menjadi acak tidak berarti bahwa prosesnya tidak dapat dibalik. Contoh sederhana adalah sebagai berikut: diberikan , secara acak menghasilkan , output . Untuk pembalikan, kita dapat menampilkan bagian pertama dari pasangan.xrx,r

Kaveh
sumber
Contoh Anda penting: tanpa padding acak, vanilla RSA tidak aman. dengan padding acak, RSA dapat terbukti memiliki sifat keamanan yang bagus dalam model oracle acak
Sasho Nikolov
1

Enkripsi dan algoritma dekripsi dapat diacak selama Anda dapat membuktikan beberapa teorema bahwa enkripsi diikuti oleh dekripsi akan memberi Anda pesan asli sebagian besar kali .

Mengapa ada yang menginginkan skema enkripsi seperti itu? Karena: 1) terdapat situasi di mana kita tidak ingin menjadi benar sepanjang waktu tapi hanya 99.999.999 kali dari setiap 100000000 dan 2) yang memungkinkan kesalahan kecil seperti sering meningkatkan sesuatu yang lain (seperti efisiensi) dengan jumlah yang tidak proporsional.

Vinayak Pathak
sumber
3
Sementara enkripsi probabilistik memang ada, mereka agak di sisi eksotis. Banyak algoritma enkripsi sehari-hari melibatkan keacakan tanpa menjadi probabilistik.
Gilles 'SO- stop being evil'
@Gilles: Perbedaan penting untuk dibuat.
Raphael
0

Sebagai contoh, dalam enkripsi RSA , Anda perlu membuat dua bilangan prima dan dan bilangan bulat yang akan digunakan untuk membuat kunci publik dan pribadi Anda.pqe

Jika Anda menghasilkan salah satu dari nilai-nilai ini dengan cara deterministik, maka generasi mereka dapat direproduksi, yang berpotensi membahayakan enkripsi Anda. Jika angka-angka ini dihasilkan secara acak, maka ini bukan masalah.

Memperbarui

Sebagai contoh jawaban Ran G. yang lebih spesifik , Anda dapat melihat kriptografi Kurva Elliptic , di mana algoritme membutuhkan parameter acak (biasanya disebut , atau ) untuk mengenkripsi dan mendekripsi pesan. Jika parameter "acak" yang sama digunakan lebih dari sekali, kunci mereka dapat dihitung dari dua pesan terenkripsi. Ini adalah masalah / premis dari hack PlayStation 3 tahun lalu .dkr

Pedro
sumber
1
Ini adalah keacakan dalam generasi kunci, yang saya ragu adalah pertanyaannya: setiap generasi kunci harus melibatkan keacakan, jika kuncinya dapat diprediksi (atau diturunkan dan tidak dihasilkan).
Gilles 'SANGAT berhenti menjadi jahat'
Saya tidak berpikir itu adalah tempat untuk pengacakan OP dalam pikiran. Kunci diberikan dan statis untuk crypt (en | de). Bagaimana Anda memilih kunci Anda terlepas dari itu.
Raphael
@Gilles: Saya tidak akan menganggapnya sebagai potongan yang jelas. Nilai , dan biasanya disimpan dalam bentuk terenkripsi, dengan kata sandi pilihan pengguna. Sebenarnya, mereka adalah kunci, tapi dari pengguna 's perspektif, mereka nilai hanya acak yang dihasilkan oleh mengetik omong kosong pada keyboard dan tidak ada hubungannya dengan password mereka hati-hati dipilih. pqe
Pedro
@Pedro Saya tidak mengerti bagaimana komentar terbaru Anda berhubungan dengan pertanyaan. Bahkan dari perspektif file kunci (yang tidak saya lihat dalam pertanyaan), kuncinya ternyata tidak dibuat secara acak, itu berasal dari file kunci dan kata sandi.
Gilles 'SANGAT berhenti menjadi jahat'