From 2db90bfe4b174570424c408f04000902411d8755 Mon Sep 17 00:00:00 2001 From: Joshua Baer Date: Mon, 12 Apr 2021 21:51:55 +0200 Subject: update to current state of book --- buch/chapters/90-crypto/aes.tex | 866 ++++++++++++++++++++-------------------- 1 file changed, 433 insertions(+), 433 deletions(-) (limited to 'buch/chapters/90-crypto/aes.tex') 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. + + + + + -- cgit v1.2.1