Keacakan dan Keacakan Semu

Keacakan adalah inti dari kriptografi — kunci, nonce, dan tantangan harus tidak dapat diprediksi — dan keacakan semu memungkinkan benih acak sejati yang pendek direntangkan menjadi urutan panjang yang tidak dapat dibedakan dari acak oleh musuh yang efisien.

Definition

Keacakan semu adalah properti yang secara komputasi tidak dapat dibedakan dari keacakan sejati; generator pseudorandom secara deterministik memperluas benih acak pendek menjadi keluaran yang lebih panjang yang tidak dapat dibedakan oleh algoritma efisien mana pun dari acak.

Scope

Topik ini mencakup peran keacakan dalam kriptografi: persyaratan pada sumber entropi dan generator angka acak sejati, definisi dan konstruksi generator pseudorandom yang aman secara kriptografis dan fungsi pseudorandom, serta konsekuensi bencana dari keacakan yang lemah atau digunakan kembali. Ini membahas bagaimana objek pseudorandom memformalkan primitif simetris. Ini tidak termasuk sandi spesifik dan asumsi kesulitan, yang dibahas dalam topik terkait.

Core questions

• Mengapa kriptografi membutuhkan keacakan yang tidak dapat diprediksi, dan apa yang salah tanpanya?
• Apa yang membedakan generator yang aman secara kriptografis dari generator statistik?
• Bagaimana benih acak sejati yang pendek dapat direntangkan menjadi keluaran pseudorandom yang panjang?
• Apa itu fungsi dan permutasi pseudorandom, dan bagaimana mereka memodelkan sandi?
• Bagaimana entropi berkualitas tinggi dikumpulkan dan dikondisikan dalam sistem nyata?

Key concepts

• entropi dan keacakan sejati
• generator angka acak
• generator pseudorandom (PRG)
• fungsi pseudorandom (PRF)
• permutasi pseudorandom (PRP)
• ketidakmampuan komputasi untuk dibedakan
• derivasi benih dan kunci
• kegagalan penggunaan kembali keacakan
• pengkondisian entropi

Key theories

Generator pseudorandom

Generator pseudorandom memperluas benih pendek menjadi string yang lebih panjang yang tidak dapat dibedakan dari keacakan seragam oleh pembeda yang efisien; generator semacam itu ada jika dan hanya jika fungsi satu arah ada, menghubungkan keacakan semu dengan dasar-dasar kriptografi.

Fungsi dan permutasi pseudorandom

Keluarga fungsi pseudorandom, yang dapat dibangun dari generator pseudorandom apa pun, tidak dapat dibedakan dari fungsi yang benar-benar acak oleh musuh yang mengkuerinya; objek ini mendasari pemodelan keamanan sandi blok dan kode otentikasi pesan.

Mechanisms

Generator angka acak sejati mengumpulkan entropi fisik (derau termal, jitter waktu), yang dikondisikan dan digunakan untuk menyemai generator pseudorandom yang aman secara kriptografis yang secara deterministik menghasilkan semua bit yang tampak acak yang dibutuhkan sistem. Fungsi pseudorandom dibangun dari generator (konstruksi GGM) dan memodelkan primitif berkunci; sandi blok diperlakukan sebagai permutasi pseudorandom. Definisi keamanan mensyaratkan bahwa tidak ada musuh yang efisien, yang diberi keluaran, dapat memprediksi bit lebih lanjut atau membedakannya dari acak.

Clinical relevance

Kegagalan keacakan adalah sumber berulang dari kerusakan dunia nyata yang dahsyat: bug Debian OpenSSL tahun 2008 melumpuhkan pembuatan kunci, nonce ECDSA yang dapat diprediksi membocorkan kunci pribadi (Sony PlayStation 3, beberapa dompet Bitcoin), dan entropi perangkat tertanam yang lemah menghasilkan kunci yang dapat ditebak dalam skala besar. Oleh karena itu, keacakan yang kuat — pengumpulan entropi yang tepat dan generator pseudorandom yang teruji — sangat penting untuk setiap penerapan kriptografi.

Evidence & guidelines

NIST SP 800-90A/B/C menentukan generator bit acak deterministik yang disetujui, validasi sumber entropi, dan panduan konstruksi. Praktik terbaik menggunakan RNG kriptografi yang teruji dari sistem operasi (daripada membuat sendiri), memastikan entropi yang cukup sebelum menghasilkan kunci, dan tidak pernah menggunakan kembali nonce. Suite uji statistik membantu mendeteksi cacat besar tetapi tidak dapat menetapkan kekuatan kriptografi.

History

Teori komputasi keacakan semu didirikan oleh Blum dan Micali serta oleh Yao sekitar tahun 1982, mendefinisikan ketidakpastian dan ketidakmampuan untuk dibedakan. Goldreich, Goldwasser, dan Micali menunjukkan cara membangun fungsi pseudorandom dari generator pada tahun 1986, dan Hastad, Impagliazzo, Levin, dan Luby kemudian membuktikan bahwa generator pseudorandom ada jika fungsi satu arah ada. Bencana praktis berulang dari keacakan yang lemah telah menjadikan kualitas entropi dan RNG sebagai perhatian teknik utama.

Key figures

• Oded Goldreich
• Shafi Goldwasser
• Silvio Micali
• Manuel Blum
• Andrew Yao

Seminal works

• goldreich1986
• goldreich2001
• katz2020

Frequently asked questions

Mengapa saya tidak bisa menggunakan fungsi acak normal seperti rand() untuk kriptografi?

Generator angka acak biasa dibangun untuk keseragaman statistik dan kecepatan, bukan ketidakpastian; keluarannya dapat diprediksi dari beberapa sampel. Kriptografi membutuhkan generator yang keluaran masa depannya tidak mungkin diprediksi bahkan dengan keluaran masa lalu, yang membutuhkan RNG yang aman secara kriptografis yang disemai dengan entropi nyata.

Apa perbedaan antara keacakan sejati dan keacakan semu?

Keacakan sejati berasal dari sumber fisik yang tidak dapat diprediksi dan persediaannya terbatas. Keacakan semu dihasilkan secara deterministik dari benih acak sejati yang pendek dan dapat diproduksi secara massal; ia hanya perlu tidak dapat dibedakan dari keacakan sejati oleh musuh yang efisien, yang cukup untuk penggunaan kriptografi.