Skip to content

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.

Aufbau des Rundenschlüssel-Arrays
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.

Ablauf der AES-Verschlüsselung
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.

Carsten Eilers

Trackbacks

Dipl.-Inform. Carsten Eilers am : Verfahren der Kryptographie, Teil 7: AES-Entschlüsselung und -Sicherheit

Vorschau anzeigen
Die Entschlüsselung eines mit AES verschlüsselten Textes erfolgt durch Anwendung der inversen Transformationen in umgekehrter Reihenfolge. Die dafür benötigte inverse S-Box wird aus der vorhandenen S-Box berechnet. Die Rundensc

Dipl.-Inform. Carsten Eilers am : Verfahren der Kryptographie, Teil 11: Hybride Verschlüsselungsverfahren

Vorschau anzeigen
Ein hybrides Verschlüsselungsverfahren wurde bereits bei der Vorstellung von Anwendungen des AES-Algorithmus erwähnt. Bei einem hybriden Verfahren werden ein symmetrisches und ein asymmetrisches Verfahren kombiniert, um in den Genuss der

Dipl.-Inform. Carsten Eilers am : Kryptographie - Ein Überblick

Vorschau anzeigen
Die Kryptographie ist ein ein sehr umfangreiches Themengebiet, und obwohl ich mich jetzt seit 30 Artikeln damit befasst habe sind längst nicht alle Themen vorgestellt worden. Aber zumindest die wichtigsten habe ich beschrieben, und damit soll e

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
Wi-Fi Protected Access 2 (WPA2) implementiert die grundlegenden Funktionen des aktuellen Sicherheitsstandards IEEE 802.11i für drahtlose Netze nach dem IEEE 802.11 Standard (WLAN). Im Gegensatz zum ursprünglichen Verschlüs

Dipl.-Inform. Carsten Eilers am : WLAN-Sicherheit 11 - Der Counter-Mode/CBC-MAC von WPA2

Vorschau anzeigen
Wi-Fi Protected Access 2 (WPA2) implementiert die grundlegenden Funktionen des aktuellen Sicherheitsstandards IEEE 802.11i für drahtlose Netze nach dem IEEE 802.11 Standard (WLAN). Der allgemeine Aufbau, Schlüsselmanagement und Schl&amp;uu

Dipl.-Inform. Carsten Eilers am : Drucksache: Windows Developer 1.18 - Sicherheit von Kryptoverfahren

Vorschau anzeigen
Im Windows Developer 1.18 ist ein Überblick über den aktuellen Stand der Sicherheit in der Kryptographie erschienen: Welche Kryptoverfahren und Schlüssellängen sollte man verwenden, welche sollte man meiden? Im Windows De

entwickler.de am : PingBack

Die Anzeige des Inhaltes dieses Trackbacks ist leider nicht möglich.