Kryptografische Hashfunktionen - Kryptografie - page 249

Die Kompressionsfunktion

Eine Funktion kann als Kompressionsfunktion für den Schwamm genutzt wer-
den, wenn sie Bitfolgen in der Größe des Status (in unserem Fall 1.600 Bit) verar-
beitet und ausgibt. Keccak ist durch das Schwamm-Prinzip sowie durch eine
Kompressionsfunktion definiert, das dieses nutzt. Diese Kompressionsfunktion
läuft in 24 Runden ab. Jede Runde besteht aus fünf Teilrunden, die mit den grie-
chischen Buchstaben θ, ρ, π , χ und ι (theta, rho, pi, chi und iota) bezeichnet wer-
den. Diese laufen wie folgt ab ( A ist der Status):

In Teilrunde θ wird von allen 320 Spalten des Status das Paritätsbit berech-
net und in regelmäßiger Form mit benachbarten Spalten exklusiv-oder-ver-
knüpft. Die Formel lautet:
A i,j,k = A i,j,k

1.

⊕ par( A 0..4,j-1,k ) ⊕ par( A 0..4,j+1,k-1 )

In Teilrunde ρ wird jedes der 25 Wörter des Status nach hinten rotiert. Um
wie viele Einheiten rotiert wird, ergibt sich aus folgender Tabelle (die Zahlen
sind modulo 64 zu nehmen).

2.

x=0 x=1 x=2 x=3 x=4

y=0 0 1 190 28 91

y=1 36 300 6 55 276

y=2 3 10 171 153 231

y=3 105 45 15 21 136

y=4 210 66 253 120 78

In Teilrunde π werden die 25 Wörter des Status nach folgender Formel per-
mutiert:
A 3i+2j,i,0..63 = A i,j,0..63

3.

In Teilrunde χ werden jeweils die Bits einer Reihe wie folgt verknüpft:
A i,j,k = A i,j,k

4.

⊕ ¬ A i,j+1,k ∧ A i,j+2,k

In Teilrunde ι wird eine Konstante mit dem Status exklusiv-oder-verknüpft,
die sich mit jeder Runde ändert. Die Konstante ist, wie der Status, ein
5×5×64-Bit-Array. Nur sieben der 1.600 Bits der Konstante können einen
von Null verschiedenen Wert haben. Diese sieben Bits liegen alle innerhalb
des unteren linken Worts. Die Konstante wird mithilfe eines linearen Feed-
back-Shift-Registers generiert, was uns aber an dieser Stelle nicht interessieren
soll. Der Wert der Konstante ist in folgender Liste in Hexadezimalschreib-
weise gegeben (man muss sich Status und Konstante hierbei als 1.600-Bit-
Folge der Form A 0,0,0 , A 1,0,0 , A 2,0,0 , ..., A 4,4,62 , A 4,4,63 vorstellen):

5.