Bagaimana KECCAK beroperasi pada array negara yang diisi dengan nol?
Saya mencoba menerapkan spons di Jawa. Status dimulai sebagai larik 200 byte kosong dari semua nol. Dalam dokumen sampel KMAC dari NIST, hal berikut ini terjadi:
(garis hitam adalah jeda halaman pdf)
Cara saya membaca ini adalah bahwa keadaan dengan sekelompok nol dikirim ke KECCAK, dan kemudian keadaan dengan data yang tampaknya acak dikembalikan. Apakah SHA3 / KECCAK mengubah data kosong menjadi data acak? Apakah saya mengajukan pertanyaan yang benar di sini? Setiap bantuan dihargai.
Jawaban
Saya pribadi menemukan dokumen Keccak.team Psuedo Code sangat membantu untuk memahami bagaimana Keccak-p.
Seperti yang dikatakan DannyNiu dalam komentarnya, sebagian besar (semua?) Permutasi kriptografi menggunakan "konstanta bulat". Konstanta ini entah bagaimana tercampur dalam keadaan Keccak.
Dokumen pseudocode memberikan konstanta bulat sebagai tabel:
RC[0] 0x0000000000000001 RC[12] 0x000000008000808B
RC[1] 0x0000000000008082 RC[13] 0x800000000000008B
RC[2] 0x800000000000808A RC[14] 0x8000000000008089
RC[3] 0x8000000080008000 RC[15] 0x8000000000008003
RC[4] 0x000000000000808B RC[16] 0x8000000000008002
RC[5] 0x0000000080000001 RC[17] 0x8000000000000080
RC[6] 0x8000000080008081 RC[18] 0x000000000000800A
RC[7] 0x8000000000008009 RC[19] 0x800000008000000A
RC[8] 0x000000000000008A RC[20] 0x8000000080008081
RC[9] 0x0000000000000088 RC[21] 0x8000000000008080
RC[10] 0x0000000080008009 RC[22] 0x0000000080000001
RC[11] 0x000000008000000A RC[23] 0x8000000080008008
dan menjelaskan bagaimana mereka digunakan. Di langkah iota dari$n^\text{th}$ Putaran keccak, itu $n^\text{th}$ putaran konstan $RC[n]$ diperkenalkan dan memasukkan XOR ke kata pertama, jalur pertama.
Terlepas dari konstanta bulat, permutasi Keccak memiliki difusi yang sangat baik: satu bit di suatu tempat dalam keadaan awal akan berkontribusi secara signifikan ke banyak bit keluaran.
Kombinasi keduanya berarti permutasi Keccak Anda terlihat sangat acak. Ia tidak dapat, tentu saja, mengubah nol entropi menjadi acak, karena tidak ada algoritma hingga yang dapat melakukan itu, tetapi tujuan dari Keccak adalah untuk mencampurkan berbagai hal dan membuatnya tampak acak.
Fungsi permutasi Keccak biasanya akan memetakan input nol (semua bit adalah 0) ke output nol, jika bukan karena langkah iota, di mana satu kata dari status adalah XOR dengan konstanta bukan nol.
Sekitar tiga (dari 24) putaran cukup untuk difusi lengkap yaitu setiap bit dari status mempengaruhi setiap bit lainnya tiga putaran kemudian. Bisa dikatakan, permutasi mencampurkan negara delapan kali sepenuhnya. Itu berarti jika hanya satu bit yang 1, itu akan berdifusi dengan cepat di atas status sehingga 3 putaran kemudian sekitar setengah dari bit status adalah 1.
Membiarkan $R$menjadi himpunan nilai status yang secara wajar dapat disebut "tampilan biasa" (dengan definisi persis apa pun), misalnya semua atau hampir semua bit memiliki nilai yang sama, atau pola bit pendek berulang secara teratur. Di antara semua$2^{1600}$ negara bagian, yang di $R$adalah pecahan yang sangat kecil. Sangat tidak mungkin bahwa ada negara bagian di$R$ dipetakan ke keluaran juga di $R$. Ini berlaku selama$|R| \ll 2^{800}$ (lihat "paradoks ulang tahun").
Itu berarti bahwa tidak ada masukan yang tampak biasa yang dipetakan ke keluaran yang tampak biasa. Dan probabilitas untuk setiap status tertentu yang akan dipetakan ke keluaran$R$ dapat diabaikan, yaitu keluaran akan selalu terlihat acak, kecuali seseorang dengan sengaja menyusun masukan dengan menghitung invers permutasi.