communityWir suchen ständig neue Tutorials und Artikel! Habt ihr selbst schonmal einen Artikel verfasst und seid bereit dieses Wissen mit der Community zu teilen? Oder würdet ihr gerne einmal über ein Thema schreiben das euch besonders auf dem Herzen liegt? Dann habt ihr nun die Gelegenheit eure Arbeit zu veröffentlichen und den Ruhm dafür zu ernten. Schreibt uns einfach eine Nachricht mit dem Betreff „Community Articles“ und helft mit das Angebot an guten Artikeln zu vergrößern. Als Autor werdet ihr für den internen Bereich freigeschaltet und könnt dort eurer literarischen Ader freien Lauf lassen.

Advanced Encryption Standard (AES) Drucken E-Mail
Benutzerbewertung: / 283
SchwachPerfekt 
Geschrieben von: Kristian, Laurent Haan   
Sonntag, den 17. Februar 2008 um 19:34 Uhr

Inhaltsverzeichnis

  1. Einführung in die Kryptographie
  2. Rechtliche Grundlagen zur Kryptographie
  3. Einführung in den Advanced Encryption Standard
    1. Weitere Informationen:
  4. Beschreibung des Advanced Encryption Standard Algorithmuses
    1. Beschreibung:
  5. AES Operationen: SubBytes, ShiftRows, MixColumns und AddRoundKey
    1. Die AddRoundKey Operation:
    2. Die ShiftRows Operation:
    3. Die SubBytes Operation:
    4. Die MixColumns Operation:
    5. Arithmetische Operationen im Galois-Feld:
      1. Addition und Subtraktion
      2. Multiplikation
      3. Potenzieren und Logarithmieren
      4. Division
      5. Multiplikative Inverse
  6. Der Rijndael Key Schedule
    1. Rotation:
    2. Rcon:
    3. S-Box:
    4. Der Key Schedule Kern:
  7. Die Schlüsselexpansion
  8. Implementierung des Key Schedule
    1. Implementierung: Allgemeine Kommentare
    2. Implementierung: S-Box
      1. S-Box („ROM-Tabellen“)
      2. S-Box („On-the-fly“)
    3. Implementierung: Rotation
    4. Implementierung: Rcon
      1. Rcon („ROM-Tabelle“)
      2. Rcon („On-the-fly“)
    5. Implementierung: Vorwärts- und Rückwärts-Tabellen
    6. Implementierung: Key Schedule Kern
    7. Implementierung: Die Schlüsselexpansion
    8. Implementierung: Nutzung der Schlüsselexpansion
  9. Implementierung der AES Verschlüsselung
    1. Implementierung: SubBytes
    2. Implementierung: ShiftRows
    3. Implementierung: AddRoundKey
    4. Implementierung: MixColumns
    5. Implementierung: AES Runden
    6. Implementierung: Der Körper von AES
    7. Implementierung: Instanz erzeugen
    8. Implementierung: Chiffrieren
  10. Implementierung der AES Entschlüsselung
    1. Implementierung: Dechiffrieren
  11. Betriebsarten
  12. Performance
  13. Schluss
  14. Literatur
  15. Weitergehende Links

Einführung in die Kryptographie

Serge Vaudenay schreibt in seinem Buch "A Classical Introduction to Cryptography":

Die Kryptographie ist die Wissenschaft der Informations- und Kommunikationssicherheit.

Die Kryptographie (Lehre vom Ver- und Entschlüsseln von Nachrichten) ist die Wissenschaft der geheimen Codes, die es ermöglicht Vertraulichkeit über unsichere Kommunikationswege sicherzustellen. Sie schützt vor unautorisierten Parteien indem sie das Entschlüsseln von Nachrichten durch unautorisierte Mithörer verhindert. Allgemein gesprochen, es wird ein kryptographisches System verwendet um einen Klartext (engl. plaintext) in einen Geheimtext (engl. ciphertext) zu transformieren, indem oftmals ein geheimer Schlüssel (engl. key) verwendet wird.

symmetric-key-encryption

Der Leser sei darauf hingewiesen, dass es Kryptosysteme gibt, die überhaupt keinen Schlüssel benötigen. Ein berühmtes Beispiel ist ROT13 (Abkürzung für Rotation 13), ein einfacher Caesar-Chiffre, der den Text verschleiert, indem er jeden Buchstaben des lateinischen Alphabets durch den im Alphabet um 13 Stellen davor bzw. dahinter liegenden Buchstaben ersetzt. Da unser Alphabet 26 Buchstaben besitzt, kann man den Klartext einfach durch eine erneute Verschlüsselung mit ROT13 erhalten.

Lassen Sie mich erwähnen, dass es sogenannte Public-Key Chiffre gibt, wie den sehr sicheren Rivest-Shamir-Adleman (gewöhnlich RSA genannt) der einen öffentlichen Schlüssel zur Verschlüsselung einer Nachricht verwendet und einen geheimen Schlüssel zur Entschlüsselung.

Die Kryptographie ist ein sehr wichtiger Bereich in der Informatik und wird in vielen Anwendungen eingesetzt. Das berühmteste Beispiel für Kryptographie ist sicherlich die Enigma-Maschine, die legendäre Chiffremaschine, die von dem deutschen Dritten Reich verwendet wurde, um Nachrichten zu verschlüsseln, und deren Sicherheitslücke zum Untergang der deutschen U-Boot Flotte führte.

Rechtliche Grundlagen zur Kryptographie

Bevor wir fortfahren, lesen Sie bitte zunächst einige rechtliche Grundlagen, da es in einigen Ländern Verordnungen hinsichtlich der Verwendung von kryptographischen Systemen gibt. Wir beschränken uns allerdings in diesem Artikel auf die deutsche Gesetzeslage und führen die aktuelle Situation etwas aus.

Die Kryptographie gewinnt immer mehr Bedeutung in Hinsicht auf Kopierschutzmechanismen um das Urheberrecht zu wahren. Z.B. ein Registrierungsschlüssel, also ein Code, den das Installationsprogramm als gültig oder nicht gültig erkennen muss. Vor nicht all zu langer Zeit war ein Verbot von Email-Verschlüsselung angedacht.

In Deutschland ist die Verwendung jeder Art von Verschlüsselungstechnik nach aktuellen Stand der Dinge erlaubt.

Am 22. Mai 2001 trat das Digitale Signaturgesetz in Kraft, dass digitale und manuelle Signaturen (bis auf wenige Ausnahmen, z.B. Eheschließung) als gleichrangig anerkennt. In Frankreich und Rußland etwa war lange die Verwendung von Verschlüsselungssystemen gänzlich verboten. In Frankreich denkt man über eine Lockerung dieses Verbotes nach. 1996 hat der U.S. Economic Espionage Act das Wort „Geschäftsgeheimnis“ neu definiert und damit ein Gesetz erlassen, daß Firmen in den USA dazu zwingt, Geschäftsinformationen durch geeignete Maßnahmen zu sichern. Dies beinhaltet vor allem auch Sicherheit vor Angriffen auf die Rechnersysteme und Ausspähung der Daten.

Man sieht also, daß man sich noch nicht ganz einig ist auf der Welt, ob die Kryptographie ein Segen oder ein Fluch ist.

Im Zuge jüngerer Ereignisse (Kampf gegen den Terror) ist die Diskussion über ein Verbot von effektiven Verschlüsselungsmechanismen auch in Deutschland wieder neu entflammt. Schließlich wird es sehr schwierig kriminelle Elemente zu überwachen, wenn man ihre Kommunikation nicht kontrollieren kann. Also hat man sich ein Modell ausgedacht indem jeder, der Verschlüsselung verwendet an öffentlicher Stelle einen Nachschlüssel hinterlegen muß. Wie Prof. J. Buchmann in einem Interview des Darmstädter Echos damals bemerkt hatte, werden sich gerade diese kriminellen Elemente nicht an eine solche Vorschrift halten, schließlich halten sie sich allgemein nicht an Vorschriften.

Einführung in den Advanced Encryption Standard

Dieser Artikel wird sich mit dem AES (engl. Advanced Encryption Standard) befassen und Code in C implementieren. Die Grundlage für die Software entstand bei der Programmierung eines C166 bei Siemens und dem TSZ - München. Der Advanced Encryption Standard, im folgenden mit AES abgekürzt, ist der Gewinner des Wettbewerbs, abgehalten im Jahr 1997 von der US Regierung, nachdem der alte Data Encryption Standard (DES) als zu schwach, aufgrund seiner geringen Schlüsselgröße und der stark angestiegenen Rechenleistung, eingestuft worden war. Fünfzehn Kandidaten wurden im Jahre 1998 zum Wettbewerb zugelassen. 1999, also ein Jahr später, wurde der Teilnehmerkreis durch weitere öffentliche Vorschläge auf insgesamt fünf Finalisten reduziert. Im Oktober 2000 wurde einer dieser 5 Algorithmen als der kommende Standard ausgewählt: eine leicht modifizierte Version des Rijndael.

Der Rijndael, der nach seinen Entwicklern Joan Daemen und Vincent Rijmen benannt wurde, ist ein symmetrisches Kryptosystem, ein sogenannter Blockchiffre. Das bedeutet, dass der Algorithmus mit einer Größe von festgelegten Bitgruppen arbeitet, Blöcke genannt. Er nimmt einen Eingabeblock, mit einer bestimmten Größe, gewöhnlich 128 Bit, entgegen und produziert einen korrespondierenden Ausgabeblock, gleicher Größe. Die Transformation benötigt eine zweite Eingabe, den geheimen Schlüssel. Es ist wichtig zu wissen, dass der geheime Schlüssel theoretisch jede Länge haben darf, der AES aber nur drei unterschiedliche Schlüsselgrößen nutzt: 128, 192 und 256 Bit.

Ein Vorläufer von AES ist Square, ebenfalls von den beiden Autoren zusammen mit Lars Knuden entworfen. Rijndael verwendet eine umkehrbare 8x8 Bit S-Box und nutzt Berechnungen mit Polynomen über den Körper GF[28], um gute Diffusionseigenschaften sicherzustellen. Die Berechnungen erinnern an fehlererkennende bzw. korrigierende Codes (MDS-Codes). Rijndael überzeugte nicht nur durch Effizienz, sondern auch durch seine mathematisch elegante und einfache Struktur.
Um eine Nachricht mit dem AES zu verschlüsseln, die länger als die Blockgröße ist, werden diverse Betriebsmodi genutzt, auf die ich am Ende des Tutorials, nach der eigentlichen Implementierung des AES, näher eingehen werde.
Während AES nur mit Blockgrößen von 128 Bit und Schlüsselgrößen von 128, 192 und 256 Bit arbeitet, unterstützt der originale Rijndael Schlüssel- und Blockgrößen, die ein Vielfaches von 32 darstellen, mit einem Minimum von 128 und einem Maximum von 256 Bit.

Weitere Informationen:

Im Gegensatz zum DES, der auf dem Feistelnetzwerk beruht, basiert der AES auf dem Substitutions-Permutations-Netzwerk (SPN), bei dem eine Folge von mathematischen Operationen, mit Substitutionen (auch S-Box genannt) und Permutationen (P-Boxen) genutzt werden. Der Rijndael ist aus einzelnen Schichten aufgebaut, die nacheinander unterschiedliche Wirkungen auf jeweils einen gesamten Block ausüben.

Geschwindigkeit: Rijndael gehört zu den Kandidaten, die die schnellsten Implementierungen erlauben. Der Algorithmus zeichnet sich insbesondere durch eine gleichmäßig gute Performanz über alle betrachteten Plattformen aus, wie z.B. 32-Bit Prozessoren, 8-Bit Mikrocontroller, die derzeit weitverbreitet in Chipkarten eingesetzt werden, und Implementierungen in Hardware. Rijndael erlaubt unter allen Kandidaten die schnellste Erzeugung von Rundenschlüsseln.

Speicherbedarf: Rijndael benötigt sehr geringe Ressourcen an RAM- und ROM-Speicher und ist damit hervorragend für den Einsatz in Umgebungen mit beschränkten Ressourcen geeignet. Der Algorithmus bietet insbesondere die Möglichkeit, die Rundenschlüssel für jede Runde separat zu berechnen (Schlüsselerzeugung „on-the-fly“). Alle Eigenschaften haben eine große Bedeutung für Anwendungen in Chipkarten.

Beschreibung des Advanced Encryption Standard Algorithmuses

AES ist ein iterativer Blockchiffre mit einer festen Blockgröße von 128 Bit und einer variablen Schlüssellänge. Die verschiedenen Transformationen operieren auf den Zwischenergebnissen, State genannt. Der State ist ein rechteckiges Array von Bytes und da die Blockgröße 128 Bit beträgt, was 16 Byte entspricht, umfasst das rechteckige Array eine Dimension von 4x4. (In der Rijndael Version mit einer variablen Blockgröße, ist die Reihengröße festgelegt auf 4 und die Spaltengröße variabel. Die Anzahl an Spalten ist die Blockgröße geteilt durch 32 und wird Nb genannt).

a0,0
a0,1
a0,2
a0,3
a0,4
a0,5
a1,0
a1,1
a1,2
a1,3
a1,4
a1,5
a2,0
a2,1
a2,2
a2,3
a2,4
a2,5
a3,0
a3,1
a3,2
a3,3
a3,4
a3,5

Tabelle 1. Darstellung des State Blocks bei 192 Bit

Der Chiffreschlüssel ist ähnlich aufgebaut, wie das rechteckige Array mit vier Reihen. Die Anzahl an Spalten beim Chiffreschlüssel, Nk genannt, entspricht der Schlüssellänge geteilt durch 32.

k0,0
k0,1
k0,2
k0,3
k1,0
k1,1
k1,2
k1,3
k2,0
k2,1
k2,2
k2,3
k3,0
k3,1
k3,2
k3,3

Tabelle 2. Darstellung des Key Blocks

Es ist sehr wichtig zu wissen, das die Chiffre-Eingabe-Bytes auf die State-Bytes in der Reihenfolge a0,0, a1,0, a2,0, a3,0, a0,1, a1,1, a2,1, a3,1 ... abgebildet werden und die Bytes des Chiffreschlüssels in der Reihenfolge k0,0, k1,0, k2,0, k3,0, k0,1, k1,1, k2,1, k3,1 ... auf das Array. Am Ende der Chiffreoperation, wird die Chiffreausgabe vom State extrahiert, indem die Statebytes in derselben Reihenfolge gelesen werden. AES verwendet eine variable Anzahl von Runden, die festgelegt sind: Ein Schlüssel der Größe 128 besitzt 10 Runden. Ein Schlüssel der Größe 192 hat 12 Runden. Ein Schlüssel der Größe 256 hat 14 Runden. Während jeder Runde, werden die folgenden Operationen am State angewendet:

  1. SubBytes: Im ersten Schritt jeder Runde wird für jedes Byte im Block ein Äquivalent in der S-Box gesucht. Somit werden die Daten monoalphabetisch verschlüsselt.
  2. ShiftRow: Wie oben erwähnt, liegt ein Block in Form einer zweidimensionalen Tabelle mit vier Zeilen (4x4) vor. In diesem Schritt werden die Zeilen um eine bestimmte Anzahl von Spalten nach links verschoben, was einem Links-Shift entspricht. Überlaufende Zellen werden von rechts fortgesetzt. Die Anzahl der Verschiebungen ist zeilen- und blocklängenabhängig.
  3. MixColumn: Schließlich werden die Spalten vermischt. Es wird zunächst jede Zelle einer Spalte mit einer Konstanten multipliziert und anschließend die Ergebnisse XOR verknüpft. Hinter dieser Vorgehensweise steckt ein komplizierter mathematischer Zusammenhang - eine lineare Transformation an den Spalten des State - der später näher erläutert wird.
  4. AddRoundKey: In der Vorrunde und am Ende jeder weiteren Verschlüsselungsrunde wird die KeyAddition ausgeführt. Hierbei wird eine bitweise XOR-Verknüpfung zwischen dem Block und dem aktuellen Rundenschlüssel vorgenommen. Dies ist die einzige Funktion in AES, die den Algorithmus vom Benutzerschlüssel abhängig macht. Der aktuelle Benutzerschlüssel wird vom Rijndael Key Schedule abgeleitet.

In der finalen Runde wird die MixColumn Operation ausgelassen. Der Algorithmus sieht wie folgt aus (pseudo-C):

AES(state, CipherKey)
{
    KeyExpansion(CipherKey, ExpandedKey);
    AddRoundKey(state, ExpandedKey);
    for (i = 1; i < Nr; i++) {
        Round(state, ExpandedKey + Nb * i);
    }
    FinalRound(state, ExpandedKey + Nb * Nr);
}

Beschreibung:

  • Zunächst muss der Schlüssel in R + 1 Teilschlüssel (auch Rundenschlüssel genannt) aufgeteilt werden. Die Rundenschlüssel müssen die gleiche Länge wie die Blöcke erhalten. Somit muss der Benutzerschlüssel auf die Länge b * (R + 1) expandiert werden, wobei b die Blockgröße angibt. Die Schlüsselexpansion vollzieht sich in der Funktion KeyExpansion().
  • Der Rundenschlüssel wird mit dem State-Block bitweise XOR verknüpft, bevor mit der for-Schleife begonnen wird.
  • Die FinalRound() ist dieselbe Runde, wie Round(), mit der Ausnahme das die Operation MixColumns() fehlt.
  • Während jeder Runde, wird ein anderer Teil des expandierten Schlüssels (ExpandedKey) für die Operationen verwendet.
  • Der ExpandedKey sollte stets vom Chiffreschlüssel abgeleitet, niemals direkt spezifiziert werden.

Bevor wir uns detaillierter mit der Arbeitsweise des AES befassen, können Sie sich interaktiv ein wenig mit dem Rijndael-Algorithmus vertraut machen. Dafür steht eine multimediale Flash-Animation zur Verfügung.

Lernen Sie die Funktionsweise des Advanced Encryption Standard (AES) anschaulich mit der Rijndael Animation (Version 4) näher kennen.

AES Operationen: SubBytes, ShiftRows, MixColumns und AddRoundKey

Die AddRoundKey Operation:

In dieser Operation, wird eine bitweise XOR-Verknüpfung zwischen dem Block (State) und dem aktuellen Rundenschlüssel vorgenommen. Der Rundenschlüssel wird vom Chiffreschlüssel abgeleitet, mithilfe des Rijndael Key Schedule. Die Länge des Rundenschlüssels entspricht bekannterweise der Blockgröße b. Bei 128 Bit sind das 16 Byte.

a0,0
a0,1
a0,2
a0,3
k0,0
k0,1
k0,2
k0,3
b0,0
b0,1
b0,2
b0,3
a1,0
a1,1
a1,2
a1,3
k1,0
k1,1
k1,2
k1,3
=
b1,0
b1,1
b1,2
b1,3
a2,0
a2,1
a2,2
a2,3
k2,0
k2,1
k2,2
k2,3
b2,0
b2,1
b2,2
b2,3
a3,0
a3,1
a3,2
a3,3
k3,0
k3,1
k3,2
k3,3
b3,0
b3,1
b3,2
b3,3

Tabelle 3. AddRoundKey Operation mit b(i,j) = a(i,j) XOR k(i,j)

Eine graphische Repräsentation dieser Operation kann unten betrachtet werden:

Highslide JS
AES-AddRoundKey: Im AddRoundKey Schritt wird jedes Byte des State mit einem Byte des aktuellen Rundenschlüssels kombiniert, indem die XOR-Verknüpfung (⊕) verwendet wird.

Die ShiftRows Operation:

In diesem Schritt werden die Zeilen um eine bestimmte Anzahl von Spalten nach links verschoben. Überlaufende Zellen werden von rechts fortgesetzt. Die Anzahl der Verschiebungen ist zeilen- und blocklängenabhängig, richtet sich also nach einem Index. Man spricht von einer sogenannten ShiftRows-Transformation, bei der die Bytes des Blocks permutiert werden.

Highslide JS
AES-ShiftRows: Im ShiftRows Schritt, werden die Bytes in jeder Reihe des State zyklisch nach links geschoben. Die Anzahl der Verschiebungen ist zeilen- und blocklängenabhängig.

Bitte notieren Sie das die Inversion von ShiftRows derselbe zyklische Shift ist, diesmal nur nicht nach links, sondern nach rechts. Dies wird später für die Entschlüsselung von Bedeutung sein.

Die SubBytes Operation:

Die SubBytes Operation ist eine nichtlineare Byte-Substitution, die in jeder Runde für jedes Byte im Block ein Äquivalent in der S-Box sucht. Die Substitutionstabelle (S-Box) ist umkehrbar und wird durch die Synthese von zwei Transformationen konstruiert:

  1. Nehme die vielfache Inverse des Rijndael Galois-Feldes.
  2. Wenden Sie eine affine Transformation, die in der Rijndael Dokumentation beschrieben wird an.

Da die S-Box unabhängig von der Eingabe ist, werden vorberechnete Formen verwendet, falls genug Speicher (256 Bytes) für eine S-Box zur Verfügung steht. Jedes Byte des State wird dann durch einen Wert in der S-Box substituiert, dessen Index mit dem aktuellen Wert im State korrespondiert:

a(i,j) = SBox[a(i,j)]

Bitte notieren Sie das die Inversion von SubBytes dieselbe Operation unter Verwendung der inversen S-Box darstellt, die ebenfalls vorberechnet vorliegen kann.

Highslide JS
AES-SubBytes: In der Operation SubBytes, wird jedes Byte des State durch einen Wert in der S-Box substituiert.

Die MixColumns Operation:

Die folgenden Operationen beruhen auf komplexen mathematischen Kalkulationen im Rijndael Galois-Feld GF(28). Sie müssen diese theoretischen Details für die Implementation des AES nicht genau kennen, sofern Sie allerdings Wert auf die exakten mathematischen Vorgänge legen, sollten Sie die nächsten Zeilen etwas genauer studieren. Andernfalls können Sie diese Zeilen getrost überfliegen.

In der MixColumns Stufe wird eine von vier Spalten der 4×4 existierenden Rijndael-Werte genommen und anschließend wird eine Matrizenmultiplikation im Rijndael Galois-Feld durchgeführt, damit jedes Eingabe-Byte alle vier Ausgabe-Bytes beeinflußt. Die bei der Verschlüsselung erwünschte Diffusion, also die Verteilung von Redundanzen, wird unter anderem mithilfe der sogenannten MDS-Matrix (Maximum Distance Separable) erzielt. Die Matrix repräsentiert eine Funktion mit ganz bestimmten Diffusionseigenschaften. Die Diffusion wurde von Claude Elwood Shannon in seiner Ausarbeitung „Communication Theory of Secrecy Systems“, die 1949 veröffentlicht wurde, beschrieben. Primär geht es bei der Diffusion darum, dass die Ausgabebits auf möglichst komplexe Art und Weise von den Eingabebits abhängen sollten. In einer Verschlüsselung sollte sich bei einer Änderung des Klartextes, der Geheimtext in einer nicht absehbaren und pseudozufälligen Weise vollständig verändern. Diese Eigenschaft wird durch das Strict Avalanche Criterion (SAC) definiert, wonach sich durch Änderung eines Eingabebits jedes Ausgabebit mit der Wahrscheinlichkeit von genau 1/2 ändert. Eine unmittelbare Folge, welche sich aus dieser Eigenschaft für die Kryptoanalyse ergibt, ist das es dem Angreifer erschwert wird den Schlüssel zu berechnen, auch wenn er eine Vielzahl verschiedener Klartext/Geheimtext-Paare besitzt, die mit demselben Schlüssel generiert wurden. Der AES erzielt die Diffusion und Konfusion mit dem Substitutions-Permutations-Netzwerk, realisiert in SubBytes (S-Box Substitution), ShiftRows, MixColumns und der nachfolgenden Multiplikationsstufe. Die Designkriterien für die MDS-Matrix sind komplex, d.h. es gestaltet sich mitunter schwierig eine gute MDS-Matrix zu entwerfen. In der Regel werden für die Konstruktion dieser Matrizen besondere mathematische Kenntnisse benötigt, die Matrizen werden anschließend in aufwendigen Computersimulationen auf ihre kryptographische Eignung hin überprüft.

Theoretisch gesehen ist eine m×n Matrix A über einen finiten Feld K eine MDS-Matrix, wenn sie die Transformationsmatrix der linearen Transformation f(x)=Ax von Kn bis Km darstellt, so dass keine zwei unterschiedlichen (m+n)-Tupel der Form (x,f(x)) in n oder mehr Komponenten koinzidieren. In der Kodierungstheorie (insbesondere Fehlerkorrektur-Codes) sind vor allem Codes von Interesse, in welchen die Codewörter so weit wie möglich voneinander entfernt liegen. Der Abstand zwischen zwei Codewörtern ist die Hamming-Distanz. Der Einsatz von Maximum-Distanz-Codes in der Kryptographie geht auf Serge Vaudenay zurück, der den Vorteil von Distanz-Codes in krypotgraphischen Algorithmen entdeckte.

Nach der zeilenweisen Permutation im Schritt ShiftRows wird in dem Schritt MixColumns jede Spalte eines Blocks als Polynom über F 28 aufgefasst und mit dem konstanten Polynom a(x) := a3x3 + a2x2 + a1x + a0 mit Koeffizienten a0(x) = x, a1(x) = 1, a2(x) = 1 und a3(x) = x + 1 multipliziert und modulo M(x) := x4 + 1 reduziert. Diese Berechnung kann sehr effizient implementiert werden, indem jede Spalte (bi,j)i=0,...,3 der Zustandsvariablen State über F 28 mit der MDS-Matrix multipliziert wird. Dieser Schritt ist zusammen mit der MDS-Matrix des AES nachfolgend abgebildet:

State-mul

Es handelt sich um eine zyklische Matrix, eine spezielle Form der Toeplitz-Matrix, bei der jeder Zeilenvektor jeweils um ein Element (Permutationsbedingung) nach rechts verschoben wird, relativ zum vorangegangenen Zeilenvektor.

circulant_matrix

Die Matrix erfüllt die Bedingung A2 ≠ I, d.h. es handelt sich nicht um eine involutorische Matrize deren Quadrat die Einheitsmatrix ist. Die Ursache dafür, dass die Matrix mit sich selbst multipliziert nicht die Einheitsmatrix generiert, liegt nicht in den Elementen begründet.

non_involutory_aes_mds_matrix

Eine einfache Möglichkeit MDS-Matrizen zu erhalten, ist auf zyklische Matrizen zurückzugreifen. Allerdings kann eine zyklische 4×4 Matrix nicht gleichzeitig MDS und involutorisch sein. Das trifft auch auf höherdimensionale, zyklische Matrizen zu. Ein anderer Ansatz für die Konstruktion von involutorischen MDS-Matrizen beruht auf sogenannten Cauchy-Matrizen, eine Generalisierung der Hilbert-Matrix. Im AES wurde eine zyklische Matrix für die Konstruktion verwendet. Das hat allerdings den Nachteil das die Matrix nicht involutorisch ist, so dass bei der Ver- und Entschlüsselung nicht gleich optimale Diffusionsleistungen erzielt werden können. Die Verwendung einer 4×4 Matrix führt außerdem zu weniger primitiven Rechenoperationen, die allerdings in mehreren Runden wiederholt werden müssen, um eine gute Diffusion zu gewährleisten. In einer grafischen Darstellung des Substitutions-Permutations-Netzwerks wird diese Diffusionswirkung grafisch veranschaulicht.

aes_substitution_permutation_network

Die Multiplikation von Polynomen mit x und x + 1 (bzw. '02' und '03') sind besonders schnell als Shift- und XOR-Operationen zu realisieren. Beispielsweise kann die Multiplikation eines Polynoms f aus F 28[X] mit x + 1 (bzw. '03') und die anschließende Reduzierung modulo m(x) := x8 + x4 + x3 + x + 1 erfolgen, indem die Binärzahl a aus den Koeffizienten von f um eine Stelle nach links geschoben mit sich selbst und danach bei Auftreten eines Übertrags mit '1b' XORiert wird. Zwei Zeilen in C veranschaulichen die Vorgehensweise:

a ^= a << 1;
if (a & 0x100) a ^= 0x011b;

Durch die MixColumns-Transformation tritt jedes Byte einer Spalte in Wechselwirkung mit jedem anderen Byte der Spalte. Die vorangegangene zeilenweise operierende ShiftRows-Transformation bewirkt, dass in jeder Runde andere Bytes miteinander vermischt werden, wodurch insgesamt eine starke Diffusionswirkung erreicht wird. Weitere Designkriterien sind die Invertierbarkeit und die Performanz der Transformation.

Zur Invertierung der MixColumns-Transformation bei der Entschlüsselung wird jede Spalte (bi,j) eines Blocks mit dem Polynom r(x) := r3x3 + r2x2 + r1x + r0 mit Koeffizienten r0(x) = x3 + x2 + x, r1(x) = x3 + 1, r2(x) = x3 + x2 + 1 und r3(x) = x3 + x + 1 multipliziert und modulo M(x) := x4 + 1 reduziert. Die korrespondierende inverse MDS-Matrix lautet:

corr-matrix

Die bei der Invertierung auftretenden Multiplikationen werden am schnellsten über zwei Tabellen ausgeführt, in denen zum einen die Potenzen eines Generatorpolynoms g(x) von F 28 und zum anderen die Logarithmen der Werte von F 28 zur Basis g(x) gespeichert sind.

Highslide JS
AES-MixColumns: Im Schritt MixColumns, findet eine Matrizenmultiplikation eines Spaltenvektors des State mit einer speziellen Matrix statt, damit alle 4 Eingabebytes jedes Ausgabebyte beeinflussen.

Auch die Addition und Multiplikation geht in diesem Schritt ein wenig anders als gewöhnlich vonstatten.
Sie können den nächsten Abschnitt überspringen, falls Sie an den Grundlagen nicht interessiert sind:

Arithmetische Operationen im Galois-Feld:

In jedem Handy, CD-Player und Computer steckt ein Chip, der lineare Gleichungssysteme über einem endlichen Körper blitzschnell löst, um fehlerbehaftetes Datenmaterial zu korrigieren. Auch der Advanced Encryption Standard greift intern auf einen endlichen Körper zurück.

Der endliche Körper oder Galoiskörper ist eine Menge mit einer endlichen Anzahl von Elementen, auf der die Grundoperationen Addition, Subtraktion, Multiplikation und Division definiert sind. Genauer gesagt, erlaubt der Galoiskörper des Rijndael GF(28) nur 8-Bit große Nummern (0 bis 255). Alle mathematischen Operationen in diesem Feld resultieren wiederum in einer 8-Bit Nummer. Demzufolge findet auch kein Variablenüberlauf statt.

Alle Byte-Werte im AES Algorithmus werden als Verkettung ihrer individuellen Bitwerte (0 oder 1) in der Reihenfolge { b7, b6, b5, b4, b3, b2, b1, b0 } dargestellt.

b7x7 + b6x6 + b5x5 + b4x4 + b3x3 + b2x2 + b1x1 + b0 = Σ bixi mit 0 ≤ i ≤ 7

Zum Beispiel identifiziert { 0 1 1 0 0 0 1 1 } das spezifische endliche Feldelement x6 + x5 + x + 1.

Addition und Subtraktion

Die Addition und Subtraktion werden mithilfe der exklusiv-ODER Operation durchgeführt. Die zwei Operationen sind identisch; es gibt keinen Unterschied zwischen der Addition und der Subtraktion.

/* Add two numbers in a GF(2^8) finite field */
uint8_t galois_add(uint8_t a, uint8_t b) 
{
    return a ^ b;
}
 
/* Subtract two numbers in a GF(2^8) finite field */
uint8_t galois_sub(uint8_t a, uint8_t b) 
{
    return a ^ b;
}
Multiplikation

Die Multiplikation im Rijndael Galois-Feld ist ein wenig komplizierter. Sie korrespondiert mit der Multiplikation von Polynomen modulo mit einem unreduzierbaren Polynom 8 Grades. Ein Polynom gilt dann als nicht weiter reduzierbar, wenn man es entweder nur durch sich selbst oder durch 1 teilen kann. Für den AES Algorithmus lautet das unreduzierbare Polynom

m(x) := x8 + x4 + x3 + x + 1

hexadezimal mit {01}{1b} notiert.

Die modulare Reduktion durch m(x) garantiert dass das Ergebnis ein Polynom ist, welches einen kleineren Grad als 8 hat, so dass es als Byte repräsentiert werden kann. Im Gegensatz zur Addition existiert auf der Byteebene keine einfache Operation die zu dieser Multiplikation korrespondiert.

Es existiert allerdings für den speziellen Fall, das der Multiplikant x ist, eine effektive Methode, die Multiplikation auf der Byteebene sehr effizient durchzuführen. Wenn x • b(x), dann gilt:

b7x8 + b6x7 + b5x6 + b4x5 + b3x4 + b2x3 + b1x2 + b0x

Dieses Polynom wird dann wieder mit m(x) reduziert, sofern das Bit b7 1 ist. Falls es 0 ist, liegt das Polynom bereits in der reduzierten Form vor. Daraus folgt das die Multiplikation mit x (z.B. { 0 0 0 0 0 0 1 0 } oder {02}) durch einen Links-Shift auf der Byteebene und einem anschließenden bedingten bitweisen XOR mit {1b} implementiert werden kann. Der Links-Shift bewirkt nichts anderes als eine Graderhöhung aller Elemente des Polynoms, die durch die Multiplikation mit x entsteht. Beispielsweise wird x3 durch die Multiplikation mit x zu x4. Diese Operation wird offiziell xtime() genannt. Die Multiplikation mit höheren Exponenten von x, kann durch mehrfache Anwendung dieser Operation realisiert werden. Durch Zwischenergebnisse kann die Multiplikation für jede Konstante implementiert werden:

Zum Beispiel,

{57} • {13} = {fe}
weil

{57} • {02} = xtime({57}) = {ae}
{57} • {04} = xtime({ae}) = {47}
{57} • {08} = xtime({47}) = {8e}
{57} • {10} = xtime({8e}) = {07},

daraus folgt:

{57} • {13} = {57} • ({01} ⊕ {02} ⊕ {10})
            = {57} ⊕ {ae} ⊕ {07}
            = {fe}.

Wir betrachten den Algorithmus für die Multiplikation mit x mithilfe von xtime():

/**
 * Rijndael fast multiplying binary polynomial with polynomial x
 */
uint8_t xtime(x)
{
    return ((x << 1) ^ ((x & 0x80) ? 0x1B : 0x00));
}

Der Ausdruck wirkt anfangs etwas kryptisch, ist allerdings recht trivial. Auf der linken Seite wird zunächst ein Links-Shift durchgeführt. Auf der rechten Seite erfolgt eine Bitmaskierung mit der hexadezimalen Zahl {80} die binär dem Tupel { 1 0 0 0 0 0 0 0 } entspricht. Es wird also überprüft ob der Wert in x am MSB 1 ist, d.h. ob nach dem Links-Shift eine Reduktion notwendig wird. Ist das der Fall, wird der links geshiftete Ausdruck mit dem Polynom {1b} durch ein XOR reduziert, andernfalls wird das links geshiftete x nicht mehr verändert, da eine XORierung mit 0x00 keine Auswirkung auf das Bitmuster hat. Das x8 Bit spielt keine Rolle, da es bei 8-Bit Integern überhaupt nicht zur Verfügung steht. Es wird also nur geprüft ob dieses Bit bei einem Links-Shift auftauchen würde und somit eine Reduktion notwendig wäre. Deshalb kommt das unreduzierbare Polynom verkürzt mit x4 + x3 + x + 1 zum Einsatz.

Wir betrachten den Algorithmus für die Multiplikation mit einer beliebigen Konstante schrittweise:

  • Man nehme zwei 8-Bit große Nummern, a und b, und ein 8-Bit großes Produkt p.
  • Setze das Produkt auf null.
  • Mache eine Kopie von a und b, die wir im Rest des Algorithmuses einfach mit a und b aufrufen werden.
  • Rufe die folgende Schleife acht Mal auf:
    1. Falls das LSB von b gesetzt ist, führe eine bitweise XOR-Verknüpfung des Produktes p mit dem Wert von a durch
    2. Achten Sie darauf ob das MSB (das Achte von links) von a auf eins gesetzt ist
    3. Rotiere a ein Bit nach links, verwerfe damit das MSB und lasse das LSB null sein
    4. Falls das MSB vor dieser Rotation gesetzt war, führe eine bitweise XOR-Verknüpfung von a mit der hexadezimalen Ziffer 0x1b durch
    5. Rotiere b ein Bit nach rechts, verwerfe das LSB, und lasse das MSB null sein
  • Das Produkt p besitzt nun das Produkt von a und b

Vielen Dank an Sam Trenholme für die detaillierte Erklärung. Nachfolgend können wir damit die allgemeine Multiplikation im GF(28) in C-Code realisieren:

/**
 * Multiply two numbers in the GF(2^8) finite field defined 
 * by the polynomial x^8 + x^4 + x^3 + x + 1 
 */
uint8_t galois_multiplication(uint8_t a, uint8_t b) 
{
    uint8_t p = 0;
    uint8_t hi_bit_set;
    uint8_t counter;
 
    for (counter = 0; counter < 8; counter++) {
        if ((b & 1) == 1) 
            p ^= a;
        hi_bit_set = (a & 0x80);    // xtime() ...
        a <<= 1;
        if (hi_bit_set == 0x80) 
            a ^= 0x1b;              // ...
        b >>= 1;
    }
 
    return p;
}

Der Code verwendet xtime() in einer etwas anschaulichereren Weise. Der betreffende Abschnitt ist hervorgehoben.

Die Funktion ist in der Lage zwei beliebige Zahlen im GF miteinander zu multiplizieren. Das geschieht durch eine Schleife, die insgesamt 8 mal durchlaufen wird, was den 8-Bit Stellen einer Zahl entspricht. In jedem Schleifendurchgang wird die Funktion xtime() aufgerufen, d.h. a wird mit dem Polynom x (0x02) multipliziert, ggf. mit (0x1b) reduziert und wieder an a zugewiesen. Am Ende der Schleife wird das Polynom b durch einen Rechts-Shift reduziert. Diese Reduzierung wird am Anfang der Schleife überprüft, indem nachgesehen wird, ob das LSB von b gesetzt ist. Die Schleife korrespondiert nämlich mit dem Stellenwert des Polynoms. Das heißt, dass das LSB nach dem dritten Schleifendurchgang der dritten Stelle im Polynom entspricht. Die Bitstellen des Polynoms wurden im dritten Schleifendurchgang schließlich bereits drei mal nach rechts geschoben, das Polynom also um drei Grade reduziert. Ist das LSB gesetzt, wird das letzte berechnete Ergebnis von xtime() mit einem XOR zu p addiert. Das ist prinzipiell nichts anderes, als die angesprochene mehrfache Anwendung von xtime(), die immer dann zum Einsatz kommt, wenn an der Stelle des Polynoms im zweiten Multiplikator, die dem jeweiligen Grad entspricht, eine 1 stand.

Nachdem wir nun die Addition, Subtraktion und Multiplikation im Rijndael GF kennengelernt haben, können wir die Vorgänge bei der MixColumns Stufe genau nachvollziehen. Um diese tatsächlich zu verstehen, ist es oft hilfreich, sich mit einem konkreten Beispiel auseinanderzusetzen. Wir greifen dazu auf unsere Rijndael Animation zurück und berechnen die erste Transformation per Hand:

Highslide JS
MixColumns: Darstellung der Transformation der ersten Spalte im Galois-Feld (MixColumns-Stufe).

Wir führen die Berechnung für die erste Zeile der MDS Matrix durch. Es ergibt sich für die erste Spalte nach den Regeln der Matrizenmultiplikation folgender Zusammenhang:

{D4} • {02} + {BF} • {03} + {5D} • {01} + {30} • {01}

Reduktion des Polynoms für die Multiplikation:

m(x) := x8 + x4 + x3 + x + 1

Nun können wir beginnen die 4 Multiplikationen durchzuführen. Wir beginnen mit {D4} • {02}, und stellen beide Werte entsprechend in 8-Bit Gruppen binär dar:

{D4} = 11010100, {02} = 00000010

Daraus ergibt sich folgende Multiplikation:

(x7 + x6 + x4 + x2) (x) =
x8 + x7 + x5 + x3

Nun müssen wir abschließend noch das Ergebnis modulo m(x) := x8 + x4 + x3 + x + 1 reduzieren. Dazu nutzen wir die Division. Bedenken Sie das entgegen dem, was Sie vielleicht in der Schule gelernt haben, die Dualzahlen nicht subtrahiert, sondern XOR-verknüpft werden.

                        
          110101000 (mod) 100011011
         ⊕100011011     
           010110011

Wir erhalten das Ergebnis B3 (010110011) für die Multiplikation der beiden hexadezimalen Zahlen D4 und 02 im Galois-Feld. Berechnen wir noch ein zweites Beispiel. Wir nehmen uns die nächste Multiplikation vor, nämlich {BF} • {03}:

(x7 + x5 + x4 + x3 + x2 + x) (x + 1) =
x8 + x7 + x6 + 2x5 + 2x4 + 2x3 + 2x2 + 2x + 1 =
x8 + x7 + x6 + 1

In diesem Beispiel zeigt sich das Vielfache von 2 bei der Multiplikation wegfallen, was auf die Arithmetik bei dualen Zahlen zurückzuführen ist. Erneut führen wir die Reduktion mit dem modulo-Operator durch.

                        
          111000001 (mod) 100011011
         ⊕100011011     
           011011010

Wir erhalten das Ergebnis DA (011011010) für die Multiplikation der beiden hexadezimalen Zahlen BF und 03 im Galois-Feld. Analog zu den beiden bereits getätigten Multiplikationen werden die beiden anderen durchgeführt. Da es sich um eine Multiplikation mit 01 handelt, muss nicht viel gerechnet werden. Wir erhalten das folgende Ergebnis:

{B3} + {DA} + {5D} + {30}

Die Addition erfolgt bekannterweise über eine einfache XOR-Verknüpfung (⊕). Wir verzichten darauf, diesen trivialen Schritt hier näher darzustellen und präsentieren das Ergebnis der Addition, dieser vier Zahlen. Das Ergebnis ist 04, welches sich erwartungsgemäß mit dem Ergebnis in der Rijndael Animation deckt.

Potenzieren und Logarithmieren

Eine weitere interessante Operation im Galois-Feld ist das Potenzieren und Logarithmieren. Potenziert wird durch wiederholte Multiplikation mit derselben Nummer. Mit einigen, aber nicht allen Nummern im Rijndael Galois-Feld, ist es möglich durch das Potenzieren über alle Werte im GF, mit Ausnahme der Null, zu iterieren. Diese Nummern nennen sich primitive Elemente oder Generatoren. Mit Hilfe eines primitiven Elements kann die Multiplikation in einem endlichen Körper sehr übersichtlich organisiert werden.

Ein erzeugendes Element der multiplikativen, zyklischen Gruppe F * eines endlichen Körpers F heißt primitives Element des Körpers F. Ein Element u in einem kommutativen Ring R heißt Einheit, wenn es ein Element v ∈ R gibt derart, dass uv = 1 ist. Eine Einheit u ∈ (Z/(n))× heißt primitiv, wenn es die Einheitengruppe erzeugt. Wie kann man diese primitiven Einheiten finden? Man ist hierbei prinzipiell auf Probieren angewiesen, man kann den Vorgang allerdings durch einige triviale Überlegungen deutlich vereinfachen. Das Rijndael Galois-Feld hat die folgenden Generatoren.

3 5 6 9 11 14 17 18 19 20 23 24 25 26 28 30 31 33 34 35 39 40 42 44 48 49 60 62 63 65 69 70 71 72 73 75 76 78 79 82 84 86 87 88 89 90 91 95 100 101 104 105 109 110 112 113 118 119 121 122 123 126 129 132 134 135 136 138 142 143 144 147 149 150 152 153 155 157 160 164 165 166 167 169 170 172 173 178 180 183 184 185 186 190 191 192 193 196 200 201 206 207 208 214 215 218 220 221 222 226 227 229 230 231 233 234 235 238 240 241 244 245 246 248 251 253 254 255

Nachdem ein Generator mehrmals multipliziert wurde, erreicht man nach exakt 255 Multplikationen wieder den Ursprungswert. Nachfolgend können Sie eine Potenztabelle in hexadezimaler Schreibweise für den Generator 0x03 betrachten:

   | 0  1  2  3  4  5  6  7  8  9  a  b  c  d  e  f|   
---|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|---
00 |01 03 05 0f 11 33 55 ff 1a 2e 72 96 a1 f8 13 35| 00
10 |5f e1 38 48 d8 73 95 a4 f7 02 06 0a 1e 22 66 aa| 10
20 |e5 34 5c e4 37 59 eb 26 6a be d9 70 90 ab e6 31| 20
30 |53 f5 04 0c 14 3c 44 cc 4f d1 68 b8 d3 6e b2 cd| 30
40 |4c d4 67 a9 e0 3b 4d d7 62 a6 f1 08 18 28 78 88| 40
50 |83 9e b9 d0 6b bd dc 7f 81 98 b3 ce 49 db 76 9a| 50
60 |b5 c4 57 f9 10 30 50 f0 0b 1d 27 69 bb d6 61 a3| 60
70 |fe 19 2b 7d 87 92 ad ec 2f 71 93 ae e9 20 60 a0| 70
80 |fb 16 3a 4e d2 6d b7 c2 5d e7 32 56 fa 15 3f 41| 80
90 |c3 5e e2 3d 47 c9 40 c0 5b ed 2c 74 9c bf da 75| 90
a0 |9f ba d5 64 ac ef 2a 7e 82 9d bc df 7a 8e 89 80| a0
b0 |9b b6 c1 58 e8 23 65 af ea 25 6f b1 c8 43 c5 54| b0
c0 |fc 1f 21 63 a5 f4 07 09 1b 2d 77 99 b0 cb 46 ca| c0
d0 |45 cf 4a de 79 8b 86 91 a8 e3 3e 42 c6 51 f3 0e| d0
e0 |12 36 5a ee 29 7b 8d 8c 8f 8a 85 94 a7 f2 0d 17| e0
f0 |39 4b dd 7c 84 97 a2 fd 1c 24 6c b4 c7 52 f6 01| f0
---|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|---
   | 0  1  2  3  4  5  6  7  8  9  a  b  c  d  e  f|   

Die Multiplikation vollzieht sich von links nach rechts. In dem Diagramm wird zunächst 0x01 mit 0x03 multipliziert, was zu dem Ergebnis 0x03 führt. Danach wird 0x03 erneut mit 0x03 multipliziert, mit dem Ergebnis 0x05 usw.

Aus der Potenztabelle lässt sich umgehend die korrespondierende Logarithmustabelle generieren.

   | 0  1  2  3  4  5  6  7  8  9  a  b  c  d  e  f|   
---|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|---
00 |00 ff 19 01 32 02 1a c6 4b c7 1b 68 33 ee df 03| 00
10 |64 04 e0 0e 34 8d 81 ef 4c 71 08 c8 f8 69 1c c1| 10
20 |7d c2 1d b5 f9 b9 27 6a 4d e4 a6 72 9a c9 09 78| 20
30 |65 2f 8a 05 21 0f e1 24 12 f0 82 45 35 93 da 8e| 30
40 |96 8f db bd 36 d0 ce 94 13 5c d2 f1 40 46 83 38| 40
50 |66 dd fd 30 bf 06 8b 62 b3 25 e2 98 22 88 91 10| 50
60 |7e 6e 48 c3 a3 b6 1e 42 3a 6b 28 54 fa 85 3d ba| 60
70 |2b 79 0a 15 9b 9f 5e ca 4e d4 ac e5 f3 73 a7 57| 70
80 |af 58 a8 50 f4 ea d6 74 4f ae e9 d5 e7 e6 ad e8| 80
90 |2c d7 75 7a eb 16 0b f5 59 cb 5f b0 9c a9 51 a0| 90
a0 |7f 0c f6 6f 17 c4 49 ec d8 43 1f 2d a4 76 7b b7| a0
b0 |cc bb 3e 5a fb 60 b1 86 3b 52 a1 6c aa 55 29 9d| b0
c0 |97 b2 87 90 61 be dc fc bc 95 cf cd 37 3f 5b d1| c0
d0 |53 39 84 3c 41 a2 6d 47 14 2a 9e 5d 56 f2 d3 ab| d0
e0 |44 11 92 d9 23 20 2e 89 b4 7c b8 26 77 99 e3 a5| e0
f0 |67 4a ed de c5 31 fe 18 0d 63 8c 80 c0 f7 70 07| f0
---|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|---
   | 0  1  2  3  4  5  6  7  8  9  a  b  c  d  e  f|   

In diesem Diagramm lässt sich erkennen, das der Logarithmus von 01 erwartungsgemäß 00 ist. Darüberhinaus sieht man, wie oft man die hexadezimale Zahl 0x03 multiplizieren muss um die gewünschte Zahl zu erhalten.

Beachten Sie, dass unsere Logarithmustabelle eigentlich nur 255 Werte besitzt. Die 0x00 ist ein spezieller Fall, da ein Generator mit keiner Zahl so oft multipliziert werden kann, das 0 heraus käme. Alles was mit 0 multipliziert wird, ergibt wiederum 0. Man könnte diesen Eintrag in der Tabelle auch durch einen beliebigen Eintrag ersetzen, da auf dieses Feld (0x00) niemals zugegriffen wird.
Bei Überläufen, die bei der gewöhnlichen Addition stattfinden kann, sollte das stets berücksichtigt werden. Auf 8-Bit Systemen muss deshalb 1 addiert werden, sobald ein Überlauf (Carry) stattfindet.

Um eine Zahl im obigen Diagramm zu erhalten, müssen Sie lediglich den Hexwert auf der linken Seite mit dem Hexwert oben kombinieren. Nehmen wir als Beispiel die Zahl 6a, mit den Koordinaten Zeile 60 und Spalte a. In der Logarithmustabelle ergibt das den korrespondierenden Hexwert 0x28, was der Dezimalzahl 40 entspricht. Das bedeutet wir müssen 40 mal mit 0x03 multiplizieren um den Wert 6a zu erhalten. In der Potenztabelle sehen wir das exakt nach vierzig Multiplikationen mit 0x03 die Hexzahl 6a erscheint. Und wie wir bereits weiter oben erfahren haben, muss eine Zahl insgesamt 255 mal mit sich selbst multipliziert werden, um wieder dieselbe Zahl zu erhalten. Das entspricht exakt dem hexadezimalen Wert ff. Auch lässt sich sehen, das wir für die Koordinaten 03 die Zahl 0x01 vorfinden. Das bedeutet, wir müssen 0x01 einmal mit 0x03 multiplizieren und erhalten 0x03 als Ergebnis. Auch das deckt sich mit unseren Erwartungen.

Sie werden sich nun womöglich fragen, welchem Zweck diese Betrachtungen dienen? Wie wir im Kapitel über die MixColumns Operation erfahren haben, werden die bei der Invertierung auftretenden Multiplikationen am schnellsten über zwei Tabellen ausgeführt. Diese Tabellen sind die Potenz- und Logarithmustabelle. Alles was wir dazu benötigen sind zusätzliche 512 Byte Speicherplatz um die beiden Tabellen dort abzulegen. Als Beispiel multiplizieren wir erneut die beiden hexadezimalen Zahlen 57 und 13 miteinander, diesmal verwenden wir aber nicht xtime(), sondern die generierten Tabellen:

  • Wir sehen zuerst in die Logarithmustabelle und entnehmen für die Koordinaten 57 den Wert 62.
  • Dasselbe machen wir für den Multiplikand und erhalten den Wert 0e.
  • Nun addieren wir noch beide Werte auf herkömmliche Art und Weise und erhalten das Ergebnis 70.
  • Zum Schluß müssen wir nur noch den korrespondierenden Hexwert in der Potenztabelle ermitteln, dieser lautet fe und damit haben wir das Ergebnis vorliegen.

Nachfolgend ist der zugehörige neue Code für die Multiplikation aufgelistet:

/**
 * Fast multiply two numbers in the GF(2^8) finite field defined
 * using a logarithm and exponentiation table.
 */
uint8_t galois_fast_multiplication(uint8_t a, uint8_t b) 
{
    return ((a && b) ? exptable[(logtable[a] + logtable[b]) % 255] : 0);
}

Sobald wir über eine Potenz- und Logarithmustabelle (engl. lookup tables) verfügen, können wir auf die zeitraubende Funktion galois_multiplication verzichten und die Ergebnisse direkt mithilfe der Tabellen auslesen. Für die Verschlüsselung ist die Zeitersparnis durch diese Tabellen nicht sehr groß, da dort die höchste Zahl mit der multipliziert wird, die 3 ist. Allerdings beschleunigt es die Entschlüsselung, bei der mit größeren Multiplikatoren gerechnet wird. Zudem sind die Tabellen für die spätere Berechnung der S-Box von Bedeutung, die mithilfe der multiplikativen Inversen berechnet wird, auf welche wir später, nach der Division, zu sprechen kommen werden.

Werfen wir zunächst noch einen kurzen Blick auf einen Benchmark zwischen den beiden Funktionen. Der Benchmark greift auf QPF/QPC zurück um die CPU-Ticks zu zählen. Die Funktion galois_fast_multiplication schneidet in der Regel noch einmal um den Faktor 4 besser ab als die bereits effizient implementierte Funktion galois_multiplication, die wir weiter oben kennengelernt haben.

galois-mul-perf-test

Eine vollständige Auflistung der 128 möglichen Potenz- und Logarithmustabellen für alle Generatoren finden Sie hier. Das C-Programm, mit dem die Tabellen erstellt wurden, finden Sie unter der Adresse rijndael-tables-calc.

Division

Die Division im Rijndael Galois-Feld ist etwas komplexer als die Addition, jedoch bedeutent einfacher als die Multiplikation. Man nehme an, a ist der Divident und b der Divisor. Um diese arithmetische Operation durchzuführen muss man lediglich den Logarithmus von a mit dem von b subtrahieren und modulo 255 nehmen.

Multiplikative Inverse

Die multiplikative Inverse ist schlicht die Inverse einer bestimmten Zahl. Beachten Sie das die multiplikative Inverse von 0 im GF nicht undefiniert ist, sondern wiederum 0 ist. Um die multiplikative Inverse einer Zahl a zu berechnen, kann man wie folgt vorgehen:

  • Finde den korrespondierenden Logarithmus von a in der Logarithmustabelle.
  • Subtrahiere diesen Wert von 255.
  • Suche den zu dem Ergebnis korrespondierenden Wert in der Potenztabelle.
  • Das ist die multiplikative Inverse (1 / a).
/**
 * Calculates the multiplicative inverse of a number in GF.
 */
uint8_t galois_mul_inverse(uint8_t number) 
{
    // 0 is self inverting
    return number ? exptable[(255 - logtable[number])] : 0;
}

Damit wären die arithmetischen Operationen und die vier wesentlichen Schichtoperationen (AddRoundKey, ShiftRows, SubBytes, MixColumns), die während einer AES-Runde durchgeführt werden hinreichend erklärt. Bevor wir uns mit weiteren Details befassen und langsam aber stetig zur Implementierung voranschreiten, werfen wir einen abschließenden Blick auf das Rijndael Schichtenmodell.

Highslide JS
Rijndael-Algorithmus: Grafische Darstellung der vier Schichtoperationen des Rijndael-Algorithmus. In jeder Runde werden diese vier Schichten durchlaufen.

Der Rijndael Key Schedule

Der Key Schedule ist ein Schlüsselerzeugungsalgorithmus, der verantwortlich für die Schlüsselexpansion ist, dessen Teile während den verschiedenen Iterationen verwendet werden. Jede Schlüssellänge wird auf verschiedene Größen expandiert:

  • Ein 128 Bit großer Schlüssel wird auf einen 176 Byte großen Schlüssel expandiert.
  • Ein 192 Bit großer Schlüssel wird auf einen 208 Byte großen Schlüssel expandiert.
  • Ein 256 Bit großer Schlüssel wird auf 240 Byte expandiert.

Es existiert eine Beziehung zwischen der Größe des Chiffreschlüssels, der Anzahl an Runden und der Größe des expandierten Schlüssels. Die Beziehung ergibt sich aus der bereits genannten Formel b * (R + 1). Die Variable R steht dabei für die Anzahl der Runden. Die nachfolgende Tabelle führt den Zusammenhang zwischen Rundenzahl, Schlüssel- und Blockgröße noch einmal vor Augen:

Nr
Nb=4
(128 Bit)
Nb=6
(192 Bit)
Nb=8
(256 Bit)
Nk=4
(128 Bit)
10
12
14
Nk=6
(192 Bit)
12
12
14
Nk=8
(256 Bit)
14
14
14

Tabelle 4. Zusammenhang zwischen Rundenzahl, Schlüssel- und Blockgröße

Für einen 128-Bit großen Schlüssel, gibt es eine initiale AddRoundKey Operation plus 10 weiteren Runden. Jede Runde benötigt einen 16 Byte großen Rundenschlüssel, daher benötigen wir 10+1 Rundenschlüssel von 16 Byte, was 167 Byte entspricht. Dasselbe Verfahren kann auf die beiden anderen Schlüsselgrößen angewendet werden. Wir halten also folgende Formel in der englischen Schreibweise fest:

ExpandedKeySize = BlockSize * (nbrRounds + 1)

Der Key Schedule basiert auf Iterationen des Key Schedule Kerns, der auf 4-Byte großen Wörtern arbeitet. Der Kern nutzt eine bestimmte Zahl von Operationen, die nachfolgend erklärt werden:

Rotation:

Das 4-Byte große Wort (Hex) wird zyklisch um ein Byte nach links geschoben:

---------------------    ---------------------
| 1d | 2c | 3a | 4f | -> | 2c | 3a | 4f | 1d |
---------------------    ---------------------

Rcon:

Rcon ist das, was die Rijndael Dokumentation als stetige Potenz von x, also {02}, zu einem benutzerspezifischen Wert nennt. Das Rcon Word-Array, Rcon[i], beinhaltet Werte die durch [xi-1,{00},{00},{00}] gegeben sind, mit xi-1 als Anzahl der Exponenten von x (x als hexadezimaler Wert {02}) im endlichen Feld GF(28). Alle Operationen bedienen sich der Arithmetik im Galois-Feld. Es erfolgt wiederum eine modulo Reduktion mit dem unreduzierbaren Polynom m(x) := x8 + x4 + x3 + x + 1.

Zum Beispiel ist Rcon(1) = 1, das Rcon(2) = 2, das Rcon(3) = 4 und das Rcon(9) die hexadezimale Nummer 0x1b. Es gilt Rcon(i) = x(254+i).

Im Prinzip reichen für 128-Bit Blöcke 10 Rcons aus, da der Rijndael bei dieser Blockgröße nicht mehr Rcons verwendet. Die Rcon Werte können als statische Tabelle vorliegen, die mit i=1 beginnt oder „on-the-fly“, also zur Laufzeit berechnet werden. Wie Sie sich vielleicht bereits denken, können alle Werte leicht mit der Funktion xtime() berechnet werden, deren Aufgabe es ist stetig mit dem Polynom x zu multiplizieren.

S-Box:

Der Key Schedule nutzt dieselbe S-Box Substitution, wie der Hauptalgorithmus. Die Substitutionsbox oder S-Box des Rijndael-Algorithmus gibt an, wie in jeder Runde jedes Byte eines Blocks durch einen anderen Wert zu ersetzen ist. Die S-Box besteht aus einer Liste von 256 Bytes, die konstruiert werden, indem zunächst jedes Byte außer der Null, aufgefasst als Vertreter von F28, durch sein multiplikatives Inverses ersetzt wird (die Null bleibt am Platz). Danach wird eine affine Abbildung über F2 als Matrixmultiplikation und Addition von (1 1 0 0 0 1 1 0) berechnet:

S-Box-mul

In dieser Darstellung bezeichnet x0 bzw. y0 das jeweils niedrigstwertige und x7 bzw. y7 das jeweils höchstwertige Bit eines Byte, dem 8-Tupel (1 1 0 0 0 1 1 0) entspricht somit der Hexadezimalwert '63'. Der Konstruktion der S-Box liegen Designkriterien zugrunde, wonach die Anfälligkeit für die Methoden der linearen und der differentiellen Kryptoanalyse sowie für algebraische Attacken minimiert werden.

Typischerweise wird die S-Box in Blockchiffren eingesetzt, um die Beziehung zwischen Klar- und Geheimtext zu verwischen (in der kryptologischen Fachsprache "Konfusion" genannt). Die S-Box des AES setzt auch teilweise das Shannon'sche Prinzip der Diffusion um.

Der Key Schedule Kern:

Nun, nachdem wir wissen was die Operationen sind, lassen Sie mich Ihnen den Key Schedule Kern (in pseudo-C) zeigen:

keyScheduleCore(word)
{
    Rotate(word);
    SBoxSubstitution(word);
    word[0] = word[0] XOR RCON[i];
}

In dem obigen Code, hat ein Wort insgesamt 4 Byte und i ist der Iterationszähler des Key Scheduler.

Die Schlüsselexpansion

Ver- und Entschlüsselung erfordern die Erzeugung von jeweils Nr-vielen Rundenschlüsseln, dem sogenannten Schlüsselplan. Dies erfolgt durch eine Expandierung des geheimen Anwenderschlüssels, indem rekursiv abgeleitete 4-Byte-Wörter an den Anwenderschlüssel angehängt werden.
Der Erzeugungsprozess ist nichtlinear, er ist nicht invertierbar und ohne Kenntnis des geheimen Benutzerschlüssels können eventuell bekannte Teile eines Schlüsselplans in keiner Richtung vollständig rekonstruiert werden. Zwei weitere Vorteile sind, dass eine starke Diffusionswirkung auf Benutzerschlüssel ausgeübt wird und die Schlüsselerzeugung schnell und flexibel implementierbar ist.

Zuallererst lassen Sie mich Ihnen die Funktion KeyExpansion() für die Schlüsselexpansion so zeigen, wie sie in der Rijndael Dokumentation vorzufinden ist (es gibt 2 Versionen, eine für die Schlüsselgröße 128, 192 und eine für die Größe 256):

KeyExpansion(byte CipherKey, word ExpandedKey)
{
    for (i = 0; i < Nk; i++)
        ExpandedKey[i] = (CipherKey[4*i], CipherKey[4*i + 1], CipherKey[4*i + 2], 
                          CipherKey[4*i + 3]);
 
    for (i = Nk; i < Nb*(Nr+1); i++) {
        temp = ExpandedKey[i – 1];
        if (i % Nk == 0)
            temp = SubBytes (RotBytes(temp)) ^ Rcon[i / Nk];
        else if ((Nk == 8) && (i % Nk == 4))    // for 256 bit
            temp = SubBytes (temp);
        ExpandedKey[i] = ExpandedKey[i – Nk] ^ temp;
    }
}
  • Nk ist die Anzahl an Spalten im Chiffreschlüssel (128-bit → 4, 192-bit → 5, 256-bit → 6)
  • Der ExpandedKey ist vom Typ "word", also 4-Byte groß

Die ersten Nk Wörter k0,…, kNk-1 des Schlüsselplans werden durch den geheimen Anwenderschlüssel selbst gebildet. Für Nk = 4 oder 6 wird das jeweils nächste 4-Byte-Wort ki durch eine XOR-Verknüpfung des vorhergehenden Wortes ki-1 mit ki-Nk bestimmt.

Falls i = 0 mod Nk ist, wird auf das Wort ki-1 vor der XOR-Verknüpfung eine Funktion FNk(k, i) angewendet, die aus einer zyklischen Links-Verschiebung (Links-Rotation) r(k) von k um ein Byte, einer Ersetzung S(r(k)) aus der Rijndael S-Box und einer XOR-Verknüpfung mit einer Konstanten c(|i/Nk|) zusammengesetzt ist, so dass sich die Funktion F insgesamt zu FNk(k, i) := S(r(k)) ⊕ c(|i/Nk|) ergibt.

Die Konstanten c(j) sind definiert durch c(j) := (rc(j), 0, 0, 0), wobei die rc(j) vorberechnet und in einer Tabelle gespeichert werden können. Für Schlüssel der Länge von 256 Bit (d. h. Nk = 8) wird eine zusätzliche S-Box-Operation zwischengeschaltet: Falls i = 4 mod Nk wird vor der XOR-Operation ki-1 durch S(ki-1) ersetzt. Auf diese Weise werden als Schlüsselplan insgesamt Nb·(Nr + 1) 4-Byte-Wörter gebildet, einschließlich des geheimen Benutzerschlüssels. Für jede Runde i = 0,…, Nr-1 werden dem Schlüsselplan die jeweils nächsten Nb 4-Byte-Wörter kNb·i bis kNb·(i + 1) als Rundenschlüssel entnommen.

Lassen Sie mich versuchen, es in einer verständlichen Art und Weise zu erklären:

  • Die ersten n Bytes des expandierten Schlüssels (ExpandedKey) sind einfach der Chiffreschlüssel (CipherKey), also ist n die Größe des Chiffreschlüssels
  • Der Rcon Wert i wird auf 1 gesetzt
  • Solange wir nicht genug Bytes für den ExpandedKey haben, führen wir Operationen durch um n mehr Bytes für den expandierten Schlüssels zu generieren (nehmen Sie zur Kenntnis das die Variable "n" benutzt wird, da der Wert abhängig von der Schlüsselgröße ist)

Machen Sie sich keine großen Sorgen, falls Sie immer noch Probleme haben die Funktionsweise des Key Schedule ganz zu verstehen, die Implementierung ist nicht schwer. Was Sie sich merken sollten ist:

  • für n=16, generieren wir: 4 + 3*4 = 16 Bytes per Iteration
  • für n=24, generieren wir: 4 + 5*4 = 24 Bytes per Iteration
  • für n=32, generieren wir: 4 + 3*4 + 4 + 3*4 = 32 Bytes per Iteration

Die Implementierung des Key Schedule ist sehr fortschrittlich, aber da es viele Codewiederholungen gibt, ist es möglich die Schleife ein wenig zu optimieren und den Modulo Operator zu nutzen um zusätzliche Bedingungen zu überprüfen. Nachfolgend sehen Sie eine grafische Veranschaulichung der Schlüsselexpansion.

Keyexpansion-AES

Implementierung des Key Schedule

Wir werden die Implementierung des AES mit der Schlüsselexpansion beginnen. Wie Sie im theoretischen Teil oben lesen konnten, versuchen wir den Schlüssel, dessen Größe zwischen 128 und 256 Bit liegt, in einen Größeren zu expandieren, von dem dann verschiedene Rundenschlüssel abgeleitet werden können.

Ich bevorzuge es die Hilfsfunktionen (wie Rotate, Rcon oder S-Box) zuerst zu implementieren, diese zu testen und dann zu den größeren Schleifen überzugehen. Falls Sie kein Anhänger dieses sogenannten Bottom-Up Ansatzes sind, sind Sie dazu eingeladen an einem späteren Punkt in diesem Tutorial zu beginnen und sich anschließend nach oben zu arbeiten. Allerdings erachte ich meinen Ansatz in diesem Fall für sinnvoller.

Implementierung: Allgemeine Kommentare

Obwohl Sie vielleicht der Ansicht sind, dass die Nutzung des Datentyps int der beste Weg ist um den Rijndael-Algorithmus in der Programmiersprache C zu implementieren, da 32-Bit exakt der Größe eines Words entsprechen, rate ich nur bedingt dazu den Typ int in C zu benutzen. Wie Sie womöglich bereits wissen ist der Datentyp int maschinenabhängig. Es ist nicht garantiert, das ein Compiler den Datentyp int immer auf 32-Bit abbildet. Auf 8 und 16-Bit Prozessoren (inklusive des Intel x86 Prozessors, der im Real Modus operiert) hat ein int keine 32-Bit. Auch auf einem 64-Bit Prozessorsystem kann der Compiler den Datentyp auf 64-Bit expandieren und dadurch unsere Implementierung zerstören. Darüberhinaus werden bei Nutzung von 4-Byte großen Integern weitere Bitmaskierungen und Shifts im Code notwendig, die die Lesbarkeit des Quellcodes deutlich vermindern.

Dieser Artikel befasst sich mit dem Rijndael-Algorithmus und soll deshalb primär auf Lesbarkeit ausgerichtet sein. Viele Rijndael Implementierungen nutzen 32-Bit Integer mit einer starken Optimierung, bei der sogar zu großen Teilen auf "Inline Assembler" zurückgegriffen wird. Der Quellcode ist dann kaum mehr nachzuvollziehen und für einen Artikel über die Funktionsweise des Rijndael gänzlich ungeeignet. Der Leser soll den Quellcode verstehen und bei Bedarf auch leicht in eine andere Programmiersprache übersetzen können. Codeoptimierungen bleiben deshalb dem Leser bzw. Programmierer selbst überlassen. Aus diesem Grunde werden wir auf den Datentyp unsigned char zurückgreifen, der die Größe eines Chars besitzt (wird auch CHAR_BIT genannt und ist in der limits.h definiert) der 8-Bit groß ist. Jack Klein schreibt dazu:

Beinahe alle modernen Computer verwenden heute 8-Bit große Bytes (technisch auch Oktetts genannt), aber es existieren immer noch einige wenige Systeme mit anderen Größen, z.B. 9-Bit. Auch können einige Prozessoren (besonders sogenannte „Digital Signal Processors“) nicht effizient auf den Speicher in kleineren Portionen, als die Prozessor-Wortbreite, zugreifen. Es existiert mindestens ein DSP, mit dem ich gearbeitet habe, wo ein CHAR_BIT 32 beträgt. Die char-Typen, short, int und long sind alle fast immer 32-Bit groß.

Da wir unseren Code so portabel wie möglich halten wollen, und da es Aufgabe des Compilers ist zu entscheiden ob der Datentyp char vorzeichenbehaftet ist oder nicht, werden wir im gesamten Code einen Alias spezifizieren, der den Datentyp abstrahiert. Im neuen ANSI C99 Standard wurde eine neue Header in die Standardbibliothek aufgenommen. Der Name der Header lautet stdint.h. In ihr sind zahlreiche neue Integertypen definiert, darunter int8_t, uint8_t, int16_t, uint16_t, int32_t, uint32_t, int64_t und uint64_t. Der Vorteil ist, das man sich nicht mehr um die Portabilität kümmern muss und die Bitbreite direkt aus dem Namen des Datentyps ersichtlich wird.

Leider gibt es nach wie vor Compiler, die die neue Header nicht von Haus aus zur Verfügung stellen. Dazu zählt auch die Compilerversion in der Visual Studio 2008 Entwicklungsumgebung. Allerdings kann man die Header beispielsweise von der Adresse http://msinttypes.googlecode.com/svn/trunk/stdint.h beziehen. Visual Studio 2010 liefert die Header mit. Für unser Tutorial ist es auch ausreichend den Datentyp mit dem typedef Spezifizierer selbst zu definieren, falls die Header stdint.h nicht zur Verfügung steht.

typedef unsigned char   uint8_t

Implementierung: S-Box

Die Werte der S-Box und inversen S-Box können bekannterweise „on-the-fly“ berechnet werden um Speicher zu sparen oder vorberechnet und in einem Array gespeichert werden. In den nachfolgenden beiden Unterkapiteln werden wir beide Methoden implementieren. Wir beginnen mit der einfachen Methode, der Implementierung über ROM-Tabellen.

S-Box („ROM-Tabellen“)

Da man davon ausgehen kann, dass jede Maschine auf dem der AES läuft mindestens 2x256 Bytes zur Verfügung hat (es gibt zwei S-Boxen, eine für die Verschlüsselung und eine weitere Tabelle für die Entschlüsselung), werden die Werte der S-Box oft in einem Array gespeichert. Da die Tabellen dann direkt Bestandteil des Programmdatensegmentes sind, nennt man sie auch oft ROM-Tabellen.

Hier ist der Code für die zwei S-Boxen. Es handelt sich dabei einfach um eine Suchtabelle, die für einen spezifischen Index den entsprechenden Wert im Array zurückliefert:

/* Forward S-Box */
static const uint8_t SBox[256] = {
    // 0     1     2     3     4     5     6     7     8     9     A     B     C     D     E     F
    0x63, 0x7c, 0x77, 0x7b, 0xf2, 0x6b, 0x6f, 0xc5, 0x30, 0x01, 0x67, 0x2b, 0xfe, 0xd7, 0xab, 0x76, // 0
    0xca, 0x82, 0xc9, 0x7d, 0xfa, 0x59, 0x47, 0xf0, 0xad, 0xd4, 0xa2, 0xaf, 0x9c, 0xa4, 0x72, 0xc0, // 1
    0xb7, 0xfd, 0x93, 0x26, 0x36, 0x3f, 0xf7, 0xcc, 0x34, 0xa5, 0xe5, 0xf1, 0x71, 0xd8, 0x31, 0x15, // 2
    0x04, 0xc7, 0x23, 0xc3, 0x18, 0x96, 0x05, 0x9a, 0x07, 0x12, 0x80, 0xe2, 0xeb, 0x27, 0xb2, 0x75, // 3
    0x09, 0x83, 0x2c, 0x1a, 0x1b, 0x6e, 0x5a, 0xa0, 0x52, 0x3b, 0xd6, 0xb3, 0x29, 0xe3, 0x2f, 0x84, // 4
    0x53, 0xd1, 0x00, 0xed, 0x20, 0xfc, 0xb1, 0x5b, 0x6a, 0xcb, 0xbe, 0x39, 0x4a, 0x4c, 0x58, 0xcf, // 5
    0xd0, 0xef, 0xaa, 0xfb, 0x43, 0x4d, 0x33, 0x85, 0x45, 0xf9, 0x02, 0x7f, 0x50, 0x3c, 0x9f, 0xa8, // 6
    0x51, 0xa3, 0x40, 0x8f, 0x92, 0x9d, 0x38, 0xf5, 0xbc, 0xb6, 0xda, 0x21, 0x10, 0xff, 0xf3, 0xd2, // 7
    0xcd, 0x0c, 0x13, 0xec, 0x5f, 0x97, 0x44, 0x17, 0xc4, 0xa7, 0x7e, 0x3d, 0x64, 0x5d, 0x19, 0x73, // 8
    0x60, 0x81, 0x4f, 0xdc, 0x22, 0x2a, 0x90, 0x88, 0x46, 0xee, 0xb8, 0x14, 0xde, 0x5e, 0x0b, 0xdb, // 9
    0xe0, 0x32, 0x3a, 0x0a, 0x49, 0x06, 0x24, 0x5c, 0xc2, 0xd3, 0xac, 0x62, 0x91, 0x95, 0xe4, 0x79, // A
    0xe7, 0xc8, 0x37, 0x6d, 0x8d, 0xd5, 0x4e, 0xa9, 0x6c, 0x56, 0xf4, 0xea, 0x65, 0x7a, 0xae, 0x08, // B
    0xba, 0x78, 0x25, 0x2e, 0x1c, 0xa6, 0xb4, 0xc6, 0xe8, 0xdd, 0x74, 0x1f, 0x4b, 0xbd, 0x8b, 0x8a, // C
    0x70, 0x3e, 0xb5, 0x66, 0x48, 0x03, 0xf6, 0x0e, 0x61, 0x35, 0x57, 0xb9, 0x86, 0xc1, 0x1d, 0x9e, // D
    0xe1, 0xf8, 0x98, 0x11, 0x69, 0xd9, 0x8e, 0x94, 0x9b, 0x1e, 0x87, 0xe9, 0xce, 0x55, 0x28, 0xdf, // E
    0x8c, 0xa1, 0x89, 0x0d, 0xbf, 0xe6, 0x42, 0x68, 0x41, 0x99, 0x2d, 0x0f, 0xb0, 0x54, 0xbb, 0x16  // F
};
 
/* Reverse S-Box */
static const uint8_t RSBox[256] = { 
    // 0     1     2     3     4     5     6     7     8     9     A     B     C     D     E     F
    0x52, 0x09, 0x6a, 0xd5, 0x30, 0x36, 0xa5, 0x38, 0xbf, 0x40, 0xa3, 0x9e, 0x81, 0xf3, 0xd7, 0xfb, // 0
    0x7c, 0xe3, 0x39, 0x82, 0x9b, 0x2f, 0xff, 0x87, 0x34, 0x8e, 0x43, 0x44, 0xc4, 0xde, 0xe9, 0xcb, // 1 
    0x54, 0x7b, 0x94, 0x32, 0xa6, 0xc2, 0x23, 0x3d, 0xee, 0x4c, 0x95, 0x0b, 0x42, 0xfa, 0xc3, 0x4e, // 2 
    0x08, 0x2e, 0xa1, 0x66, 0x28, 0xd9, 0x24, 0xb2, 0x76, 0x5b, 0xa2, 0x49, 0x6d, 0x8b, 0xd1, 0x25, // 3 
    0x72, 0xf8, 0xf6, 0x64, 0x86, 0x68, 0x98, 0x16, 0xd4, 0xa4, 0x5c, 0xcc, 0x5d, 0x65, 0xb6, 0x92, // 4 
    0x6c, 0x70, 0x48, 0x50, 0xfd, 0xed, 0xb9, 0xda, 0x5e, 0x15, 0x46, 0x57, 0xa7, 0x8d, 0x9d, 0x84, // 5 
    0x90, 0xd8, 0xab, 0x00, 0x8c, 0xbc, 0xd3, 0x0a, 0xf7, 0xe4, 0x58, 0x05, 0xb8, 0xb3, 0x45, 0x06, // 6 
    0xd0, 0x2c, 0x1e, 0x8f, 0xca, 0x3f, 0x0f, 0x02, 0xc1, 0xaf, 0xbd, 0x03, 0x01, 0x13, 0x8a, 0x6b, // 7 
    0x3a, 0x91, 0x11, 0x41, 0x4f, 0x67, 0xdc, 0xea, 0x97, 0xf2, 0xcf, 0xce, 0xf0, 0xb4, 0xe6, 0x73, // 8 
    0x96, 0xac, 0x74, 0x22, 0xe7, 0xad, 0x35, 0x85, 0xe2, 0xf9, 0x37, 0xe8, 0x1c, 0x75, 0xdf, 0x6e, // 9 
    0x47, 0xf1, 0x1a, 0x71, 0x1d, 0x29, 0xc5, 0x89, 0x6f, 0xb7, 0x62, 0x0e, 0xaa, 0x18, 0xbe, 0x1b, // A 
    0xfc, 0x56, 0x3e, 0x4b, 0xc6, 0xd2, 0x79, 0x20, 0x9a, 0xdb, 0xc0, 0xfe, 0x78, 0xcd, 0x5a, 0xf4, // B 
    0x1f, 0xdd, 0xa8, 0x33, 0x88, 0x07, 0xc7, 0x31, 0xb1, 0x12, 0x10, 0x59, 0x27, 0x80, 0xec, 0x5f, // C 
    0x60, 0x51, 0x7f, 0xa9, 0x19, 0xb5, 0x4a, 0x0d, 0x2d, 0xe5, 0x7a, 0x9f, 0x93, 0xc9, 0x9c, 0xef, // D 
    0xa0, 0xe0, 0x3b, 0x4d, 0xae, 0x2a, 0xf5, 0xb0, 0xc8, 0xeb, 0xbb, 0x3c, 0x83, 0x53, 0x99, 0x61, // E 
    0x17, 0x2b, 0x04, 0x7e, 0xba, 0x77, 0xd6, 0x26, 0xe1, 0x69, 0x14, 0x63, 0x55, 0x21, 0x0c, 0x7d  // F
};

Zusätzlich lässt sich auf die Werte mit einer separaten Getter-Funktion besser zugreifen, statt diese direkt aus dem Programm zu nutzen. Das macht den Code lesbarer und ermöglicht es später den Code leicht zu erweitern. Natürlich ist es eine Frage des persönlichen Geschmacks, Sie können auch direkt auf die S-Boxen zugreifen.

uint8_t getSBoxValue(uint8_t num)
{
    return SBox[num];
}
uint8_t getRSBoxValue(uint8_t num)
{
    return RSBox[num];
}
S-Box („On-the-fly“)

Vorausgesetzt Sie geben sich mit den vorberechneten ROM-Tabellen zufrieden, können Sie diesen Abschnitt wieder verlassen. Wir wollen nun nämlich die S-Boxen auch zur Laufzeit mit dem Programm berechnen. Die wesentlichen mathematischen Rechenoperationen wurden bereits im Abschnitt zu den arithmetischen Operationen im Galois-Feld vermittelt. Nun müssen wir diese Kenntnisse in Code umsetzen.

Die theoretischen Grundlagen zur Berechnung der S-Box fanden sich im gleichnamigen Abschnitt S-Box. Wir wissen das eine affine Abbildung über F2 als Matrixmultiplikation und Addition von (1 1 0 0 0 1 1 0) berechnet wird. Nachdem die affine Transformation durchgeführt wurde, wird der Wert XOR-verknüpft mit der dezimalen Nummer 99 (hexadezimal 0x63).

Im Kapitel über die MixColumns-Stufe wurde gezeigt, wie man sehr schnell Polynome mithilfe von Shift-Operationen multiplizieren kann. Die Funktion galois_multiplication macht davon Gebrauch. Auf diese Weise lässt sich auch sehr schnell eine Potenz- und Logarithmustabelle erstellen, die für die Berechnung der S-Box erforderlich sind. Es werden die Tabellen für den Generator 0x03 erzeugt.

uint8_t logtable[256];  // Log table
uint8_t exptable[256];  // Exp table
uint8_t a = 1;
uint8_t c;
unsigned int i;
 
for (i = 0; i < 256; i++) {
    exptable[i] = a;
    c = a & 0x80;   // Multiply by three
    a <<= 1;
    if(c == 0x80)
        a ^= 0x1b;
 
    a ^= exptable[i];
    logtable[exptable[i]] = i;  // Set the log table value
}
 
exptable[255] = exptable[0];
logtable[0] = 0;

Nun können wir die zur Verfügung stehenden Tabellen und Funktionen nutzen um die S-Box „on-the-fly“ zu generieren. Die folgende Funktion berechnet für einen Wert n (0 - 255) im Rijndael Galois-Feld den korrespondierenden Wert in der S-Box, indem die multiplikative Inverse mit der Funktion galois_mul_inverse() determiniert wird:

/**
 * Calculate the s-box for a given number using the
 * multiplicative inverse function.
 */
uint8_t calc_sbox_value(uint8_t number) 
{
    uint8_t c, s, x;
    s = x = galois_mul_inverse(number);
    for (c = 0; c < 4; c++) {
        // One bit circular rotate to the left
        s = (s << 1) | (s >> 7);
        // xor with x
        x ^= s;
    }
    x ^= 99;    // 0x63
    return x;
}

Die S-Box konnten wir bereits weiter oben als ROM-Tabelle begutachten.

Die inverse S-Box ist einfach die S-Box in umgekehrter Richtung. Beispielsweise finden wir unter den Kooridinaten 03 in der S-Box oben den Wert 7b. Daraus ergibt sich, dass an der Stelle mit den Koordinaten 7b, die Zahl 03 in der inversen S-Box stehen muss. Sie wird berechnet, indem zunächst die inverse affine Transformation des Eingabewertes berechnet wird und anschließend die multiplikative Inverse. Die inverse affine Transformation ist folgendermaßen definiert:

RS-Box-mul

Um zu überprüfen ob die inverse S-Box auch tatsächlich korrekt ist, lässt sich folgende Funktion nutzen:

void testSBoxes()
{
    int i, err = 0;
 
    for (i = 0; i < 256; ++i) {
        if (getSBoxInvert(getSBoxValue(i)) != i) {
            printf("Wrong value at %d\n", i);
            err = 1;
        }                      
    }
 
    if(err)
        printf("There were errors in the lookup table\n");
    else    
        printf("OK all lookups succeeded\n");
}

Damit wären die beiden Möglichkeiten die (inverse) S-Box zu generieren abgehandelt.

Implementierung: Rotation

Vom theoretischen Abschnitt sollten Sie bereits wissen, dass die Funktion rotate() einen Word (ein 4-Byte großes Array) nimmt, und dieses 8-Bit nach links rotiert. Da ein Byte bei uns 8-Bit beträgt, und unser Arraytyp char ist (dessen größe 1 Byte ist), entspricht die Rotation von 8-Bit dem zyklischen Shift der Arraywerte nach links.

Hier ist der Code für die rotate() Funktion:

/// <summary>
/// Rijndael's rotate operation rotates
/// the word eight bits or 1 byte to the left.
///
/// rotate(1d2c3a4f) = 2c3a4f1d
/// </summary>
/// <param name="word">word is an char array of size 4 (32 bit)</praram>
void rotate(uint8_t* word)
{
    uint8_t tmp, i;
 
    tmp = word[0];
 
    for (i = 0; i < 3; i++) {
        word[i] = word[i + 1];
    }
 
    word[3] = tmp;
}

Implementierung: Rcon

So wie die S-Box, können auch die Rcon Werte „on-the-fly“ berechnet werden oder im ROM liegen. Auch hier wird oft ein vorberechnetes Array benutzt, da die Tabelle nur wenig Speicherplatz benötigt. Das Rcon Word-Array, Rcon[i], beinhaltet Werte die durch [xi-1,{00},{00},{00}] gegeben sind, mit xi-1 als Anzahl der Exponenten von x (x als hexadezimaler Wert {02}) im endlichen Feld GF(28).

Rcon („ROM-Tabelle“)

Im Prinzip reichen für 128-Bit Blöcke 10 Rcons aus, da Rijndael in diesem Fall nicht mehr verwendet. Oftmals wird deshalb direkt die folgende Tabelle verwendet, mit 4 Byte großen Datentypen.

/* for 128-bit blocks, Rijndael never uses more than 10 rcon values */
static const uint32_t Rcon[] = {
    0x01000000, 0x02000000, 0x04000000, 0x08000000,
    0x10000000, 0x20000000, 0x40000000, 0x80000000,
    0x1B000000, 0x36000000 };

Die vollständige Rcon-Tabelle kann nachfolgend, als uint8_t Array, betrachtet werden. Äquivalent zur S-Box Implementierung, habe ich eine kleine Zugriffsfunktion geschrieben. Achten Sie darauf das es sich hier um die vollständige Tabelle handelt, die bereits bei 0 mit dem Hexwert 0x8d beginnt! In unserer späteren Implementierung gehe ich von dieser Tabelle aus und beginne demzufolge bei Index 1. Falls Sie nur die 10 Werte große Rcon Tabelle nutzen müssen Sie den Index (rconIteration) bei 0 starten lassen.

Hier ist der vollständige Code für Rcon:

/* Round constants */
static const uint8_t Rcon[255] = {
    0x8d, 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80, 0x1b, 0x36, 0x6c, 0xd8,
    0xab, 0x4d, 0x9a, 0x2f, 0x5e, 0xbc, 0x63, 0xc6, 0x97, 0x35, 0x6a, 0xd4, 0xb3,
    0x7d, 0xfa, 0xef, 0xc5, 0x91, 0x39, 0x72, 0xe4, 0xd3, 0xbd, 0x61, 0xc2, 0x9f,
    0x25, 0x4a, 0x94, 0x33, 0x66, 0xcc, 0x83, 0x1d, 0x3a, 0x74, 0xe8, 0xcb, 0x8d,
    0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80, 0x1b, 0x36, 0x6c, 0xd8, 0xab,
    0x4d, 0x9a, 0x2f, 0x5e, 0xbc, 0x63, 0xc6, 0x97, 0x35, 0x6a, 0xd4, 0xb3, 0x7d,
    0xfa, 0xef, 0xc5, 0x91, 0x39, 0x72, 0xe4, 0xd3, 0xbd, 0x61, 0xc2, 0x9f, 0x25,
    0x4a, 0x94, 0x33, 0x66, 0xcc, 0x83, 0x1d, 0x3a, 0x74, 0xe8, 0xcb, 0x8d, 0x01,
    0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80, 0x1b, 0x36, 0x6c, 0xd8, 0xab, 0x4d,
    0x9a, 0x2f, 0x5e, 0xbc, 0x63, 0xc6, 0x97, 0x35, 0x6a, 0xd4, 0xb3, 0x7d, 0xfa,
    0xef, 0xc5, 0x91, 0x39, 0x72, 0xe4, 0xd3, 0xbd, 0x61, 0xc2, 0x9f, 0x25, 0x4a,
    0x94, 0x33, 0x66, 0xcc, 0x83, 0x1d, 0x3a, 0x74, 0xe8, 0xcb, 0x8d, 0x01, 0x02,
    0x04, 0x08, 0x10, 0x20, 0x40, 0x80, 0x1b, 0x36, 0x6c, 0xd8, 0xab, 0x4d, 0x9a,
    0x2f, 0x5e, 0xbc, 0x63, 0xc6, 0x97, 0x35, 0x6a, 0xd4, 0xb3, 0x7d, 0xfa, 0xef,
    0xc5, 0x91, 0x39, 0x72, 0xe4, 0xd3, 0xbd, 0x61, 0xc2, 0x9f, 0x25, 0x4a, 0x94,
    0x33, 0x66, 0xcc, 0x83, 0x1d, 0x3a, 0x74, 0xe8, 0xcb, 0x8d, 0x01, 0x02, 0x04,
    0x08, 0x10, 0x20, 0x40, 0x80, 0x1b, 0x36, 0x6c, 0xd8, 0xab, 0x4d, 0x9a, 0x2f,
    0x5e, 0xbc, 0x63, 0xc6, 0x97, 0x35, 0x6a, 0xd4, 0xb3, 0x7d, 0xfa, 0xef, 0xc5,
    0x91, 0x39, 0x72, 0xe4, 0xd3, 0xbd, 0x61, 0xc2, 0x9f, 0x25, 0x4a, 0x94, 0x33,
    0x66, 0xcc, 0x83, 0x1d, 0x3a, 0x74, 0xe8, 0xcb 
};
uint8_t getRconValue(uint8_t num)
{
    return Rcon[num];
}
Rcon („On-the-fly“)

Wie im theoretischen Abschnitt zu Rcon erwähnt, handelt es sich bei den Round Constants im Rijndael um Potenzen von x (0x02) in Abhängigkeit von i. Dafür haben wir bereits eine Funktion names xtime() kennengelernt, die diese Potenzen sehr leicht generieren kann:

/**
 * Calculate the round constants (uint8_t).
 */
for (i = 0, x = 1; i < 10; i++) {
    Rcon[i] = x;
    x = xtime(x);
}
Implementierung: Vorwärts- und Rückwärts-Tabellen

Die Geschwindigkeit der Berechnungen im AES kann durch weitere Tabellen spürbar erhöht werden. Diese Tabellen nennen sich Vorwärts- und Rückwärts-Tabellen (engl. forward and reverse tables). Sie kommen bei der MixColumns Transformation des Rundenschlüssels zum Einsatz.
Auch diese Tabellen können statisch im ROM gespeichert oder zur Laufzeit generiert werden. Es handelt sich insgesamt um acht weitere, 1024-Byte große Tabellen, die Sie unter rijndael-forward-and-reverse-tables einsehen können.

Wir werden diese Tabellen in unserem Tutorial nicht verwenden um die Übersichtlichkeit zu wahren. Allerdings möchten wir den Code zur Generierung dieser Tabellen ebenfalls implementieren, so dass Sie bei Bedarf darauf zurückgreifen können. Wir müssen allerdings beachten, das wir einen 8-Bit großen Datentypen verwenden, die Tabellen jedoch meist aus 32-Bit großen Datentypen zusammengesetzt sind (siehe Tabelle oben). Wir belassen es bei dem 32-Bit großen Datentyp namens uint32_t und verschaffen uns nur einen allgemeinen Überblick.

Falls Sie die Tabellen nutzen möchten, müssen Sie den Generierungscode entsprechend an unseren Datentypen anpassen. Der Quellcode sieht vom Prinzip folgendermaßen aus:

/**
 * Forward S-box & tables
 */
static uint8_t FSb[256];
static uint32_t Te0[256]; 
static uint32_t Te1[256]; 
static uint32_t Te2[256]; 
static uint32_t Te3[256]; 
 
/**
 * Reverse S-box & tables
 */
static uint8_t RSb[256];
static uint32_t Td0[256];
static uint32_t Td1[256];
static uint32_t Td2[256];
static uint32_t Td3[256];
 
// ...
 
uint32_t i, x, y, z;
 
/**
 * Preprocessor macros. Tables generation code.
 */
#define ROTL8(x) ((x << 8) & 0xFFFFFFFF) | (x >> 24)
#define XTIME(x) ((x << 1) ^ ((x & 0x80) ? 0x1b : 0x00))
#define MUL(x,y) ((x && y) ? exptable[(logtable[x] + logtable[y]) % 255] : 0)
 
/**
 * Generate the forward and reverse tables.
 */
for(i = 0; i < 256; i++) {
    x = getSBoxValue(i);
    y = XTIME(x) & 0xFF;    // Preprocessor macro for xtime()
    z = (y ^ x) & 0xFF;
 
    Te0[i] = ((uint32_t) y      ) ^
             ((uint32_t) x <<  8) ^
             ((uint32_t) x << 16) ^
             ((uint32_t) z << 24);
 
    Te1[i] = ROTL8(Te0[i]);
    Te2[i] = ROTL8(Te1[i]);
    Te3[i] = ROTL8(Te2[i]);
 
    x = getRSBoxValue(i);
 
    Td0[i] = ((uint32_t) MUL(0x0e, x)      ) ^
             ((uint32_t) MUL(0x09, x) <<  8) ^
             ((uint32_t) MUL(0x0d, x) << 16) ^
             ((uint32_t) MUL(0x0b, x) << 24);
 
    Td1[i] = ROTL8(Td0[i]);
    Td2[i] = ROTL8(Td1[i]);
    Td3[i] = ROTL8(Td2[i]);
}

Implementierung: Key Schedule Kern

Die Implementierung des Key Schedule Kerns aus dem Pseudo-C Code ist sehr einfach. Der ganze Code führt die Operationen schrittweise an dem 4-Byte großen Word durch. Die Parameter sind das Word und der Schleifenzähler, auf den Rcon angewiesen ist.

/// <summary>
/// Rijndael's key scheduler core function
/// </summary>
/// <param name="word">A single word</praram>
/// <param name="iteration">Number of iterations</praram>
void keyScheduleCore(uint8_t* word, int32_t iteration)
{
    uint32_t i;
 
    // rotate the 32-bit word 8 bits to the left
    rotate(word);
 
    // apply S-Box substitution on all 4 parts of the 32-bit word
    for (i = 0; i < 4; ++i) {
        word[i] = getSBoxValue(word[i]);
    }
 
    // XOR the output of the rcon operation with i to the first part (leftmost) only
    word[0] = word[0] ^ getRconValue(iteration);
}

Implementierung: Die Schlüsselexpansion

Die Schlüsselexpansion ist der Punkt, wo alles zusammenkommt. Wie Sie in der ziemlich langen Beschreibung der Rijndael Schlüsselexpansion sehen konnten, müssen wir etliche Operationen mehrmals durchführen, abhängig von der Schlüsselgröße. Da die Schlüsselgröße nur eine begrenzte Anzahl an Werten annehmen kann, habe ich mich entschlossen diesen als Aufzählungstyp (enum) zu implementieren. Das begrenzt nicht nur die Schlüsselgröße auf drei mögliche Werte, es macht den Code auch lesbarer.

typedef enum 
{
    Bits128 = 16,
    Bits192 = 24,
    Bits256 = 32
} KEYSIZE;

Unsere Funktion zur Schlüsselexpansion benötigt nur zwei Dinge:

  • den Chiffreschlüssel (Eingabe)
  • den expandierten Schlüssel (Ausgabe)

Da es in C nicht möglich ist die Größe eines per Zeiger übergebenen Arrays zu bestimmen, werden wir die Größe des Chiffreschlüssels (vom Typ keySize) und den expandierten Schlüssel (vom Typ size_t) als Parameterliste an unsere Funktion übergeben. Der Prototyp sieht folgendermaßen aus:

void expandKey(uint8_t* expandedKey, uint32_t expandedKeySize, uint8_t* cipherKey, KEYSIZE keySize);

Während ich die Funktion implementiert habe, habe ich versucht den Details in der theoretischen Fassung möglichst genau zu folgen. Wie bereits erwähnt, sind etliche Codeteile redundant - ich versuche daher die Wiederholungen gering zu halten, indem ich mit Bedingungen prüfe welche Operation gerade benötigt.

Anstatt das zu schreiben:

while(expanded_key_size < required_key_size) {
    key_schedule_core(word);
    for (i = 0; i < 4; i++)
        some_operation();
}

Bevorzuge ich eine andere Struktur:

while(expanded_key_size < required_key_size) {
    if (expanded_key_size % key_size == 0)
        key_schedule_core(word);
    some_operation();
}

Diese Struktur ist äquivalent, aber sie erlaubt mehr Flexibilität, wenn es zu der Implementierung der 256-Bit Chiffreschlüssel-Version kommt, die zusätzliche Schritte notwendig macht.

Lassen Sie mich Ihnen die expandKey() Funktion zeigen und später näher erklären:

/// <summary>
/// Rijndael's key expansion expands an 128, 192, 256 key 
/// into an 176, 208, 240 bytes key.
/// </summary>
/// <param name="expandedKey">A pointer to a byte array of large enough size</praram>
/// <param name="expandedKeySize">The size of the expanded key</praram>
/// <param name="cipherKey">The cipher key</praram>
/// <param name="keySize">The key size</praram>
void expandKey(uint8_t* expandedKey, uint32_t expandedKeySize, uint8_t* cipherKey, KEYSIZE keySize)
{
    // Current expanded keySize, in bytes
    uint32_t currentSize = 0;
    int32_t rconIteration = 1;
    int32_t i;
    uint8_t t[4] = { 0 };   // Temporary 4-byte variable
 
    // Set the 16,24,32 bytes of the expanded key to the input key
    for (i = 0; i < keySize; i++) {
        expandedKey[i] = cipherKey[i];
    }
 
    currentSize += keySize;
 
    while (currentSize < expandedKeySize) {
        // Assign the previous 4 bytes to the temporary value t
        for (i = 0; i < 4; i++) {
            t[i] = expandedKey[(currentSize - 4) + i];
        }
 
        // Every 16,24,32 bytes we apply the core schedule to t
        // and increment rconIteration afterwards
        if(currentSize % keySize == 0) {
            keyScheduleCore(t, rconIteration++);
        }
 
        // For 256-bit keys, we add an extra sbox to the calculation
        if(keySize == Bits256 && ((currentSize % keySize) == 16)) {
            for(i = 0; i < 4; i++) {
                t[i] = getSBoxValue(t[i]);
            }
        }
 
        // We XOR t with the four-byte block 16,24,32 bytes before the new expanded key.
        // This becomes the next four bytes in the expanded key.
        for(i = 0; i < 4; i++) {
            expandedKey[currentSize] = expandedKey[currentSize - keySize] ^ t[i];
            currentSize++;
        }
    }
}

Wie Sie sehen können, benutze ich niemals die innere Schleife um eine Operation zu wiederholen. Die einzige innere Schleife dient dazu über die 4 Teile des temporären Arrays t zu iterieren. Ich nutze den Modulo Operator um zu prüfen, ob eine Operation angewendet werden muss:

  • if(currentSize % keySize == 0): wann immer wir n Bytes des expandedKey kreiert haben (wo n die Chiffreschlüsselgröße ist), durchlaufen wir den Kern der Schlüsselexpansion einmal.
  • if(keySize == Bits256 && ((currentSize % keySize) == 16)): wenn wir einen 32-Bit großen Chiffreschlüssel expandieren und wenn wir gerade eben 16 Byte generiert haben (wie ich weiter oben erklärt habe, in der 32-Bit Version durchlaufen wir die erste Schleife nur 3mal, was 12 Byte erzeugt + 4 byte vom Kern), fügen wir eine zusätzliche S-Box Substitution hinzu.

Implementierung: Nutzung der Schlüsselexpansion

Schlussendlich können wir unsere neue Schlüsselexpansion testen. Ich werde die expandedKey Größe in dem Beispiel nicht berechnen, und stattdessen einen festen Wert übergeben. Hier ist der Code, der einen spezifischen Chiffreschlüssel expandieren wird:

// the expanded keySize
uint32_t expandedKeySize = 176;
 
// the expanded key
uint8_t expandedKey[expandedKeySize];
 
// the cipher key
uint8_t key[16] = { 0 };
 
// the cipher key size
KEYSIZE size = Bits256;
 
int32_t i;
 
expandKey(expandedKey, expandedKeySize, key, size);
 
printf("Expanded Key:n");
 
for (i = 0; i < expandedKeySize; i++)
    printf("%2.2x%c", expandedKey[i], (i % 16) ? 'n' : ' ');

Natürlich wird der Code diverse Konstanten nutzen, die automatisch generiert werden, sobald wir den Körper der AES Verschlüsselung implementieren.
Hier sind einige Testresultate:

Die Schlüsselexpansion eines 128-Bit großen Schlüssels, der aus null-Zeichen besteht (wie in dem Beispiel oben):

00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
62 63 63 63 62 63 63 63 62 63 63 63 62 63 63 63
9b 98 98 c9 f9 fb fb aa 9b 98 98 c9 f9 fb fb aa
90 97 34 50 69 6c cf fa f2 f4 57 33 0b 0f ac 99
ee 06 da 7b 87 6a 15 81 75 9e 42 b2 7e 91 ee 2b
7f 2e 2b 88 f8 44 3e 09 8d da 7c bb f3 4b 92 90
ec 61 4b 85 14 25 75 8c 99 ff 09 37 6a b4 9b a7
21 75 17 87 35 50 62 0b ac af 6b 3c c6 1b f0 9b
0e f9 03 33 3b a9 61 38 97 06 0a 04 51 1d fa 9f
b1 d4 d8 e2 8a 7d b9 da 1d 7b b3 de 4c 66 49 41
b4 ef 5b cb 3e 92 e2 11 23 e9 51 cf 6f 8f 18 8e

Die Schlüsselexpansion eines 192-Bit großen Schlüssels, der aus null-Zeichen besteht:

00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 62 63 63 63 62 63 63 63
62 63 63 63 62 63 63 63 62 63 63 63 62 63 63 63
9b 98 98 c9 f9 fb fb aa 9b 98 98 c9 f9 fb fb aa
9b 98 98 c9 f9 fb fb aa 90 97 34 50 69 6c cf fa
f2 f4 57 33 0b 0f ac 99 90 97 34 50 69 6c cf fa
c8 1d 19 a9 a1 71 d6 53 53 85 81 60 58 8a 2d f9
c8 1d 19 a9 a1 71 d6 53 7b eb f4 9b da 9a 22 c8
89 1f a3 a8 d1 95 8e 51 19 88 97 f8 b8 f9 41 ab
c2 68 96 f7 18 f2 b4 3f 91 ed 17 97 40 78 99 c6
59 f0 0e 3e e1 09 4f 95 83 ec bc 0f 9b 1e 08 30
0a f3 1f a7 4a 8b 86 61 13 7b 88 5f f2 72 c7 ca
43 2a c8 86 d8 34 c0 b6 d2 c7 df 11 98 4c 59 70

Die Schlüsselexpansion eines 256-Bit großen Schlüssels, der aus null-Zeichen besteht:

00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
62 63 63 63 62 63 63 63 62 63 63 63 62 63 63 63
aa fb fb fb aa fb fb fb aa fb fb fb aa fb fb fb
6f 6c 6c cf 0d 0f 0f ac 6f 6c 6c cf 0d 0f 0f ac
7d 8d 8d 6a d7 76 76 91 7d 8d 8d 6a d7 76 76 91
53 54 ed c1 5e 5b e2 6d 31 37 8e a2 3c 38 81 0e
96 8a 81 c1 41 fc f7 50 3c 71 7a 3a eb 07 0c ab
9e aa 8f 28 c0 f1 6d 45 f1 c6 e3 e7 cd fe 62 e9
2b 31 2b df 6a cd dc 8f 56 bc a6 b5 bd bb aa 1e
64 06 fd 52 a4 f7 90 17 55 31 73 f0 98 cf 11 19
6d bb a9 0b 07 76 75 84 51 ca d3 31 ec 71 79 2f
e7 b0 e8 9c 43 47 78 8b 16 76 0b 7b 8e b9 1a 62
74 ed 0b a1 73 9b 7e 25 22 51 ad 14 ce 20 d4 3b
10 f8 0a 17 53 bf 72 9c 45 c9 79 e7 cb 70 63 85

Implementierung der AES Verschlüsselung

Um den AES Verschlüsselungsalgorithmus zu implementieren, verfahren wir exakt so, wie im Abschnitt für die Schlüsselexpansion, d.h. wir fangen mit den grundlegenden Hilfsfunktionen an und schreiten anschließend zur Hauptschleife voran. Die Funktionen nehmen einen Parameter als State, der bereits erklärt wurde, ein rechteckigers Array der Größe 4x4 Byte. Wir werden den Stateblock nicht als zweidimensionales Array ansehen, sondern als eindimensionales Array der Länge 16.

Zunächst werfen wir noch einmal einen kurzen Blick auf die gesamte Prozedur.

Round(word State, word Roundkey)
{
    SubBytes(State);
    ShiftRows(State);
    MixColumns(State);
    AddRoundKey(State, RoundKey);
}
 
FinalRound(word State, word Roundkey)
{
    SubBytes(State);
    ShiftRows(State);
    AddRoundKey(State, RoundKey);   
}

Die Verschlüsselung mit Rijndael im Gesamtablauf wird durch den folgenden Pseudocode nach [DARI] veranschaulicht:

Rijndael(byte State, byte CipherKey)
{
    KeyExpansion(CipherKey, ExpandedKey);
    AddRoundKey(State, ExpandedKey);
 
    for (i = 1; i < Nr; i++) {
        Round(State, ExpandedKey + Nb*i);
    }
 
    FinalRound(State, ExpandedKey + Nb*Nr);
}

Implementierung: SubBytes

Es gibt nicht viel zu der Funktion zu sagen, es handelt sich um eine simple Substitution mit den Werten aus der S-Box:

/// <summary>
/// The SubBytes operation. In the SubBytes step, 
/// each byte in the array is updated using an 8-bit substitution box, 
/// the Rijndael S-box.
/// </summary>
/// <param name="state">The current state</praram>
void subBytes(uint8_t* state)
{
    uint32_t i;
 
    // Substitute all the values from the state with the value in the SBox
    // using the state value as index for the SBox
    for (i = 0; i < 16; i++) {
        state[i] = getSBoxValue(state[i]);
    }
}

Implementierung: ShiftRows

Ich habe mich dazu entschieden, diese Funktion in zwei Teile aufzuteilen, nicht weil es unmöglich ist alles in eine Funktion zu schreiben, sondern weil der Code so besser zu lesen und besser zu debuggen ist. Die shiftRows Funktion iteriert über alle Reihen und ruft dann shiftRow mit dem korrekten Offset auf. shiftRow macht nichts anderes als ein 4-Byte großes Array um einen bestimmten Offset zu shiften.

/// <summary>
/// The ShiftRows step operates on the rows of the state; 
/// it cyclically shifts the bytes in each row by a certain offset. 
/// For AES, the first row is left unchanged. Each byte of the 
/// second row is shifted one to the left.
/// </summary>
/// <param name="state">The current state</praram>
void shiftRows(uint8_t* state)
{
    uint8_t i;
 
    // iterate over the last 3 rows and call shiftRow() with that 
    // row; the first row isn't shifted
    for (i = 1; i < 4; i++) {
        shiftRow(state + i * 4, i);
    }
}
 
/// <summary>
/// Shifts a single row 1 byte to left.
/// </summary>
/// <param name="state">The current state</praram>
/// <param name="nbr">The round number</praram>
void shiftRow(uint8_t* state, uint8_t nbr)
{
    uint8_t i, j, tmp;
 
    // Each iteration shifts the row to the left by 1
    for (i = 0; i < nbr; i++) {
        tmp = state[0];
        for (j = 0; j < 3; j++) {
            state[j] = state[j + 1];
        }
        state[3] = tmp;
    }
}

Diese Implementierung ist der ineffizienteste Weg, aber der beste um die Arbeitsweise zu verstehen. Eine sehr einfache Verbesserung wäre es direkt mithilfe von Bitmanipulatoren die Reihe zu shiften.

Implementierung: AddRoundKey

Dieser Teil beinhaltet den Rundenschlüssel (roundKey) den wir während jeder Iteration generieren. Wir XORieren jedes Byte des Schlüssels mit dem zugehörigen Byte des State.

/// <summary>
/// Adds the round key in each round.
/// </summary>
/// <param name="state">The current state</praram>
/// <param name="roundKey">Pointer to the round key</praram>
void addRoundKey(uint8_t* state, uint8_t* roundKey)
{
    uint8_t i;
 
    for (i = 0; i < 16; i++) {
        state[i] = state[i] ^ roundKey[i] ;
    }
}

Implementierung: MixColumns

Die Operation mixColumns ist wahrscheinlich der schwierigste Part der vier Operationen. Vielleicht haben Sie sich das schon gedacht, als Sie den theoretischen Abschnitt zu der Operation gelesen haben. Die Operation beinhaltet die Galois Addition und Multiplikation und verarbeitet Spalten statt Reihen (was unbequem ist, da wir ein lineares Array nutzen, welches Reihen repräsentiert).
Zunächst benötigen wir eine Funktion, die zwei Nummern im Galois-Feld multipliziert. Im Abschnitt über arithmetische Operationen im Galois-Feld haben wir zwei Funktionen kennengelernt und bereits implementiert. Wir greifen auf die normale Multiplikation mithilfe von xtime() zurück:

/// <summary>
/// Multiplies two 8-bit large numbers in the 
/// Rijndael finite field, the Galois Field GF(2^8).
/// </summary>
/// <param name="a">The first factor</praram>
/// <param name="b">The second factor</praram>
/// <returns>The product</returns>
uint8_t mulGaloisField2_8(uint8_t a, uint8_t b)
{
    uint8_t p = 0;
    uint8_t hi_bit_set;
    uint8_t counter;
 
    for (counter = 0; counter < 8; counter++) {
        if ((b & 1) == 1) 
            p ^= a;
        hi_bit_set = (a & 0x80);    // xtime() ...
        a <<= 1;
        if (hi_bit_set == 0x80) 
            a ^= 0x1b;              // ...
        b >>= 1;
    }
 
    return p;
}

Wiedereinmal habe ich die Funktion in zwei Teile aufgeteilt, der erste Teil generiert eine Spalte und ruft dann mixColumn auf, welche dann die Multiplikation der Matrizen durchführt.

/// <summary>
/// In the MixColumns step, the four bytes of each column 
/// of the state are combined using an invertible linear transformation. 
/// The MixColumns function takes four bytes as input and outputs 
/// four bytes, where each input byte affects all four output bytes.
/// </summary>
/// <param name="state">The current state</praram>
void mixColumns(uint8_t* state)
{
    uint8_t i, j;
    uint8_t column[4];
 
    // Iterate over the 4 columns
    for (i = 0; i < 4; i++) {
        // Construct one column by iterating over the 4 rows
        for (j = 0; j < 4; j++) {
            column[j] = state[(j * 4) + i];
        }
 
        // Apply the mixColumn on one column
        mixColumn(column);
 
        // Put the values back into the state
        for (j = 0; j < 4; j++) {
            state[(j * 4) + i] = column[j];
        }
    }
}

Die Operation mixColumn ist einfach nur eine Multiplikation im Galois-Feld, also die Multiplikation des State mit der aus dem Theorieteil vorgestellten 4x4 MDS-Matrix. Da eine Addition auf eine XOR Operation zurückzuführen ist, und wir den schweren Part mit der Multiplikation bereits mithilfe der Funktion mulGaloisField2_8 realisiert haben, folgt nun eine einfache Implementierung:

/// <summary>
/// Mixes a single column, called by the MixColumns function.
/// </summary>
/// <param name="column">The column to mix</praram>
void mixColumn(uint8_t* column)
{
    uint8_t i;
    uint8_t cpy[4];
 
    for(i = 0; i < 4; i++) {
        cpy[i] = column[i];
    }
 
    column[0] = mulGaloisField2_8(cpy[0], 2) ^
                mulGaloisField2_8(cpy[1], 3) ^
                mulGaloisField2_8(cpy[2], 1) ^
                mulGaloisField2_8(cpy[3], 1);
 
    column[1] = mulGaloisField2_8(cpy[0], 1) ^
                mulGaloisField2_8(cpy[1], 2) ^
                mulGaloisField2_8(cpy[2], 3) ^
                mulGaloisField2_8(cpy[3], 1);
 
    column[2] = mulGaloisField2_8(cpy[0], 1) ^
                mulGaloisField2_8(cpy[1], 1) ^
                mulGaloisField2_8(cpy[2], 2) ^
                mulGaloisField2_8(cpy[3], 3);
 
    column[3] = mulGaloisField2_8(cpy[0], 3) ^
                mulGaloisField2_8(cpy[1], 1) ^
                mulGaloisField2_8(cpy[2], 1) ^               
                mulGaloisField2_8(cpy[3], 2);
}

Auch diese Funktion kann weiter optimiert werden (z.B. durch die Nutzung von memcpy statt der Schleife), aber ich habe die Formeln so belassen, damit man diese leichter lesen kann.

Implementierung: AES Runden

Wie Sie in der Theorie erkennen können, macht eine AES Runde nichts anderes als konsequent alle vier Operationen (Ausnahme: letzte Runde) am State anzuwenden.

/// <summary>
/// A single round in the AES algorithm, consisting
/// of 4 operations.
/// </summary>
/// <param name="state">The current state</praram>
/// <param name="roundKey">The current round key</praram>
void round(uint8_t* state, uint8_t* roundKey)
{
    subBytes(state);
    shiftRows(state);
    mixColumns(state);
    addRoundKey(state, roundKey);
}

Implementierung: Der Körper von AES

Nun, da wir alle kleinen Funktionen beisammen haben, wird die Hauptschleife einfach. Alles was wir machen müssen ist, den State zu nehmen, den expandierten Schlüssel und die Zahl an Runden als Parameter und dann eine Operation nach der anderen aufzurufen. Eine kleine Funktion, namens createRoundKey() wird verwendet um die nächsten 16 Byte vom expandedKey in den roundKey zu kopieren, indem wir die spezielle Reihenfolge nutzen.

/// <summary>
/// Creates the round key in each round.
/// </summary>
/// <param name="expandedKey">The expanded key</praram>
/// <param name="roundKey">Pointer to the round key</praram>
void createRoundKey(const uint8_t* expandedKey, uint8_t* roundKey)
{
    uint8_t i, j;
 
    // Iterate over the columns
    for (i = 0; i < 4; i++) {
        // Iterate over the rows
        for (j = 0; j < 4; j++) {
            roundKey[(i + (j * 4))] = expandedKey[(i * 4) + j];
        }
    }
}
/// <summary>
/// The main AES algorithm. The main body of 
/// encryption, performing the 4 main operation modes of 
/// the Rijndael cipher. AES operates on a state with a
/// dimension of 4×4 bytes.
/// </summary>
/// <param name="state">The current state</praram>
/// <param name="expandedKey">The expanded cipher key</praram>
/// <param name="Nr">Number of rounds</praram>
void aes(uint8_t* state, const uint8_t* expandedKey, uint32_t Nr)
{
    uint32_t i;
    uint8_t roundKey[16];
 
    createRoundKey(expandedKey, roundKey);
 
    addRoundKey(state, roundKey);
 
    for (i = 1; i < Nr; i++) {
        createRoundKey(expandedKey + 16 * i, roundKey);
        round(state, roundKey);
    }
 
    createRoundKey(expandedKey + 16 * Nr, roundKey);
 
    finalRound(state, roundKey);
}

Implementierung: Instanz erzeugen

Zu jeder Ver- oder Entschlüsselung gehören ein Schlüssel, die Anzahl an Runden und diverse andere Attribute. Vor dem Beginn einer Verschlüsselung muss der geheime Schlüssel expandiert werden, der anschließend bei der Erzeugung des Rundenschlüssels benötigt wird. Wir haben bereits eine Funktion implementiert, die den geheimen Schlüssel expandiert.

Da in der Programmiersprache C keine Klassen mit Attributen definiert werden können, müssen diese Daten immer an die entsprechenden Funktionen übergeben oder global definiert werden. Zur Parameterübergabe eignet sich eine Datenstruktur, die alle wesentlichen Daten einer laufenden Chiffreinstanz beherbergt. Die Struktur AESCONTEXT bietet die Möglichkeit alle relevanten Daten, die im Kontext zu dem Algorithmus stehen, zu speichern.

typedef struct
{
    // Number of rounds 10, 12, 14.
    uint32_t Nr;
    // Block size in 32-bit words. Always 4 for AES (128 bits).
    uint32_t Nb;
    // Key size in 32-bit words. 4, 6, 8 (128, 192, 256 bits).
    uint32_t Nk;
    // The seed key. Size will be Nk * 4 bytes = keySize.
    uint8_t* cipherKey;
    // Block cipher modes of operation.
    CIPHERMODE mode;
    // The AES key size (128, 192, 256 bits).
    KEYSIZE keySize;
    // The expanded key
    uint8_t* expandedKey;
    // The 128 bit state block
    uint8_t state[BLOCKSIZE];
} AESCONTEXT;

Vor Beginn einer neuen Ver- oder Entschlüsselung muss diese Struktur erzeugt und initialisiert werden. Das übernimmt die folgende Funktion.

/// <summary>
/// Creates a new cipher instance, initializes AES context. The AES
/// context stores Nk, Nr, Nb, cipher mode, key size and reserves space
/// for the key and expanded cipher key. Call this function always first,
/// before using the AES algorithm.
/// </summary>
/// <param name="context">A reference to the context to fill</praram>
/// <param name="keySize">The AES key size (128, 192, 256)</praram>
/// <param name="mode">The cipher mode, e.g. OFB</praram>
/// <param name="key">A byte array with the key (password)</praram>
/// <param name="keyLength">The key length</praram>
/// <returns>A positive number or 0 if no error occurs</returns>
int32_t create(AESCONTEXT* context, KEYSIZE keySize, CIPHERMODE mode, const uint8_t* key, uint32_t keyLength)
{
    uint32_t i;
 
    // The expanded keySize
    uint32_t expandedKeySize;
 
    // Set the number of rounds, etc.
    switch (keySize) {
        case Bits128:
            context->Nk = 4;     // key size = 4 words = 16 bytes = 128 bits
            context->Nr = 10;
            break;
        case Bits192:
            context->Nk = 6;     // 6 words = 24 bytes = 192 bits
            context->Nr = 12;
            break;
        case Bits256:
            context->Nk = 8;     // 8 words = 32 bytes = 256 bits
            context->Nr = 14;
            break;
        default:
            return UNKNOWN_KEYSIZE;
            break;
    }
 
    // Reserve space for the cipher key 16, 24, 32 bytes
    if ((context->cipherKey = (uint8_t *)malloc(context->Nk * 4 * sizeof(uint8_t))) == NULL) {
        return MEMORY_ALLOCATION_PROBLEM;
    }
 
    // Check if the password has the right size
    if (keyLength == context->Nk * 4) {
        for(i = 0; i < context->Nk * 4; i++) {
            context->cipherKey[i] = key[i]; // Just copy the array
        }
    } else { 
        // Password is different size, do a manual copy
        for (i = 0; i < context->Nk * 4; i++) {
            // Make sure we can use the keyBytes
            if (i < keyLength) {
                context->cipherKey[i] = key[i];
            } else {
                // We need to add some extra bytes with a *fixed* algorithm
                context->cipherKey[i] = i ^ (context->Nk << 14) % 256;
            }
        }
    }
 
    // Set the key size and the cipher mode
    context->keySize = keySize;
    context->mode = mode;
 
    // Create the expanded key
    expandedKeySize = (16 * (context->Nr + 1));
 
    if ((context->expandedKey = (uint8_t *)malloc(expandedKeySize * sizeof(uint8_t))) == NULL) {
        return MEMORY_ALLOCATION_PROBLEM;
    }
 
    // Expand the key into an 176, 208, 240 bytes key
    expandKey(context->expandedKey, expandedKeySize, context->cipherKey, context->keySize);
 
    return 0;
}

Zunächst berechnen wir die Anzahl an Runden, basierend auf der Schlüsselgröße und dann den expandierten Schlüssel, basierend auf der Anzahl an Runden. In dem Quellcode wird das Makro MEMORY_ALLOCATION_PROBLEM verwendet, dabei handelt es sich um Fehlerkonstanten, die im Code genutzt werden. Das betreffende Makro liefert einen Fehlercode zurück, wenn die Allokation von neuem Speicher auf dem Heap für den expandierten Schlüssel fehlschlägt.

Sie können an der Parameterliste von create auch einen Parameter für den Operationsmodi erkennen, diese werden in einem gesonderten Artikel behandelt und sind für den AES an dieser Stelle nicht weiter relevant.

Nach der Erzeugung einer neuen Datenstruktur mit create, muss nach Beendigung der Ver- oder Entschlüsselung die Instanz heruntergefahren werden. Dabei wird unter anderem reserverierter Speicherplatz freigegeben.

/// <summary>
/// This will shut down the created cipher instance. Call this
/// always after finishing encryption or decryption to prevent memory leaks.
/// </summary>
/// <param name="context">A reference to the context to fill</praram>
void shutdown(AESCONTEXT* context)
{
    // Deallocate reserved memory
    free(context->expandedKey);
    free(context->cipherKey);
}

Implementierung: Chiffrieren

Schlussendlich fügen wir alles zusammen. Unsere Parameter sind der Klartext, die Ausgabe und die Datenstruktur. Am Anfang müssen wir den 16 Byte großen Klartext in der richtigen Reihenfolge auf den 4x4 Byte großen State abbilden. Anschließend kann der State mit unserer AES Hauptfunktion verschlüsselt und letztenendes wieder korrekt ausgelesen werden, um den 16 Byte großen Geheimtext zu erhalten.

Klingt kompliziert, aber Sie werden sehen - es ist ganz einfach:

/// <summary>
/// Ciphers data with the AES algorithm. Necessary for encryption.
/// </summary>
/// <param name="input">The input byte array to process</praram>
/// <param name="output">The output byte array</praram>
/// <param name="context">A reference to the AES context</praram>
void cipher(const uint8_t* input, uint8_t* output, AESCONTEXT* context)
{
    uint32_t i, j;
 
    // Set the block values, for the block:
    // a0,0 a0,1 a0,2 a0,3
    // a1,0 a1,1 a1,2 a1,3
    // a2,0 a2,1 a2,2 a2,3
    // a3,0 a3,1 a3,2 a3,3
    // the mapping order is a0,0 a1,0 a2,0 a3,0 a0,1 a1,1 ... a2,3 a3,3
 
    // Iterate over the columns
    for (i = 0; i < 4; i++) {
        // Iterate over the rows
        for (j = 0; j < 4; j++) {
            context->state[(i + (j * 4))] = input[(i * 4) + j];
        }
    }
 
    // Encrypt the block using the expandedKey
    aes(context->state, context->expandedKey, context->Nr);
 
    // Unmap the block again into the output
    for (i = 0; i < 4; i++) {
        // Iterate over the rows
        for (j = 0; j < 4; j++) {
            output[(i * 4) + j] = context->state[(i + (j * 4))];
        }
    }
}

Die Funktion cipher ruft die Hauptfunktion des AES auf, in der in jeder Runde die vier Schichtoperationen des Rijndael-Algorithmuses durchlaufen werden.

Implementierung der AES Entschlüsselung

Wenn Sie die Implementierung bisher nachvollziehen konnten, werden Sie auch mit der Entschlüsselung keine Probleme haben. Im Prinzip wird die Verschlüsselung einfach invertiert und alle Operationen werden umgekehrt durchlaufen.

Da der Key Schedule gleich bleibt, müssen wir nur die inversen Funktionen implementieren, während AddRoundKey gleich bleibt.
Abgesehen von der inversen MixColumns Operation, sind die Operationen trivial und ich liste gleich den Quellcode auf.

/// <summary>
/// Inversion of the SubBytes operation. In the SubBytes step, 
/// each byte in the array is updated using an 8-bit substitution box, 
/// the Rijndael S-box.
/// </summary>
/// <param name="state">The current state</praram>
void invSubBytes(uint8_t* state)
{
    uint8_t i;
 
    // Substitute all the values from the state with the value in the SBox
    // using the state value as index for the SBox
    for (i = 0; i < 16; i++) {
        state[i] = getRSBoxValue(state[i]);
    }
}
/// <summary>
/// Inversion of the ShiftRows step, which operates on the rows of the
/// state; it cyclically shifts the bytes in each row by a certain offset. 
/// For AES, the first row is left unchanged. Each byte of the 
/// second row is shifted one to the left.
/// </summary>
/// <param name="state">The current state</praram>
void invShiftRows(uint8_t* state)
{
    uint8_t i;
 
    // Iterate over the 4 rows and call invShiftRow() with that row
    for (i = 1; i < 4; i++) {
        invShiftRow(state + (i * 4), i);
    }
}
/// <summary>
/// Shifts a single row, called by the invShiftRows function.
/// </summary>
/// <param name="state">The current state</praram>
/// <param name="nbr">The row to shift</praram>
void invShiftRow(uint8_t* state, uint8_t nbr)
{
    uint8_t i, j, tmp;
 
    // Each iteration shifts the row to the right by 1
    for (i = 0; i < nbr; i++) {
        tmp = state[3];
        for (j = 3; j > 0; j--) {
            state[j] = state[j - 1];
        }
        state[0] = tmp;
    }
}

Wie Sie sehen können ist die Implementierung annähernd dieselbe, wie bei der Verschlüsselung, mit der Ausnahme das dieses Mal die inverse S-Box für die Substitution verwendet wird.
Für die inverse MixColumns Operation, besteht der Unterschied darin, dass für die Multiplikation die folgende bekannte Matrix verwendet wird:

corr-matrix

Sie müssen also nur mit der Funktion zur Multiplikation zweier Zahlen in GF(28) den jeweiligen Wert mit der Zahl aus der inversen MDS-Matrix multiplizieren, was in dem folgenden Code resultiert:

/// <summary>
/// Inversion of the MixColumns step. Takes the four bytes of each column 
/// of the state are combined using an invertible linear transformation. 
/// The MixColumns function takes four bytes as input and outputs 
/// four bytes, where each input byte affects all four output bytes.
/// </summary>
/// <param name="state">The current state</praram>
void invMixColumns(uint8_t* state)
{
    uint8_t i, j;
    uint8_t column[4];
 
    // Iterate over the 4 columns
    for (i = 0; i < 4; i++) {
        // Construct one column by iterating over the 4 rows
        for (j = 0; j < 4; j++) {
            column[j] = state[(j * 4) + i];
        }
 
        // Apply the invMixColumn on one column
        invMixColumn(column);
 
        // Put the values back into the state
        for (j = 0; j < 4; j++) {
            state[(j * 4) + i] = column[j];
        }
    }
}

Die Zahlen aus der inversen MDS-Matrix sind entsprechend im hexadezimalen Stellensystem angegeben. Es wird jeweils eine Spalte des State mit den vier Zeilen der inversen MDS-Matrix verrechnet. Die nachfolgende Funktion führt diese Berechnung für exakt eine Spalte durch.

/// <summary>
/// Mixes a single column, called by the incMixColumns function.
/// </summary>
/// <param name="column">The column to mix</praram>
void invMixColumn(uint8_t* column)
{
    uint8_t i;
    uint8_t cpy[4];
 
    for(i = 0; i < 4; i++) {
        cpy[i] = column[i];
    }
 
    column[0] = mulGaloisField2_8(cpy[0], 0x0E) ^
                mulGaloisField2_8(cpy[1], 0x0B) ^
                mulGaloisField2_8(cpy[2], 0x0D) ^
                mulGaloisField2_8(cpy[3], 0x09);
 
    column[1] = mulGaloisField2_8(cpy[0], 0x09) ^
                mulGaloisField2_8(cpy[1], 0x0E) ^
                mulGaloisField2_8(cpy[2], 0x0B) ^
                mulGaloisField2_8(cpy[3], 0x0D);
 
    column[2] = mulGaloisField2_8(cpy[0], 0x0D) ^
                mulGaloisField2_8(cpy[1], 0x09) ^
                mulGaloisField2_8(cpy[2], 0x0E) ^
                mulGaloisField2_8(cpy[3], 0x0B);
 
    column[3] = mulGaloisField2_8(cpy[0], 0x0B) ^
                mulGaloisField2_8(cpy[1], 0x0D) ^
                mulGaloisField2_8(cpy[2], 0x09) ^
                mulGaloisField2_8(cpy[3], 0x0E);
}

Bitte nehmen Sie zur Kenntnis das ich mir einige Codeabschnitte hätte sparen können, wenn ich einen zusätzlichen Parameter in der MixColumns Operation eingeführt hätte, welche entweder die Matrix für die Ver- oder Entschlüsselung benutzen würde (dasselbe trifft natürlich auf andere Operationen zu).
Nachdem wir alle inversen Operationen geschrieben haben, können wir die inverse AES Runde spezifizieren:

/// <summary>
/// Inversion of a single round in the AES algorithm,
/// consisting of 4 operations.
/// </summary>
/// <param name="state">The current state</praram>
/// <param name="roundKey">The current round key</praram>
void invRound(uint8_t* state, uint8_t* roundKey)
{
    invShiftRows(state);
    invSubBytes(state);
    addRoundKey(state, roundKey);
    invMixColumns(state);
}

Zum Schluß muss nur noch alles in einer inversen Funktion zusammengesetzt werden. Beachten Sie das wir unseren expandierten Schlüssel rückwärts nutzen, beginnend mit den letzten 16 Byte.

/// <summary>
/// Inversion of the AES algorithm. The main body of 
/// decryption, performing the 4 main operation modes of 
/// the Rijndael cipher. AES operates on a state with a
/// dimension of 4×4 bytes.
/// </summary>
/// <param name="state">The current state</praram>
/// <param name="expandedKey">The expanded cipher key</praram>
/// <param name="Nr">Number of rounds</praram>
void invAes(uint8_t* state, const uint8_t* expandedKey, uint32_t Nr)
{
    uint32_t i;
    uint8_t roundKey[16];
 
    createRoundKey(expandedKey + 16 * Nr, roundKey);
 
    addRoundKey(state, roundKey);
 
    for (i = Nr - 1; i > 0; i--) {
        createRoundKey(expandedKey + 16 * i, roundKey);
        invRound(state, roundKey);
    }
 
    createRoundKey(expandedKey, roundKey);
 
    invFinalRound(state, roundKey);
}

Implementierung: Dechiffrieren

Auch wenn ich sicher bin, dass Sie selbst herausfinden können, wie die Implementation der Entschlüsselungsfunktion aussieht, möchte ich diese hier präsentieren. Sie ist äquivalent zur Verschlüsselungsfunktion, mit dem Unterschied das die inverse Funktion aufgerufen wird.

/// <summary>
/// Deciphers data with the AES algorithm. Necessary for decryption.
/// </summary>
/// <param name="input">The input byte array to process</praram>
/// <param name="output">The output byte array</praram>
/// <param name="context">A reference to the AES context</praram>
void decipher(const uint8_t* input, uint8_t* output, AESCONTEXT* context)
{
    uint32_t i, j;
 
    // Set the block values, for the block:
    // a0,0 a0,1 a0,2 a0,3
    // a1,0 a1,1 a1,2 a1,3
    // a2,0 a2,1 a2,2 a2,3
    // a3,0 a3,1 a3,2 a3,3
    // the mapping order is a0,0 a1,0 a2,0 a3,0 a0,1 a1,1 ... a2,3 a3,3
 
    // Iterate over the columns
    for (i = 0; i < 4; i++) {
        // Iterate over the rows
        for (j = 0; j < 4; j++) {
            context->state[(i + (j * 4))] = input[(i * 4) + j];
        }
    }
 
    // Decrypt the block using the expandedKey
    invAes(context->state, context->expandedKey, context->Nr);
 
    // Unmap the block again into the output
    for (i = 0; i < 4; i++) {
        // Iterate over the rows
        for (j = 0; j < 4; j++) {
            output[(i * 4) + j] = context->state[(i + (j * 4))];
        }
    }
}

Das ist das Ende der Implementierung des Advanced Encryption Standard in der Programmiersprache C. Alles was noch zu tun ist, ist die fertigen Funktionen zu nehmen und sie in einem Operationsmodi zu nutzen um Nachrichten jeglicher Größe zu ver- und entschlüsseln. Die Operationsmodi von Blockchiffren werden wir in einem gesonderten Artikel beleuchten. Wir möchten hier nur der Vollständigkeit halber kurz auf diese Modi eingehen.

Betriebsarten

Die Betriebsarten (Modus), in der Blockchiffren - somit auch der AES - betrieben werden, dienen dazu Klartexte zu verschlüsseln, die länger als die Blocklänge des Chiffrierverfahrens sind. Der AES verschlüsselt stets nur einen Block der Größe 16 Byte. Neben den klassischen Betriebsarten für Blockchiffren, wie etwa Electronic Code Book (ECB), Cipher Block Chaining (CBC), Cipher Feedback (CFB), Output Feedback (OFB) (vgl. [FIPS81]) oder Message Authentication Codes (MAC), werden zur Zeit einige neue Vorschläge für weitere Betriebsarten unter den Gesichtspunkten Sicherheit, Fehlertoleranz, Synchronisationseigenschaften und Implementierbarkeit diskutiert. Neue Vorschläge bieten zusätzlichen Integritätsschutz oder setzen AES als Schlüsselstromgenerator ein.

Im weiteren Vorgehen wird NIST wohl erst einmal einige der Standardbetriebsarten (u.a. ECB, CBC, CFB) im Rahmen eines eigenen FIPS-Standard für die AES-Betriebsarten festlegen, zusätzliche Modi werden möglicherweise später dazukommen.

Performance

Implementierungen für verschiedene Plattformen haben die überragende Performance von Rijndael bestätigt. Die Bandbreite reicht dabei von kleinen 8-Bit-Controllern mit wenig Speicher und Schlüsselerzeugung „on-the-fly“ bis zu sehr leistungsfähigen 32-Bit-Prozessoren. Bei ausreichend verfügbarem Speicherplatz kann zudem eine weitgehende Beschleunigung durch Tabellen erreicht werden, die den Zugriff auf die vorberechneten Ergebnisse der verschiedenen Transformationen ermöglichen.

Aufgrund der komplexeren inversen MixColumns-Operation können je nach Implementierung die Rechenzeiten für die Ver- und Entschlüsselung unterschiedlich ausfallen, wobei dieser Effekt durch die Verwendung von Tabellen gänzlich kompensiert werden kann. Zum Vergleich: Auf einem Pentium III/200 MHz ist für 128 Bit-Schlüssel in beiden Richtungen ein Durchsatz von über 8 MByte/sec erzielbar [GLAD]. Natürlich hängen die Rechenzeiten auch von der jeweiligen Schlüssellänge bzw. von der Anzahl der zu durchlaufenden Runden ab.

Lassen Sie uns abschließend ein Resümee zur Performance der hier vorgestellten Implementierung ziehen. Der Rijndael-Algorithmus kann, wie viele andere Algorithmen auch, auf sehr verschiedene Art und Weise implementiert werden. Nicht zuletzt wegen seiner hervorragenden Performance wurde der AES zum Standard auserkoren. Der in diesem Artikel vorgestellte Quellcode wurde aufgrund der Übersichtlichkeit und zum besseren Verständnis der algorithmischen Vorgänge nicht optimiert und weist demzufolge nur suboptimale Laufzeiteigenschaften auf. Mittels Optimierungen, z.B. der Reduktion von Funktions- und Schleifenaufrufen, der Nutzung von Assembler mit prozessorspezifischen Befehlssätzen (SSE, MMX, etc.) in kritischen Abschnitten oder der Definition von vorgefertigten Tabellen, wird die Effizienz des AES weiter gesteigert. Durch die Nutzung der schnellen Funktion zur Multiplikation zweier Zahlen in GF(28) wird die Performance bereits deutlich erhöht. So benötigt das in diesem Artikel implementierte Programm zur Verschlüsselung einer 140 MB großen Datei auf einem Intel Q9450 annähernd fünf Minuten. Diese Zeit verkürzt sich auf nur noch 33 Sekunden, wenn die oben vorgestellten Potenz- und Logarithmustabellen für die Multiplikation verwendet werden. Der Leser kann diesen signifikanten Unterschied selbst bei der Kompilierung der im Anhang zur Verfügung gestellten Anwendung mit der Präprozessor-Anweisung _USE_OPTIMIZATION_LEVEL_1 testen. Das Makro gestattet es, zwischen der langsamen und schnellen Multiplikation zu wählen. Durch weitere Optimierungen mit der Stufe _USE_OPTIMIZATION_LEVEL_2 wird die Zeit für die Verschlüsselung einer 140 MB großen Datei auf 13 Sekunden reduziert, d.h. die Verschlüsselung ist um den Faktor 36 schneller als bei der normalen Implementierung mit xtime(). Mit der neuen Intel® Core™ 2010 Prozessorfamilie, basierend auf der 32nm Intel® Mikroarchitektur Codename Westmere, hat Intel einen neuen Befehlssatz unter dem Namen Intel® Advanced Encryption Standard Instructions (AES-NI) eingeführt. Der Befehlssatz wurde speziell für den Advanced Encryption Standard entwickelt und erlaubt es hardwaregestützt Daten mit enormer Geschwindigkeit zu ver- und entschlüsseln. Die neue Architektur stellt dafür sechs neue SIMD-Instruktionen bereit. Die ersten vier Instruktionen (AESENC, AESENCLAST, AESDEC und AESDELAST) garantieren die Hochleistungsver- und entschlüsselung, die anderen beiden Instruktionen (AESIMC und AESKEYGENASSIST) unterstützen die AES Schlüsselexpansion. Da diese Instruktionen in datenunabhängiger Zeit ablaufen und keine Suchtabellen verwenden, helfen sie dabei Seitenkanalattacken zu unterbinden. Darüberhinaus ist es möglich mit den Instruktionen den AES einfach und mit wenig Code zu implementieren. Der Visual Studio 2010 Compiler nutzt mit den intrinsischen Befehlen _mm_aesenc_si128 usw. die neuen zur Verfügung stehenden Instruktionen, sofern diese von dem ausführenden Prozessor unterstützt werden.

Schluss

Im Anhang dieses Artikels finden Sie den AES, implementiert in C nach der in diesem Artikel vorgestellten Anleitung. Zusätzlich befindet sich die interaktive Flash-Animation Rijndael-Inspector für den Desktoprechner, in Form einer ausführbaren Anwendung, im Paket. Der Quellcode stellt vier Funktionen zur Verfügung, die basierend auf den drei Betriebsarten OFB, CBC, CFB, beliebig lange Dateien und Byteströme ver- und entschlüsseln können. Dies kann in drei verschiedenen Optimierungsstufen geschehen, die sich mithilfe eines Makros freischalten lassen. Bei Bedarf können weitere Funktionen und Eigenschaften zum Quellcode hinzugefügt werden. Der fortgeschrittene Programmierer sollte auch in der Lage sein, Schwachstellen im Laufzeitverhalten der aktuellen Implementierung zu erkennen und den Code entsprechend zu optimieren.

Wie sicher ist der AES? Diese Frage ist für Personen, die keine Kryptographen sind, schwer zu beantworten. Der AES ist in den USA für staatliche Dokumente mit höchster Geheimhaltungsstufe zugelassen und gilt damit als sehr sicher. Da der AES keine bisher bekannten Schwachstellen besitzt, ist die Brute-Force-Methode die einzig mögliche Methode, um die Verschlüsselung zu knacken. Bei einer Schlüssellänge von 256 Bits ergibt sich die astronomisch hohe Zahl von 2256 verschiedenen Schlüsseln. Mit der heute zur Verfügung stehenden Rechenleistung verspricht eine Brute-Force-Methode keinen Erfolg, wenn das Passwort entsprechend komplex gewählt wurde, d.h. eine hohe Entropie aufweist.

Durch sogenannte „Timing Attacks“ lässt sich allerdings ein Angriff auf die Implementierung fahren, der die Komplexität des Algorithmus reduzieren kann. Durch eine Laufzeitanalyse ist der Angreifer so unter Umständen in der Lage wichtige Informationen über die Eingabe zu gewinnen. Insbesondere die MixColumns Stufe ist dafür anfällig. Der Programmierer kann derartige Angriffe aber durch die gezielte zeitliche Beeinflussung bestimmter Coderoutinen abwehren.

Literatur

  • Joan Daemen, Vincent Rijmen: The Design of Rijndael. AES: The Advanced Encryption Standard. Springer-Verlag. ISBN 3-540-42580-2
  • Hans Kurzweil: Endliche Körper: Verstehen, Rechnen, Anwenden. Springer-Verlag. 978-3540795971

Weitergehende Links

  • FIPS-197: Offizielle Spezifikation des AES vom NIST
  • CrypTool: CrypTool ist eine freie Software, die die Konzepte der Kryptographie und der Kryptoanalyse erfahrbar macht. CrypTool ist weltweit das verbreitetste Lernprogramm dieser Art
  • Crypto++® Library: Eine freie C++ Klassenbibliothek mit kryptographischen Schemen. Viele Algorithmen wurden mithilfe von Assembler auf eine größtmögliche Leistung und Effizienz hin optimiert
  • Applied Crypto++: Block Ciphers: Ein Artikel über Crypto++ auf codeproject.com mit dem Titel "Encrypt Data using Symmetric Encryption with Crypto++"
  • http://kuno-kohn.de/crypto/crypto/index.htm: Eine gut strukturierte Seite rund um das Thema Kryptographie
  • Intel® Advanced Encryption Standard (AES) Instructions Set: Der neue Befehlssatz AES-NI von Intel enthält sechs neue SIMD-Instruktionen zur hardwaregestützten Ver- und Entschlüsselung mit dem AES
Zuletzt aktualisiert am Dienstag, den 26. März 2013 um 11:00 Uhr
 
AUSWAHLMENÜ