diff options
Diffstat (limited to '')
-rw-r--r-- | buch/chapters/90-crypto/aes.tex | 866 |
1 files changed, 433 insertions, 433 deletions
diff --git a/buch/chapters/90-crypto/aes.tex b/buch/chapters/90-crypto/aes.tex index acdda22..168ff2c 100644 --- a/buch/chapters/90-crypto/aes.tex +++ b/buch/chapters/90-crypto/aes.tex @@ -1,433 +1,433 @@ -% -% aes.tex -- Beschreibung des AES Algorithmus -% -% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil -% -\section{Advanced Encryption Standard -- AES -\label{buch:section:aes}} -\rhead{Advanced Encryption Standard} -Eine wichtige Forderung bei der Konzeption des damals neuen -Advanced Encryption Standard war, dass darin keine ``willkürlich'' -erscheinenden Operationen geben darf, bei denen der Verdacht -entstehen könnte, dass sich dahinter noch offengelegtes Wissen -über einen möglichen Angriff auf den Verschlüsselungsalgorithmus -verbergen könnte. -Dies war eine Schwäche des vor AES üblichen DES Verschlüsselungsalgorithmus. -In seiner Definition kommt eine Reihe von Konstanten vor, über deren -Herkunft nichts bekannt war. -Die Gerüchteküche wollte wissen, dass die NSA die Konstanten aus dem -ursprünglichen Vorschlag abgeändert habe, und dass dies geschehen sei, -um den Algorithmus durch die NSA angreifbar zu machen. - -Eine weiter Forderung war, dass die Sicherheit des neuen -Verschlüsselungsstandards ``skalierbar'' sein soll, dass man also -die Schlüssellänge mit der Zeit von 128~Bit auf 196 oder sogar 256~Bit -steigern kann. -Der Standard wird dadurch langlebiger und gleichzeitig entsteht die -Möglichkeit, Sicherheit gegen Rechenleistung einzutauschen. -Weniger leistungsfähige Systeme können den Algorithmus immer noch -nutzen, entweder mit geringerer Verschlüsselungsrate oder geringerer -Sicherheit. - -In diesem Abschnitt soll gezeigt werde, wie sich die AES -spezifizierten Operationen als mit der Arithmetik der -endlichen Körper beschreiben lassen. -Im Abschnitt~\ref{buch:subsection:byte-operationen} werden -Bytes als Elemente in einem endlichen Körper $\mathbb{F}_{2^8}$ -interpretiert. -Damit kann dann die sogenannte $S$-Box konstruiert werden und -es ist leicht zu verstehen, dass sie invertierbar ist. -Aus den Byte-Operationen können dann Mischoperationen erzeugt -werden, die Bytes untereinander verknüpfen, die aber auch wieder -als Operationen in einem endlichen Körper verstanden werden können. - -\subsection{Byte-Operationen -\label{buch:subsection:byte-operationen}} -Moderne Prozessoren operieren auf Wörtern, die Vielfache von Bytes sind. -Byte-Operationen sind besonders effizient in Hardware zu realisieren. -AES verwendet daher als Grundelemente Operationen auf Bytes, die als -Elemente eines endlichen Körpers $\mathbb{F}_{2^8}$ interpretiert werden. - -\subsubsection{Bytes als Elemente von $\mathbb{F}_{2^8}$} -Das Polynom $m(X)=X^8+X^4+X^3+X+1\in \mathbb{F}_2[X]$ ist irreduzibel, -somit ist $\mathbb{F}_{2^8} = \mathbb{F}_2[X]/(m)$ ein Körper. -Die Elemente können dargestellt werden als Polynome, das Byte -$\texttt{63}_{16}$ bekommt die Form -\[ -p(X) = p_7X^7 + p_6X^6 + \dots + p_2X^2+p_1X + p_0, -\] -sie bestehen daher aus den $8$ Bits $p_7,\dots,p_0$. - -Die Interpretation der Bytes als Elemente eines Körpers bedeutet, -dass jede Multiplikation mit einem nicht verschwindenden Byte -invertierbar ist. -Ausserdem mischen diese Operationen die einzelnen Bits auf einigermassen -undurchsichtige, aber umkehrbare Art durcheinander, wie dies für ein -Verschlüsselungsverfahren wünschenswert ist. - -\subsubsection{$S$-Box} -Für die Operation der $S$-Box wird wie folgt zusammengesetzt. -Zunächst wird ein Byte $x$ durch das zugehörige multiplikative -inverse Element -\[ -x\mapsto \bar{x} = \begin{cases} -x^{-1}&\qquad \text{für $x\in \mathbb{F}_{2^8}^*$}\\ -0 &\qquad \text{für $x=0$} -\end{cases} -\] -ersetzt. - -Im zweiten Schritt betrachten wir $\mathbb{F}_{2^8}$ als einen -$8$-dimensionalen Vektorraum über $\mathbb{F}_2$. -Einem Polynom $p(X)=p_7X^7 + \dots + p_1X+p_0$ wird der Spaltenvektor -mit den Komponenten $p_0$ bis $p_7$ zugeordnet. - -\begin{figure} -\centering -\includegraphics[width=\textwidth]{chapters/90-crypto/images/sbox.pdf} -\caption{Berechnung der Inversen der Matrix $A$ in der $S$-Box des -AES-Algorithmus mit dem Gauss-Algorithmus -\label{buch:crypto:fig:sbox}} -\end{figure} - -Eine lineare Transformation in diesem Vektorraum kann durch eine -$8\times 8$-Matrix in $M_8(\mathbb{F}_2)$ betrachtet werden. -In der $S$-Box wird die Matrix -\[ -A= -\begin{pmatrix} -1&0&0&0&1&1&1&1\\ -1&1&0&0&0&1&1&1\\ -1&1&1&0&0&0&1&1\\ -1&1&1&1&0&0&0&1\\ -1&1&1&1&1&0&0&0\\ -0&1&1&1&1&1&0&0\\ -0&0&1&1&1&1&1&0\\ -0&0&0&1&1&1&1&1 -\end{pmatrix}, -\qquad -A^{-1} -= -\begin{pmatrix} -0&0&1&0&0&1&0&1\\ -1&0&0&1&0&0&1&0\\ -0&1&0&0&1&0&0&1\\ -1&0&1&0&0&1&0&0\\ -0&1&0&1&0&0&1&0\\ -0&0&1&0&1&0&0&1\\ -1&0&0&1&0&1&0&0\\ -0&1&0&0&1&0&1&0 -\end{pmatrix} -\] -verwendet. -Mit dem Gauss-Algorithmus, schematisch dargestellt in -Abbildung~\ref{buch:crypto:fig:sbox}, kann man die Inverse -bestimmen, die Multiplikation mit $A$ ist also eine invertierbare -Abbildung. - -Der letzte Schritt ist dann wieder eine Addition von -$q(X)=X^7+X^6+X+1\in \mathbb{F}_{2^8}$, durch Subtraktion -von $q(X)$ invertiert werden kann. -Die $S$-Box-Operation kann also bektoriell geschrieben werden also -\[ - S(x) = A\overline{x}+q. -\] - -Die Implementation ist möglicherweise mit einer Tabelle am schnellsten, -es sind ja nur 256 Bytes im Definitionsbereich der $S$-Box-Abbildung -und ebenso nur 256 möglich Werte. - -\subsection{Block-Operationen -\label{buch:subsection:block-operationen}} -Die zu verschlüsselnden Daten werden in in Blöcke aufgeteilt, deren -Länge Vielfache von $32$ bit sind. -Die kleinste Blockgrösse ist 128\,Bit, die grösste ist 256\,Bit. -Die Bytes eines Blockes werden dann in einem Rechteck angeordnet -als -\begin{equation} -\begin{tabular}{|>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}|} -\hline - b_{0} & b_{4} & b_{8} & b_{12} & b_{16} & b_{20} & b_{24} & b_{28} \\ - b_{1} & b_{5} & b_{9} & b_{13} & b_{17} & b_{21} & b_{25} & b_{29} \\ - b_{2} & b_{6} & b_{10} & b_{14} & b_{18} & b_{22} & b_{26} & b_{30} \\ - b_{3} & b_{7} & b_{11} & b_{15} & b_{19} & b_{23} & b_{27} & b_{31} \\ -\hline -\end{tabular} -\label{buch:crypto:eqn:block} -\end{equation} -für eine Blocklänge von 256\,Bits. - - - -\subsubsection{Zeilenshift} -\begin{figure} -\centering -\includegraphics[width=\textwidth]{chapters/90-crypto/images/shift.pdf} -\caption{Zeilenshift in einem Block von 256 bits -\label{buch:crypto:fig:shift}} -\end{figure} -Die Verschlüsselung muss sicherstellen, dass die Bytes des Blockes -untereinander gut gemischt werden. -Die bisher beschriebenen Operationen operieren immer nur auf einzelnen -Bytes während -die im nächsten Abschnitt beschriebene Spalten-Mischoperation -nur auf Spalten wird. -Die Zeilenmischoperation permutiert die Zeilen in den vier Zeilen -eines Blocks zyklisch, die erste Zeile bleibt an Ort, die zweite -Zeile wird um ein Byte rotiert, die dritte um zwei und die letzte -um 3 Bytes, wie in Abbildung~\ref{buch:crypto:fig:zeilenshift} -dargestellt. -Diese Operation könnte mit einer Permutationsmatrix beschrieben werden, -dies wäre jedoch keine effiziente Implementation. -Der Zeilenschift hat ansonsten keine elegante algebraische Beschreibung. - -\subsubsection{Spalten mischen} -Jede Spalte von \eqref{buch:crypto:eqn:block} kann als Vektor des -vierdimensionalen Vektorraumes $\mathbb{F}_{2^8}^4$. -Die Zeilenmischoperation wendet ein lineare Abbildung auf jeden -Spaltenvektor von~\eqref{buch:crypto:eqn:block}. -Die Koeffizienten der Matrix sind Elemente von $\mathbb{F}_{2^8}$. -Die Matrix ist -\[ -C=\begin{pmatrix} -\texttt{02}_{16}&\texttt{03}_{16}&\texttt{01}_{16}&\texttt{01}_{16}\\ -\texttt{01}_{16}&\texttt{02}_{16}&\texttt{03}_{16}&\texttt{01}_{16}\\ -\texttt{01}_{16}&\texttt{01}_{16}&\texttt{02}_{16}&\texttt{03}_{16}\\ -\texttt{03}_{16}&\texttt{01}_{16}&\texttt{01}_{16}&\texttt{02}_{16} -\end{pmatrix}. -\] -Um nachzuprüfen, dass die Matrix $C$ invertierbar ist, könnte man den -Gauss-Algorithmus verwenden und damit die Inverse berechnen. -Dazu müsste man die multiplikativen Inversen kennen, was etwas mühsam -ist. -Man kann aber aber auch die Determinante bestimmen, dazu braucht man -nur multiplizieren zu können, was in diesem Fall sehr leicht möglich ist, -weil kein Überlauf entsteht. -Dabei hilft es zu beachten, dass die Multiplikation mit $\texttt{02}_{16}$ -nur eine Einbit-Shiftoperation nach links ist. -Nur die Multiplikation $\texttt{03}_{16}\cdot\texttt{03}_{16}=\text{05}_{16}$ -gibt etwas mehr zu überlegen. -Mit geeigneten Zeilen-Operationen kann man die Berechnung der Determinante -von $C$ mit dem Entwicklungssatz etwas vereinfachen. -Man erhält -\begin{align*} -\det(C) -&= -\left| -\begin{matrix} -\texttt{02}_{16}&\texttt{03}_{16}&\texttt{01}_{16}&\texttt{01}_{16}\\ -\texttt{01}_{16}&\texttt{02}_{16}&\texttt{03}_{16}&\texttt{01}_{16}\\ -\texttt{00}_{16}&\texttt{03}_{16}&\texttt{01}_{16}&\texttt{02}_{16}\\ -\texttt{00}_{16}&\texttt{00}_{16}&\texttt{03}_{16}&\texttt{02}_{16} -\end{matrix} -\right| -\\ -&= -\texttt{02}_{16} -\left| -\begin{matrix} -\texttt{02}_{16}&\texttt{03}_{16}&\texttt{01}_{16}\\ -\texttt{03}_{16}&\texttt{01}_{16}&\texttt{02}_{16}\\ -\texttt{00}_{16}&\texttt{03}_{16}&\texttt{02}_{16} -\end{matrix} -\right| -+ -\texttt{01}_{16} -\left| -\begin{matrix} -\texttt{03}_{16}&\texttt{01}_{16}&\texttt{01}_{16}\\ -\texttt{03}_{16}&\texttt{01}_{16}&\texttt{02}_{16}\\ -\texttt{00}_{16}&\texttt{03}_{16}&\texttt{02}_{16} -\end{matrix} -\right| -\\ -&= -\texttt{02}_{16} -\left| -\begin{matrix} -\texttt{02}_{16}&\texttt{03}_{16}&\texttt{01}_{16}\\ -\texttt{01}_{16}&\texttt{02}_{16}&\texttt{03}_{16}\\ -\texttt{00}_{16}&\texttt{03}_{16}&\texttt{02}_{16} -\end{matrix} -\right| -+ -\texttt{01}_{16} -\left| -\begin{matrix} -\texttt{03}_{16}&\texttt{01}_{16}&\texttt{01}_{16}\\ -\texttt{00}_{16}&\texttt{00}_{16}&\texttt{01}_{16}\\ -\texttt{00}_{16}&\texttt{03}_{16}&\texttt{02}_{16} -\end{matrix} -\right| -\\ -&= -\texttt{02}_{16} -\left( -\texttt{02}_{16} -\left| -\begin{matrix} -\texttt{02}_{16}&\texttt{03}_{16}\\ -\texttt{03}_{16}&\texttt{02}_{16} -\end{matrix} -\right| -+ -\texttt{01}_{16} -\left| -\begin{matrix} -\texttt{03}_{16}&\texttt{01}_{16}\\ -\texttt{03}_{16}&\texttt{02}_{16} -\end{matrix} -\right| -\right) -+ -\texttt{01}_{16} -\left| -\begin{matrix} -\texttt{03}_{16}&\texttt{01}_{16}&\texttt{01}_{16}\\ -\texttt{00}_{16}&\texttt{03}_{16}&\texttt{02}_{16}\\ -\texttt{00}_{16}&\texttt{00}_{16}&\texttt{01}_{16} -\end{matrix} -\right| -\\ -&= -\texttt{02}_{16} -( -\texttt{02}_{16}(\texttt{04}_{16}+\texttt{05}_{16}) -+ -(\texttt{06}_{16}+\texttt{03}_{16}) -) -+ -\texttt{03}_{16}\texttt{03}_{16} -\\ -&= -\texttt{02}_{16} -( -\texttt{02}_{16} -+ -\texttt{05}_{16} -) -+ -\texttt{05}_{16} -= -\texttt{0e}_{16}+\texttt{05}_{16} -= -\texttt{0a}_{16} -\ne 0. -\end{align*} -Damit ist gezeigt, dass die Matrix $C$ invertierbar auf den -Spaltenvektoren wirkt. -Die Inverse der Matrix kann einmal berechnet und anschliessend -für die Entschlüsselung verwendet werden. - -Alternativ kann man die Multiplikation mit der Matrix $C$ auch -interpretieren als eine Polynommultiplikation. -Dazu interpretiert man die Spalten des Blocks als Polynom vom Grad~3 -mit Koeffizienten in $\mathbb{F}_{2^8}$. -Durch Reduktion mit dem irreduziblen Polynom -$n(Z)=Z^4+1\in\mathbb{F}_{2^8}[X]$ entsteht aus dem Polynomring -wieder ein Körper. -Die Wirkung der Matrix $C$ ist dann nichts anderes als Multiplikation -mit dem Polynom -\[ -c(Z) = \texttt{03}_{16}Z^3 + Z^2+Z^1+\texttt{02}_{16}, -\] -die natürlich ebenfalls umkehrbar ist. - -\subsection{Schlüssel -\label{buch:subsection:schlüssel}} -Die von den Byte- und Blockoperationen mischen die einzelnen Bits -der Daten zwar ganz schön durcheinander, aber es wird noch kein -Schlüsselmaterial eingearbeitet, welches den Prozess einzigartig -macht. - -\subsubsection{Schlüsseladdition} -Nach jeder Spaltenmischoperation wird ein Rundenschlüssel -zum Blockhinzuaddiert. -Beim ersten Mal wird dazu einfach das Schlüsselmaterial verwendet. -Für die folgenden Runden muss aus diesem Schlüssel neues -Material, die sogenannten Rundenschlüssel, gewonnen werden. - -\subsubsection{Rundenschlüssel} -\begin{figure} -\centering -\includegraphics{chapters/90-crypto/images/keys.pdf} -\caption{Erzeugung der erweiterten Schlüsseldaten aus dem Schlüssel -$K_0,\dots,K_7$ für Schlüssellänge 256\,bit. -Die mit $S$ beschrifteten Blöcke wenden die $S$-Box auf jedes einzelne -Byte an. -$\pi$ ist die zyklische Vertauschung der Bytes eines Wortes. -Die Operation $r_i$ ist eine Addition einer Konstanten, die in jeder -Runde anders ist. -\label{buch:crypto:fig:keys}} -\end{figure} -Die Erzeugung der Rundenschlüssel ist in Abbildung -\ref{buch:crypto:fig:keys} -schematisch dargestellt. -Die Blöcke beschreiben wieder Spaltenvektoren im vierdimensionalen -Raum $\mathbb{F}_{2^8}^4$. -Die Blöcke $K_0$ bis $K_7$ stellen den ursprünglichen Schlüssel dar. -Die Erzeugung eines neuen Blocks Schlüsselmatrial beginnt damit, -dass der letzte Vektor des vorangegangenblocks drei Operationen -unterworfen werden. -\begin{itemize} -\item -Die Operation $\pi$ vertauscht die Bytes des Vektors zyklisch: -\begin{center} -\begin{tikzpicture}[>=latex,thick] -\def\s{0.6} -\begin{scope} -\draw (0,0) rectangle (\s,{4*\s}); -\foreach \y in {1,...,3}{ - \draw (0,{\y*\s}) (\s,{\y*\s}); -} -\node at ({0.5*\s},{0.5*\s}) {$b_3$}; -\node at ({0.5*\s},{1.5*\s}) {$b_2$}; -\node at ({0.5*\s},{2.5*\s}) {$b_1$}; -\node at ({0.5*\s},{3.5*\s}) {$b_0$}; -\end{scope} -\draw[->] ({1.1*\s},{2*\s}) -- ({4.9*\s},{2*\s}); -\node at ({3*\s},{2*\s}) [above] {$\pi$}; -\begin{scope}[xshift=3cm] -\draw (0,0) rectangle (\s,{4*\s}); -\foreach \y in {1,...,3}{ - \draw (0,{\y*\s}) (\s,{\y*\s}); -} -\node at ({0.5*\s},{0.5*\s}) {$b_0$}; -\node at ({0.5*\s},{1.5*\s}) {$b_3$}; -\node at ({0.5*\s},{2.5*\s}) {$b_2$}; -\node at ({0.5*\s},{3.5*\s}) {$b_1$}; -\end{scope} -\end{tikzpicture} -\end{center} -\item -Die $S$-Operation wendet die $S$-Box auf alle Bytes eines Vektors an. -\item -Die $r_i$ Operation addiert in Runde eine Konstante $r_i$ zur $0$-Komponente. -\end{itemize} -Die Konstante $r_i$ ist wieder ein einzelnes Byte und es ist daher -naheliegend, diese Bytes mit Hilfe der Arithmetik in $\mathbb{F}_{2^8}$ -zu erzeugen. -Man kann daher $r_i$ definieren als -$(\texttt{02}_{16})^{i-1}\in\mathbb{F}_{2^8}$. - -\subsection{Runden} -Der AES-Verschlüsselungsalgorithmus besteht jetzt darin, die bisher -definierten Operationen wiederholt anzuwenden. -Eine einzelne Runde besteht dabei aus folgenden Schritten: -\begin{enumerate} -\item Wende die $S$-Box auf alle Bytes des Blocks an. -\item Führe den Zeilenshift durch. -\item Mische die Spalten (wird in der letzten Runde) -\item Erzeuge den nächsten Rundenschlüssel -\item Addiere den Rundenschlüssel -\end{enumerate} -Der AES-Verschlüsselungsalgorithmus beginnt damit, dass der Schlüssel -zum Datenblock addiert wird. -Anschliessend werden je nach Blocklänge verschiedene Anzahlen von -Runden durchgeführt, 10 Runden für 128\,bit, 12 Runden für 192\,bit und -14 Runden für 256\,bit. - - - - - +%
+% aes.tex -- Beschreibung des AES Algorithmus
+%
+% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil
+%
+\section{Advanced Encryption Standard -- AES
+\label{buch:section:aes}}
+\rhead{Advanced Encryption Standard}
+Eine wichtige Forderung bei der Konzeption des damals neuen
+Advanced Encryption Standard war, dass darin keine ``willkürlich''
+erscheinenden Operationen geben darf, bei denen der Verdacht
+entstehen könnte, dass sich dahinter noch offengelegtes Wissen
+über einen möglichen Angriff auf den Verschlüsselungsalgorithmus
+verbergen könnte.
+Dies war eine Schwäche des vor AES üblichen DES Verschlüsselungsalgorithmus.
+In seiner Definition kommt eine Reihe von Konstanten vor, über deren
+Herkunft nichts bekannt war.
+Die Gerüchteküche wollte wissen, dass die NSA die Konstanten aus dem
+ursprünglichen Vorschlag abgeändert habe, und dass dies geschehen sei,
+um den Algorithmus durch die NSA angreifbar zu machen.
+
+Eine weiter Forderung war, dass die Sicherheit des neuen
+Verschlüsselungsstandards ``skalierbar'' sein soll, dass man also
+die Schlüssellänge mit der Zeit von 128~Bit auf 196 oder sogar 256~Bit
+steigern kann.
+Der Standard wird dadurch langlebiger und gleichzeitig entsteht die
+Möglichkeit, Sicherheit gegen Rechenleistung einzutauschen.
+Weniger leistungsfähige Systeme können den Algorithmus immer noch
+nutzen, entweder mit geringerer Verschlüsselungsrate oder geringerer
+Sicherheit.
+
+In diesem Abschnitt soll gezeigt werde, wie sich die AES
+spezifizierten Operationen als mit der Arithmetik der
+endlichen Körper beschreiben lassen.
+Im Abschnitt~\ref{buch:subsection:byte-operationen} werden
+Bytes als Elemente in einem endlichen Körper $\mathbb{F}_{2^8}$
+interpretiert.
+Damit kann dann die sogenannte $S$-Box konstruiert werden und
+es ist leicht zu verstehen, dass sie invertierbar ist.
+Aus den Byte-Operationen können dann Mischoperationen erzeugt
+werden, die Bytes untereinander verknüpfen, die aber auch wieder
+als Operationen in einem endlichen Körper verstanden werden können.
+
+\subsection{Byte-Operationen
+\label{buch:subsection:byte-operationen}}
+Moderne Prozessoren operieren auf Wörtern, die Vielfache von Bytes sind.
+Byte-Operationen sind besonders effizient in Hardware zu realisieren.
+AES verwendet daher als Grundelemente Operationen auf Bytes, die als
+Elemente eines endlichen Körpers $\mathbb{F}_{2^8}$ interpretiert werden.
+
+\subsubsection{Bytes als Elemente von $\mathbb{F}_{2^8}$}
+Das Polynom $m(X)=X^8+X^4+X^3+X+1\in \mathbb{F}_2[X]$ ist irreduzibel,
+somit ist $\mathbb{F}_{2^8} = \mathbb{F}_2[X]/(m)$ ein Körper.
+Die Elemente können dargestellt werden als Polynome, das Byte
+$\texttt{63}_{16}$ bekommt die Form
+\[
+p(X) = p_7X^7 + p_6X^6 + \dots + p_2X^2+p_1X + p_0,
+\]
+sie bestehen daher aus den $8$ Bits $p_7,\dots,p_0$.
+
+Die Interpretation der Bytes als Elemente eines Körpers bedeutet,
+dass jede Multiplikation mit einem nicht verschwindenden Byte
+invertierbar ist.
+Ausserdem mischen diese Operationen die einzelnen Bits auf einigermassen
+undurchsichtige, aber umkehrbare Art durcheinander, wie dies für ein
+Verschlüsselungsverfahren wünschenswert ist.
+
+\subsubsection{$S$-Box}
+Für die Operation der $S$-Box wird wie folgt zusammengesetzt.
+Zunächst wird ein Byte $x$ durch das zugehörige multiplikative
+inverse Element
+\[
+x\mapsto \bar{x} = \begin{cases}
+x^{-1}&\qquad \text{für $x\in \mathbb{F}_{2^8}^*$}\\
+0 &\qquad \text{für $x=0$}
+\end{cases}
+\]
+ersetzt.
+
+Im zweiten Schritt betrachten wir $\mathbb{F}_{2^8}$ als einen
+$8$-dimensionalen Vektorraum über $\mathbb{F}_2$.
+Einem Polynom $p(X)=p_7X^7 + \dots + p_1X+p_0$ wird der Spaltenvektor
+mit den Komponenten $p_0$ bis $p_7$ zugeordnet.
+
+\begin{figure}
+\centering
+\includegraphics[width=\textwidth]{chapters/90-crypto/images/sbox.pdf}
+\caption{Berechnung der Inversen der Matrix $A$ in der $S$-Box des
+AES-Algorithmus mit dem Gauss-Algorithmus
+\label{buch:crypto:fig:sbox}}
+\end{figure}
+
+Eine lineare Transformation in diesem Vektorraum kann durch eine
+$8\times 8$-Matrix in $M_8(\mathbb{F}_2)$ betrachtet werden.
+In der $S$-Box wird die Matrix
+\[
+A=
+\begin{pmatrix}
+1&0&0&0&1&1&1&1\\
+1&1&0&0&0&1&1&1\\
+1&1&1&0&0&0&1&1\\
+1&1&1&1&0&0&0&1\\
+1&1&1&1&1&0&0&0\\
+0&1&1&1&1&1&0&0\\
+0&0&1&1&1&1&1&0\\
+0&0&0&1&1&1&1&1
+\end{pmatrix},
+\qquad
+A^{-1}
+=
+\begin{pmatrix}
+0&0&1&0&0&1&0&1\\
+1&0&0&1&0&0&1&0\\
+0&1&0&0&1&0&0&1\\
+1&0&1&0&0&1&0&0\\
+0&1&0&1&0&0&1&0\\
+0&0&1&0&1&0&0&1\\
+1&0&0&1&0&1&0&0\\
+0&1&0&0&1&0&1&0
+\end{pmatrix}
+\]
+verwendet.
+Mit dem Gauss-Algorithmus, schematisch dargestellt in
+Abbildung~\ref{buch:crypto:fig:sbox}, kann man die Inverse
+bestimmen, die Multiplikation mit $A$ ist also eine invertierbare
+Abbildung.
+
+Der letzte Schritt ist dann wieder eine Addition von
+$q(X)=X^7+X^6+X+1\in \mathbb{F}_{2^8}$, durch Subtraktion
+von $q(X)$ invertiert werden kann.
+Die $S$-Box-Operation kann also bektoriell geschrieben werden also
+\[
+ S(x) = A\overline{x}+q.
+\]
+
+Die Implementation ist möglicherweise mit einer Tabelle am schnellsten,
+es sind ja nur 256 Bytes im Definitionsbereich der $S$-Box-Abbildung
+und ebenso nur 256 möglich Werte.
+
+\subsection{Block-Operationen
+\label{buch:subsection:block-operationen}}
+Die zu verschlüsselnden Daten werden in in Blöcke aufgeteilt, deren
+Länge Vielfache von $32$ bit sind.
+Die kleinste Blockgrösse ist 128\,Bit, die grösste ist 256\,Bit.
+Die Bytes eines Blockes werden dann in einem Rechteck angeordnet
+als
+\begin{equation}
+\begin{tabular}{|>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}|}
+\hline
+ b_{0} & b_{4} & b_{8} & b_{12} & b_{16} & b_{20} & b_{24} & b_{28} \\
+ b_{1} & b_{5} & b_{9} & b_{13} & b_{17} & b_{21} & b_{25} & b_{29} \\
+ b_{2} & b_{6} & b_{10} & b_{14} & b_{18} & b_{22} & b_{26} & b_{30} \\
+ b_{3} & b_{7} & b_{11} & b_{15} & b_{19} & b_{23} & b_{27} & b_{31} \\
+\hline
+\end{tabular}
+\label{buch:crypto:eqn:block}
+\end{equation}
+für eine Blocklänge von 256\,Bits.
+
+
+
+\subsubsection{Zeilenshift}
+\begin{figure}
+\centering
+\includegraphics[width=\textwidth]{chapters/90-crypto/images/shift.pdf}
+\caption{Zeilenshift in einem Block von 256 bits
+\label{buch:crypto:fig:shift}}
+\end{figure}
+Die Verschlüsselung muss sicherstellen, dass die Bytes des Blockes
+untereinander gut gemischt werden.
+Die bisher beschriebenen Operationen operieren immer nur auf einzelnen
+Bytes während
+die im nächsten Abschnitt beschriebene Spalten-Mischoperation
+nur auf Spalten wird.
+Die Zeilenmischoperation permutiert die Zeilen in den vier Zeilen
+eines Blocks zyklisch, die erste Zeile bleibt an Ort, die zweite
+Zeile wird um ein Byte rotiert, die dritte um zwei und die letzte
+um 3 Bytes, wie in Abbildung~\ref{buch:crypto:fig:zeilenshift}
+dargestellt.
+Diese Operation könnte mit einer Permutationsmatrix beschrieben werden,
+dies wäre jedoch keine effiziente Implementation.
+Der Zeilenschift hat ansonsten keine elegante algebraische Beschreibung.
+
+\subsubsection{Spalten mischen}
+Jede Spalte von \eqref{buch:crypto:eqn:block} kann als Vektor des
+vierdimensionalen Vektorraumes $\mathbb{F}_{2^8}^4$.
+Die Zeilenmischoperation wendet ein lineare Abbildung auf jeden
+Spaltenvektor von~\eqref{buch:crypto:eqn:block}.
+Die Koeffizienten der Matrix sind Elemente von $\mathbb{F}_{2^8}$.
+Die Matrix ist
+\[
+C=\begin{pmatrix}
+\texttt{02}_{16}&\texttt{03}_{16}&\texttt{01}_{16}&\texttt{01}_{16}\\
+\texttt{01}_{16}&\texttt{02}_{16}&\texttt{03}_{16}&\texttt{01}_{16}\\
+\texttt{01}_{16}&\texttt{01}_{16}&\texttt{02}_{16}&\texttt{03}_{16}\\
+\texttt{03}_{16}&\texttt{01}_{16}&\texttt{01}_{16}&\texttt{02}_{16}
+\end{pmatrix}.
+\]
+Um nachzuprüfen, dass die Matrix $C$ invertierbar ist, könnte man den
+Gauss-Algorithmus verwenden und damit die Inverse berechnen.
+Dazu müsste man die multiplikativen Inversen kennen, was etwas mühsam
+ist.
+Man kann aber aber auch die Determinante bestimmen, dazu braucht man
+nur multiplizieren zu können, was in diesem Fall sehr leicht möglich ist,
+weil kein Überlauf entsteht.
+Dabei hilft es zu beachten, dass die Multiplikation mit $\texttt{02}_{16}$
+nur eine Einbit-Shiftoperation nach links ist.
+Nur die Multiplikation $\texttt{03}_{16}\cdot\texttt{03}_{16}=\text{05}_{16}$
+gibt etwas mehr zu überlegen.
+Mit geeigneten Zeilen-Operationen kann man die Berechnung der Determinante
+von $C$ mit dem Entwicklungssatz etwas vereinfachen.
+Man erhält
+\begin{align*}
+\det(C)
+&=
+\left|
+\begin{matrix}
+\texttt{02}_{16}&\texttt{03}_{16}&\texttt{01}_{16}&\texttt{01}_{16}\\
+\texttt{01}_{16}&\texttt{02}_{16}&\texttt{03}_{16}&\texttt{01}_{16}\\
+\texttt{00}_{16}&\texttt{03}_{16}&\texttt{01}_{16}&\texttt{02}_{16}\\
+\texttt{00}_{16}&\texttt{00}_{16}&\texttt{03}_{16}&\texttt{02}_{16}
+\end{matrix}
+\right|
+\\
+&=
+\texttt{02}_{16}
+\left|
+\begin{matrix}
+\texttt{02}_{16}&\texttt{03}_{16}&\texttt{01}_{16}\\
+\texttt{03}_{16}&\texttt{01}_{16}&\texttt{02}_{16}\\
+\texttt{00}_{16}&\texttt{03}_{16}&\texttt{02}_{16}
+\end{matrix}
+\right|
++
+\texttt{01}_{16}
+\left|
+\begin{matrix}
+\texttt{03}_{16}&\texttt{01}_{16}&\texttt{01}_{16}\\
+\texttt{03}_{16}&\texttt{01}_{16}&\texttt{02}_{16}\\
+\texttt{00}_{16}&\texttt{03}_{16}&\texttt{02}_{16}
+\end{matrix}
+\right|
+\\
+&=
+\texttt{02}_{16}
+\left|
+\begin{matrix}
+\texttt{02}_{16}&\texttt{03}_{16}&\texttt{01}_{16}\\
+\texttt{01}_{16}&\texttt{02}_{16}&\texttt{03}_{16}\\
+\texttt{00}_{16}&\texttt{03}_{16}&\texttt{02}_{16}
+\end{matrix}
+\right|
++
+\texttt{01}_{16}
+\left|
+\begin{matrix}
+\texttt{03}_{16}&\texttt{01}_{16}&\texttt{01}_{16}\\
+\texttt{00}_{16}&\texttt{00}_{16}&\texttt{01}_{16}\\
+\texttt{00}_{16}&\texttt{03}_{16}&\texttt{02}_{16}
+\end{matrix}
+\right|
+\\
+&=
+\texttt{02}_{16}
+\left(
+\texttt{02}_{16}
+\left|
+\begin{matrix}
+\texttt{02}_{16}&\texttt{03}_{16}\\
+\texttt{03}_{16}&\texttt{02}_{16}
+\end{matrix}
+\right|
++
+\texttt{01}_{16}
+\left|
+\begin{matrix}
+\texttt{03}_{16}&\texttt{01}_{16}\\
+\texttt{03}_{16}&\texttt{02}_{16}
+\end{matrix}
+\right|
+\right)
++
+\texttt{01}_{16}
+\left|
+\begin{matrix}
+\texttt{03}_{16}&\texttt{01}_{16}&\texttt{01}_{16}\\
+\texttt{00}_{16}&\texttt{03}_{16}&\texttt{02}_{16}\\
+\texttt{00}_{16}&\texttt{00}_{16}&\texttt{01}_{16}
+\end{matrix}
+\right|
+\\
+&=
+\texttt{02}_{16}
+(
+\texttt{02}_{16}(\texttt{04}_{16}+\texttt{05}_{16})
++
+(\texttt{06}_{16}+\texttt{03}_{16})
+)
++
+\texttt{03}_{16}\texttt{03}_{16}
+\\
+&=
+\texttt{02}_{16}
+(
+\texttt{02}_{16}
++
+\texttt{05}_{16}
+)
++
+\texttt{05}_{16}
+=
+\texttt{0e}_{16}+\texttt{05}_{16}
+=
+\texttt{0a}_{16}
+\ne 0.
+\end{align*}
+Damit ist gezeigt, dass die Matrix $C$ invertierbar auf den
+Spaltenvektoren wirkt.
+Die Inverse der Matrix kann einmal berechnet und anschliessend
+für die Entschlüsselung verwendet werden.
+
+Alternativ kann man die Multiplikation mit der Matrix $C$ auch
+interpretieren als eine Polynommultiplikation.
+Dazu interpretiert man die Spalten des Blocks als Polynom vom Grad~3
+mit Koeffizienten in $\mathbb{F}_{2^8}$.
+Durch Reduktion mit dem irreduziblen Polynom
+$n(Z)=Z^4+1\in\mathbb{F}_{2^8}[X]$ entsteht aus dem Polynomring
+wieder ein Körper.
+Die Wirkung der Matrix $C$ ist dann nichts anderes als Multiplikation
+mit dem Polynom
+\[
+c(Z) = \texttt{03}_{16}Z^3 + Z^2+Z^1+\texttt{02}_{16},
+\]
+die natürlich ebenfalls umkehrbar ist.
+
+\subsection{Schlüssel
+\label{buch:subsection:schlüssel}}
+Die von den Byte- und Blockoperationen mischen die einzelnen Bits
+der Daten zwar ganz schön durcheinander, aber es wird noch kein
+Schlüsselmaterial eingearbeitet, welches den Prozess einzigartig
+macht.
+
+\subsubsection{Schlüsseladdition}
+Nach jeder Spaltenmischoperation wird ein Rundenschlüssel
+zum Blockhinzuaddiert.
+Beim ersten Mal wird dazu einfach das Schlüsselmaterial verwendet.
+Für die folgenden Runden muss aus diesem Schlüssel neues
+Material, die sogenannten Rundenschlüssel, gewonnen werden.
+
+\subsubsection{Rundenschlüssel}
+\begin{figure}
+\centering
+\includegraphics{chapters/90-crypto/images/keys.pdf}
+\caption{Erzeugung der erweiterten Schlüsseldaten aus dem Schlüssel
+$K_0,\dots,K_7$ für Schlüssellänge 256\,bit.
+Die mit $S$ beschrifteten Blöcke wenden die $S$-Box auf jedes einzelne
+Byte an.
+$\pi$ ist die zyklische Vertauschung der Bytes eines Wortes.
+Die Operation $r_i$ ist eine Addition einer Konstanten, die in jeder
+Runde anders ist.
+\label{buch:crypto:fig:keys}}
+\end{figure}
+Die Erzeugung der Rundenschlüssel ist in Abbildung
+\ref{buch:crypto:fig:keys}
+schematisch dargestellt.
+Die Blöcke beschreiben wieder Spaltenvektoren im vierdimensionalen
+Raum $\mathbb{F}_{2^8}^4$.
+Die Blöcke $K_0$ bis $K_7$ stellen den ursprünglichen Schlüssel dar.
+Die Erzeugung eines neuen Blocks Schlüsselmatrial beginnt damit,
+dass der letzte Vektor des vorangegangenblocks drei Operationen
+unterworfen werden.
+\begin{itemize}
+\item
+Die Operation $\pi$ vertauscht die Bytes des Vektors zyklisch:
+\begin{center}
+\begin{tikzpicture}[>=latex,thick]
+\def\s{0.6}
+\begin{scope}
+\draw (0,0) rectangle (\s,{4*\s});
+\foreach \y in {1,...,3}{
+ \draw (0,{\y*\s}) (\s,{\y*\s});
+}
+\node at ({0.5*\s},{0.5*\s}) {$b_3$};
+\node at ({0.5*\s},{1.5*\s}) {$b_2$};
+\node at ({0.5*\s},{2.5*\s}) {$b_1$};
+\node at ({0.5*\s},{3.5*\s}) {$b_0$};
+\end{scope}
+\draw[->] ({1.1*\s},{2*\s}) -- ({4.9*\s},{2*\s});
+\node at ({3*\s},{2*\s}) [above] {$\pi$};
+\begin{scope}[xshift=3cm]
+\draw (0,0) rectangle (\s,{4*\s});
+\foreach \y in {1,...,3}{
+ \draw (0,{\y*\s}) (\s,{\y*\s});
+}
+\node at ({0.5*\s},{0.5*\s}) {$b_0$};
+\node at ({0.5*\s},{1.5*\s}) {$b_3$};
+\node at ({0.5*\s},{2.5*\s}) {$b_2$};
+\node at ({0.5*\s},{3.5*\s}) {$b_1$};
+\end{scope}
+\end{tikzpicture}
+\end{center}
+\item
+Die $S$-Operation wendet die $S$-Box auf alle Bytes eines Vektors an.
+\item
+Die $r_i$ Operation addiert in Runde eine Konstante $r_i$ zur $0$-Komponente.
+\end{itemize}
+Die Konstante $r_i$ ist wieder ein einzelnes Byte und es ist daher
+naheliegend, diese Bytes mit Hilfe der Arithmetik in $\mathbb{F}_{2^8}$
+zu erzeugen.
+Man kann daher $r_i$ definieren als
+$(\texttt{02}_{16})^{i-1}\in\mathbb{F}_{2^8}$.
+
+\subsection{Runden}
+Der AES-Verschlüsselungsalgorithmus besteht jetzt darin, die bisher
+definierten Operationen wiederholt anzuwenden.
+Eine einzelne Runde besteht dabei aus folgenden Schritten:
+\begin{enumerate}
+\item Wende die $S$-Box auf alle Bytes des Blocks an.
+\item Führe den Zeilenshift durch.
+\item Mische die Spalten (wird in der letzten Runde)
+\item Erzeuge den nächsten Rundenschlüssel
+\item Addiere den Rundenschlüssel
+\end{enumerate}
+Der AES-Verschlüsselungsalgorithmus beginnt damit, dass der Schlüssel
+zum Datenblock addiert wird.
+Anschliessend werden je nach Blocklänge verschiedene Anzahlen von
+Runden durchgeführt, 10 Runden für 128\,bit, 12 Runden für 192\,bit und
+14 Runden für 256\,bit.
+
+
+
+
+
|