Pertanyaan tentang penggunaan PRF untuk membangun PRG

Question

Misalkan F menjadi fungsi pseudorandom aman dengan kunci 128-bit dan panjang blok 256-bit. Apa sajakah fungsi G berikut yang merupakan generator pseudorandom aman? (Pilih semua yang berlaku.)

SEBUAH. $G(x)=F_x(0...0)$, dimana $x$ adalah $128$masukan -bit.

B. $G(x)=F_x(0...0)|| F_x(0...0)$, dimana $x$ adalah $128$masukan -bit.

C. $G(x)=F_x(0...0)||F_x(1...1)$, dimana $x$ adalah $128$masukan -bit.

D. $G(x)=F_{0...0}(x)|| F_{1...1}(x)$, dimana $x$ adalah $256$masukan -bit.

Jawaban yang diberikan guru kami adalah $A,D$. Tapi saya tidak mengerti. Dan Mengapa C salah?

Answer 1

Kami tidak langsung menjawab pertanyaan pekerjaan rumah, tapi akan memberi petunjuk.

Seorang penyerang diasumsikan memiliki kendali atas semua input non-rahasia. Kuncinya adalah rahasia, bukan blok. Jawaban ini memiliki definisi PRG yang baik: dalam istilah sederhana PRG adalah fungsi yang mengambil bitstring seed input rahasia dengan panjang tetap, dan mengeluarkan bitstring yang lebih panjang yang tidak dapat dibedakan dari bitstring acak dengan probabilitas yang tidak dapat diabaikan.

SEBUAH. $G(x)=F_{x}(0...0)$, di mana x adalah kunci masukan 128-bit.

Apakah penyerang mengontrol salah satu masukan? Dapatkah penyerang membedakan output dari fungsi acak dengan probabilitas yang tidak dapat diabaikan (yaitu, apakah ada pola yang dapat diamati dalam output)? Apakah keluaran lebih panjang dari masukan?

Variabel masukan satu-satunya adalah kunci rahasia. Tidak ada pola tambahan yang ditambahkan ke keluaran. Berapa lama hasilnya?

B. $G(x)=F_{x}(0...0)||F_{x}(0...0)$, di mana x adalah kunci masukan 128-bit.

Pertanyaan yang sama.

Variabel masukan satu-satunya adalah kunci rahasia. Output mengulangi beberapa urutan dua kali. Berapa lama hasilnya?

C. $G(x)=F_{x}(0...0)||F_{x}(1...1)$, di mana x adalah kunci masukan 128-bit.

Pertanyaan yang sama.

Variabel masukan satu-satunya adalah kunci rahasia. Apakah keluarannya memiliki pola tambahan? Berapa lama hasilnya?

D. $G(x)=F_{0...0}(x)||F_{1...1}(x)$, di mana x adalah blok data masukan 256-bit.

Pertanyaan yang sama.

Variabel input hanya blok data publik. Apakah keluarannya memiliki pola tambahan? Berapa lama hasilnya?

Ada opsi yang hilang yang melanjutkan pola: E. $G(x)=F_{0...0}(x)||F_{0...0}(x)$, di mana x adalah blok data 256-bit publik.

Kalau bisa jawab AD, E harus sepele.