Cryptography Engineering, Teil 1: Zur Theorie des Advanced Encryption Standard
Seite 3: AES-Algorithmus
Der AES-Algorithmus
Der Leser ist jetzt in der Lage, die Grundrechenarten in GF(2^8) auszuführen, und gerüstet, AES zu implementieren. AES ist eine Blockchiffre. Sie zerlegt die zu ver- beziehungsweise entschlüsselnde Nachricht in Blöcke der Größe 128 Bit (16 Bytes), die sich einzeln der Ver- oder Entschlüsselung zuführen lassen. Durch Aneinanderfügen (Konkatenation) der so verarbeiteten Blöcke erhält man schließlich den Chiffretext (Ciphertext) respektive die Klartextnachricht (Plaintext oder Message). AES gehört zu den iterativen Blockchiffren. Die Verschlüsselungsfunktion Cipher und die Entschlüsselungsfunktion InvCipher (inverse cipher) setzen sich aus einfacheren Teilfunktionen zusammen, die wiederholt – iterativ – auf den zu verarbeitenden Block angewendet werden. Jede dieser Wiederholungen heißt eine Runde.
Den prinzipiellen Ablauf von Cipher und InvCipher gibt Abbildung 2 wieder. Die Rundeniteration ist durch die Schleife deutlich zu erkennen. Vor den Runden finden sich initiale Operationen und nach den Runden in der Schleife noch eine reduzierte Abschlussrunde. Die Rundenanzahl ist in der Variablen Nr abgelegt. Sie differiert je nachdem, welche Schlüssellänge zum Einsatz kommt: 10 Runden für 128 Bit Schlüssellänge, 12 für 192 Bit und 14 für 256 Bit.
Beide Funktionen operieren auf einem Array state, das anfangs im Falle von Cipher den Klartext und für InvCipher den Chiffretext enthält. Laut AES-Spezifikation ist dieses Array zweidimensional und somit eine Matrix. Die Ein- und Ausgabeblöcke als (im Grund eindimensionales) Array von 16 Bytes konvertiert AES gemäß dem oberen Teil von Abbildung 3 in die state-Matrix. Für die Implementierung lässt sich das Ganze aber vereinfachen. Das Array state kann man nämlich auch eindimensional abbilden (unterer Teil von Abbildung 3). Die Spalten sind statt über einen Spaltenindex über einen geeigneten Offset zum eindimensionalen Index anzusprechen. Damit entfällt die Konvertierung von Byte-Array zu Matrix (in nach [/i]state[/i]) und Matrix zu Byte-Array (state nach out). Bereits Abbildung 2 unterschlägt diese Konvertierungen und weicht damit von der formalen Spezifikation von AES ab. Sie orientiert sich damit jedoch näher an der späteren Implementierung.
Die AES-Funktionen
Die Funktion SubBytes() in Cipher() interpretiert state als einen Stream von Bytes. Sie ersetzt jedes Byte durch ein Byte der AES-Substitutionsbox (S-Box). Die S-Box ist eine Tabelle, die angibt, welcher Bytewert durch welchen ersetzt werden soll. Der Wert des zu ersetzenden Bytes dient als Index innerhalb der Tabelle. Der entsprechende Eintrag an der indizierten Stelle ist der Substitutionswert des Bytes. Die S-Box ist in der AES-Spezifikation auf Seite 16 wiedergegeben. Sie implementiert eine Permutation; würfelt also die Bytes anhand der Tabelle durcheinander. InvSubBytes() von InvCipher() ist die Umkehrung von SubBytes(). Sie verwendet die inverse S-Box, die sich in der Spezifikation auf Seite 22 findet.
S-Boxen haben eine lange Tradition in Blockchiffren. Im Gegensatz zu heuristisch erstellten S-Boxen anderer Algorithmen wie denen von DES (Data Encryption Standard) sind die S-Boxen von AES systematisch aufgebaut. Sie basieren auf den multiplikativen Inversen, auf die noch eine affine Transformation folgt (siehe 5.1 auf Seite 15 der Spec). Die S-Box-Einträge lassen sich somit also errechnen und nicht nur als Tabelle wiedergeben. Diese Artikelreihe kommt darauf bei der Implementierung für 8-Bit-Mikrocontroller zurück.
ShiftRows() in Cipher() und die Umkehrung InvShiftRows() in InvCipher() verschieben die Bytes in den Reihen von state. Genauer: Sie rotieren die Reihen der Matrix. Die erste um ein Byte nach links beziehungsweise rechts, die zweite um zwei Bytes und so fort.
MixColumns() und InvMixColums() "mischen" die Spalten der Matrix state durcheinander. Die Operation basiert auf einer Matrixmultiplikation. Das klingt komplizierter, als es wirklich ist, denn die Operationen finden sich fast schon zum Abtippen bereit auf Seite 18 und 23 der Spezifikation. Die Operationen verwenden intensiv die Multiplikation in GF(2^8). Mit dem Algorithmus aus Abbildung 1 ist das jedoch auch einfach zu implementieren.
