Freitag, 8. Juni 2012


Topthema

Donnerstag, 28. September 2006 | Topthema

About Security #74: Kryptographie — Advanced Encryption Standard (AES)

(Link zum Artikel: http://www.entwickler.de/php/kolumnen/031531)
  • Teilen
  • kommentieren
  • empfehlen
  • Bookmark and Share

AES, der Advanced Encryption Standard, ist der offizielle Nachfolger von DES. Da abzusehen war, dass 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). Dabei wurden folgende Anforderungen festgelegt:

N E U ! Security aktuell
T�glich aktuelle Security-Infos!

  • 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, d.h. z.B. 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). 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.

About Security: Die komplette Serie

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(2^8)(Galois Field), der 256 Elemente besitzt. Ein Byte a7a6..a0 kann darin als Polynom a7x^7 + a6x^6 + a5x^5 + a4x^4 + a3x^3 + a2x^2 + a1x + a0dargestellt werden. Darauf wird dann eine Addition und Multiplikation definiert. Wer an den Grundlagen interessiert ist, findet eine Einf�hrung z.B. im Standard-Dokument FIPS 197.

S-Box

AES verwendet wie DES eine S-Box genannte Substitutionsbox. Auf die mathematischen Grundlagen der S-Box kann hier aus Platzgr�nden nicht eingegangen werden.

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:  b0 b1 b2 b3 ... b15       State:  b0 b4 b8 b12 b1 b5 b9 b13 b2 b6 b10 b14 b3 b7 b11 b15
bi = 1 Byte
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. Bei einem 128-Bit-Schl�ssel erh�lt man also vier Rundenschl�ssel. Die fehlenden Rundenschl�ssel werden durch die Schl�sselexpansion aus dem Chiffrierschl�ssel gebildet.

Aufbau des Rundenschl�ssel-Arrays
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 [a0,a1,a2,a3] wird [a1,a2,a3,a0]
  • Rcon[i]
    enth�lt die Rundenkonstanten, auf deren Berechnung hier aus Platzgr�nden nicht eingegangen werden kann.

Die eigentliche Expansion erfolgt 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
Transformationen

Die ben�tigten Transformationen:

  • 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

Der prinzipielle Ablauf:

Ablauf der 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. Mehr dazu und zur Sicherheit und Anwendung von AES in der n�chsten Folge.

Wenn Sie Fragen oder Themenvorschl�ge haben, k�nnen Sie diese gerne an die angegebene E-Mail-Adresse senden oder im Security-Forum einbringen!

Carsten Eilers

About Security � �bersicht zum aktuellen Thema "Kryptographie � AES"

Kommentare

Folgende Links könnten Sie auch interessieren