Advanced Encryption Standard/Arbeitsweise

Arbeitsweise

Rijndael ist eine als Substitutions-Permutations-Netzwerk entworfene Blockchiffre.

• Bei Rijndael können Blocklänge und Schlüssellänge unabhängig voneinander die Werte 128, 160, 192, 224 oder 256 Bits erhalten, während bei AES die Blockgröße auf 128 Bit festgelegt ist und die Schlüsselgröße 128, 192 oder 256 Bit betragen kann.

Rijndael ist eine iterierte Blockchiffre

• d. h. der Block wird in mehreren aufeinanderfolgenden Runden verschlüsselt, die bis auf die verwendeten Rundenschlüssel gleich sind.
• Für jede Runde wird ein anderer Rundenschlüssel aus dem Originalschlüssel berechnet (Schlüsselexpansion).
• Die Anzahl $R$ der Runden variiert und ist vom Maximum der Blockgröße $b$ und der Schlüssellänge $k$ abhängig (beim AES also nur von der Schlüssellänge):

Anzahl der Runden bei Rijndael

max(b, k)	128	160	192	224	256
Rundenzahl R	10	11	12	13	14

Der Datenblock, der ver- oder entschlüsselt werden soll, wird zunächst in eine zweidimensionale Tabelle geschrieben, deren Zellen ein Byte groß sind und die vier Zeilen und je nach Blockgröße 4 bis 8 Spalten hat.

Ablauf

• Schlüsselexpansion
• AddRoundKey(Rundenschlüssel[0])
• Kryptografiesrunden r = 1 bis R-1:
  • SubBytes()
  • ShiftRows()
  • MixColumns()
  • AddRoundKey(Rundenschlüssel[r])
• Schlussrunde:
  • SubBytes()
  • ShiftRows()
  • AddRoundKey(Rundenschlüssel[R])

S-Box

Rijndael verwendet eine S-Box, um bei der Operation SubBytes() jedes Byte des Datenblocks durch ein anderes zu ersetzen, und sie wird auch bei der Schlüsselexpansion eingesetzt.

• Eine S-Box (Substitutionsbox) dient zur monoalphabetischen Kryptografie.
• Sie bewirkt vor allem die Verwischung der Beziehung zwischen Klar- und Geheimtext, was in der kryptologischen Fachsprache Konfusion genannt wird, kann aber auch zur Umsetzung des Shannon’schen Prinzips der Diffusion beitragen.

Die S-Box von Rijndael ist nach Kriterien konstruiert, die die Anfälligkeit für die Methoden der linearen und der differentiellen Kryptoanalyse sowie für algebraische Attacken minimieren sollen.

• Sie besteht aus 256 Bytes, die erzeugt werden, indem jedes Byte außer der Null, aufgefasst als Vertreter des endlichen Körpers $\mathbb {F} _{2^{8}}$, durch sein multiplikatives Inverses ersetzt wird, worauf noch eine affine Transformation erfolgt. Es ist

$S(x)={\overline {x}}\oplus ({\overline {x}}\lll 1)\oplus ({\overline {x}}\lll 2)\oplus ({\overline {x}}\lll 3)\oplus ({\overline {x}}\lll 4)\oplus (63)_{\text{hex}}$.

Dabei steht ${\overline {x}}$ für das multiplikative Inverse von $x$ in $\mathbb {F} _{2^{8}}$, oder für 0, falls $x=0$. $b\lll n$ bezeichnet die Linksrotation des Bytes $b$ um $n$ Bitpositionen und $\oplus$ das bitweise XOR.

Die Werte der S-Box und der zum Entschlüsseln benötigten inversen S-Box können entweder für jedes substituierte Byte erneut (dynamisch) berechnet werden, um Speicher zu sparen, oder vorberechnet und in einem Array gespeichert werden.

Schlüsselexpansion

Prinzip der Schlüsselexpansion bei AES

Zunächst müssen aus dem Schlüssel $R+1$ Teilschlüssel (auch Rundenschlüssel genannt) erzeugt werden, die jeweils die gleiche Größe wie ein Datenblock haben.

• Somit muss der Benutzerschlüssel auf die Länge $b\cdot (R+1)$ expandiert werden, wobei $b$ die Blockgröße in Bit angibt.
• Der Schlüssel wird in eine zweidimensionale Tabelle mit vier Zeilen und Zellen der Größe 1 Byte abgebildet.
• Fasst man jede Spalte als 32-bit-Wort auf, ergibt das ein eindimensionales Array mit $b/32\cdot (R+1)$ Elementen.

Sei $N=k/32$ die Länge des Benutzerschlüssels in Wörtern.

• Dieser wird zunächst in die ersten Wörter $W_{0},\cdots ,W_{N-1}$ des Arrays eingetragen.
• Dann werden in einer Iteration die weiteren Wörter $W_{i}$ jeweils durch bitweises XOR von $W_{i-1}$ und $W_{i-N}$ berechnet.
• Für jedes $N$-te Wort wird $W_{i-1}$ zuvor rotiert, byteweise substituiert und mit einer von $i$ abhängigen Konstanten verknüpft.
• Falls $N>6$ ist, wird dazwischen alle $N$ Wörter noch eine weitere Substitution ausgeführt.

Für $i=N,\ldots ,b/32\cdot (R+1)-1$:

$W_{i}={\begin{cases}W_{i-N}\oplus \operatorname {S} (W_{i-1}\lll 8)\oplus C_{i/N-1}&{\text{wenn }}i\equiv 0{\pmod {N}}\\W_{i-N}\oplus \operatorname {S} (W_{i-1})&{\text{wenn }}N>6{\text{ und }}i\equiv 4{\pmod {N}}\\W_{i-N}\oplus W_{i-1}&{\text{sonst}}\\\end{cases}}$

$\operatorname {S} (x)$ bezeichnet die Substitution jedes Bytes in $x$ durch die gleiche S-Box, die auch beim Verschlüsseln eines Datenblocks eingesetzt wird. $x\lll 8$ ist die Rotation von $x$ um 8 Bitpositionen nach links.

• Die Konstanten $C_{j}$ werden gebildet, indem $2^{j}$, berechnet im Körper $\mathbb {F} _{2^{8}}$, in das höchste Byte von $C_{j}$ eingetragen wird, während die übrigen Bytes 0 sind.

AddRoundKey

Bitweise XOR-Verknüpfung zwischen dem Block und dem aktuellen Rundenschlüssel

Vor der ersten und nach jeder Kryptografiesrunde wird der Datenblock mit einem der Rundenschlüssel XOR-verknüpft.

• Dies ist die einzige Funktion in AES, in die der Benutzerschlüssel eingeht.

SubBytes

Im ersten Schritt jeder Runde wird jedes Byte $B$ im Block durch den Eintrag $S(B)$ der S-Box ersetzt.

• Somit werden die Daten byteweise monoalphabetisch verschlüsselt.

ShiftRows

Zeilen werden um eine bestimmte Anzahl von Spalten nach links verschoben

Wie oben erwähnt, liegt ein Block in Form einer zweidimensionalen Tabelle mit vier Zeilen vor.

• In diesem zweiten Schritt jeder Runde 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:

r	b=128	b=160	b=192	b=224	b=256
Zeile 1	0	0	0	0	0
Zeile 2	1	1	1	1	1
Zeile 3	2	2	2	2	3
Zeile 4	3	3	3	4	4

Je nach Blocklänge b und Zeile in der Datentabelle wird die Zeile um 1 bis 4 Spalten verschoben.
Für den AES sind nur die fett markierten Werte relevant.

MixColumns

Die Spalten werden vermischt

Als dritte Operation jeder Runde außer der Schlussrunde werden die Daten innerhalb der Spalten vermischt.

• Zur Berechnung eines Bytes $b_{j}$ der neuen Spalte wird jedes Byte $a_{j}$ der alten mit einer Konstanten (1, 2 oder 3) multipliziert.
• Dies geschieht modulo des irreduziblen Polynoms $x^{8}+x^{4}+x^{3}+x+1$ im Galois-Körper $GF(2^{8})$.
• Dann werden die Ergebnisse XOR-verknüpft:

$b_{0}=(a_{0}\cdot 2)\oplus (a_{1}\cdot 3)\oplus (a_{2}\cdot 1)\oplus (a_{3}\cdot 1)$

$b_{1}=(a_{0}\cdot 1)\oplus (a_{1}\cdot 2)\oplus (a_{2}\cdot 3)\oplus (a_{3}\cdot 1)$

$b_{2}=(a_{0}\cdot 1)\oplus (a_{1}\cdot 1)\oplus (a_{2}\cdot 2)\oplus (a_{3}\cdot 3)$

$b_{3}=(a_{0}\cdot 3)\oplus (a_{1}\cdot 1)\oplus (a_{2}\cdot 1)\oplus (a_{3}\cdot 2)$

In Matrixschreibweise:

${\begin{pmatrix}b_{0}\\b_{1}\\b_{2}\\b_{3}\end{pmatrix}}={\begin{pmatrix}2&3&1&1\\1&2&3&1\\1&1&2&3\\3&1&1&2\end{pmatrix}}{\begin{pmatrix}a_{0}\\a_{1}\\a_{2}\\a_{3}\end{pmatrix}}$

Nach den Rechengesetzen in diesem Galois-Körper gilt für die Multiplikation:

• $a\cdot 1=a$
• $a\cdot 2={\begin{cases}2a&{\text{wenn }}a<2^{7}\\2a\oplus (11{\text{b}})_{\text{hex}}&{\text{wenn }}a\geq 2^{7}\end{cases}}$
• $a\cdot 3=(a\cdot 2)\oplus a$

Dabei bezeichnet $2a$ die normale Multiplikation von a mit 2 und $\oplus$ die bitweise XOR-Verknüpfung.

Entschlüsselung

Bei der Entschlüsselung von Daten wird genau rückwärts vorgegangen.

• Die Daten werden zunächst wieder in zweidimensionale Tabellen gelesen und die Rundenschlüssel generiert.
• Allerdings wird nun mit der Schlussrunde angefangen und alle Funktionen in jeder Runde in der umgekehrten Reihenfolge aufgerufen.
• Durch die vielen XOR-Verknüpfungen unterscheiden sich die meisten Funktionen zum Entschlüsseln nicht von denen zum Verschlüsseln.
• Jedoch muss eine andere S-Box genutzt werden (die sich aus der originalen S-Box berechnen lässt) und die Zeilenverschiebungen erfolgen in die andere Richtung.