In che modo KECCAK opera su un array di stati pieno di zeri?
Sto cercando di implementare una spugna in Java. Lo stato inizia come un array vuoto di 200 byte di tutti zeri. Nel documento di esempio KMAC del NIST, accade quanto segue:
(la linea nera è un'interruzione di pagina pdf)
Il modo in cui sto leggendo questo è che uno stato con un mucchio di zeri è stato inviato a KECCAK, quindi è stato restituito uno stato con dati apparentemente casuali. SHA3/KECCAK trasforma i dati vuoti in dati casuali? Sto facendo le domande giuste qui? Qualsiasi aiuto è apprezzato.
Risposte
Personalmente trovo molto utile il documento Keccak.team Psuedo Code per capire come Keccak-p.
Come ha detto DannyNiu nei commenti, la maggior parte (tutte?) Permutazioni crittografiche impiegano "costanti rotonde". Queste costanti sono in qualche modo mescolate nello stato di Keccak.
Il documento in pseudocodice fornisce le costanti rotonde come tabella:
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
e spiega come vengono utilizzati. Nel passo iota del$n^\text{th}$Keccak-p rotondo, il$n^\text{th}$costante rotonda$RC[n]$viene presentato e ottiene XOR nella prima parola, prima corsia.
A parte le costanti rotonde, la permutazione di Keccak ha un'ottima diffusione: un singolo bit da qualche parte nello stato iniziale contribuirà in modo significativo a molti bit di output.
La combinazione di entrambi significa che la tua permutazione Keccak sembra molto casuale. Non può, ovviamente, trasformare l'entropia zero in casuale, poiché nessun algoritmo finito può farlo, ma l'obiettivo di Keccak è mescolare le cose e farle apparire casuali.
La funzione di permutazione di Keccak normalmente mapperebbe l'ingresso zero (tutti i bit sono 0) sull'uscita zero, se non fosse per il passo iota, in cui una parola dello stato è XORed con una costante diversa da zero.
Circa tre round (su 24) sono sufficienti per una diffusione completa, cioè ogni bit dello stato influenza ogni altro bit tre round dopo. Si potrebbe dire che la permutazione mescola completamente lo stato otto volte. Ciò significa che se solo un bit è 1, si diffonderà rapidamente nello stato in modo che 3 round dopo circa la metà dei bit di stato siano 1.
Permettere$R$essere l'insieme dei valori di stato che possono essere ragionevolmente definiti "regolari" (da qualsiasi definizione esatta), ad esempio tutti o quasi tutti i bit hanno lo stesso valore, oppure un modello di bit breve si ripete regolarmente. Tra tutti i$2^{1600}$stati, quelli in$R$sono una frazione molto piccola. È molto improbabile che qualsiasi stato in$R$è mappato su un output anche in$R$. Questo vale finché$|R| \ll 2^{800}$(vedi "paradosso del compleanno").
Ciò significherebbe che non esiste un input dall'aspetto regolare mappato su un output dall'aspetto regolare. E la probabilità che un dato stato venga mappato a un'uscita in$R$è trascurabile, cioè l'output sembrerà sempre casuale, tranne che qualcuno costruisce deliberatamente l'input calcolando l'inverso della permutazione.