Verfahren der Kryptographie, Teil 6: Der Advanced Encryption Standard (AES)
Der Advanced Encryption Standard, abgekürzt AES, ist der offizielle Nachfolger von DES. Als abzusehen war, das DES nicht mehr lange sicher sein würde, wurde vom US-amerikanischen National Institute of Standards and Technology (NIST) am 2. Januar 1997 die Suche nach einem Nachfolger offiziell eingeleitet.
Am 12. September 1997 folgte die offizielle Ausschreibung (Request for Candidate). Nach einer Änderung der geforderten Blockgrößen von Anfangs 128, 192 und 256 Bit auf letztlich ausschließlich 128 Bit wurden letztendlich die folgenden Anforderungen an den zu entwickelden Algorithmus festgelegt:
- Der neue Algorithmus muss eine symmetrische Blockchiffre
- mit einer Blocklänge von mindestens 128 Bit sein, die
- 128, 192 und 256 Bit lange Schlüssel verwenden kann.
- Die Implementierung soll sowohl in Hard- wie auch Software möglich sein und
- überdurchschnittliche Performance haben.
- Für den Einsatz in Smartcards wird ein geringer Ressourcenbedarf gefordert, also zum Beispiel kurzer Code und geringer Speicherbedarf.
- Natürlich muss der neue Algorithmus allen bekannten Methoden der Kryptanalyse widerstehen.
- Außerdem muss der Algorithmus von jedermann unentgeltlich genutzt werden können.
Daraufhin wurden 15 Algorithmen eingereicht, von denen nach einer ersten Auswahlrunde im August 1999 fünf in die engere Wahl kamen (Presseerklärung, PDF).
Am Ende der zweiten Auswahlrunde fiel die Wahl auf den von Joan Daemen und Vincent Rijmen unter den Namen Rijndael eingereichten Algorithmus (Presseerklärung vom 2. Oktober 2000 auf archive.org).
Am 26. November 2001 wurde der Advanced Encryption Standard (AES) in FIPS 197 (PDF) veröffentlicht.
Der Algorithmus
Während Rijndael für Schlüssellängen und Blockgrößen zwischen 128 und 256 Bit in 32-Bit-Schritten spezifiziert werden kann, wurde für AES die Blockgröße auf 128 Bit und die Schlüssellänge auf 128, 192 oder 256 Bit festgelegt.
AES wendet eine Reihe von Transformationen in mehreren Runden auf die Eingabe an. Die Anzahl der Runden ist abhängig von der Schlüssellänge:
Schlüssellänge | Rundenzahl |
---|---|
128 | 10 |
192 | 12 |
256 | 14 |
AES verwendet Bytes und Worte aus 4 Bytes. Gerechnet wird im endlichen
Körper GF(28) (Galois Field), der 256 Elemente
besitzt.
Ein Byte
a7a6...a0
kann darin als Polynom
a7x7 + a6x6 + a5x5 +
a4x4 + a3x3 + a2x2 +
a1x + a0
dargestellt werden. Darauf wird dann eine Addition und Multiplikation
definiert.
Wenn Sie an den Grundlagen interessiert sind, findet Sie zum Beispiel im Standard-Dokument FIPS 197 (PDF) eine Einführung.
Die S-Box
AES verwendet wie DES eine S-Box genannte Substitutionsbox. Auf die mathematischen Grundlagen der S-Box gehe ich hier aus Platzgründen nicht ein. Auch dazu finden Sie alles Relevante in FIPS 197 (PDF).
Das Einlesen der Daten
AES arbeitet mit zweidimensionalen Byte-Arrays mit 8 Bit großen Elementen, genannt State (dt. Zustand). Ein solcher State ist eine Tabelle mit vier Zeilen und vier Spalten, in die zu Beginn der Klartext spaltenweise eingelesen wird.
Eingabeblock: | b0b1b2...b15 | State: |
b0 b4 b8 b12 b1 b5 b9 b13 b2 b6 b10 b14 b3 b7 b11 b15 |
|||
bi = 1 Byte |
Der Schlüssel
Für die Verschlüsselung werden (Rundenzahl+1) Rundenschlüssel benötigt. Die Rundenschlüssel werden in einem zweidimensionalen Array aus 32-Bit-Werten gespeichert. Dabei wird der Chiffrierschlüssel in die ersten Elemente des Arrays geschrieben, siehe Abbildung 1. Bei einem 128-Bit-Schlüssel erhält man also vier Rundenschlüssel. Die fehlenden Rundenschlüssel werden durch eine Schlüsselexpansion aus dem Chiffrierschlüssel gebildet.
Abb. 1: Aufbau des Rundenschlüssel-Arrays von AES (Klick für großes Bild)
Die Schlüsselexpansion
Für die Schlüsselexpansion werden folgende Funktionen benötigt:
- SubWord
- wendet auf einen 4-Byte-Eingabewert die S-Box an, um den Ausgabewert zu ermitteln
- RotWord
- ist eine zyklische Linksrotation: Aus [a0a1a2a3] wird [a1a2a3a0]
- Rcon[i]
- enthält die Rundenkonstanten, auf deren Berechnung ich hier aus Platzgründen ebenfalls nicht eingehe.
Die eigentliche Expansion erfolgt dann nach folgendem Pseudocode:
Schlüsselexpansion(Schlüssel key, Rundenschlüssel-Array w, Schlüssellänge[Bytes] n)
BEGIN
i = 0
WHILE (i < n)
w[i] = (key[4*i], key[4*i+1], key[4*i+2], key[4*i+3])
i = i+1
ENDWHILE
i = n
WHILE (i < 4 * (Rundenzahl+1)]
temp = w[i-1]
IF (i mod n = 0)
temp = SubWord(RotWord(temp)) XOR Rcon[i/n]
ELSEIF (n > 6 and i mod n = 4)
temp = SubWord(temp)
ENDIF
w[i] = w[i-n] XOR temp
i = i + 1
ENDWHILE
END
Die Transformationen
Die folgenden Transformationen werden benötigt:
- SubBytes
- Jedes Byte im aktuellen Block wird durch eine S-Box umgewandelt.
- ShiftRow
- Die Bytes des aktuellen Blocks werden zeilenweise nach links verschoben, übergelaufene Zellen von rechts nachgeschoben.
- MixColumn
- Die Spalten des aktuellen Blocks werden mit einem konstanten Polynom multipliziert, was einer Diffusion entspricht.
- AddRoundKey
- Aktueller Block und aktueller Rundenschlüssel werden bitweise XOR-verknüpft
Die Verschlüsselung mit AES
Den prinzipiellen Ablauf zeigt Abbildung 2.
Abb. 2: Ablauf der AES-Verschlüsselung
Die AES-Verschlüsselung als Pseudocode:
AES-Verschlüsselung(Klartextblock, Geheimtextblock, Rundenschlüssel-Array w)
BEGIN
State = Klartextblock
AddRoundKey(State, w[0])
FOR Runde = 1 TO Rundenzahl-1
SubBytes(State)
ShiftRow(State)
MixColumn(State)
AddRoundKey(State, w[Runde])
ENDFOR
SubBytes(State)
ShiftRow(State)
AddRoundKey(State, w[Rundenzahl])
Geheimtextblock = State
END
Die Entschlüsselung erfolgt durch Anwendung der inversen Transformationen in umgekehrter Reihenfolge. Die sowie die Sicherheit und Anwendung von AES sind das Thema der nächsten Folge.
Trackbacks
Dipl.-Inform. Carsten Eilers am : Verfahren der Kryptographie, Teil 7: AES-Entschlüsselung und -Sicherheit
Vorschau anzeigen
Dipl.-Inform. Carsten Eilers am : Verfahren der Kryptographie, Teil 11: Hybride Verschlüsselungsverfahren
Vorschau anzeigen
Dipl.-Inform. Carsten Eilers am : Verfahren der Kryptographie, Teil 17: SHA-3 steht als Alternative und Ersatz bereit
Vorschau anzeigen
Dipl.-Inform. Carsten Eilers am : Kryptographie - Ein Überblick
Vorschau anzeigen
www.ceilers-news.de am : PingBack
Die Anzeige des Inhaltes dieses Trackbacks ist leider nicht möglich.Dipl.-Inform. Carsten Eilers am : WLAN-Sicherheit 8 - Der aktuelle Standard-Verschlüsselungsalgorithmus: WPA2
Vorschau anzeigen
Dipl.-Inform. Carsten Eilers am : WLAN-Sicherheit 11 - Der Counter-Mode/CBC-MAC von WPA2
Vorschau anzeigen
Dipl.-Inform. Carsten Eilers am : Drucksache: PHP Magazin 1.18 - Welche Kryptoverfahren sollte man verwenden bzw. meiden?
Vorschau anzeigen
Dipl.-Inform. Carsten Eilers am : Drucksache: Windows Developer 1.18 - Sicherheit von Kryptoverfahren
Vorschau anzeigen
entwickler.de am : PingBack
Die Anzeige des Inhaltes dieses Trackbacks ist leider nicht möglich.