aboutsummaryrefslogtreecommitdiffstats
path: root/buch/chapters/90-crypto
diff options
context:
space:
mode:
Diffstat (limited to 'buch/chapters/90-crypto')
-rw-r--r--buch/chapters/90-crypto/aes.tex866
-rw-r--r--buch/chapters/90-crypto/arith.tex590
-rw-r--r--buch/chapters/90-crypto/chapter.tex62
-rw-r--r--buch/chapters/90-crypto/ff.tex1328
-rw-r--r--buch/chapters/90-crypto/images/Makefile58
-rw-r--r--buch/chapters/90-crypto/images/keys.tex242
-rw-r--r--buch/chapters/90-crypto/images/multiplikation.tex928
-rw-r--r--buch/chapters/90-crypto/images/sbox.m104
-rw-r--r--buch/chapters/90-crypto/images/sbox.tex482
-rw-r--r--buch/chapters/90-crypto/images/schieberegister.tex240
-rw-r--r--buch/chapters/90-crypto/images/shift.tex262
-rw-r--r--buch/chapters/90-crypto/uebungsaufgaben/9001.tex62
12 files changed, 2612 insertions, 2612 deletions
diff --git a/buch/chapters/90-crypto/aes.tex b/buch/chapters/90-crypto/aes.tex
index 168ff2c..acdda22 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.
+
+
+
+
+
diff --git a/buch/chapters/90-crypto/arith.tex b/buch/chapters/90-crypto/arith.tex
index 2520a69..dcc31b8 100644
--- a/buch/chapters/90-crypto/arith.tex
+++ b/buch/chapters/90-crypto/arith.tex
@@ -1,295 +1,295 @@
-%
-% arith.tex
-%
-% (c) 2021 Prof Dr Andreas Müller, Hochschule Rapperswil
-%
-\section{Arithmetik für die Kryptographie
-\label{buch:section:arithmetik-fuer-kryptographie}}
-\rhead{Arithmetik für die Kryptographie}
-Die Algorithmen der mathematischen Kryptographie basieren
-auf den Rechenoperationen in grossen, aber endlichen Körpern.
-Für die Division liefert der euklidische Algorithmus eine
-Methode, der in so vielen Schritten die Inverse findet,
-wie Dividend und Divisor Binärstellen haben.
-Dies ist weitgehend optimal.
-
-Die Division ist umkehrbar, in der Kryptographie strebt man aber an,
-Funktionen zu konstruieren, die nur mit grossem Aufwand umkehrbar sind.
-Eine solche Funktion ist das Potenzieren in einem endlichen Körper.
-Die Berechnung von Potenzen durch wiederholte Multiplikation ist jedoch
-prohibitiv aufwendig, daher ist ein schneller Potenzierungsalgorithmus
-nötig, der in Abschnitt~\ref{buch:subsection:potenzieren} beschrieben
-wird.
-Bei der Verschlüsselung grosser Datenmengen wie zum Beispiel bei
-der Verschlüsselung ganzer Harddisks mit Hilfe des AES-Algorithmus
-kommt es auf die Geschwindigkeit auch der elementarsten Operationen
-in den endlichen Körpern an.
-Solche Methoden werden in den Abschnitten
-\ref{buch:subsection:rechenoperationen-in-fp}
-und
-\ref{buch:subsection:rechenoperatione-in-f2l}
-besprochen.
-
-\subsection{Potenzieren
-\label{buch:subsection:potenzieren}}
-Wir gehen davon aus, dass wir einen schnellen Algorithmus zur
-Berechnung des Produktes zweier Elemente $a,b$ in einer
-beliebigen Gruppe $G$ haben.
-Die Gruppe $G$ kann die Multiplikation der ganzen oder reellen Zahlen
-sein, dies wird zum Beispiel in Implementation der Potenzfunktion
-verwendet.
-Für kryptographische Anwendungen ist $G$ die multiplikative Gruppe
-eines endlichen Körpers oder eine elliptische Kurve.
-
-Zur Berechnung von $a^k$ sind bei einer naiven Durchführung des
-Algorithmus $k-1$ Multiplikationen nötig, immer sofort gefolgt
-von einer Reduktion $\mod p$ um sicherzustellen, dass die Resultate
-nicht zu gross werden.
-Ist $l$ die Anzahl der Binärstellen von $k$, dann benötigt dieser
-naive Algorithmus $O(2^l)$ Multiplikationen, die Laufzeit wächst
-also exponentiell mit der Bitlänge von $k$ an.
-Der nachfolgend beschriebene Algorithmus reduziert die Laufzeit auf
-die $O(l)$.
-
-Zunächst schreiben wir den Exponenten $k$ in binärer Form als
-\[
-k = k_l2^l + k_{l-1}2^{l-1} + \dots k_22^2+k_12^1 k_02^0.
-\]
-Die Potenz $a^k$ kann dann geschrieben werden als
-\[
-a^k
-=
-a^{k_l2^l} \cdot a^{k_{l-1}2^{l-1}} \cdot \dots \cdot
-a^{k_22^2} \cdot a^{k_12^1} \cdot a^{k_02^0}
-\]
-Nur diejenigen Faktoren tragen etwas bei, für die $k_i\ne 0$ ist.
-Die Potenz kann man daher auch schreiben als
-\[
-a^k
-=
-\prod_{k_i\ne 0} a^{2^i}.
-\]
-Es sind also nur so viele Faktoren zu berücksichtigen, wie $k$
-Binärstellen $1$ hat.
-
-Die einzelnen Faktoren $a^{2^i}$ können durch wiederholtes Quadrieren
-erhalten werden:
-\[
-a^{2^i} = a^{2\cdot 2^{i-1}} = (a^{2^{i-1}})^2,
-\]
-also durch maximal $l-1$ Multiplikationen.
-Wenn $k$ keine Ganzzahl ist sondern binäre Nachkommastellen hat, also
-\[
-k=k_l2^l + \dots + k_12^1 + k_02^0 + k_{-1}2^{-1} + k_{-2}2^{-2}+\dots,
-\]
-dann können die Potenzen $a^{2^{-i}}$ durch wiederholtes Wurzelziehen
-\[
-a^{2^{-i}} = a^{\frac12\cdot 2^{-i+1}} = \sqrt{a^{2^{-i+1}}}
-\]
-gefunden werden.
-Die Berechnung der Quadratwurzel lässt sich in Hardware effizient
-implementieren.
-
-\begin{algorithmus}
-Der folgende Algorithmus berechnet $a^k$ in $O(\log_2(k))$
-Multiplikationen
-\begin{enumerate}
-\item Initialisiere $p=1$ und $q=a$
-\item Falls $k$ ungerade ist, setze $p:=p\cdot q$
-\item Setze $q:=q^2$ und $k := k/2$, wobei die ganzzahlige Division durch $2$
-am effizientesten als Rechtsshift implementiert werden kann.
-\item Falls $k>0$, fahre weiter bei 2.
-\end{enumerate}
-\end{algorithmus}
-
-\begin{beispiel}
-Die Berechnung von $1.1^{17}$ mit diesem Algorithmus ergibt
-\begin{enumerate}
-\item $p=1$, $q=1.1$
-\item $k$ ist ungerade: $p:=1.1$
-\item $q:=q^2=1.21$, $k := 8$
-\item $k$ ist gerade
-\item $q:=q^2=1.4641$, $k := 4$
-\item $k$ ist gerade
-\item $q:=q^2=2.14358881$, $k := 2$
-\item $k$ ist gerade
-\item $q:=q^2=4.5949729863572161$, $k := 1$
-\item $k$ ist ungerade: $p:=1.1\cdot p = 5.05447028499293771$
-\item $k:=0$
-\end{enumerate}
-Multiplikationen sind nur nötig in den Schritten 3, 5, 7, 9, 10, es
-werden also genau $5$ Multiplikationen ausgeführt.
-\end{beispiel}
-
-\subsection{Rechenoperationen in $\mathbb{F}_p$
-\label{buch:subsection:rechenoperationen-in-fp}}
-Die Multiplikation macht aus zwei Faktoren $a$ und $b$ ein
-Resultat mit Bitlänge $\log_2 a+\log_2 b$, die Bitlänge wird
-also typischerweise verdoppelt.
-In $\mathbb{F}_p$ muss anschliessend das Resultat $\mod p$
-reduziert werden, so dass die Bitlänge wieder höchstens
-$\log_2p$ ist.
-In folgenden soll gezeigt werden, dass dieser Speicheraufwand
-für eine Binärimplementation deutlich reduziert werden kann,
-wenn die Reihenfolge der Operationen modifiziert wird.
-
-Für die Multiplikation von $41\cdot 47$ rechnet man im Binärsystem
-\begin{center}
-\begin{tabular}{>{$}r<{$}}
-\texttt{{\color{darkgreen}1}0{\color{red}1}001}\cdot\texttt{101111}\\
-\hline
-\texttt{101111}\\
-\texttt{{\color{red}101111}\phantom{000}}\\
-\texttt{{\color{darkgreen}101111}\phantom{00000}}\\
-\hline
-\texttt{11110000111}\\
-\hline
-\end{tabular}
-\end{center}
-In $\mathbb{F}_{53}$ muss im Anschluss Modulo $p=53$ reduziert werden.
-
-Der Speicheraufwand entsteht zunächst dadurch, dass durch die Multiplikation
-mit $2$ die Summanden immer länger werden.
-Man kann den die Sumanden kurz halten, indem man jedesmal, wenn
-der Summand nach der Multiplikation mit $2$ grösser als $p$ geworden ist,
-$p$ subtrahiert (Abbildung~\ref{buch:crypto:fig:reduktion}).
-Ebenso kann bei nach jeder Addition das bereits reduzierten zweiten
-Faktors wieder reduziert werden.
-Die Anzahl der nötigen Reduktionsoperationen wird durch diese
-frühzeitig durchgeführten Reduktionen nicht teurer als bei der Durchführung
-des Divisionsalgorithmus.
-
-\begin{figure}
-\begin{center}
-\begin{tabular}{>{$}r<{$}>{$}r<{$}>{$}r<{$}|>{$}r<{$}>{$}r<{$}>{$}r<{$}}
-\text{Multiplikation mit $2$}&\text{Reduktion?}&\text{reduziert}
- &\text{Summanden}&\text{Summe}&\text{reduziert}
-\\
-\hline
-\texttt{101111} & &\texttt{101111}
- &\texttt{101111}&\texttt{101111}&\texttt{101111}
-\\
-\texttt{101111\phantom{0}} &\texttt{{\color{red}1011110}}&\texttt{101001}
- & & &
-\\
-\texttt{101111\phantom{00}} &\texttt{0{\color{red}111010}}&\texttt{011101}
- & & &
-\\
-\texttt{101111\phantom{000}} &\texttt{0001010}&\texttt{000101}
- &\texttt{000101}&\texttt{110100}&\texttt{110100}
-\\
-\texttt{101111\phantom{0000}} &\texttt{0010100}&\texttt{001010}
- & & &
-\\
-\texttt{101111\phantom{00000}}&\texttt{0101000}&\texttt{010100}
- &\texttt{010100}&\texttt{{\color{red}1001000}}&\texttt{10011}\rlap{$\mathstrut=19$}
-\end{tabular}
-\end{center}
-\caption{Multiplikation von $41=\texttt{101001}_2$ mit $47=\texttt{101111}_2$,
-Reduktion nach jeder Multiplikation mit $2$: falls das Resultat
-$>p$ ist, wie in den rot markierten Zeilen $p=53=\texttt{110101}_2$
-durchgeführt.
-Bei der Bildung der Summe wird ebenfalls in jedem Schritt falls nötig
-reduziert, angezeigt durch die roten Zahlen in der zweitletzten
-Spalte.
-Die Anzahl der Subtraktionen, die für die Reduktionen nötig sind, ist
-von der selben Grössenordnung wie bei der Durchführung des
-Divisionsalgorithmus.
-\label{buch:crypto:fig:reduktion}}
-\end{figure}
-
-Es ist also möglich, mit gleichem Aufwand an Operationen
-aber mit halbe Speicherplatzbedarf die Multiplikationen in $\mathbb{F}_p$
-durchzuführen.
-Die Platzeinsparung ist besonders bei Implementationen in Hardware
-hilfreich, wo on-die Speicherplatz teuer sein kann.
-
-\subsection{Rechenoperationen in $\mathbb{F}_{2^l}$
-\label{buch:subsection:rechenoperatione-in-f2l}}
-Von besonderem praktischem Interesse sind die endlichen Körper
-$\mathbb{F}_{2^l}$.
-Die arithmetischen Operationen in diesen Körpern lassen sich besonders
-effizient in Hardware realisieren.
-
-\subsubsection{Zahldarstellung}
-Ein endlicher Körper $\mathbb{F}_{2^l}$ ist definiert durch ein
-irreduzibles Polynom in $\mathbb{F}_2[X]$ vom Grad $2^l$
-\[
-m(X)
-=
-X^l + m_{l-1}X^{l-1} + m_{l-2}X^{l-2} + \dots + m_2X^2 + m_1X + m_0
-\]
-gegeben.
-Ein Element in $\mathbb{F}_2[X]/(m)$ kann dargestellt werden durch ein
-Polynom vom Grad $l-1$, also durch
-\[
-a = a_{l-1}X^{l-1} + a_{l-2}X^{l-2} +\dots + a_2X^2 + a_1X + a_0.
-\]
-In einer Maschine kann eine Zahl also als eine Bitfolge der Länge $l$
-dargestellt werden.
-
-\subsubsection{Addition}
-Die Addition in $\mathbb{F}_2$ ist in Hardware besonders leicht zu
-realisieren.
-Die Addition ist die XOR-Operation, die Multiplikation ist die UND-Verknüfung.
-Ausserdem stimmen in $\mathbb{F}_2$ Addition und Subtraktion überein.
-
-Die Addition zweier Polynome erfolgt komponentenweise.
-Die Addition von zwei Elemente von $\mathbb{F}_{2^l}$ kann also
-durch die bitweise XOR-Verknüpfung der Darstellungen der Summanden
-erfolgen.
-Diese Operation ist in einem einzigen Maschinenzyklus realisierbar.
-Die Subtraktion, die für die Reduktionsoperation module $m(X)$ nötig
-ist, ist mit der Addition identisch.
-
-\subsubsection{Multiplikation}
-Die Multiplikation zweier Polynome benötigt zunächst die Multiplikation
-mit $X$, wodurch der Grad des Polynoms ansteigt und möglicherweise so
-gross wird, dass eine Reduktionsoperation modulo $m(X)$ nötig wird.
-Die Reduktion wird immer dann nötig, wenn der Koeffizient von $X^l$
-nicht $0$ ist.
-Der Koeffizient kann dann zum Verschwinden gebracht werden, indem
-$m(X)$ addiert wird.
-
-\begin{figure}
-\centering
-\includegraphics{chapters/90-crypto/images/schieberegister.pdf}
-\caption{Implementation der Multiplikation mit $X$ in einem
-endlichen Körper $\mathbb{F}_{2^l}$ mit dem Minimalpolynom
-$m(X) = X^8+X^4+X^3+X^+1$ als Feedback-Schieberegister.
-\label{buch:crypto:fig:schieberegister}}
-\end{figure}
-
-In Abbildung~\ref{buch:crypto:fig:schieberegister} wird gezeigt,
-wie die Reduktion erfolgt, wenn die Multiplikation mit $X$, also der
-Shift nach links, einen Überlauf ergibt.
-Das Minimalpolynom $m(X)=X^8+X^4+X^3+X+1$ bedeutet, dass in $\mathbb{F}_{2^l}$
-$X^8=X^4+X^3+X+1$ gilt, so dass man das Überlaufbit durch
-$X^4+X^3+X+1$ ersetzen und addieren kann.
-
-Ein Produktes $p(X)\cdot q(X)$, wobei $p(X)$ und
-$q(X)$ Repräsentaten von Elementen $\mathbb{F}_{2^l}$ sind, kann jetzt
-wie folgt berechnet werden.
-Mit dem Schieberegister werden die Vielfachen $X^k\cdot p(X)$
-für $k=0,\dots,l-1$ berechnet.
-Diejenigen Vielfachen, für die der Koeffizient von $X^k$ in $q(X)$
-von $0$ verschieden ist werden aufsummiert und ergeben das Produkt.
-Der Prozess in Abbildung~\ref{buch:crypto:fig:multiplikation}
-dargestellt.
-
-\begin{figure}
-\centering
-\includegraphics[width=\textwidth]{chapters/90-crypto/images/multiplikation.pdf}
-\caption{Multiplikation zweier Elemente von $\mathbb{F}_{2^l}$.
-Mit Hilfe des Schieberegisters am linken Rand werden die Produkte
-$X\cdot p(X)$, $X^2\cdot p(X),\dots,X^7\cdot p(X)$ nach der in
-Abbildung~\ref{buch:crypto:fig:schieberegister} dargestellten
-Methode berechnet.
-Am rechten Rand werden diejenigen $X^k\cdot p(X)$ aufaddiert,
-für die der $X^k$-Koeffizient von $q(X)$ von $0$ verschieden ist.
-\label{buch:crypto:fig:multiplikation}}
-\end{figure}
-
-
-% XXX Beispiel F einer Oakley-Gruppe
-
+%
+% arith.tex
+%
+% (c) 2021 Prof Dr Andreas Müller, Hochschule Rapperswil
+%
+\section{Arithmetik für die Kryptographie
+\label{buch:section:arithmetik-fuer-kryptographie}}
+\rhead{Arithmetik für die Kryptographie}
+Die Algorithmen der mathematischen Kryptographie basieren
+auf den Rechenoperationen in grossen, aber endlichen Körpern.
+Für die Division liefert der euklidische Algorithmus eine
+Methode, der in so vielen Schritten die Inverse findet,
+wie Dividend und Divisor Binärstellen haben.
+Dies ist weitgehend optimal.
+
+Die Division ist umkehrbar, in der Kryptographie strebt man aber an,
+Funktionen zu konstruieren, die nur mit grossem Aufwand umkehrbar sind.
+Eine solche Funktion ist das Potenzieren in einem endlichen Körper.
+Die Berechnung von Potenzen durch wiederholte Multiplikation ist jedoch
+prohibitiv aufwendig, daher ist ein schneller Potenzierungsalgorithmus
+nötig, der in Abschnitt~\ref{buch:subsection:potenzieren} beschrieben
+wird.
+Bei der Verschlüsselung grosser Datenmengen wie zum Beispiel bei
+der Verschlüsselung ganzer Harddisks mit Hilfe des AES-Algorithmus
+kommt es auf die Geschwindigkeit auch der elementarsten Operationen
+in den endlichen Körpern an.
+Solche Methoden werden in den Abschnitten
+\ref{buch:subsection:rechenoperationen-in-fp}
+und
+\ref{buch:subsection:rechenoperatione-in-f2l}
+besprochen.
+
+\subsection{Potenzieren
+\label{buch:subsection:potenzieren}}
+Wir gehen davon aus, dass wir einen schnellen Algorithmus zur
+Berechnung des Produktes zweier Elemente $a,b$ in einer
+beliebigen Gruppe $G$ haben.
+Die Gruppe $G$ kann die Multiplikation der ganzen oder reellen Zahlen
+sein, dies wird zum Beispiel in Implementation der Potenzfunktion
+verwendet.
+Für kryptographische Anwendungen ist $G$ die multiplikative Gruppe
+eines endlichen Körpers oder eine elliptische Kurve.
+
+Zur Berechnung von $a^k$ sind bei einer naiven Durchführung des
+Algorithmus $k-1$ Multiplikationen nötig, immer sofort gefolgt
+von einer Reduktion $\mod p$ um sicherzustellen, dass die Resultate
+nicht zu gross werden.
+Ist $l$ die Anzahl der Binärstellen von $k$, dann benötigt dieser
+naive Algorithmus $O(2^l)$ Multiplikationen, die Laufzeit wächst
+also exponentiell mit der Bitlänge von $k$ an.
+Der nachfolgend beschriebene Algorithmus reduziert die Laufzeit auf
+die $O(l)$.
+
+Zunächst schreiben wir den Exponenten $k$ in binärer Form als
+\[
+k = k_l2^l + k_{l-1}2^{l-1} + \dots k_22^2+k_12^1 k_02^0.
+\]
+Die Potenz $a^k$ kann dann geschrieben werden als
+\[
+a^k
+=
+a^{k_l2^l} \cdot a^{k_{l-1}2^{l-1}} \cdot \dots \cdot
+a^{k_22^2} \cdot a^{k_12^1} \cdot a^{k_02^0}
+\]
+Nur diejenigen Faktoren tragen etwas bei, für die $k_i\ne 0$ ist.
+Die Potenz kann man daher auch schreiben als
+\[
+a^k
+=
+\prod_{k_i\ne 0} a^{2^i}.
+\]
+Es sind also nur so viele Faktoren zu berücksichtigen, wie $k$
+Binärstellen $1$ hat.
+
+Die einzelnen Faktoren $a^{2^i}$ können durch wiederholtes Quadrieren
+erhalten werden:
+\[
+a^{2^i} = a^{2\cdot 2^{i-1}} = (a^{2^{i-1}})^2,
+\]
+also durch maximal $l-1$ Multiplikationen.
+Wenn $k$ keine Ganzzahl ist sondern binäre Nachkommastellen hat, also
+\[
+k=k_l2^l + \dots + k_12^1 + k_02^0 + k_{-1}2^{-1} + k_{-2}2^{-2}+\dots,
+\]
+dann können die Potenzen $a^{2^{-i}}$ durch wiederholtes Wurzelziehen
+\[
+a^{2^{-i}} = a^{\frac12\cdot 2^{-i+1}} = \sqrt{a^{2^{-i+1}}}
+\]
+gefunden werden.
+Die Berechnung der Quadratwurzel lässt sich in Hardware effizient
+implementieren.
+
+\begin{algorithmus}
+Der folgende Algorithmus berechnet $a^k$ in $O(\log_2(k))$
+Multiplikationen
+\begin{enumerate}
+\item Initialisiere $p=1$ und $q=a$
+\item Falls $k$ ungerade ist, setze $p:=p\cdot q$
+\item Setze $q:=q^2$ und $k := k/2$, wobei die ganzzahlige Division durch $2$
+am effizientesten als Rechtsshift implementiert werden kann.
+\item Falls $k>0$, fahre weiter bei 2.
+\end{enumerate}
+\end{algorithmus}
+
+\begin{beispiel}
+Die Berechnung von $1.1^{17}$ mit diesem Algorithmus ergibt
+\begin{enumerate}
+\item $p=1$, $q=1.1$
+\item $k$ ist ungerade: $p:=1.1$
+\item $q:=q^2=1.21$, $k := 8$
+\item $k$ ist gerade
+\item $q:=q^2=1.4641$, $k := 4$
+\item $k$ ist gerade
+\item $q:=q^2=2.14358881$, $k := 2$
+\item $k$ ist gerade
+\item $q:=q^2=4.5949729863572161$, $k := 1$
+\item $k$ ist ungerade: $p:=1.1\cdot p = 5.05447028499293771$
+\item $k:=0$
+\end{enumerate}
+Multiplikationen sind nur nötig in den Schritten 3, 5, 7, 9, 10, es
+werden also genau $5$ Multiplikationen ausgeführt.
+\end{beispiel}
+
+\subsection{Rechenoperationen in $\mathbb{F}_p$
+\label{buch:subsection:rechenoperationen-in-fp}}
+Die Multiplikation macht aus zwei Faktoren $a$ und $b$ ein
+Resultat mit Bitlänge $\log_2 a+\log_2 b$, die Bitlänge wird
+also typischerweise verdoppelt.
+In $\mathbb{F}_p$ muss anschliessend das Resultat $\mod p$
+reduziert werden, so dass die Bitlänge wieder höchstens
+$\log_2p$ ist.
+In folgenden soll gezeigt werden, dass dieser Speicheraufwand
+für eine Binärimplementation deutlich reduziert werden kann,
+wenn die Reihenfolge der Operationen modifiziert wird.
+
+Für die Multiplikation von $41\cdot 47$ rechnet man im Binärsystem
+\begin{center}
+\begin{tabular}{>{$}r<{$}}
+\texttt{{\color{darkgreen}1}0{\color{red}1}001}\cdot\texttt{101111}\\
+\hline
+\texttt{101111}\\
+\texttt{{\color{red}101111}\phantom{000}}\\
+\texttt{{\color{darkgreen}101111}\phantom{00000}}\\
+\hline
+\texttt{11110000111}\\
+\hline
+\end{tabular}
+\end{center}
+In $\mathbb{F}_{53}$ muss im Anschluss Modulo $p=53$ reduziert werden.
+
+Der Speicheraufwand entsteht zunächst dadurch, dass durch die Multiplikation
+mit $2$ die Summanden immer länger werden.
+Man kann den die Sumanden kurz halten, indem man jedesmal, wenn
+der Summand nach der Multiplikation mit $2$ grösser als $p$ geworden ist,
+$p$ subtrahiert (Abbildung~\ref{buch:crypto:fig:reduktion}).
+Ebenso kann bei nach jeder Addition das bereits reduzierten zweiten
+Faktors wieder reduziert werden.
+Die Anzahl der nötigen Reduktionsoperationen wird durch diese
+frühzeitig durchgeführten Reduktionen nicht teurer als bei der Durchführung
+des Divisionsalgorithmus.
+
+\begin{figure}
+\begin{center}
+\begin{tabular}{>{$}r<{$}>{$}r<{$}>{$}r<{$}|>{$}r<{$}>{$}r<{$}>{$}r<{$}}
+\text{Multiplikation mit $2$}&\text{Reduktion?}&\text{reduziert}
+ &\text{Summanden}&\text{Summe}&\text{reduziert}
+\\
+\hline
+\texttt{101111} & &\texttt{101111}
+ &\texttt{101111}&\texttt{101111}&\texttt{101111}
+\\
+\texttt{101111\phantom{0}} &\texttt{{\color{red}1011110}}&\texttt{101001}
+ & & &
+\\
+\texttt{101111\phantom{00}} &\texttt{0{\color{red}111010}}&\texttt{011101}
+ & & &
+\\
+\texttt{101111\phantom{000}} &\texttt{0001010}&\texttt{000101}
+ &\texttt{000101}&\texttt{110100}&\texttt{110100}
+\\
+\texttt{101111\phantom{0000}} &\texttt{0010100}&\texttt{001010}
+ & & &
+\\
+\texttt{101111\phantom{00000}}&\texttt{0101000}&\texttt{010100}
+ &\texttt{010100}&\texttt{{\color{red}1001000}}&\texttt{10011}\rlap{$\mathstrut=19$}
+\end{tabular}
+\end{center}
+\caption{Multiplikation von $41=\texttt{101001}_2$ mit $47=\texttt{101111}_2$,
+Reduktion nach jeder Multiplikation mit $2$: falls das Resultat
+$>p$ ist, wie in den rot markierten Zeilen $p=53=\texttt{110101}_2$
+durchgeführt.
+Bei der Bildung der Summe wird ebenfalls in jedem Schritt falls nötig
+reduziert, angezeigt durch die roten Zahlen in der zweitletzten
+Spalte.
+Die Anzahl der Subtraktionen, die für die Reduktionen nötig sind, ist
+von der selben Grössenordnung wie bei der Durchführung des
+Divisionsalgorithmus.
+\label{buch:crypto:fig:reduktion}}
+\end{figure}
+
+Es ist also möglich, mit gleichem Aufwand an Operationen
+aber mit halbe Speicherplatzbedarf die Multiplikationen in $\mathbb{F}_p$
+durchzuführen.
+Die Platzeinsparung ist besonders bei Implementationen in Hardware
+hilfreich, wo on-die Speicherplatz teuer sein kann.
+
+\subsection{Rechenoperationen in $\mathbb{F}_{2^l}$
+\label{buch:subsection:rechenoperatione-in-f2l}}
+Von besonderem praktischem Interesse sind die endlichen Körper
+$\mathbb{F}_{2^l}$.
+Die arithmetischen Operationen in diesen Körpern lassen sich besonders
+effizient in Hardware realisieren.
+
+\subsubsection{Zahldarstellung}
+Ein endlicher Körper $\mathbb{F}_{2^l}$ ist definiert durch ein
+irreduzibles Polynom in $\mathbb{F}_2[X]$ vom Grad $2^l$
+\[
+m(X)
+=
+X^l + m_{l-1}X^{l-1} + m_{l-2}X^{l-2} + \dots + m_2X^2 + m_1X + m_0
+\]
+gegeben.
+Ein Element in $\mathbb{F}_2[X]/(m)$ kann dargestellt werden durch ein
+Polynom vom Grad $l-1$, also durch
+\[
+a = a_{l-1}X^{l-1} + a_{l-2}X^{l-2} +\dots + a_2X^2 + a_1X + a_0.
+\]
+In einer Maschine kann eine Zahl also als eine Bitfolge der Länge $l$
+dargestellt werden.
+
+\subsubsection{Addition}
+Die Addition in $\mathbb{F}_2$ ist in Hardware besonders leicht zu
+realisieren.
+Die Addition ist die XOR-Operation, die Multiplikation ist die UND-Verknüfung.
+Ausserdem stimmen in $\mathbb{F}_2$ Addition und Subtraktion überein.
+
+Die Addition zweier Polynome erfolgt komponentenweise.
+Die Addition von zwei Elemente von $\mathbb{F}_{2^l}$ kann also
+durch die bitweise XOR-Verknüpfung der Darstellungen der Summanden
+erfolgen.
+Diese Operation ist in einem einzigen Maschinenzyklus realisierbar.
+Die Subtraktion, die für die Reduktionsoperation module $m(X)$ nötig
+ist, ist mit der Addition identisch.
+
+\subsubsection{Multiplikation}
+Die Multiplikation zweier Polynome benötigt zunächst die Multiplikation
+mit $X$, wodurch der Grad des Polynoms ansteigt und möglicherweise so
+gross wird, dass eine Reduktionsoperation modulo $m(X)$ nötig wird.
+Die Reduktion wird immer dann nötig, wenn der Koeffizient von $X^l$
+nicht $0$ ist.
+Der Koeffizient kann dann zum Verschwinden gebracht werden, indem
+$m(X)$ addiert wird.
+
+\begin{figure}
+\centering
+\includegraphics{chapters/90-crypto/images/schieberegister.pdf}
+\caption{Implementation der Multiplikation mit $X$ in einem
+endlichen Körper $\mathbb{F}_{2^l}$ mit dem Minimalpolynom
+$m(X) = X^8+X^4+X^3+X^+1$ als Feedback-Schieberegister.
+\label{buch:crypto:fig:schieberegister}}
+\end{figure}
+
+In Abbildung~\ref{buch:crypto:fig:schieberegister} wird gezeigt,
+wie die Reduktion erfolgt, wenn die Multiplikation mit $X$, also der
+Shift nach links, einen Überlauf ergibt.
+Das Minimalpolynom $m(X)=X^8+X^4+X^3+X+1$ bedeutet, dass in $\mathbb{F}_{2^l}$
+$X^8=X^4+X^3+X+1$ gilt, so dass man das Überlaufbit durch
+$X^4+X^3+X+1$ ersetzen und addieren kann.
+
+Ein Produktes $p(X)\cdot q(X)$, wobei $p(X)$ und
+$q(X)$ Repräsentaten von Elementen $\mathbb{F}_{2^l}$ sind, kann jetzt
+wie folgt berechnet werden.
+Mit dem Schieberegister werden die Vielfachen $X^k\cdot p(X)$
+für $k=0,\dots,l-1$ berechnet.
+Diejenigen Vielfachen, für die der Koeffizient von $X^k$ in $q(X)$
+von $0$ verschieden ist werden aufsummiert und ergeben das Produkt.
+Der Prozess in Abbildung~\ref{buch:crypto:fig:multiplikation}
+dargestellt.
+
+\begin{figure}
+\centering
+\includegraphics[width=\textwidth]{chapters/90-crypto/images/multiplikation.pdf}
+\caption{Multiplikation zweier Elemente von $\mathbb{F}_{2^l}$.
+Mit Hilfe des Schieberegisters am linken Rand werden die Produkte
+$X\cdot p(X)$, $X^2\cdot p(X),\dots,X^7\cdot p(X)$ nach der in
+Abbildung~\ref{buch:crypto:fig:schieberegister} dargestellten
+Methode berechnet.
+Am rechten Rand werden diejenigen $X^k\cdot p(X)$ aufaddiert,
+für die der $X^k$-Koeffizient von $q(X)$ von $0$ verschieden ist.
+\label{buch:crypto:fig:multiplikation}}
+\end{figure}
+
+
+% XXX Beispiel F einer Oakley-Gruppe
+
diff --git a/buch/chapters/90-crypto/chapter.tex b/buch/chapters/90-crypto/chapter.tex
index 920941d..d2fcbbf 100644
--- a/buch/chapters/90-crypto/chapter.tex
+++ b/buch/chapters/90-crypto/chapter.tex
@@ -1,31 +1,31 @@
-%
-% chapter.tex -- Anwendungen von Matrizen in der Codierungstheorie und
-% Kryptographie
-%
-% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil
-%
-% !TeX spellcheck = de_CH
-\chapter{Anwendungen in Kryptographie und Codierungstheorie
-\label{buch:chapter:kryptographie}}
-\lhead{Kryptographie und Codierungstheorie}
-\rhead{}
-Die algebraische Theorie der endlichen Körper hat sich als besonders
-nützliche herausgestellt in der Krypographie.
-Die Eigenschaften dieser Körper sind reichhaltig genug, um
-kryptographsch widerstandsfähige Algorithmen zu liefern, die
-auch in ihrer Stärke beliebig skaliert werden können.
-Gleichzeitig liefert die Algebra auch eine effiziente Implementierung.
-In diesem Abschnitt soll dies an einigen Beispielen gezeigt werden.
-
-\input{chapters/90-crypto/arith.tex}
-\input{chapters/90-crypto/ff.tex}
-\input{chapters/90-crypto/aes.tex}
-%\input{chapters/90-crypto/rs.tex}
-
-\section*{Übungsaufgaben}
-\rhead{Übungsaufgaben}
-\aufgabetoplevel{chapters/90-crypto/uebungsaufgaben}
-\begin{uebungsaufgaben}
-\uebungsaufgabe{9001}
-\end{uebungsaufgaben}
-
+%
+% chapter.tex -- Anwendungen von Matrizen in der Codierungstheorie und
+% Kryptographie
+%
+% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil
+%
+% !TeX spellcheck = de_CH
+\chapter{Anwendungen in Kryptographie und Codierungstheorie
+\label{buch:chapter:kryptographie}}
+\lhead{Kryptographie und Codierungstheorie}
+\rhead{}
+Die algebraische Theorie der endlichen Körper hat sich als besonders
+nützliche herausgestellt in der Krypographie.
+Die Eigenschaften dieser Körper sind reichhaltig genug, um
+kryptographsch widerstandsfähige Algorithmen zu liefern, die
+auch in ihrer Stärke beliebig skaliert werden können.
+Gleichzeitig liefert die Algebra auch eine effiziente Implementierung.
+In diesem Abschnitt soll dies an einigen Beispielen gezeigt werden.
+
+\input{chapters/90-crypto/arith.tex}
+\input{chapters/90-crypto/ff.tex}
+\input{chapters/90-crypto/aes.tex}
+%\input{chapters/90-crypto/rs.tex}
+
+\section*{Übungsaufgaben}
+\rhead{Übungsaufgaben}
+\aufgabetoplevel{chapters/90-crypto/uebungsaufgaben}
+\begin{uebungsaufgaben}
+\uebungsaufgabe{9001}
+\end{uebungsaufgaben}
+
diff --git a/buch/chapters/90-crypto/ff.tex b/buch/chapters/90-crypto/ff.tex
index 8a38f93..535b359 100644
--- a/buch/chapters/90-crypto/ff.tex
+++ b/buch/chapters/90-crypto/ff.tex
@@ -1,664 +1,664 @@
-%
-% ff.tex -- Kryptographie und endliche Körper
-%
-% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil
-%
-
-\section{Kryptographie und endliche Körper
-\label{buch:section:kryptographie-und-endliche-koerper}}
-\rhead{Kryptographie und endliche Körper}
-
-\subsection{Potenzen in $\mathbb{F}_p$ und diskreter Logarithmus
-\label{buch:subsection:potenzen-diskreter-logarithmus}}
-Für kryptographische Anwendungen wird eine einfach zu berechnende
-Funktion benötigt,
-die ohne zusätzliches Wissen, üblicherweise der Schlüssel genannt,
-nicht ohne weiteres umkehrbar ist.
-Die arithmetischen Operationen in einem endlichen Körper sind
-mit geringem Aufwand durchführbar.
-Für die ``schwierigste'' Operation, die Division, steht der
-euklidische Algorithmus zur Verfügung.
-
-Die nächstschwierigere Operation ist die Potenzfunktion.
-Für $g\in \Bbbk$ und $a\in\mathbb{N}$ ist die Potenz $g^a\in\Bbbk$
-natürlich durch die wiederholte Multiplikation definiert.
-In der Praxis werden aber $g$ und $a$ Zahlen mit vielen Binärstellen
-sein, die die wiederholte Multiplikation ist daher sicher nicht
-effizient, das Kriterium der einfachen Berechenbarkeit scheint
-also nicht erfüllt.
-Der folgende Algorithmus berechnet die Potenz in $O(\log_2 a)$
-Multiplikationen.
-
-\begin{algorithmus}[Divide-and-conquer]
-\label{buch:crypto:algo:divide-and-conquer}
-Sei $a=a_0 + a_12^1 + a_22^2 + \dots + a_k2^k$ die Binärdarstellung
-der Zahl $a$.
-\begin{enumerate}
-\item setze $f=g$, $x=1$, $i=0$
-\label{divide-and-conquer-1}
-\item solange $i\ge k$ ist, führe aus
-\label{divide-and-conquer-2}
-\begin{enumerate}
-\item
-\label{divide-and-conquer-3}
-falls $a_i=1$ setze $x \coloneqq x \cdot f$
-\item
-\label{divide-and-conquer-4}
-$i \coloneqq i+1$ und $f\coloneqq f\cdot f$
-\end{enumerate}
-\end{enumerate}
-Die Potenz $x=g^a$ kann so in $O(\log_2a)$ Multiplikationen
-berechnet werden.
-\end{algorithmus}
-
-\begin{proof}[Beweis]
-Die Initalisierung in Schritt~\ref{divide-and-conquer-1} stellt sicher,
-dass $x$ den Wert $g^0$ hat.
-Schritt~\ref{divide-and-conquer-4} stellt sicher,
-dass die Variable $f$ immer den Wert $g^{2^i}$ hat.
-Im Schritt~\ref{divide-and-conquer-3} wird zu $x$ die Potenz
-$g^{a_i2^i}$ hinzumultipliziert.
-Am Ende des Algorithmus hat daher $x$ den Wert
-\[
-x = g^{a_02^0} \cdot g^{a_12^1} \cdot g^{a_22^2} \cdot\ldots\cdot 2^{a_k2^k}
-=
-g^{a_0+a_12+a_22^2+\dots+a_k2^k}
-=
-g^a.
-\]
-Die Schleife wird $\lfloor1+\log_2ab\rfloor$ mal durchlaufen.
-In jedem Fall wird auf jeden Fall die Multiplikation in
-Schritt~\ref{divide-and-conquer-4} durchgeführt
-und im schlimmsten Fall auch noch die Multiplikation in
-Schritt~\ref{divide-and-conquer-3}.
-Es werden also nicht mehr als $2\lfloor 1+\log_2a\rfloor=O(\log_2a)$
-Multiplikationen durchgeführt.
-\end{proof}
-
-\begin{beispiel}
-Man berechne die Potenz $7^{2021}$ in $\mathbb{F}_p$.
-Die Binärdarstellung von 2021 ist $2021_{10}=\texttt{11111100101}_2$.
-Wir stellen die nötigen Operationen des
-Algorithmus~\ref{buch:crypto:algo:divide-and-conquer} in der folgenden
-Tabelle
-\begin{center}
-\begin{tabular}{|>{$}r<{$}|>{$}r<{$}|>{$}r<{$}|>{$}r<{$}|}
-\hline
- i& f& a_i& x\\
-\hline
- 0& 7& 1& 7\\
- 1& 49& 0& 7\\
- 2&1110& 1& 24\\
- 3& 486& 0& 24\\
- 4&1234& 0& 24\\
- 5& 667& 1& 516\\
- 6& 785& 1& 977\\
- 7& 418& 1& 430\\
- 8& 439& 1& 284\\
- 9& 362& 1& 819\\
-10& 653& 1& 333\\
-\hline
-\end{tabular}
-\end{center}
-Daraus liest man ab, dass $7^{2021}=333\in\mathbb{F}_{1291}$.
-\end{beispiel}
-
-Die Tabelle suggeriert, dass die Potenzen von $g$ ``wild'', also
-scheinbar ohne System in $\mathbb{F}_p$ herumspringen.
-Dies deutet an, dass die Umkehrung der Exponentialfunktion in $\mathbb{F}_p$
-schwierig ist.
-Die Umkehrfunktion der Exponentialfunktion, die Umkehrfunktion von
-$x\mapsto g^x$ in $\mathbb{F}_p$ heisst der {\em diskrete Logarithmus}.
-\index{diskreter Logarithmus}%
-Tatsächlich ist der diskrete Logarithmus ähnlich schwierig zu bestimmen
-wie das Faktorisieren von Zahlen, die das Produkt grosser
-Primafaktoren ähnlicher Grössenordnung wie $p$ sind.
-Die Funktion $x\mapsto g^x$ ist die gesuchte, schwierig zu invertierende
-Funktion.
-
-Auf dern ersten Blick scheint der
-Algorithmus~\ref{buch:crypto:algo:divide-and-conquer}
-den Nachteil zu haben, dass erst die Binärdarstellung der Zahl $a$
-ermittelt werden muss.
-In einem Computer ist dies aber normalerweise kein Problem, da $a$
-im Computer ohnehin binär dargestellt ist.
-Die Binärziffern werden in der Reihenfolge vom niederwertigsten zum
-höchstwertigen Bit benötigt.
-Die folgende Modifikation des Algorithmus ermittelt laufend
-auch die Binärstellen von $a$.
-Die dazu notwendigen Operationen sind im Binärsystem besonders
-effizient implementierbar, die Division durch 2 ist ein Bitshift, der
-Rest ist einfach das niederwertigste Bit der Zahl.
-
-\begin{algorithmus}
-\label{buch:crypto:algo:divide-and-conquer2}
-\begin{enumerate}
-\item
-Setze $f=g$, $x=1$, $i=0$
-\item
-Solange $a>0$ ist, führe aus
-\begin{enumerate}
-\item
-Verwende den euklidischen Algorithmus um $r$ und $b$ zu bestimmen mit $a=2b+r$
-\item
-Falls $r=1$ setze $x \coloneqq x \cdot f$
-\item
-$i \coloneqq i+1$, $a = b$ und $f\coloneqq f\cdot f$
-\end{enumerate}
-\end{enumerate}
-Die Potenz $x=g^a$ kann so in $O(\log_2a)$ Multiplikationen
-berechnet werden.
-\end{algorithmus}
-
-
-%
-% Diffie-Hellman Schlüsseltausch
-%
-\subsection{Diffie-Hellman-Schlüsseltausch
-\label{buch:subsection:diffie-hellman}}
-Eine Grundaufgabe der Verschlüsselung im Internet ist, dass zwei
-Kommunikationspartner einen gemeinsamen Schlüssel für die Verschlüsselung
-der Daten aushandeln können müssen.
-Es muss davon ausgegangen werden, dass die Kommunikation abgehört wird.
-Trotzdem soll es für einen Lauscher nicht möglich sein, den
-ausgehandelten Schlüssel zu ermitteln.
-
-% XXX Historisches zu Diffie und Hellman
-
-Die beiden Partner $A$ und $B$ einigen sich zunächst auf eine Zahl $g$,
-die öffentlich bekannt sein darf.
-Weiter erzeugen sie eine zufällige Zahl $a$ und $b$, die sie geheim
-halten.
-Das Verfahren soll aus diesen beiden Zahlen einen Schlüssel erzeugen,
-den beide Partner berechnen können, ohne dass sie $a$ oder $b$
-übermitteln müssen.
-Die beiden Zahlen werden daher auch die privaten Schlüssel genannt.
-
-Die Idee von Diffie und Hellman ist jetzt, die Werte $x=g^a$ und $y=g^b$
-zu übertragen.
-In $\mathbb{R}$ würden dadurch natürlich dem Lauscher auch $a$ offenbart,
-er könnte einfach $a=\log_g x$ berechnen.
-Ebenso kann auch $b$ als $b=\log_g y$ erhalten werden, die beiden
-privaten Schlüssel wären also nicht mehr privat.
-Statt der Potenzfunktion in $\mathbb{R}$ muss also eine Funktion
-verwendet werden, die nicht so leicht umgekehrt werden kann.
-Die Potenzfunktion in $\mathbb{F}_p$ erfüllt genau diese Eigenschaft.
-Die Kommunikationspartner einigen sich also auch noch auf die (grosse)
-Primzahl $p$ und übermitteln $x=g^a\in\mathbb{F}_p$ und
-$y=g^b\in\mathbb{F}_p$.
-
-\begin{figure}
-\centering
-\includegraphics{chapters/90-crypto/images/dh.pdf}
-\caption{Schlüsselaustausch nach Diffie-Hellman.
-Die Kommunikationspartner $A$ und $B$ einigen sich öffentlich auf
-$p\in\mathbb{N}$ und $g\in\mathbb{F}_p$.
-$A$ wählt dann einen privaten Schlüssel $a\in\mathbb{N}$ und
-$B$ wählt $b\in\mathbb{N}$, sie tauschen dann $x=g^a$ und $y=g^b$
-aus.
-$A$ erhält den gemeinsamen Schlüssel aus $y^a$, $B$ erhält ihn
-aus $x^b$.
-\label{buch:crypto:fig:dh}}
-\end{figure}
-
-Aus $x$ und $y$ muss jetzt der gemeinsame Schlüssel abgeleitet werden.
-$A$ kennt $y=g^b$ und $a$, $B$ kennt $x=g^a$ und $b$.
-Beide können die Zahl $s=g^{ab}\in\mathbb{F}_p$ berechnen.
-$A$ macht das, indem er $y^a=(g^b)^a = g^{ab}$ rechnet,
-$B$ rechnet $x^b = (g^a)^b = g^{ab}$, beide natürlich in $\mathbb{F}_p$.
-Der Lauscher kann aber $g^{ab}$ nicht ermitteln, dazu müsste er
-$a$ oder $b$ ermitteln können.
-Die Zahl $s=g^{ab}$ kann also als gemeinsamer Schlüssel verwendet
-werden.
-
-
-
-\subsection{Elliptische Kurven
-\label{buch:subsection:elliptische-kurven}}
-Das Diffie-Hellman-Verfahren basiert auf der Schwierigkeit, in einem
-Körper $\mathbb{F}_p$ die Gleichung $a^x=b$ nach $x$ aufzulösen.
-Die Addition in $\mathbb{F}_p$ wird dazu nicht benötigt.
-Es reicht, eine Menge mit einer Multiplikation zu haben, in der das
-die Gleichung $a^x=b$ schwierig zu lösen ist.
-Ein Gruppe wäre also durchaus ausreichend.
-
-Ein Kandidat für eine solche Gruppe könnte der Einheitskreis
-$S^1=\{z\in\mathbb{C}\;|\; |z|=1\}$ in der komplexen Ebene sein.
-Wählt man eine Zahl $g=e^{i\alpha}$, wobei $\alpha$ ein irrationales
-Vielfaches von $\pi$ ist, dann sind alle Potenzen $g^n$ für natürliche
-Exponenten voneinander verschieden.
-Wäre nämlich $g^{n_1}=g^{n_2}$, dann wäre $e^{i\alpha(n_1-n_2)}=1$ und
-somit müsste $\alpha=2k\pi/(n_1-n_2)$ sein.
-Damit wäre aber $\alpha$ ein rationales Vielfaches von $\pi$, im Widerspruch
-zur Voraussetzung.
-Die Abbildung $n\mapsto g^n\in S^1$ ist auf den ersten Blick etwa ähnlich
-undurchschaubar wie die Abbildung $n\mapsto g^n\in\mathbb{F}_p$.
-Es gibt zwar die komplexe Logarithmusfunktion, mit der man $n$ bestimmen
-kann, dazu muss man aber den Wert von $g^n$ mit beliebiger Genauigkeit
-kennen, denn die Werte von $g^n$ können beliebig nahe beieinander liegen.
-
-Der Einheitskreis ist die Lösungsmenge der Gleichung $x^2+y^2=1$ für
-reelle Koordinaten $x$ und $y$,
-doch Rundungsunsicherheiten verunmöglichen den Einsatz in einem
-Verfahren ähnlich dem Diffie-Hellman-Verfahren.
-Dieses Problem kann gelöst werden, indem für die Variablen Werte
-aus einem endlichen Körper verwendet werden.
-Gesucht ist also eine Gleichung in zwei Variablen, deren Lösungsmenge
-in einem endlichen Körper eine Gruppenstruktur trägt.
-Die Lösungsmenge ist eine ``Kurve'' von Punkten mit
-Koordinaten in einem endlichen Körper.
-
-In diesem Abschnitt wird gezeigt, dass sogenannte elliptische Kurven
-über endlichen Körpern genau die verlangen Eigenschaften haben.
-
-\subsubsection{Elliptische Kurven}
-Elliptische Kurven sind Lösungen einer Gleichung der Form
-\begin{equation}
-Y^2+XY=X^3+aX+b
-\label{buch:crypto:eqn:ellipticcurve}
-\end{equation}
-mit Werten von $X$ und $Y$ in einem geeigneten Körper.
-Die Koeffizienten $a$ und $b$ müssen so gewählt werden, dass die
-Gleichung~\eqref{buch:crypto:eqn:ellipticcurve} genügend viele
-Lösungen hat.
-Über den komplexen Zahlen hat die Gleichung natürlich für jede Wahl von
-$X$ drei Lösungen.
-Für einen endlichen Körper können wir dies im allgemeinen nicht erwarten,
-aber wenn wir genügend viele Wurzeln zu $\mathbb{F}$ hinzufügen können wir
-mindestens erreichen, dass die Lösungsmenge so viele Elemente hat,
-dass ein Versuch, die Gleichung $g^x=b$ mittels Durchprobierens zu
-lösen, zum Scheitern verurteil ist.
-
-\begin{definition}
-\label{buch:crypto:def:ellipticcurve}
-Die {\em elliptische Kurve} $E_{a,b}(\Bbbk)$ über dem Körper $\Bbbk$ ist
-die Menge
-\[
-E_{a,b}(\Bbbk)
-=
-\{(X,Y)\in\Bbbk^2\;|\;Y^2+XY=X^3+aX+b\},
-\]
-für $a,b\in\Bbbk$.
-\end{definition}
-
-Um die Anschauung zu vereinfachen, werden wir elliptische Kurven über
-dem Körper $\mathbb{R}$ visualisieren.
-Die daraus gewonnenen geometrischen Einsichten werden wir anschliessend
-algebraisch umsetzen.
-In den reellen Zahlen kann man die
-Gleichung~\eqref{buch:crypto:eqn:ellipticcurve}
-noch etwas vereinfachen.
-Indem man in \eqref{buch:crypto:eqn:ellipticcurve}
-quadratisch ergänzt, bekommt man
-\begin{align}
-Y^2 + XY + \frac14X^2 &= X^3+\frac14 X^2 +aX+b
-\notag
-\\
-\Rightarrow\qquad
-v^2&=X^3+\frac14X^2+aX+b,
-\label{buch:crypto:eqn:ell2}
-\end{align}
-indem man $v=Y+\frac12X$ setzt.
-Man beachte, dass man diese Substition nur machen kann, wenn $\frac12$
-definiert ist.
-In $\mathbb{R}$ ist dies kein Problem, aber genau über den Körpern
-mit Charakteristik $2$, die wir für die Computer-Implementation
-bevorzugen, ist dies nicht möglich.
-Es geht hier aber nur um die Visualisierung.
-
-Auch die Form \eqref{buch:crypto:eqn:ell2} lässt sich noch etwas
-vereinfachen.
-Setzt man $X=u-\frac1{12}$, dann verschwindet nach einiger Rechnung,
-die wir hier nicht durchführen wollen, der quadratische Term
-auf der rechten Seite.
-Die interessierenden Punkte sind Lösungen der einfacheren Gleichung
-\begin{equation}
-v^2
-=
-u^3+\biggl(a-\frac{1}{48}\biggr)u + b-\frac{a}{12}+\frac{1}{864}
-=
-u^3+Au+B.
-\label{buch:crypto:ellvereinfacht}
-\end{equation}
-In dieser Form ist mit $(u,v)$ immer auch $(u,-v)$ eine Lösung,
-die Kurve ist symmetrisch bezüglich der $u$-Achse.
-Ebenso kann man ablesen, dass nur diejenigen $u$-Werte möglich sind,
-für die das kubische Polynom $u^3+Au+B$ auf der rechten Seite von
-\eqref{buch:crypto:ellvereinfacht}
-nicht negativ ist.
-
-Sind $u_1$, $u_2$ und $u_3$ die Nullstellen des kubischen Polynoms
-auf der rechten Seite von~\eqref{buch:crypto:ellvereinfacht}, folgt
-\[
-v^2
-=
-(u-u_1)(u-u_2)(u-u_3)
-=
-u^3
--(u_1+u_2+u_3)u^2
-+(u_1u_2+u_1u_3+u_2u_3)u
--
-u_1u_2u_3.
-\]
-Durch Koeffizientenvergleich sieht man, dass $u_1+u_2+u_3=0$ sein muss.
-\begin{figure}
-\centering
-\includegraphics{chapters/90-crypto/images/elliptic.pdf}
-\caption{Elliptische Kurve in $\mathbb{R}$ in der Form
-$v^2=u^3+Au+B$ mit Nullstellen $u_1$, $u_2$ und $u_3$ des
-kubischen Polynoms auf der rechten Seite.
-Die blauen Punkte und Geraden illustrieren die Definition der
-Gruppenoperation in der elliptischen Kurve.
-\label{buch:crypto:fig:elliptischekurve}}
-\end{figure}
-Abbildung~\ref{buch:crypto:fig:elliptischekurve}
-zeigt eine elliptische Kurve in der Ebene.
-
-\subsubsection{Geometrische Definition der Gruppenoperation}
-In der speziellen Form \ref{buch:crypto:ellvereinfacht} ist die
-elliptische Kurve symmetrisch unter Spiegelung an der $u$-Achse.
-Die Spiegelung ist eine Involution, zweimalige Ausführung führt auf
-den ursprünglichen Punkt zurück.
-Die Inverse in einer Gruppe hat diese Eigenschaft auch, es ist
-daher naheliegend, den gespiegelten Punkt als die Inverse eines
-Elementes zu nehmen.
-
-Eine Gerade durch zwei Punkte der
-in Abbildung~\ref{buch:crypto:fig:elliptischekurve}
-dargestellten Kurve schneidet die Kurve ein drittes Mal.
-Die Gruppenoperation wird so definiert, dass drei Punkte der Kurve
-auf einer Geraden das Gruppenprodukt $e$ haben.
-Da aus $g_1g_2g_3=e$ folgt $g_3=(g_1g_2)^{-1}$ oder
-$g_1g_2=g_3^{-1}$, erhält man das Gruppenprodukt zweier Elemente
-auf der elliptischen Kurve indem erst den dritten Schnittpunkt
-ermittelt und diesen dann an der $u$-Achse spiegelt.
-
-Die geometrische Konstruktion schlägt fehl, wenn $g_1=g_2$ ist.
-In diesem Fall kann man die Tangente im Punkt $g_1$ an die Kurve
-verwenden.
-Dieser Fall tritt zum Beispiel auch in den drei Punkten
-$(u_1,0)$, $(u_2,0)$ und $(u_3,0)$ ein.
-
-Um das neutrale Element der Gruppe zu finden, können wir
-zwei Punkte $g$ und $g^{-1}$ miteinander verknüpfen.
-Die Gerade durch $g$ und $g^{-1}$ schneidet aber die Kurve
-kein drittes Mal.
-Ausserdem sind alle Geraden durch $g$ und $g^{-1}$ für verschiedene
-$g$ parallel.
-Das neutrale Element entspricht also einem unendlich weit entfernten Punkt.
-Das neutrale Element entsteht immer dann als Produkt, wenn zwei
-Punkte die gleiche $u$-Koordinaten haben.
-
-\subsubsection{Gruppenoperation, algebraische Konstruktion}
-Nach den geometrischen Vorarbeiten zur Definition der Gruppenoperation
-kann können wir die Konstruktion jetzt algebraisch umsetzen.
-
-Zunächst überlegen wir uns wieder eine Involution, welche als Inverse
-dienen kann.
-Dazu beachten wir, dass die linke Seite der definierenden Gleichung
-\begin{equation}
-Y^2+XY=X^3-aX+b.
-\label{buch:crypto:eqn:grupopgl}
-\end{equation}
-auch als $Y(Y+X)$ geschrieben werden kann.
-Die Abbildung $Y\mapsto -X-Y$ macht daraus
-\[
-(-X-Y)(-X-Y+X)=(X+Y)Y,
-\]
-dies ist also die gesuchte Involution.
-
-Seien also $g_1=(x_1,y_1)$ und $g_2=(x_2,y_2)$ zwei verschiedene Lösungen
-der Gleichung \eqref{buch:crypto:eqn:grupopgl}
-Als erstes brauchen wir eine Gleichung für die Gerade durch die beiden
-Punkte.
-Sei also $l(X,Y)$ eine Linearform derart, dass $l(g_1)=d$ und $l(g_2)=d$
-für ein geeignetes $d\in\Bbbk$.
-Dann gilt auch für die Punkte
-\[
-g(t) = tg_1 + (1-t)g_2
-\qquad\Rightarrow\qquad
-l(g(t))
-=
-tl(g_1) + (1-t)l(g_2)
-=
-tc+(1-t)c
-=
-(t+1-t)c
-=c,
-\]
-jeder Punkt der Geraden durch $g_1$ und $g_2$ lässt sich in dieser Form
-schreiben.
-
-Setzt man jetzt $g(t)$ in die Gleichung ein, erhält man eine kubische
-Gleichung in $t$, von der wir bereits zwei Nullstellen kennen, nämlich
-$0$ und $1$.
-Die kubische Gleichung muss also durch $t$ und $(t-1)$ teilbar sein.
-Diese Berechnung kann man einfach in einem Computeralgebrasystem
-durchführen.
-Das Polynom ist
-\[
-p(t)
-=
-\]
-Nach Division durch $t(t-1)$ erhält man als den Quotienten
-\begin{align*}
-q(t)
-&=
-(y_2-y_1)^2
-+
-(y_2-y_1) (x_2-x_1)
-+
-t(x_2-x_1)^3
--
-2x_2^3+3x_1x_2^2-x_1^3
-\end{align*}
-und den Rest
-\[
-r(t)
-=
-t(y_1^2+x_1y_1-x_1^3-ax_1-b)
-+
-(1-t)(y_2^2+x_2y_2-x_2^3-ax_2-b).
-\]
-Die Klammerausdrücke verschwinden, da die sie gleichbedeutend damit sind,
-dass die Punkte Lösungen von \eqref{buch:crypto:eqn:grupopgl} sind.
-
-Für den dritten Punkt auf der Geraden muss $t$ so gewählt werden, dass
-$q(t)=0$ ist.
-Dies ist aber eine lineare Gleichung mit der Lösung
-\begin{align*}
-t
-&=
--\frac{
-(y_1-y_2)^2
-+
-(y_2-y_1)(x_2-x_1)
--2x_2^3+3x_1x_2^2-x_1^3
-}{(x_2-x_1)^3}
-.
-\end{align*}
-Setzt man dies $g(t)$ ein, erhält man für die Koordinaten des dritten
-Punktes $g_3$ die Werte
-\begin{align}
-x_3
-&=
-\frac{
-(y_2-y_1)^2(x_2-x_1) + (y_2-y_1)(x_2-x_1)^2
--(x_2^4+x_1^4)
-}{
-(x_2-x_1)^3
-}
-\label{buch:crypto:eqn:x3}
-\\
-y_3
-&=
-\frac{
-(y_2-y_1)^3
-+(x_2-x_1)(y_2-y_1)^2
--(x_{2}-x_{1})^3 ( y_{2} - y_{1})
--(x_{2}-x_{1})^2 ( x_{1} y_{2}- x_{2} y_{1})
-}{
-(x_2-x_1)^3
-}
-\label{buch:crypto:eqn:y3}
-\end{align}
-Die Gleichungen
-\eqref{buch:crypto:eqn:x3}
-und
-\eqref{buch:crypto:eqn:y3}
-ermöglichen also, das Element $g_1g_2^{-1}$ zu berechnen.
-Interessant daran ist, dass in den Formeln die Konstanten $a$ und $b$
-gar nicht vorkommen.
-
-Es bleibt noch der wichtige Fall des Quadrierens in der Gruppe zu
-behandeln, also den Fall $g_1=g_2$.
-In diese Fall sind die Formeln
-\eqref{buch:crypto:eqn:x3}
-und
-\eqref{buch:crypto:eqn:y3}
-ganz offensichtlich nicht anwendbar.
-Die geometrische Anschauung hat nahegelegt, die Tangent an die Kurve
-im Punkt $g_1$ zu nehmen.
-In $\mathbb{R}$ würde man dafür einen Grenzübergang $g_2\to g_1$ machen,
-aber in einem endlichen Körper ist dies natürlich nicht möglich.
-
-Wir schreiben die Gerade als Parameterdarstellung in der Form
-\(
-t\mapsto g(t)= (x_1+ut, y_1+vt)
-\)
-für beliebige Parameter in $\Bbbk$.
-Die Werte $u_1$ und $u_2$ müssen so gewählt werden, dass $g(t)$ eine
-Tangente wird.
-Setzt man $g(t)$ in die Gleichung~\eqref{buch:crypto:eqn:grupopgl} ein,
-entsteht ein kubische Gleichung, die genau dann eine doppelte Nullstelle
-bei $0$ hat, wenn $u,v$ die Tangentenrichtung beschreiben.
-Einsetzen von $g(t)$ in \eqref{buch:crypto:eqn:grupopgl}
-ergibt die Gleichung
-\begin{align}
-0
-&=
--u^3t^3
-+
-(-3u^2x_{1}+v^2+uv)t^2
-+
-(2vy_1+uy_1-3ux_1^2+vx_1-au)t
-+
-(y_1^2+x_1y_1-x_1^3-ax_1-b)
-\label{buch:crypto:eqn:tangente1}
-\end{align}
-Damit bei $t=0$ eine doppelte Nullstelle mussen die letzten beiden
-Koeffizienten verschwinden, dies führt auf die Gleichungen
-\begin{align}
-y_1^2+x_1y_1&=x_1^3+ax_1+b
-\label{buch:crypto:eqn:rest1}
-\\
-(2y_1
-+x_1)v
-+(y_1
--3x_1^2
--a)u
-&=0
-\label{buch:crypto:eqn:rest2}
-\end{align}
-Die erste Gleichung \eqref{buch:crypto:eqn:rest1} drückt aus,
-dass $g_1$ ein Punkt der Kurve ist, sie ist automatisch erfüllt.
-
-Die zweite Gleichung
-\eqref{buch:crypto:eqn:rest2}
-legt das Verhältnis von $u$ und $v$, also die
-\label{buch:crypto:eqn:rest2}
-Tangentenrichtung fest.
-Eine mögliche Lösung ist
-\begin{equation}
-\begin{aligned}
-u &= x_1+2y_1
-\\
-v &= -y_1+3x_1^2+a.
-\end{aligned}
-\label{buch:crypto:eqn:uv}
-\end{equation}
-
-Der Quotient ist ein lineares Polynom in $t$, die Nullstelle parametrisiert
-den Punkt, der $(g_1)^{-2}$ entspricht.
-Der zugehörige Wert von $t$ ist
-\begin{equation}
-t=-\frac{3u^2x_1-v^2-uv}{u^3}.
-\label{buch:crypto:eqn:t}
-\end{equation}
-
-
-Setzt man
-\label{buch:crypto:eqn:t}
-und
-\eqref{buch:crypto:eqn:uv}
-in $g(t)$ ein, erhält man sehr komplizierte Ausdrücke für den dritten Punkt.
-Wir verzichten darauf, diese Ausdrücke hier aufzuschreiben.
-In der Praxis wird man in einem Körper der Charakteristik 2 arbeiten.
-In diesem Körper werden alle geraden Koeffizienten zu $0$, alle ungeraden
-Koeffizienten werden unabhängig vom Vorzeichen zu $1$.
-Damit bekommt man die folgenden, sehr viel übersichtlicheren Ausdrücke
-für den dritten Punkt:
-\begin{equation}
-\begin{aligned}
-x
-&=
--\frac{
-y_1^2+x_1y_1+x_1^4+x_1^3+ax_1-a^2
- }{
-x_1^2
-}
-\\
-y
-&=
-\frac{
-y_1^3+(x_1^2+x_1+a)y_1^2+(x_1^4 +a^2)y_1+x_1^6+ax_1^4+ax_1^3+a^2x_1^2+a^2x_1+a^3
-}{
- x_1^3
-}
-\end{aligned}
-\label{buch:crypto:eqn:tangentechar2}
-\end{equation}
-Damit haben wir einen vollständigen Formelsatz für die Berechnung der
-Gruppenoperation in der elliptischen Kurve mindestens für den praktisch
-relevanten Fall einer Kurve über einem Körper der Charakteristik $2$.
-
-\begin{satz}
-Die elliptische Kurve
-\[
-E_{a,b}(\mathbb{F}_{p^l})
-=
-\{
-(X,Y)\in\mathbb{F}_{p^l}
-\;|\;
-Y^2+XY = X^3-aX-b
-\}
-\]
-trägt eine Gruppenstruktur, die wie folgt definiert ist:
-\begin{enumerate}
-\item Der Punkt $(0,0)$ entspricht dem neutralen Element.
-\item Das inverse Element von $(x,y)$ ist $(-x,-y-x)$.
-\item Für zwei verschiedene Punkte $g_1$ und $g_2$ kann $g_3=(g_1g_2)^{-1}$
-mit Hilfe der Formeln
-\eqref{buch:crypto:eqn:x3}
-und
-\eqref{buch:crypto:eqn:y3}
-gefunden werden.
-\item Für einen Punkt $g_1$ kann $g_3=g_1^{-2}$ in Charakteristik $2$ mit
-Hilfe der Formeln
-\eqref{buch:crypto:eqn:tangentechar2}
-gefunden werden.
-\end{enumerate}
-Diese Operationen machen $E_{a,b}(\mathbb{F}_{p^l})$ zu einer endlichen
-abelschen Gruppe.
-\end{satz}
-
-\subsubsection{Beispiele}
-% XXX
-TODO: elliptische Kurven in IPsec: Oakley Gruppen
-
-\subsubsection{Diffie-Hellman in einer elliptischen Kurve}
-% XXX
-TODO: $g^x$ in einer elliptischen Kurve
-
-
-
+%
+% ff.tex -- Kryptographie und endliche Körper
+%
+% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil
+%
+
+\section{Kryptographie und endliche Körper
+\label{buch:section:kryptographie-und-endliche-koerper}}
+\rhead{Kryptographie und endliche Körper}
+
+\subsection{Potenzen in $\mathbb{F}_p$ und diskreter Logarithmus
+\label{buch:subsection:potenzen-diskreter-logarithmus}}
+Für kryptographische Anwendungen wird eine einfach zu berechnende
+Funktion benötigt,
+die ohne zusätzliches Wissen, üblicherweise der Schlüssel genannt,
+nicht ohne weiteres umkehrbar ist.
+Die arithmetischen Operationen in einem endlichen Körper sind
+mit geringem Aufwand durchführbar.
+Für die ``schwierigste'' Operation, die Division, steht der
+euklidische Algorithmus zur Verfügung.
+
+Die nächstschwierigere Operation ist die Potenzfunktion.
+Für $g\in \Bbbk$ und $a\in\mathbb{N}$ ist die Potenz $g^a\in\Bbbk$
+natürlich durch die wiederholte Multiplikation definiert.
+In der Praxis werden aber $g$ und $a$ Zahlen mit vielen Binärstellen
+sein, die die wiederholte Multiplikation ist daher sicher nicht
+effizient, das Kriterium der einfachen Berechenbarkeit scheint
+also nicht erfüllt.
+Der folgende Algorithmus berechnet die Potenz in $O(\log_2 a)$
+Multiplikationen.
+
+\begin{algorithmus}[Divide-and-conquer]
+\label{buch:crypto:algo:divide-and-conquer}
+Sei $a=a_0 + a_12^1 + a_22^2 + \dots + a_k2^k$ die Binärdarstellung
+der Zahl $a$.
+\begin{enumerate}
+\item setze $f=g$, $x=1$, $i=0$
+\label{divide-and-conquer-1}
+\item solange $i\ge k$ ist, führe aus
+\label{divide-and-conquer-2}
+\begin{enumerate}
+\item
+\label{divide-and-conquer-3}
+falls $a_i=1$ setze $x \coloneqq x \cdot f$
+\item
+\label{divide-and-conquer-4}
+$i \coloneqq i+1$ und $f\coloneqq f\cdot f$
+\end{enumerate}
+\end{enumerate}
+Die Potenz $x=g^a$ kann so in $O(\log_2a)$ Multiplikationen
+berechnet werden.
+\end{algorithmus}
+
+\begin{proof}[Beweis]
+Die Initalisierung in Schritt~\ref{divide-and-conquer-1} stellt sicher,
+dass $x$ den Wert $g^0$ hat.
+Schritt~\ref{divide-and-conquer-4} stellt sicher,
+dass die Variable $f$ immer den Wert $g^{2^i}$ hat.
+Im Schritt~\ref{divide-and-conquer-3} wird zu $x$ die Potenz
+$g^{a_i2^i}$ hinzumultipliziert.
+Am Ende des Algorithmus hat daher $x$ den Wert
+\[
+x = g^{a_02^0} \cdot g^{a_12^1} \cdot g^{a_22^2} \cdot\ldots\cdot 2^{a_k2^k}
+=
+g^{a_0+a_12+a_22^2+\dots+a_k2^k}
+=
+g^a.
+\]
+Die Schleife wird $\lfloor1+\log_2ab\rfloor$ mal durchlaufen.
+In jedem Fall wird auf jeden Fall die Multiplikation in
+Schritt~\ref{divide-and-conquer-4} durchgeführt
+und im schlimmsten Fall auch noch die Multiplikation in
+Schritt~\ref{divide-and-conquer-3}.
+Es werden also nicht mehr als $2\lfloor 1+\log_2a\rfloor=O(\log_2a)$
+Multiplikationen durchgeführt.
+\end{proof}
+
+\begin{beispiel}
+Man berechne die Potenz $7^{2021}$ in $\mathbb{F}_p$.
+Die Binärdarstellung von 2021 ist $2021_{10}=\texttt{11111100101}_2$.
+Wir stellen die nötigen Operationen des
+Algorithmus~\ref{buch:crypto:algo:divide-and-conquer} in der folgenden
+Tabelle
+\begin{center}
+\begin{tabular}{|>{$}r<{$}|>{$}r<{$}|>{$}r<{$}|>{$}r<{$}|}
+\hline
+ i& f& a_i& x\\
+\hline
+ 0& 7& 1& 7\\
+ 1& 49& 0& 7\\
+ 2&1110& 1& 24\\
+ 3& 486& 0& 24\\
+ 4&1234& 0& 24\\
+ 5& 667& 1& 516\\
+ 6& 785& 1& 977\\
+ 7& 418& 1& 430\\
+ 8& 439& 1& 284\\
+ 9& 362& 1& 819\\
+10& 653& 1& 333\\
+\hline
+\end{tabular}
+\end{center}
+Daraus liest man ab, dass $7^{2021}=333\in\mathbb{F}_{1291}$.
+\end{beispiel}
+
+Die Tabelle suggeriert, dass die Potenzen von $g$ ``wild'', also
+scheinbar ohne System in $\mathbb{F}_p$ herumspringen.
+Dies deutet an, dass die Umkehrung der Exponentialfunktion in $\mathbb{F}_p$
+schwierig ist.
+Die Umkehrfunktion der Exponentialfunktion, die Umkehrfunktion von
+$x\mapsto g^x$ in $\mathbb{F}_p$ heisst der {\em diskrete Logarithmus}.
+\index{diskreter Logarithmus}%
+Tatsächlich ist der diskrete Logarithmus ähnlich schwierig zu bestimmen
+wie das Faktorisieren von Zahlen, die das Produkt grosser
+Primafaktoren ähnlicher Grössenordnung wie $p$ sind.
+Die Funktion $x\mapsto g^x$ ist die gesuchte, schwierig zu invertierende
+Funktion.
+
+Auf dern ersten Blick scheint der
+Algorithmus~\ref{buch:crypto:algo:divide-and-conquer}
+den Nachteil zu haben, dass erst die Binärdarstellung der Zahl $a$
+ermittelt werden muss.
+In einem Computer ist dies aber normalerweise kein Problem, da $a$
+im Computer ohnehin binär dargestellt ist.
+Die Binärziffern werden in der Reihenfolge vom niederwertigsten zum
+höchstwertigen Bit benötigt.
+Die folgende Modifikation des Algorithmus ermittelt laufend
+auch die Binärstellen von $a$.
+Die dazu notwendigen Operationen sind im Binärsystem besonders
+effizient implementierbar, die Division durch 2 ist ein Bitshift, der
+Rest ist einfach das niederwertigste Bit der Zahl.
+
+\begin{algorithmus}
+\label{buch:crypto:algo:divide-and-conquer2}
+\begin{enumerate}
+\item
+Setze $f=g$, $x=1$, $i=0$
+\item
+Solange $a>0$ ist, führe aus
+\begin{enumerate}
+\item
+Verwende den euklidischen Algorithmus um $r$ und $b$ zu bestimmen mit $a=2b+r$
+\item
+Falls $r=1$ setze $x \coloneqq x \cdot f$
+\item
+$i \coloneqq i+1$, $a = b$ und $f\coloneqq f\cdot f$
+\end{enumerate}
+\end{enumerate}
+Die Potenz $x=g^a$ kann so in $O(\log_2a)$ Multiplikationen
+berechnet werden.
+\end{algorithmus}
+
+
+%
+% Diffie-Hellman Schlüsseltausch
+%
+\subsection{Diffie-Hellman-Schlüsseltausch
+\label{buch:subsection:diffie-hellman}}
+Eine Grundaufgabe der Verschlüsselung im Internet ist, dass zwei
+Kommunikationspartner einen gemeinsamen Schlüssel für die Verschlüsselung
+der Daten aushandeln können müssen.
+Es muss davon ausgegangen werden, dass die Kommunikation abgehört wird.
+Trotzdem soll es für einen Lauscher nicht möglich sein, den
+ausgehandelten Schlüssel zu ermitteln.
+
+% XXX Historisches zu Diffie und Hellman
+
+Die beiden Partner $A$ und $B$ einigen sich zunächst auf eine Zahl $g$,
+die öffentlich bekannt sein darf.
+Weiter erzeugen sie eine zufällige Zahl $a$ und $b$, die sie geheim
+halten.
+Das Verfahren soll aus diesen beiden Zahlen einen Schlüssel erzeugen,
+den beide Partner berechnen können, ohne dass sie $a$ oder $b$
+übermitteln müssen.
+Die beiden Zahlen werden daher auch die privaten Schlüssel genannt.
+
+Die Idee von Diffie und Hellman ist jetzt, die Werte $x=g^a$ und $y=g^b$
+zu übertragen.
+In $\mathbb{R}$ würden dadurch natürlich dem Lauscher auch $a$ offenbart,
+er könnte einfach $a=\log_g x$ berechnen.
+Ebenso kann auch $b$ als $b=\log_g y$ erhalten werden, die beiden
+privaten Schlüssel wären also nicht mehr privat.
+Statt der Potenzfunktion in $\mathbb{R}$ muss also eine Funktion
+verwendet werden, die nicht so leicht umgekehrt werden kann.
+Die Potenzfunktion in $\mathbb{F}_p$ erfüllt genau diese Eigenschaft.
+Die Kommunikationspartner einigen sich also auch noch auf die (grosse)
+Primzahl $p$ und übermitteln $x=g^a\in\mathbb{F}_p$ und
+$y=g^b\in\mathbb{F}_p$.
+
+\begin{figure}
+\centering
+\includegraphics{chapters/90-crypto/images/dh.pdf}
+\caption{Schlüsselaustausch nach Diffie-Hellman.
+Die Kommunikationspartner $A$ und $B$ einigen sich öffentlich auf
+$p\in\mathbb{N}$ und $g\in\mathbb{F}_p$.
+$A$ wählt dann einen privaten Schlüssel $a\in\mathbb{N}$ und
+$B$ wählt $b\in\mathbb{N}$, sie tauschen dann $x=g^a$ und $y=g^b$
+aus.
+$A$ erhält den gemeinsamen Schlüssel aus $y^a$, $B$ erhält ihn
+aus $x^b$.
+\label{buch:crypto:fig:dh}}
+\end{figure}
+
+Aus $x$ und $y$ muss jetzt der gemeinsame Schlüssel abgeleitet werden.
+$A$ kennt $y=g^b$ und $a$, $B$ kennt $x=g^a$ und $b$.
+Beide können die Zahl $s=g^{ab}\in\mathbb{F}_p$ berechnen.
+$A$ macht das, indem er $y^a=(g^b)^a = g^{ab}$ rechnet,
+$B$ rechnet $x^b = (g^a)^b = g^{ab}$, beide natürlich in $\mathbb{F}_p$.
+Der Lauscher kann aber $g^{ab}$ nicht ermitteln, dazu müsste er
+$a$ oder $b$ ermitteln können.
+Die Zahl $s=g^{ab}$ kann also als gemeinsamer Schlüssel verwendet
+werden.
+
+
+
+\subsection{Elliptische Kurven
+\label{buch:subsection:elliptische-kurven}}
+Das Diffie-Hellman-Verfahren basiert auf der Schwierigkeit, in einem
+Körper $\mathbb{F}_p$ die Gleichung $a^x=b$ nach $x$ aufzulösen.
+Die Addition in $\mathbb{F}_p$ wird dazu nicht benötigt.
+Es reicht, eine Menge mit einer Multiplikation zu haben, in der das
+die Gleichung $a^x=b$ schwierig zu lösen ist.
+Ein Gruppe wäre also durchaus ausreichend.
+
+Ein Kandidat für eine solche Gruppe könnte der Einheitskreis
+$S^1=\{z\in\mathbb{C}\;|\; |z|=1\}$ in der komplexen Ebene sein.
+Wählt man eine Zahl $g=e^{i\alpha}$, wobei $\alpha$ ein irrationales
+Vielfaches von $\pi$ ist, dann sind alle Potenzen $g^n$ für natürliche
+Exponenten voneinander verschieden.
+Wäre nämlich $g^{n_1}=g^{n_2}$, dann wäre $e^{i\alpha(n_1-n_2)}=1$ und
+somit müsste $\alpha=2k\pi/(n_1-n_2)$ sein.
+Damit wäre aber $\alpha$ ein rationales Vielfaches von $\pi$, im Widerspruch
+zur Voraussetzung.
+Die Abbildung $n\mapsto g^n\in S^1$ ist auf den ersten Blick etwa ähnlich
+undurchschaubar wie die Abbildung $n\mapsto g^n\in\mathbb{F}_p$.
+Es gibt zwar die komplexe Logarithmusfunktion, mit der man $n$ bestimmen
+kann, dazu muss man aber den Wert von $g^n$ mit beliebiger Genauigkeit
+kennen, denn die Werte von $g^n$ können beliebig nahe beieinander liegen.
+
+Der Einheitskreis ist die Lösungsmenge der Gleichung $x^2+y^2=1$ für
+reelle Koordinaten $x$ und $y$,
+doch Rundungsunsicherheiten verunmöglichen den Einsatz in einem
+Verfahren ähnlich dem Diffie-Hellman-Verfahren.
+Dieses Problem kann gelöst werden, indem für die Variablen Werte
+aus einem endlichen Körper verwendet werden.
+Gesucht ist also eine Gleichung in zwei Variablen, deren Lösungsmenge
+in einem endlichen Körper eine Gruppenstruktur trägt.
+Die Lösungsmenge ist eine ``Kurve'' von Punkten mit
+Koordinaten in einem endlichen Körper.
+
+In diesem Abschnitt wird gezeigt, dass sogenannte elliptische Kurven
+über endlichen Körpern genau die verlangen Eigenschaften haben.
+
+\subsubsection{Elliptische Kurven}
+Elliptische Kurven sind Lösungen einer Gleichung der Form
+\begin{equation}
+Y^2+XY=X^3+aX+b
+\label{buch:crypto:eqn:ellipticcurve}
+\end{equation}
+mit Werten von $X$ und $Y$ in einem geeigneten Körper.
+Die Koeffizienten $a$ und $b$ müssen so gewählt werden, dass die
+Gleichung~\eqref{buch:crypto:eqn:ellipticcurve} genügend viele
+Lösungen hat.
+Über den komplexen Zahlen hat die Gleichung natürlich für jede Wahl von
+$X$ drei Lösungen.
+Für einen endlichen Körper können wir dies im allgemeinen nicht erwarten,
+aber wenn wir genügend viele Wurzeln zu $\mathbb{F}$ hinzufügen können wir
+mindestens erreichen, dass die Lösungsmenge so viele Elemente hat,
+dass ein Versuch, die Gleichung $g^x=b$ mittels Durchprobierens zu
+lösen, zum Scheitern verurteil ist.
+
+\begin{definition}
+\label{buch:crypto:def:ellipticcurve}
+Die {\em elliptische Kurve} $E_{a,b}(\Bbbk)$ über dem Körper $\Bbbk$ ist
+die Menge
+\[
+E_{a,b}(\Bbbk)
+=
+\{(X,Y)\in\Bbbk^2\;|\;Y^2+XY=X^3+aX+b\},
+\]
+für $a,b\in\Bbbk$.
+\end{definition}
+
+Um die Anschauung zu vereinfachen, werden wir elliptische Kurven über
+dem Körper $\mathbb{R}$ visualisieren.
+Die daraus gewonnenen geometrischen Einsichten werden wir anschliessend
+algebraisch umsetzen.
+In den reellen Zahlen kann man die
+Gleichung~\eqref{buch:crypto:eqn:ellipticcurve}
+noch etwas vereinfachen.
+Indem man in \eqref{buch:crypto:eqn:ellipticcurve}
+quadratisch ergänzt, bekommt man
+\begin{align}
+Y^2 + XY + \frac14X^2 &= X^3+\frac14 X^2 +aX+b
+\notag
+\\
+\Rightarrow\qquad
+v^2&=X^3+\frac14X^2+aX+b,
+\label{buch:crypto:eqn:ell2}
+\end{align}
+indem man $v=Y+\frac12X$ setzt.
+Man beachte, dass man diese Substition nur machen kann, wenn $\frac12$
+definiert ist.
+In $\mathbb{R}$ ist dies kein Problem, aber genau über den Körpern
+mit Charakteristik $2$, die wir für die Computer-Implementation
+bevorzugen, ist dies nicht möglich.
+Es geht hier aber nur um die Visualisierung.
+
+Auch die Form \eqref{buch:crypto:eqn:ell2} lässt sich noch etwas
+vereinfachen.
+Setzt man $X=u-\frac1{12}$, dann verschwindet nach einiger Rechnung,
+die wir hier nicht durchführen wollen, der quadratische Term
+auf der rechten Seite.
+Die interessierenden Punkte sind Lösungen der einfacheren Gleichung
+\begin{equation}
+v^2
+=
+u^3+\biggl(a-\frac{1}{48}\biggr)u + b-\frac{a}{12}+\frac{1}{864}
+=
+u^3+Au+B.
+\label{buch:crypto:ellvereinfacht}
+\end{equation}
+In dieser Form ist mit $(u,v)$ immer auch $(u,-v)$ eine Lösung,
+die Kurve ist symmetrisch bezüglich der $u$-Achse.
+Ebenso kann man ablesen, dass nur diejenigen $u$-Werte möglich sind,
+für die das kubische Polynom $u^3+Au+B$ auf der rechten Seite von
+\eqref{buch:crypto:ellvereinfacht}
+nicht negativ ist.
+
+Sind $u_1$, $u_2$ und $u_3$ die Nullstellen des kubischen Polynoms
+auf der rechten Seite von~\eqref{buch:crypto:ellvereinfacht}, folgt
+\[
+v^2
+=
+(u-u_1)(u-u_2)(u-u_3)
+=
+u^3
+-(u_1+u_2+u_3)u^2
++(u_1u_2+u_1u_3+u_2u_3)u
+-
+u_1u_2u_3.
+\]
+Durch Koeffizientenvergleich sieht man, dass $u_1+u_2+u_3=0$ sein muss.
+\begin{figure}
+\centering
+\includegraphics{chapters/90-crypto/images/elliptic.pdf}
+\caption{Elliptische Kurve in $\mathbb{R}$ in der Form
+$v^2=u^3+Au+B$ mit Nullstellen $u_1$, $u_2$ und $u_3$ des
+kubischen Polynoms auf der rechten Seite.
+Die blauen Punkte und Geraden illustrieren die Definition der
+Gruppenoperation in der elliptischen Kurve.
+\label{buch:crypto:fig:elliptischekurve}}
+\end{figure}
+Abbildung~\ref{buch:crypto:fig:elliptischekurve}
+zeigt eine elliptische Kurve in der Ebene.
+
+\subsubsection{Geometrische Definition der Gruppenoperation}
+In der speziellen Form \ref{buch:crypto:ellvereinfacht} ist die
+elliptische Kurve symmetrisch unter Spiegelung an der $u$-Achse.
+Die Spiegelung ist eine Involution, zweimalige Ausführung führt auf
+den ursprünglichen Punkt zurück.
+Die Inverse in einer Gruppe hat diese Eigenschaft auch, es ist
+daher naheliegend, den gespiegelten Punkt als die Inverse eines
+Elementes zu nehmen.
+
+Eine Gerade durch zwei Punkte der
+in Abbildung~\ref{buch:crypto:fig:elliptischekurve}
+dargestellten Kurve schneidet die Kurve ein drittes Mal.
+Die Gruppenoperation wird so definiert, dass drei Punkte der Kurve
+auf einer Geraden das Gruppenprodukt $e$ haben.
+Da aus $g_1g_2g_3=e$ folgt $g_3=(g_1g_2)^{-1}$ oder
+$g_1g_2=g_3^{-1}$, erhält man das Gruppenprodukt zweier Elemente
+auf der elliptischen Kurve indem erst den dritten Schnittpunkt
+ermittelt und diesen dann an der $u$-Achse spiegelt.
+
+Die geometrische Konstruktion schlägt fehl, wenn $g_1=g_2$ ist.
+In diesem Fall kann man die Tangente im Punkt $g_1$ an die Kurve
+verwenden.
+Dieser Fall tritt zum Beispiel auch in den drei Punkten
+$(u_1,0)$, $(u_2,0)$ und $(u_3,0)$ ein.
+
+Um das neutrale Element der Gruppe zu finden, können wir
+zwei Punkte $g$ und $g^{-1}$ miteinander verknüpfen.
+Die Gerade durch $g$ und $g^{-1}$ schneidet aber die Kurve
+kein drittes Mal.
+Ausserdem sind alle Geraden durch $g$ und $g^{-1}$ für verschiedene
+$g$ parallel.
+Das neutrale Element entspricht also einem unendlich weit entfernten Punkt.
+Das neutrale Element entsteht immer dann als Produkt, wenn zwei
+Punkte die gleiche $u$-Koordinaten haben.
+
+\subsubsection{Gruppenoperation, algebraische Konstruktion}
+Nach den geometrischen Vorarbeiten zur Definition der Gruppenoperation
+kann können wir die Konstruktion jetzt algebraisch umsetzen.
+
+Zunächst überlegen wir uns wieder eine Involution, welche als Inverse
+dienen kann.
+Dazu beachten wir, dass die linke Seite der definierenden Gleichung
+\begin{equation}
+Y^2+XY=X^3-aX+b.
+\label{buch:crypto:eqn:grupopgl}
+\end{equation}
+auch als $Y(Y+X)$ geschrieben werden kann.
+Die Abbildung $Y\mapsto -X-Y$ macht daraus
+\[
+(-X-Y)(-X-Y+X)=(X+Y)Y,
+\]
+dies ist also die gesuchte Involution.
+
+Seien also $g_1=(x_1,y_1)$ und $g_2=(x_2,y_2)$ zwei verschiedene Lösungen
+der Gleichung \eqref{buch:crypto:eqn:grupopgl}
+Als erstes brauchen wir eine Gleichung für die Gerade durch die beiden
+Punkte.
+Sei also $l(X,Y)$ eine Linearform derart, dass $l(g_1)=d$ und $l(g_2)=d$
+für ein geeignetes $d\in\Bbbk$.
+Dann gilt auch für die Punkte
+\[
+g(t) = tg_1 + (1-t)g_2
+\qquad\Rightarrow\qquad
+l(g(t))
+=
+tl(g_1) + (1-t)l(g_2)
+=
+tc+(1-t)c
+=
+(t+1-t)c
+=c,
+\]
+jeder Punkt der Geraden durch $g_1$ und $g_2$ lässt sich in dieser Form
+schreiben.
+
+Setzt man jetzt $g(t)$ in die Gleichung ein, erhält man eine kubische
+Gleichung in $t$, von der wir bereits zwei Nullstellen kennen, nämlich
+$0$ und $1$.
+Die kubische Gleichung muss also durch $t$ und $(t-1)$ teilbar sein.
+Diese Berechnung kann man einfach in einem Computeralgebrasystem
+durchführen.
+Das Polynom ist
+\[
+p(t)
+=
+\]
+Nach Division durch $t(t-1)$ erhält man als den Quotienten
+\begin{align*}
+q(t)
+&=
+(y_2-y_1)^2
++
+(y_2-y_1) (x_2-x_1)
++
+t(x_2-x_1)^3
+-
+2x_2^3+3x_1x_2^2-x_1^3
+\end{align*}
+und den Rest
+\[
+r(t)
+=
+t(y_1^2+x_1y_1-x_1^3-ax_1-b)
++
+(1-t)(y_2^2+x_2y_2-x_2^3-ax_2-b).
+\]
+Die Klammerausdrücke verschwinden, da die sie gleichbedeutend damit sind,
+dass die Punkte Lösungen von \eqref{buch:crypto:eqn:grupopgl} sind.
+
+Für den dritten Punkt auf der Geraden muss $t$ so gewählt werden, dass
+$q(t)=0$ ist.
+Dies ist aber eine lineare Gleichung mit der Lösung
+\begin{align*}
+t
+&=
+-\frac{
+(y_1-y_2)^2
++
+(y_2-y_1)(x_2-x_1)
+-2x_2^3+3x_1x_2^2-x_1^3
+}{(x_2-x_1)^3}
+.
+\end{align*}
+Setzt man dies $g(t)$ ein, erhält man für die Koordinaten des dritten
+Punktes $g_3$ die Werte
+\begin{align}
+x_3
+&=
+\frac{
+(y_2-y_1)^2(x_2-x_1) + (y_2-y_1)(x_2-x_1)^2
+-(x_2^4+x_1^4)
+}{
+(x_2-x_1)^3
+}
+\label{buch:crypto:eqn:x3}
+\\
+y_3
+&=
+\frac{
+(y_2-y_1)^3
++(x_2-x_1)(y_2-y_1)^2
+-(x_{2}-x_{1})^3 ( y_{2} - y_{1})
+-(x_{2}-x_{1})^2 ( x_{1} y_{2}- x_{2} y_{1})
+}{
+(x_2-x_1)^3
+}
+\label{buch:crypto:eqn:y3}
+\end{align}
+Die Gleichungen
+\eqref{buch:crypto:eqn:x3}
+und
+\eqref{buch:crypto:eqn:y3}
+ermöglichen also, das Element $g_1g_2^{-1}$ zu berechnen.
+Interessant daran ist, dass in den Formeln die Konstanten $a$ und $b$
+gar nicht vorkommen.
+
+Es bleibt noch der wichtige Fall des Quadrierens in der Gruppe zu
+behandeln, also den Fall $g_1=g_2$.
+In diese Fall sind die Formeln
+\eqref{buch:crypto:eqn:x3}
+und
+\eqref{buch:crypto:eqn:y3}
+ganz offensichtlich nicht anwendbar.
+Die geometrische Anschauung hat nahegelegt, die Tangent an die Kurve
+im Punkt $g_1$ zu nehmen.
+In $\mathbb{R}$ würde man dafür einen Grenzübergang $g_2\to g_1$ machen,
+aber in einem endlichen Körper ist dies natürlich nicht möglich.
+
+Wir schreiben die Gerade als Parameterdarstellung in der Form
+\(
+t\mapsto g(t)= (x_1+ut, y_1+vt)
+\)
+für beliebige Parameter in $\Bbbk$.
+Die Werte $u_1$ und $u_2$ müssen so gewählt werden, dass $g(t)$ eine
+Tangente wird.
+Setzt man $g(t)$ in die Gleichung~\eqref{buch:crypto:eqn:grupopgl} ein,
+entsteht ein kubische Gleichung, die genau dann eine doppelte Nullstelle
+bei $0$ hat, wenn $u,v$ die Tangentenrichtung beschreiben.
+Einsetzen von $g(t)$ in \eqref{buch:crypto:eqn:grupopgl}
+ergibt die Gleichung
+\begin{align}
+0
+&=
+-u^3t^3
++
+(-3u^2x_{1}+v^2+uv)t^2
++
+(2vy_1+uy_1-3ux_1^2+vx_1-au)t
++
+(y_1^2+x_1y_1-x_1^3-ax_1-b)
+\label{buch:crypto:eqn:tangente1}
+\end{align}
+Damit bei $t=0$ eine doppelte Nullstelle mussen die letzten beiden
+Koeffizienten verschwinden, dies führt auf die Gleichungen
+\begin{align}
+y_1^2+x_1y_1&=x_1^3+ax_1+b
+\label{buch:crypto:eqn:rest1}
+\\
+(2y_1
++x_1)v
++(y_1
+-3x_1^2
+-a)u
+&=0
+\label{buch:crypto:eqn:rest2}
+\end{align}
+Die erste Gleichung \eqref{buch:crypto:eqn:rest1} drückt aus,
+dass $g_1$ ein Punkt der Kurve ist, sie ist automatisch erfüllt.
+
+Die zweite Gleichung
+\eqref{buch:crypto:eqn:rest2}
+legt das Verhältnis von $u$ und $v$, also die
+\label{buch:crypto:eqn:rest2}
+Tangentenrichtung fest.
+Eine mögliche Lösung ist
+\begin{equation}
+\begin{aligned}
+u &= x_1+2y_1
+\\
+v &= -y_1+3x_1^2+a.
+\end{aligned}
+\label{buch:crypto:eqn:uv}
+\end{equation}
+
+Der Quotient ist ein lineares Polynom in $t$, die Nullstelle parametrisiert
+den Punkt, der $(g_1)^{-2}$ entspricht.
+Der zugehörige Wert von $t$ ist
+\begin{equation}
+t=-\frac{3u^2x_1-v^2-uv}{u^3}.
+\label{buch:crypto:eqn:t}
+\end{equation}
+
+
+Setzt man
+\label{buch:crypto:eqn:t}
+und
+\eqref{buch:crypto:eqn:uv}
+in $g(t)$ ein, erhält man sehr komplizierte Ausdrücke für den dritten Punkt.
+Wir verzichten darauf, diese Ausdrücke hier aufzuschreiben.
+In der Praxis wird man in einem Körper der Charakteristik 2 arbeiten.
+In diesem Körper werden alle geraden Koeffizienten zu $0$, alle ungeraden
+Koeffizienten werden unabhängig vom Vorzeichen zu $1$.
+Damit bekommt man die folgenden, sehr viel übersichtlicheren Ausdrücke
+für den dritten Punkt:
+\begin{equation}
+\begin{aligned}
+x
+&=
+-\frac{
+y_1^2+x_1y_1+x_1^4+x_1^3+ax_1-a^2
+ }{
+x_1^2
+}
+\\
+y
+&=
+\frac{
+y_1^3+(x_1^2+x_1+a)y_1^2+(x_1^4 +a^2)y_1+x_1^6+ax_1^4+ax_1^3+a^2x_1^2+a^2x_1+a^3
+}{
+ x_1^3
+}
+\end{aligned}
+\label{buch:crypto:eqn:tangentechar2}
+\end{equation}
+Damit haben wir einen vollständigen Formelsatz für die Berechnung der
+Gruppenoperation in der elliptischen Kurve mindestens für den praktisch
+relevanten Fall einer Kurve über einem Körper der Charakteristik $2$.
+
+\begin{satz}
+Die elliptische Kurve
+\[
+E_{a,b}(\mathbb{F}_{p^l})
+=
+\{
+(X,Y)\in\mathbb{F}_{p^l}
+\;|\;
+Y^2+XY = X^3-aX-b
+\}
+\]
+trägt eine Gruppenstruktur, die wie folgt definiert ist:
+\begin{enumerate}
+\item Der Punkt $(0,0)$ entspricht dem neutralen Element.
+\item Das inverse Element von $(x,y)$ ist $(-x,-y-x)$.
+\item Für zwei verschiedene Punkte $g_1$ und $g_2$ kann $g_3=(g_1g_2)^{-1}$
+mit Hilfe der Formeln
+\eqref{buch:crypto:eqn:x3}
+und
+\eqref{buch:crypto:eqn:y3}
+gefunden werden.
+\item Für einen Punkt $g_1$ kann $g_3=g_1^{-2}$ in Charakteristik $2$ mit
+Hilfe der Formeln
+\eqref{buch:crypto:eqn:tangentechar2}
+gefunden werden.
+\end{enumerate}
+Diese Operationen machen $E_{a,b}(\mathbb{F}_{p^l})$ zu einer endlichen
+abelschen Gruppe.
+\end{satz}
+
+\subsubsection{Beispiele}
+% XXX
+TODO: elliptische Kurven in IPsec: Oakley Gruppen
+
+\subsubsection{Diffie-Hellman in einer elliptischen Kurve}
+% XXX
+TODO: $g^x$ in einer elliptischen Kurve
+
+
+
diff --git a/buch/chapters/90-crypto/images/Makefile b/buch/chapters/90-crypto/images/Makefile
index 5df9178..f4bed14 100644
--- a/buch/chapters/90-crypto/images/Makefile
+++ b/buch/chapters/90-crypto/images/Makefile
@@ -1,29 +1,29 @@
-#
-# Makefile -- build images for crypto chapter
-#
-# (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
-#
-all: dh.pdf elliptic.pdf schieberegister.pdf multiplikation.pdf sbox.pdf \
- shift.pdf keys.pdf
-
-dh.pdf: dh.tex
- pdflatex dh.tex
-
-elliptic.pdf: elliptic.tex
- pdflatex elliptic.tex
-
-schieberegister.pdf: schieberegister.tex
- pdflatex schieberegister.tex
-
-multiplikation.pdf: multiplikation.tex
- pdflatex multiplikation.tex
-
-sbox.pdf: sbox.tex
- pdflatex sbox.tex
-
-shift.pdf: shift.tex
- pdflatex shift.tex
-
-keys.pdf: keys.tex
- pdflatex keys.tex
-
+#
+# Makefile -- build images for crypto chapter
+#
+# (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
+#
+all: dh.pdf elliptic.pdf schieberegister.pdf multiplikation.pdf sbox.pdf \
+ shift.pdf keys.pdf
+
+dh.pdf: dh.tex
+ pdflatex dh.tex
+
+elliptic.pdf: elliptic.tex
+ pdflatex elliptic.tex
+
+schieberegister.pdf: schieberegister.tex
+ pdflatex schieberegister.tex
+
+multiplikation.pdf: multiplikation.tex
+ pdflatex multiplikation.tex
+
+sbox.pdf: sbox.tex
+ pdflatex sbox.tex
+
+shift.pdf: shift.tex
+ pdflatex shift.tex
+
+keys.pdf: keys.tex
+ pdflatex keys.tex
+
diff --git a/buch/chapters/90-crypto/images/keys.tex b/buch/chapters/90-crypto/images/keys.tex
index 4b1b566..d556b7c 100644
--- a/buch/chapters/90-crypto/images/keys.tex
+++ b/buch/chapters/90-crypto/images/keys.tex
@@ -1,121 +1,121 @@
-%
-% keys.tex -- template for standalon tikz images
-%
-% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
-%
-\documentclass[tikz]{standalone}
-\usepackage{amsmath}
-\usepackage{times}
-\usepackage{txfonts}
-\usepackage{pgfplots}
-\usepackage{csvsimple}
-\usetikzlibrary{arrows,intersections,math}
-\begin{document}
-\def\skala{1}
-\begin{tikzpicture}[>=latex,thick,scale=\skala]
-\definecolor{darkgreen}{rgb}{0,0.6,0}
-\def\s{0.5}
-\def\punkt#1#2{({(#1)*\s},{(#2)*\s})}
-\def\wort#1#2#3{
- \fill[color=#3] \punkt{#1}{#2} rectangle \punkt{(#1+1)}{(#2+4)};
- \draw \punkt{#1}{#2} rectangle \punkt{(#1+1)}{(#2+4)};
-}
-
-\def\summe{
- \foreach \x in {0,3,...,21}{
- \draw[->] \punkt{(\x+0.5)}{-0.1} -- \punkt{(\x+0.5)}{-2.1};
- \draw \punkt{(\x+0.5)}{-2.5} circle[radius={0.3*\s}];
- \draw \punkt{(\x+0.5-0.2)}{-2.5}
- --
- \punkt{(\x+0.5+0.2)}{-2.5};
- \draw \punkt{(\x+0.5)}{-2.5+0.2}
- --
- \punkt{(\x+0.5)}{-2.5-0.2};
- \draw[->] \punkt{(\x+0.5)}{-2.9} -- \punkt{(\x+0.5)}{-4.9};
- }
- \foreach \x in {0,3,...,18}{
- \draw[->] \punkt{(\x+1.1)}{-7} -- \punkt{(\x+2)}{-7}
- -- \punkt{(\x+2)}{-2.5} -- \punkt{(\x+3.1)}{-2.5};
- }
- \fill[color=white]
- \punkt{(9+1.25)}{-5.5}
- rectangle
- \punkt{(9+2.75)}{-4.00};
- \draw
- \punkt{(9+1.25)}{-5.5}
- rectangle
- \punkt{(9+2.75)}{-4.00};
- \node at \punkt{(9+2)}{-4.75} {$S$};
-}
-
-\def\blocks#1{
- \foreach \x in {0,3,...,21}{
- \wort{\x}{0}{#1}
- }
-}
-
-\def\schlange#1{
- \draw[->] \punkt{22.1}{2} -- \punkt{23}{2}
- -- \punkt{23}{-1.0} -- \punkt{-3}{-1.0}
- -- \punkt{-3}{-8} -- \punkt{-1}{-8} -- \punkt{-1}{-2.5}
- -- \punkt{0.1}{-2.5};
- ;
- \fill[color=white] \punkt{-3.75}{-1.75} rectangle \punkt{-2.25}{-3.25};
- \draw \punkt{-3.75}{-1.75} rectangle \punkt{-2.25}{-3.25};
- \node at \punkt{-3}{-2.5} {$\pi$};
-
- \fill[color=white] \punkt{-3.75}{-3.75} rectangle \punkt{-2.25}{-5.25};
- \draw \punkt{-3.75}{-3.75} rectangle \punkt{-2.25}{-5.25};
- \node at \punkt{-3}{-4.5} {$S$};
-
- \fill[color=white] \punkt{-3.75}{-5.75} rectangle \punkt{-2.25}{-7.25};
- \draw \punkt{-3.75}{-5.75} rectangle \punkt{-2.25}{-7.25};
- \node at \punkt{-3}{-6.5} {$r_{#1}$};
-}
-
-\begin{scope}
- \blocks{blue!20}
- \foreach \x in {0,...,7}{
- \node at \punkt{(3*\x+0.5)}{2} {$K_\x$};
- }
- \schlange{1}
- \summe
-\end{scope}
-
-\begin{scope}[yshift=-4.5cm]
- \blocks{darkgreen!20}
- \foreach \x in {8,...,15}{
- \node at \punkt{(3*(\x-8)+0.5)}{2} {$K_{\x}$};
- }
- \schlange{2}
- \summe
-\end{scope}
-
-\begin{scope}[yshift=-9cm]
- \blocks{darkgreen!20}
- \foreach \x in {16,...,23}{
- \node at \punkt{(3*(\x-16)+0.5)}{2} {$K_{\x}$};
- }
- \schlange{3}
- \summe
-\end{scope}
-
-\begin{scope}[yshift=-13.5cm]
- \blocks{darkgreen!20}
- \foreach \x in {24,...,31}{
- \node at \punkt{(3*(\x-24)+0.5)}{2} {$K_{\x}$};
- }
- \foreach \x in {0,3,...,21}{
- \draw[->,color=gray]
- \punkt{(\x+0.5)}{-0.1} -- \punkt{(\x+0.5)}{-2.1};
- \node[color=gray] at \punkt{(\x+0.5)}{-2.1} [below] {$\vdots$};
- }
- \draw[color=gray] \punkt{22.1}{2} -- \punkt{23}{2}
- -- \punkt{23}{-1.0} -- \punkt{-3}{-1.0}
- -- \punkt{-3}{-2.1};
- \node[color=gray] at \punkt{-3}{-2.1} [below] {$\vdots$};
-\end{scope}
-
-\end{tikzpicture}
-\end{document}
-
+%
+% keys.tex -- template for standalon tikz images
+%
+% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
+%
+\documentclass[tikz]{standalone}
+\usepackage{amsmath}
+\usepackage{times}
+\usepackage{txfonts}
+\usepackage{pgfplots}
+\usepackage{csvsimple}
+\usetikzlibrary{arrows,intersections,math}
+\begin{document}
+\def\skala{1}
+\begin{tikzpicture}[>=latex,thick,scale=\skala]
+\definecolor{darkgreen}{rgb}{0,0.6,0}
+\def\s{0.5}
+\def\punkt#1#2{({(#1)*\s},{(#2)*\s})}
+\def\wort#1#2#3{
+ \fill[color=#3] \punkt{#1}{#2} rectangle \punkt{(#1+1)}{(#2+4)};
+ \draw \punkt{#1}{#2} rectangle \punkt{(#1+1)}{(#2+4)};
+}
+
+\def\summe{
+ \foreach \x in {0,3,...,21}{
+ \draw[->] \punkt{(\x+0.5)}{-0.1} -- \punkt{(\x+0.5)}{-2.1};
+ \draw \punkt{(\x+0.5)}{-2.5} circle[radius={0.3*\s}];
+ \draw \punkt{(\x+0.5-0.2)}{-2.5}
+ --
+ \punkt{(\x+0.5+0.2)}{-2.5};
+ \draw \punkt{(\x+0.5)}{-2.5+0.2}
+ --
+ \punkt{(\x+0.5)}{-2.5-0.2};
+ \draw[->] \punkt{(\x+0.5)}{-2.9} -- \punkt{(\x+0.5)}{-4.9};
+ }
+ \foreach \x in {0,3,...,18}{
+ \draw[->] \punkt{(\x+1.1)}{-7} -- \punkt{(\x+2)}{-7}
+ -- \punkt{(\x+2)}{-2.5} -- \punkt{(\x+3.1)}{-2.5};
+ }
+ \fill[color=white]
+ \punkt{(9+1.25)}{-5.5}
+ rectangle
+ \punkt{(9+2.75)}{-4.00};
+ \draw
+ \punkt{(9+1.25)}{-5.5}
+ rectangle
+ \punkt{(9+2.75)}{-4.00};
+ \node at \punkt{(9+2)}{-4.75} {$S$};
+}
+
+\def\blocks#1{
+ \foreach \x in {0,3,...,21}{
+ \wort{\x}{0}{#1}
+ }
+}
+
+\def\schlange#1{
+ \draw[->] \punkt{22.1}{2} -- \punkt{23}{2}
+ -- \punkt{23}{-1.0} -- \punkt{-3}{-1.0}
+ -- \punkt{-3}{-8} -- \punkt{-1}{-8} -- \punkt{-1}{-2.5}
+ -- \punkt{0.1}{-2.5};
+ ;
+ \fill[color=white] \punkt{-3.75}{-1.75} rectangle \punkt{-2.25}{-3.25};
+ \draw \punkt{-3.75}{-1.75} rectangle \punkt{-2.25}{-3.25};
+ \node at \punkt{-3}{-2.5} {$\pi$};
+
+ \fill[color=white] \punkt{-3.75}{-3.75} rectangle \punkt{-2.25}{-5.25};
+ \draw \punkt{-3.75}{-3.75} rectangle \punkt{-2.25}{-5.25};
+ \node at \punkt{-3}{-4.5} {$S$};
+
+ \fill[color=white] \punkt{-3.75}{-5.75} rectangle \punkt{-2.25}{-7.25};
+ \draw \punkt{-3.75}{-5.75} rectangle \punkt{-2.25}{-7.25};
+ \node at \punkt{-3}{-6.5} {$r_{#1}$};
+}
+
+\begin{scope}
+ \blocks{blue!20}
+ \foreach \x in {0,...,7}{
+ \node at \punkt{(3*\x+0.5)}{2} {$K_\x$};
+ }
+ \schlange{1}
+ \summe
+\end{scope}
+
+\begin{scope}[yshift=-4.5cm]
+ \blocks{darkgreen!20}
+ \foreach \x in {8,...,15}{
+ \node at \punkt{(3*(\x-8)+0.5)}{2} {$K_{\x}$};
+ }
+ \schlange{2}
+ \summe
+\end{scope}
+
+\begin{scope}[yshift=-9cm]
+ \blocks{darkgreen!20}
+ \foreach \x in {16,...,23}{
+ \node at \punkt{(3*(\x-16)+0.5)}{2} {$K_{\x}$};
+ }
+ \schlange{3}
+ \summe
+\end{scope}
+
+\begin{scope}[yshift=-13.5cm]
+ \blocks{darkgreen!20}
+ \foreach \x in {24,...,31}{
+ \node at \punkt{(3*(\x-24)+0.5)}{2} {$K_{\x}$};
+ }
+ \foreach \x in {0,3,...,21}{
+ \draw[->,color=gray]
+ \punkt{(\x+0.5)}{-0.1} -- \punkt{(\x+0.5)}{-2.1};
+ \node[color=gray] at \punkt{(\x+0.5)}{-2.1} [below] {$\vdots$};
+ }
+ \draw[color=gray] \punkt{22.1}{2} -- \punkt{23}{2}
+ -- \punkt{23}{-1.0} -- \punkt{-3}{-1.0}
+ -- \punkt{-3}{-2.1};
+ \node[color=gray] at \punkt{-3}{-2.1} [below] {$\vdots$};
+\end{scope}
+
+\end{tikzpicture}
+\end{document}
+
diff --git a/buch/chapters/90-crypto/images/multiplikation.tex b/buch/chapters/90-crypto/images/multiplikation.tex
index dd59097..27c4329 100644
--- a/buch/chapters/90-crypto/images/multiplikation.tex
+++ b/buch/chapters/90-crypto/images/multiplikation.tex
@@ -1,464 +1,464 @@
-%
-% multiplikation.tex --
-%
-% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
-%
-\documentclass[tikz]{standalone}
-\usepackage{amsmath}
-\usepackage{times}
-\usepackage{txfonts}
-\usepackage{pgfplots}
-\usepackage{csvsimple}
-\usetikzlibrary{arrows,intersections,math}
-\begin{document}
-\def\skala{1}
-\begin{tikzpicture}[>=latex,thick,scale=\skala]
-
-\definecolor{darkgreen}{rgb}{0,0.6,0}
-
-\def\s{0.45}
-
-\def\punkt#1#2{({#1*\s},{#2*\s})}
-
-\def\pfeile{
- \foreach \x in {0.5,1.5,...,7.5}{
- \draw[->,color=blue] \punkt{\x}{-2.1} -- \punkt{(\x-1)}{-3.3};
- }
-}
-
-\begin{scope}[yshift=0.1cm]
- \node at \punkt{0}{0.5} [left] {$p(X)=\mathstrut$};
- \draw \punkt{0}{0} rectangle \punkt{8}{1};
- \foreach \x in {1,...,7}{
- \draw \punkt{\x}{0} -- \punkt{\x}{1};
- }
- \node at \punkt{0.5}{0.5} {\texttt{1}};
- \node at \punkt{1.5}{0.5} {\texttt{0}};
- \node at \punkt{2.5}{0.5} {\texttt{0}};
- \node at \punkt{3.5}{0.5} {\texttt{1}};
- \node at \punkt{4.5}{0.5} {\texttt{0}};
- \node at \punkt{5.5}{0.5} {\texttt{1}};
- \node at \punkt{6.5}{0.5} {\texttt{0}};
- \node at \punkt{7.5}{0.5} {\texttt{1}};
- \foreach \x in {0.5,1.5,...,7.5}{
- \draw[->,color=blue] \punkt{\x}{-0.1} -- \punkt{(\x-1)}{-1.3};
- }
-\end{scope}
-
-\begin{scope}[yshift=-1cm]
- \draw[<-] \punkt{8.2}{-1.3} arc (-30:30:1.8);
- \node at \punkt{9.3}{0.6} {$\mathstrut\cdot X$};
- \fill[color=blue!20] \punkt{-1}{0} rectangle \punkt{0}{1};
- \draw \punkt{0}{0} rectangle \punkt{8}{1};
- \foreach \x in {1,...,7}{
- \draw \punkt{\x}{0} -- \punkt{\x}{1};
- }
- \node[color=darkgreen] at \punkt{-0.5}{0.5} {\texttt{1}};
- \node at \punkt{0.5}{0.5} {\texttt{0}};
- \node at \punkt{1.5}{0.5} {\texttt{0}};
- \node at \punkt{2.5}{0.5} {\texttt{1}};
- \node at \punkt{3.5}{0.5} {\texttt{0}};
- \node at \punkt{4.5}{0.5} {\texttt{1}};
- \node at \punkt{5.5}{0.5} {\texttt{0}};
- \node at \punkt{6.5}{0.5} {\texttt{1}};
- \node at \punkt{7.5}{0.5} {\texttt{0}};
-
- \draw[->,color=darkgreen]
- \punkt{-0.5}{0.1} -- \punkt{-0.5}{-0.5} -- \punkt{3.1}{-0.5};
- \node[color=darkgreen] at \punkt{3.5}{-0.5} {\texttt{1}};
- \node[color=darkgreen] at \punkt{4.5}{-0.5} {\texttt{1}};
- \node[color=darkgreen] at \punkt{6.5}{-0.5} {\texttt{1}};
- \node[color=darkgreen] at \punkt{7.5}{-0.5} {\texttt{1}};
-
- \draw \punkt{0}{-2} rectangle \punkt{8}{-1};
- \foreach \x in {1,...,7}{
- \draw \punkt{\x}{-2} -- \punkt{\x}{-1};
- }
- \node at \punkt{0.5}{-1.5} {\texttt{0}};
- \node at \punkt{1.5}{-1.5} {\texttt{0}};
- \node at \punkt{2.5}{-1.5} {\texttt{1}};
- \node at \punkt{3.5}{-1.5} {\texttt{1}};
- \node at \punkt{4.5}{-1.5} {\texttt{0}};
- \node at \punkt{5.5}{-1.5} {\texttt{0}};
- \node at \punkt{6.5}{-1.5} {\texttt{0}};
- \node at \punkt{7.5}{-1.5} {\texttt{1}};
-
- \pfeile
-\end{scope}
-
-\begin{scope}[yshift=-3cm]
- \draw[<-] \punkt{8.2}{-1.3} arc (-30:30:1.8);
- \node at \punkt{9.3}{0.6} {$\mathstrut\cdot X$};
- \fill[color=blue!20] \punkt{-1}{0} rectangle \punkt{0}{1};
- \draw \punkt{0}{0} rectangle \punkt{8}{1};
- \foreach \x in {1,...,7}{
- \draw \punkt{\x}{0} -- \punkt{\x}{1};
- }
- \node[color=darkgreen] at \punkt{-0.5}{0.5} {\texttt{0}};
- \node at \punkt{0.5}{0.5} {\texttt{0}};
- \node at \punkt{1.5}{0.5} {\texttt{1}};
- \node at \punkt{2.5}{0.5} {\texttt{1}};
- \node at \punkt{3.5}{0.5} {\texttt{0}};
- \node at \punkt{4.5}{0.5} {\texttt{0}};
- \node at \punkt{5.5}{0.5} {\texttt{0}};
- \node at \punkt{6.5}{0.5} {\texttt{1}};
- \node at \punkt{7.5}{0.5} {\texttt{0}};
-
-% \draw[->,color=darkgreen]
-% \punkt{-0.5}{0.1} -- \punkt{-0.5}{-0.5} -- \punkt{3.1}{-0.5};
-% \node[color=darkgreen] at \punkt{3.5}{-0.5} {\texttt{1}};
-% \node[color=darkgreen] at \punkt{4.5}{-0.5} {\texttt{1}};
-% \node[color=darkgreen] at \punkt{6.5}{-0.5} {\texttt{1}};
-% \node[color=darkgreen] at \punkt{7.5}{-0.5} {\texttt{1}};
- \node[color=darkgreen] at \punkt{4}{-0.5} {$\|$};
-
- \draw \punkt{0}{-2} rectangle \punkt{8}{-1};
- \foreach \x in {1,...,7}{
- \draw \punkt{\x}{-2} -- \punkt{\x}{-1};
- }
- \node at \punkt{0.5}{-1.5} {\texttt{0}};
- \node at \punkt{1.5}{-1.5} {\texttt{1}};
- \node at \punkt{2.5}{-1.5} {\texttt{1}};
- \node at \punkt{3.5}{-1.5} {\texttt{0}};
- \node at \punkt{4.5}{-1.5} {\texttt{0}};
- \node at \punkt{5.5}{-1.5} {\texttt{0}};
- \node at \punkt{6.5}{-1.5} {\texttt{1}};
- \node at \punkt{7.5}{-1.5} {\texttt{0}};
-
- \pfeile
-\end{scope}
-
-\begin{scope}[yshift=-5cm]
- \draw[<-] \punkt{8.2}{-1.3} arc (-30:30:1.8);
- \node at \punkt{9.3}{0.6} {$\mathstrut\cdot X$};
- \fill[color=blue!20] \punkt{-1}{0} rectangle \punkt{0}{1};
- \draw \punkt{0}{0} rectangle \punkt{8}{1};
- \foreach \x in {1,...,7}{
- \draw \punkt{\x}{0} -- \punkt{\x}{1};
- }
- \node[color=darkgreen] at \punkt{-0.5}{0.5} {\texttt{0}};
- \node at \punkt{0.5}{0.5} {\texttt{1}};
- \node at \punkt{1.5}{0.5} {\texttt{1}};
- \node at \punkt{2.5}{0.5} {\texttt{0}};
- \node at \punkt{3.5}{0.5} {\texttt{0}};
- \node at \punkt{4.5}{0.5} {\texttt{0}};
- \node at \punkt{5.5}{0.5} {\texttt{1}};
- \node at \punkt{6.5}{0.5} {\texttt{0}};
- \node at \punkt{7.5}{0.5} {\texttt{0}};
-
-% \draw[->,color=darkgreen]
-% \punkt{-0.5}{0.1} -- \punkt{-0.5}{-0.5} -- \punkt{3.1}{-0.5};
-% \node[color=darkgreen] at \punkt{3.5}{-0.5} {\texttt{1}};
-% \node[color=darkgreen] at \punkt{4.5}{-0.5} {\texttt{1}};
-% \node[color=darkgreen] at \punkt{6.5}{-0.5} {\texttt{1}};
-% \node[color=darkgreen] at \punkt{7.5}{-0.5} {\texttt{1}};
- \node[color=darkgreen] at \punkt{4}{-0.5} {$\|$};
-
- \draw \punkt{0}{-2} rectangle \punkt{8}{-1};
- \foreach \x in {1,...,7}{
- \draw \punkt{\x}{-2} -- \punkt{\x}{-1};
- }
- \node at \punkt{0.5}{-1.5} {\texttt{1}};
- \node at \punkt{1.5}{-1.5} {\texttt{1}};
- \node at \punkt{2.5}{-1.5} {\texttt{0}};
- \node at \punkt{3.5}{-1.5} {\texttt{0}};
- \node at \punkt{4.5}{-1.5} {\texttt{0}};
- \node at \punkt{5.5}{-1.5} {\texttt{1}};
- \node at \punkt{6.5}{-1.5} {\texttt{0}};
- \node at \punkt{7.5}{-1.5} {\texttt{0}};
-
- \pfeile
-\end{scope}
-
-\begin{scope}[yshift=-7cm]
- \draw[<-] \punkt{8.2}{-1.3} arc (-30:30:1.8);
- \node at \punkt{9.3}{0.6} {$\mathstrut\cdot X$};
- \fill[color=blue!20] \punkt{-1}{0} rectangle \punkt{0}{1};
- \draw \punkt{0}{0} rectangle \punkt{8}{1};
- \foreach \x in {1,...,7}{
- \draw \punkt{\x}{0} -- \punkt{\x}{1};
- }
- \node[color=darkgreen] at \punkt{-0.5}{0.5} {\texttt{1}};
- \node at \punkt{0.5}{0.5} {\texttt{1}};
- \node at \punkt{1.5}{0.5} {\texttt{0}};
- \node at \punkt{2.5}{0.5} {\texttt{0}};
- \node at \punkt{3.5}{0.5} {\texttt{0}};
- \node at \punkt{4.5}{0.5} {\texttt{1}};
- \node at \punkt{5.5}{0.5} {\texttt{0}};
- \node at \punkt{6.5}{0.5} {\texttt{0}};
- \node at \punkt{7.5}{0.5} {\texttt{0}};
-
- \draw[->,color=darkgreen]
- \punkt{-0.5}{0.1} -- \punkt{-0.5}{-0.5} -- \punkt{3.1}{-0.5};
- \node[color=darkgreen] at \punkt{3.5}{-0.5} {\texttt{1}};
- \node[color=darkgreen] at \punkt{4.5}{-0.5} {\texttt{1}};
- \node[color=darkgreen] at \punkt{6.5}{-0.5} {\texttt{1}};
- \node[color=darkgreen] at \punkt{7.5}{-0.5} {\texttt{1}};
-% \node[color=darkgreen] at \punkt{4}{-0.5} {$\|$};
-
- \draw \punkt{0}{-2} rectangle \punkt{8}{-1};
- \foreach \x in {1,...,7}{
- \draw \punkt{\x}{-2} -- \punkt{\x}{-1};
- }
- \node at \punkt{0.5}{-1.5} {\texttt{1}};
- \node at \punkt{1.5}{-1.5} {\texttt{0}};
- \node at \punkt{2.5}{-1.5} {\texttt{0}};
- \node at \punkt{3.5}{-1.5} {\texttt{1}};
- \node at \punkt{4.5}{-1.5} {\texttt{0}};
- \node at \punkt{5.5}{-1.5} {\texttt{0}};
- \node at \punkt{6.5}{-1.5} {\texttt{1}};
- \node at \punkt{7.5}{-1.5} {\texttt{1}};
-
- \pfeile
-\end{scope}
-
-\begin{scope}[yshift=-9cm]
- \draw[<-] \punkt{8.2}{-1.3} arc (-30:30:1.8);
- \node at \punkt{9.3}{0.6} {$\mathstrut\cdot X$};
- \fill[color=blue!20] \punkt{-1}{0} rectangle \punkt{0}{1};
- \draw \punkt{0}{0} rectangle \punkt{8}{1};
- \foreach \x in {1,...,7}{
- \draw \punkt{\x}{0} -- \punkt{\x}{1};
- }
- \node[color=darkgreen] at \punkt{-0.5}{0.5} {\texttt{1}};
- \node at \punkt{0.5}{0.5} {\texttt{0}};
- \node at \punkt{1.5}{0.5} {\texttt{0}};
- \node at \punkt{2.5}{0.5} {\texttt{1}};
- \node at \punkt{3.5}{0.5} {\texttt{0}};
- \node at \punkt{4.5}{0.5} {\texttt{0}};
- \node at \punkt{5.5}{0.5} {\texttt{1}};
- \node at \punkt{6.5}{0.5} {\texttt{1}};
- \node at \punkt{7.5}{0.5} {\texttt{0}};
-
- \draw[->,color=darkgreen]
- \punkt{-0.5}{0.1} -- \punkt{-0.5}{-0.5} -- \punkt{3.1}{-0.5};
- \node[color=darkgreen] at \punkt{3.5}{-0.5} {\texttt{1}};
- \node[color=darkgreen] at \punkt{4.5}{-0.5} {\texttt{1}};
- \node[color=darkgreen] at \punkt{6.5}{-0.5} {\texttt{1}};
- \node[color=darkgreen] at \punkt{7.5}{-0.5} {\texttt{1}};
-% \node[color=darkgreen] at \punkt{4}{-0.5} {$\|$};
-
- \draw \punkt{0}{-2} rectangle \punkt{8}{-1};
- \foreach \x in {1,...,7}{
- \draw \punkt{\x}{-2} -- \punkt{\x}{-1};
- }
- \node at \punkt{0.5}{-1.5} {\texttt{0}};
- \node at \punkt{1.5}{-1.5} {\texttt{0}};
- \node at \punkt{2.5}{-1.5} {\texttt{1}};
- \node at \punkt{3.5}{-1.5} {\texttt{1}};
- \node at \punkt{4.5}{-1.5} {\texttt{1}};
- \node at \punkt{5.5}{-1.5} {\texttt{1}};
- \node at \punkt{6.5}{-1.5} {\texttt{0}};
- \node at \punkt{7.5}{-1.5} {\texttt{1}};
-
- \pfeile
-\end{scope}
-
-\begin{scope}[yshift=-11cm]
- \draw[<-] \punkt{8.2}{-1.3} arc (-30:30:1.8);
- \node at \punkt{9.3}{0.6} {$\mathstrut\cdot X$};
- \fill[color=blue!20] \punkt{-1}{0} rectangle \punkt{0}{1};
- \draw \punkt{0}{0} rectangle \punkt{8}{1};
- \foreach \x in {1,...,7}{
- \draw \punkt{\x}{0} -- \punkt{\x}{1};
- }
- \node[color=darkgreen] at \punkt{-0.5}{0.5} {\texttt{0}};
- \node at \punkt{0.5}{0.5} {\texttt{0}};
- \node at \punkt{1.5}{0.5} {\texttt{0}};
- \node at \punkt{2.5}{0.5} {\texttt{1}};
- \node at \punkt{3.5}{0.5} {\texttt{1}};
- \node at \punkt{4.5}{0.5} {\texttt{1}};
- \node at \punkt{5.5}{0.5} {\texttt{0}};
- \node at \punkt{6.5}{0.5} {\texttt{1}};
- \node at \punkt{7.5}{0.5} {\texttt{0}};
-
-% \draw[->,color=darkgreen]
-% \punkt{-0.5}{0.1} -- \punkt{-0.5}{-0.5} -- \punkt{3.1}{-0.5};
-% \node[color=darkgreen] at \punkt{3.5}{-0.5} {\texttt{1}};
-% \node[color=darkgreen] at \punkt{4.5}{-0.5} {\texttt{1}};
-% \node[color=darkgreen] at \punkt{6.5}{-0.5} {\texttt{1}};
-% \node[color=darkgreen] at \punkt{7.5}{-0.5} {\texttt{1}};
- \node[color=darkgreen] at \punkt{4}{-0.5} {$\|$};
-
- \draw \punkt{0}{-2} rectangle \punkt{8}{-1};
- \foreach \x in {1,...,7}{
- \draw \punkt{\x}{-2} -- \punkt{\x}{-1};
- }
- \node at \punkt{0.5}{-1.5} {\texttt{0}};
- \node at \punkt{1.5}{-1.5} {\texttt{0}};
- \node at \punkt{2.5}{-1.5} {\texttt{1}};
- \node at \punkt{3.5}{-1.5} {\texttt{1}};
- \node at \punkt{4.5}{-1.5} {\texttt{1}};
- \node at \punkt{5.5}{-1.5} {\texttt{0}};
- \node at \punkt{6.5}{-1.5} {\texttt{1}};
- \node at \punkt{7.5}{-1.5} {\texttt{0}};
-
- \pfeile
-\end{scope}
-
-\begin{scope}[yshift=-13cm]
- \draw[<-] \punkt{8.2}{-1.3} arc (-30:30:1.8);
- \node at \punkt{9.3}{0.6} {$\mathstrut\cdot X$};
- \fill[color=blue!20] \punkt{-1}{0} rectangle \punkt{0}{1};
- \draw \punkt{0}{0} rectangle \punkt{8}{1};
- \foreach \x in {1,...,7}{
- \draw \punkt{\x}{0} -- \punkt{\x}{1};
- }
- \node[color=darkgreen] at \punkt{-0.5}{0.5} {\texttt{0}};
- \node at \punkt{0.5}{0.5} {\texttt{0}};
- \node at \punkt{1.5}{0.5} {\texttt{1}};
- \node at \punkt{2.5}{0.5} {\texttt{1}};
- \node at \punkt{3.5}{0.5} {\texttt{1}};
- \node at \punkt{4.5}{0.5} {\texttt{0}};
- \node at \punkt{5.5}{0.5} {\texttt{1}};
- \node at \punkt{6.5}{0.5} {\texttt{0}};
- \node at \punkt{7.5}{0.5} {\texttt{0}};
-
-% \draw[->,color=darkgreen]
-% \punkt{-0.5}{0.1} -- \punkt{-0.5}{-0.5} -- \punkt{3.1}{-0.5};
-% \node[color=darkgreen] at \punkt{3.5}{-0.5} {\texttt{1}};
-% \node[color=darkgreen] at \punkt{4.5}{-0.5} {\texttt{1}};
-% \node[color=darkgreen] at \punkt{6.5}{-0.5} {\texttt{1}};
-% \node[color=darkgreen] at \punkt{7.5}{-0.5} {\texttt{1}};
- \node[color=darkgreen] at \punkt{4}{-0.5} {$\|$};
-
- \draw \punkt{0}{-2} rectangle \punkt{8}{-1};
- \foreach \x in {1,...,7}{
- \draw \punkt{\x}{-2} -- \punkt{\x}{-1};
- }
- \node at \punkt{0.5}{-1.5} {\texttt{0}};
- \node at \punkt{1.5}{-1.5} {\texttt{1}};
- \node at \punkt{2.5}{-1.5} {\texttt{1}};
- \node at \punkt{3.5}{-1.5} {\texttt{0}};
- \node at \punkt{4.5}{-1.5} {\texttt{1}};
- \node at \punkt{5.5}{-1.5} {\texttt{1}};
- \node at \punkt{6.5}{-1.5} {\texttt{1}};
- \node at \punkt{7.5}{-1.5} {\texttt{1}};
-
-% \pfeile
-\end{scope}
-
-\begin{scope}[xshift=9cm]
-
-\begin{scope}[yshift=0.1cm]
- \draw[->] \punkt{-11.8}{0.5} -- \punkt{-0.1}{0.5};
- \draw \punkt{0}{0} rectangle \punkt{8}{1};
- \foreach \x in {1,...,7}{
- \draw \punkt{\x}{0} -- \punkt{\x}{1};
- }
- \draw \punkt{4}{-0.1} -- \punkt{4}{-3};
- \node at \punkt{0.5}{0.5} {\texttt{1}};
- \node at \punkt{1.5}{0.5} {\texttt{0}};
- \node at \punkt{2.5}{0.5} {\texttt{0}};
- \node at \punkt{3.5}{0.5} {\texttt{1}};
- \node at \punkt{4.5}{0.5} {\texttt{0}};
- \node at \punkt{5.5}{0.5} {\texttt{1}};
- \node at \punkt{6.5}{0.5} {\texttt{0}};
- \node at \punkt{7.5}{0.5} {\texttt{1}};
-\end{scope}
-
-\def\summation#1#2#3#4#5#6#7#8{
- \draw[->] \punkt{4}{2.3} -- \punkt{4}{1};
-
- \draw[->] \punkt{-11.8}{0.5} -- \punkt{3.5}{0.5};
-
- \draw \punkt{4}{0.5} circle[radius=0.2];
- \draw \punkt{4}{0.20} -- \punkt{4}{0.80};
- \draw \punkt{3.7}{0.5} -- \punkt{4.3}{0.5};
-
- \draw[->] \punkt{4}{-0.05} -- \punkt{4}{-0.95};
- \draw \punkt{0}{-2} rectangle \punkt{8}{-1};
- \foreach \x in {1,...,7}{
- \draw \punkt{\x}{-2} -- \punkt{\x}{-1};
- }
-
- \node at \punkt{0.5}{-1.5} {\texttt{#1}};
- \node at \punkt{1.5}{-1.5} {\texttt{#2}};
- \node at \punkt{2.5}{-1.5} {\texttt{#3}};
- \node at \punkt{3.5}{-1.5} {\texttt{#4}};
- \node at \punkt{4.5}{-1.5} {\texttt{#5}};
- \node at \punkt{5.5}{-1.5} {\texttt{#6}};
- \node at \punkt{6.5}{-1.5} {\texttt{#7}};
- \node at \punkt{7.5}{-1.5} {\texttt{#8}};
-}
-
-\begin{scope}[yshift=-1.9cm]
- \summation{1}{0}{0}{1}{0}{1}{0}{1}
-\end{scope}
-
-\begin{scope}[yshift=-3.9cm]
- \summation{1}{1}{1}{1}{0}{1}{1}{1}
-\end{scope}
-
-\begin{scope}[yshift=-5.9cm]
- \summation{1}{1}{1}{1}{0}{1}{1}{1}
-\end{scope}
-
-\begin{scope}[yshift=-7.9cm]
- \summation{0}{1}{1}{0}{0}{1}{0}{0}
-\end{scope}
-
-\begin{scope}[yshift=-9.9cm]
- \summation{0}{1}{0}{1}{1}{0}{0}{1}
-\end{scope}
-
-\begin{scope}[yshift=-11.9cm]
- \summation{0}{1}{0}{1}{1}{0}{0}{1}
-\end{scope}
-
-\begin{scope}[yshift=-13.9cm]
- \summation{0}{0}{1}{1}{0}{1}{1}{0}
- \node at \punkt{0}{-1.5} [left] {$p(X)\cdot q(X)=\mathstrut$};
-\end{scope}
-
-\end{scope}
-
-\begin{scope}[xshift=5cm]
-
-\begin{scope}[yshift=2cm]
- \node at \punkt{0}{0.5} [left] {$q(X)=\mathstrut$};
- \draw \punkt{0}{0} rectangle \punkt{8}{1};
- \foreach \x in {1,...,7}{
- \draw \punkt{\x}{0} -- \punkt{\x}{1};
- }
- \node at \punkt{0.5}{0.5} {\texttt{1}};
- \node at \punkt{1.5}{0.5} {\texttt{0}};
- \node at \punkt{2.5}{0.5} {\texttt{1}};
- \node at \punkt{3.5}{0.5} {\texttt{1}};
- \node at \punkt{4.5}{0.5} {\texttt{0}};
- \node at \punkt{5.5}{0.5} {\texttt{1}};
- \node at \punkt{6.5}{0.5} {\texttt{0}};
- \node at \punkt{7.5}{0.5} {\texttt{1}};
-
- \draw[->] \punkt{7.5}{-0.1} -- ({7.5*\s},{-1.3});
- \node at ({7.5*\s},{-1.2}) [below] {$\mathstrut\cdot\texttt{1}$};
-
- \def\y{1.2}
-
- \draw[->] \punkt{6.5}{-0.1} -- ({6.5*\s},{-1*2-\y-0.1});
- \node at ({6.5*\s},{-1*2-\y}) [below] {$\mathstrut\cdot\texttt{0}$};
-
- \draw[->] \punkt{5.5}{-0.1} -- ({5.5*\s},{-2*2-\y-0.1});
- \node at ({5.5*\s},{-2*2-\y}) [below] {$\mathstrut\cdot\texttt{1}$};
-
- \draw[->] \punkt{4.5}{-0.1} -- ({4.5*\s},{-3*2-\y-0.1});
- \node at ({4.5*\s},{-3*2-\y}) [below] {$\mathstrut\cdot\texttt{0}$};
-
- \draw[->] \punkt{3.5}{-0.1} -- ({3.5*\s},{-4*2-\y-0.1});
- \node at ({3.5*\s},{-4*2-\y}) [below] {$\mathstrut\cdot\texttt{1}$};
-
- \draw[->] \punkt{2.5}{-0.1} -- ({2.5*\s},{-5*2-\y-0.1});
- \node at ({2.5*\s},{-5*2-\y}) [below] {$\mathstrut\cdot\texttt{1}$};
-
- \draw[->] \punkt{1.5}{-0.1} -- ({1.5*\s},{-6*2-\y-0.1});
- \node at ({1.5*\s},{-6*2-\y}) [below] {$\mathstrut\cdot\texttt{0}$};
-
- \draw[->] \punkt{0.5}{-0.1} -- ({0.5*\s},{-7*2-\y-0.1});
- \node at ({0.5*\s},{-7*2-\y}) [below] {$\mathstrut\cdot\texttt{1}$};
-\end{scope}
-
-\end{scope}
-
-\end{tikzpicture}
-\end{document}
-
+%
+% multiplikation.tex --
+%
+% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
+%
+\documentclass[tikz]{standalone}
+\usepackage{amsmath}
+\usepackage{times}
+\usepackage{txfonts}
+\usepackage{pgfplots}
+\usepackage{csvsimple}
+\usetikzlibrary{arrows,intersections,math}
+\begin{document}
+\def\skala{1}
+\begin{tikzpicture}[>=latex,thick,scale=\skala]
+
+\definecolor{darkgreen}{rgb}{0,0.6,0}
+
+\def\s{0.45}
+
+\def\punkt#1#2{({#1*\s},{#2*\s})}
+
+\def\pfeile{
+ \foreach \x in {0.5,1.5,...,7.5}{
+ \draw[->,color=blue] \punkt{\x}{-2.1} -- \punkt{(\x-1)}{-3.3};
+ }
+}
+
+\begin{scope}[yshift=0.1cm]
+ \node at \punkt{0}{0.5} [left] {$p(X)=\mathstrut$};
+ \draw \punkt{0}{0} rectangle \punkt{8}{1};
+ \foreach \x in {1,...,7}{
+ \draw \punkt{\x}{0} -- \punkt{\x}{1};
+ }
+ \node at \punkt{0.5}{0.5} {\texttt{1}};
+ \node at \punkt{1.5}{0.5} {\texttt{0}};
+ \node at \punkt{2.5}{0.5} {\texttt{0}};
+ \node at \punkt{3.5}{0.5} {\texttt{1}};
+ \node at \punkt{4.5}{0.5} {\texttt{0}};
+ \node at \punkt{5.5}{0.5} {\texttt{1}};
+ \node at \punkt{6.5}{0.5} {\texttt{0}};
+ \node at \punkt{7.5}{0.5} {\texttt{1}};
+ \foreach \x in {0.5,1.5,...,7.5}{
+ \draw[->,color=blue] \punkt{\x}{-0.1} -- \punkt{(\x-1)}{-1.3};
+ }
+\end{scope}
+
+\begin{scope}[yshift=-1cm]
+ \draw[<-] \punkt{8.2}{-1.3} arc (-30:30:1.8);
+ \node at \punkt{9.3}{0.6} {$\mathstrut\cdot X$};
+ \fill[color=blue!20] \punkt{-1}{0} rectangle \punkt{0}{1};
+ \draw \punkt{0}{0} rectangle \punkt{8}{1};
+ \foreach \x in {1,...,7}{
+ \draw \punkt{\x}{0} -- \punkt{\x}{1};
+ }
+ \node[color=darkgreen] at \punkt{-0.5}{0.5} {\texttt{1}};
+ \node at \punkt{0.5}{0.5} {\texttt{0}};
+ \node at \punkt{1.5}{0.5} {\texttt{0}};
+ \node at \punkt{2.5}{0.5} {\texttt{1}};
+ \node at \punkt{3.5}{0.5} {\texttt{0}};
+ \node at \punkt{4.5}{0.5} {\texttt{1}};
+ \node at \punkt{5.5}{0.5} {\texttt{0}};
+ \node at \punkt{6.5}{0.5} {\texttt{1}};
+ \node at \punkt{7.5}{0.5} {\texttt{0}};
+
+ \draw[->,color=darkgreen]
+ \punkt{-0.5}{0.1} -- \punkt{-0.5}{-0.5} -- \punkt{3.1}{-0.5};
+ \node[color=darkgreen] at \punkt{3.5}{-0.5} {\texttt{1}};
+ \node[color=darkgreen] at \punkt{4.5}{-0.5} {\texttt{1}};
+ \node[color=darkgreen] at \punkt{6.5}{-0.5} {\texttt{1}};
+ \node[color=darkgreen] at \punkt{7.5}{-0.5} {\texttt{1}};
+
+ \draw \punkt{0}{-2} rectangle \punkt{8}{-1};
+ \foreach \x in {1,...,7}{
+ \draw \punkt{\x}{-2} -- \punkt{\x}{-1};
+ }
+ \node at \punkt{0.5}{-1.5} {\texttt{0}};
+ \node at \punkt{1.5}{-1.5} {\texttt{0}};
+ \node at \punkt{2.5}{-1.5} {\texttt{1}};
+ \node at \punkt{3.5}{-1.5} {\texttt{1}};
+ \node at \punkt{4.5}{-1.5} {\texttt{0}};
+ \node at \punkt{5.5}{-1.5} {\texttt{0}};
+ \node at \punkt{6.5}{-1.5} {\texttt{0}};
+ \node at \punkt{7.5}{-1.5} {\texttt{1}};
+
+ \pfeile
+\end{scope}
+
+\begin{scope}[yshift=-3cm]
+ \draw[<-] \punkt{8.2}{-1.3} arc (-30:30:1.8);
+ \node at \punkt{9.3}{0.6} {$\mathstrut\cdot X$};
+ \fill[color=blue!20] \punkt{-1}{0} rectangle \punkt{0}{1};
+ \draw \punkt{0}{0} rectangle \punkt{8}{1};
+ \foreach \x in {1,...,7}{
+ \draw \punkt{\x}{0} -- \punkt{\x}{1};
+ }
+ \node[color=darkgreen] at \punkt{-0.5}{0.5} {\texttt{0}};
+ \node at \punkt{0.5}{0.5} {\texttt{0}};
+ \node at \punkt{1.5}{0.5} {\texttt{1}};
+ \node at \punkt{2.5}{0.5} {\texttt{1}};
+ \node at \punkt{3.5}{0.5} {\texttt{0}};
+ \node at \punkt{4.5}{0.5} {\texttt{0}};
+ \node at \punkt{5.5}{0.5} {\texttt{0}};
+ \node at \punkt{6.5}{0.5} {\texttt{1}};
+ \node at \punkt{7.5}{0.5} {\texttt{0}};
+
+% \draw[->,color=darkgreen]
+% \punkt{-0.5}{0.1} -- \punkt{-0.5}{-0.5} -- \punkt{3.1}{-0.5};
+% \node[color=darkgreen] at \punkt{3.5}{-0.5} {\texttt{1}};
+% \node[color=darkgreen] at \punkt{4.5}{-0.5} {\texttt{1}};
+% \node[color=darkgreen] at \punkt{6.5}{-0.5} {\texttt{1}};
+% \node[color=darkgreen] at \punkt{7.5}{-0.5} {\texttt{1}};
+ \node[color=darkgreen] at \punkt{4}{-0.5} {$\|$};
+
+ \draw \punkt{0}{-2} rectangle \punkt{8}{-1};
+ \foreach \x in {1,...,7}{
+ \draw \punkt{\x}{-2} -- \punkt{\x}{-1};
+ }
+ \node at \punkt{0.5}{-1.5} {\texttt{0}};
+ \node at \punkt{1.5}{-1.5} {\texttt{1}};
+ \node at \punkt{2.5}{-1.5} {\texttt{1}};
+ \node at \punkt{3.5}{-1.5} {\texttt{0}};
+ \node at \punkt{4.5}{-1.5} {\texttt{0}};
+ \node at \punkt{5.5}{-1.5} {\texttt{0}};
+ \node at \punkt{6.5}{-1.5} {\texttt{1}};
+ \node at \punkt{7.5}{-1.5} {\texttt{0}};
+
+ \pfeile
+\end{scope}
+
+\begin{scope}[yshift=-5cm]
+ \draw[<-] \punkt{8.2}{-1.3} arc (-30:30:1.8);
+ \node at \punkt{9.3}{0.6} {$\mathstrut\cdot X$};
+ \fill[color=blue!20] \punkt{-1}{0} rectangle \punkt{0}{1};
+ \draw \punkt{0}{0} rectangle \punkt{8}{1};
+ \foreach \x in {1,...,7}{
+ \draw \punkt{\x}{0} -- \punkt{\x}{1};
+ }
+ \node[color=darkgreen] at \punkt{-0.5}{0.5} {\texttt{0}};
+ \node at \punkt{0.5}{0.5} {\texttt{1}};
+ \node at \punkt{1.5}{0.5} {\texttt{1}};
+ \node at \punkt{2.5}{0.5} {\texttt{0}};
+ \node at \punkt{3.5}{0.5} {\texttt{0}};
+ \node at \punkt{4.5}{0.5} {\texttt{0}};
+ \node at \punkt{5.5}{0.5} {\texttt{1}};
+ \node at \punkt{6.5}{0.5} {\texttt{0}};
+ \node at \punkt{7.5}{0.5} {\texttt{0}};
+
+% \draw[->,color=darkgreen]
+% \punkt{-0.5}{0.1} -- \punkt{-0.5}{-0.5} -- \punkt{3.1}{-0.5};
+% \node[color=darkgreen] at \punkt{3.5}{-0.5} {\texttt{1}};
+% \node[color=darkgreen] at \punkt{4.5}{-0.5} {\texttt{1}};
+% \node[color=darkgreen] at \punkt{6.5}{-0.5} {\texttt{1}};
+% \node[color=darkgreen] at \punkt{7.5}{-0.5} {\texttt{1}};
+ \node[color=darkgreen] at \punkt{4}{-0.5} {$\|$};
+
+ \draw \punkt{0}{-2} rectangle \punkt{8}{-1};
+ \foreach \x in {1,...,7}{
+ \draw \punkt{\x}{-2} -- \punkt{\x}{-1};
+ }
+ \node at \punkt{0.5}{-1.5} {\texttt{1}};
+ \node at \punkt{1.5}{-1.5} {\texttt{1}};
+ \node at \punkt{2.5}{-1.5} {\texttt{0}};
+ \node at \punkt{3.5}{-1.5} {\texttt{0}};
+ \node at \punkt{4.5}{-1.5} {\texttt{0}};
+ \node at \punkt{5.5}{-1.5} {\texttt{1}};
+ \node at \punkt{6.5}{-1.5} {\texttt{0}};
+ \node at \punkt{7.5}{-1.5} {\texttt{0}};
+
+ \pfeile
+\end{scope}
+
+\begin{scope}[yshift=-7cm]
+ \draw[<-] \punkt{8.2}{-1.3} arc (-30:30:1.8);
+ \node at \punkt{9.3}{0.6} {$\mathstrut\cdot X$};
+ \fill[color=blue!20] \punkt{-1}{0} rectangle \punkt{0}{1};
+ \draw \punkt{0}{0} rectangle \punkt{8}{1};
+ \foreach \x in {1,...,7}{
+ \draw \punkt{\x}{0} -- \punkt{\x}{1};
+ }
+ \node[color=darkgreen] at \punkt{-0.5}{0.5} {\texttt{1}};
+ \node at \punkt{0.5}{0.5} {\texttt{1}};
+ \node at \punkt{1.5}{0.5} {\texttt{0}};
+ \node at \punkt{2.5}{0.5} {\texttt{0}};
+ \node at \punkt{3.5}{0.5} {\texttt{0}};
+ \node at \punkt{4.5}{0.5} {\texttt{1}};
+ \node at \punkt{5.5}{0.5} {\texttt{0}};
+ \node at \punkt{6.5}{0.5} {\texttt{0}};
+ \node at \punkt{7.5}{0.5} {\texttt{0}};
+
+ \draw[->,color=darkgreen]
+ \punkt{-0.5}{0.1} -- \punkt{-0.5}{-0.5} -- \punkt{3.1}{-0.5};
+ \node[color=darkgreen] at \punkt{3.5}{-0.5} {\texttt{1}};
+ \node[color=darkgreen] at \punkt{4.5}{-0.5} {\texttt{1}};
+ \node[color=darkgreen] at \punkt{6.5}{-0.5} {\texttt{1}};
+ \node[color=darkgreen] at \punkt{7.5}{-0.5} {\texttt{1}};
+% \node[color=darkgreen] at \punkt{4}{-0.5} {$\|$};
+
+ \draw \punkt{0}{-2} rectangle \punkt{8}{-1};
+ \foreach \x in {1,...,7}{
+ \draw \punkt{\x}{-2} -- \punkt{\x}{-1};
+ }
+ \node at \punkt{0.5}{-1.5} {\texttt{1}};
+ \node at \punkt{1.5}{-1.5} {\texttt{0}};
+ \node at \punkt{2.5}{-1.5} {\texttt{0}};
+ \node at \punkt{3.5}{-1.5} {\texttt{1}};
+ \node at \punkt{4.5}{-1.5} {\texttt{0}};
+ \node at \punkt{5.5}{-1.5} {\texttt{0}};
+ \node at \punkt{6.5}{-1.5} {\texttt{1}};
+ \node at \punkt{7.5}{-1.5} {\texttt{1}};
+
+ \pfeile
+\end{scope}
+
+\begin{scope}[yshift=-9cm]
+ \draw[<-] \punkt{8.2}{-1.3} arc (-30:30:1.8);
+ \node at \punkt{9.3}{0.6} {$\mathstrut\cdot X$};
+ \fill[color=blue!20] \punkt{-1}{0} rectangle \punkt{0}{1};
+ \draw \punkt{0}{0} rectangle \punkt{8}{1};
+ \foreach \x in {1,...,7}{
+ \draw \punkt{\x}{0} -- \punkt{\x}{1};
+ }
+ \node[color=darkgreen] at \punkt{-0.5}{0.5} {\texttt{1}};
+ \node at \punkt{0.5}{0.5} {\texttt{0}};
+ \node at \punkt{1.5}{0.5} {\texttt{0}};
+ \node at \punkt{2.5}{0.5} {\texttt{1}};
+ \node at \punkt{3.5}{0.5} {\texttt{0}};
+ \node at \punkt{4.5}{0.5} {\texttt{0}};
+ \node at \punkt{5.5}{0.5} {\texttt{1}};
+ \node at \punkt{6.5}{0.5} {\texttt{1}};
+ \node at \punkt{7.5}{0.5} {\texttt{0}};
+
+ \draw[->,color=darkgreen]
+ \punkt{-0.5}{0.1} -- \punkt{-0.5}{-0.5} -- \punkt{3.1}{-0.5};
+ \node[color=darkgreen] at \punkt{3.5}{-0.5} {\texttt{1}};
+ \node[color=darkgreen] at \punkt{4.5}{-0.5} {\texttt{1}};
+ \node[color=darkgreen] at \punkt{6.5}{-0.5} {\texttt{1}};
+ \node[color=darkgreen] at \punkt{7.5}{-0.5} {\texttt{1}};
+% \node[color=darkgreen] at \punkt{4}{-0.5} {$\|$};
+
+ \draw \punkt{0}{-2} rectangle \punkt{8}{-1};
+ \foreach \x in {1,...,7}{
+ \draw \punkt{\x}{-2} -- \punkt{\x}{-1};
+ }
+ \node at \punkt{0.5}{-1.5} {\texttt{0}};
+ \node at \punkt{1.5}{-1.5} {\texttt{0}};
+ \node at \punkt{2.5}{-1.5} {\texttt{1}};
+ \node at \punkt{3.5}{-1.5} {\texttt{1}};
+ \node at \punkt{4.5}{-1.5} {\texttt{1}};
+ \node at \punkt{5.5}{-1.5} {\texttt{1}};
+ \node at \punkt{6.5}{-1.5} {\texttt{0}};
+ \node at \punkt{7.5}{-1.5} {\texttt{1}};
+
+ \pfeile
+\end{scope}
+
+\begin{scope}[yshift=-11cm]
+ \draw[<-] \punkt{8.2}{-1.3} arc (-30:30:1.8);
+ \node at \punkt{9.3}{0.6} {$\mathstrut\cdot X$};
+ \fill[color=blue!20] \punkt{-1}{0} rectangle \punkt{0}{1};
+ \draw \punkt{0}{0} rectangle \punkt{8}{1};
+ \foreach \x in {1,...,7}{
+ \draw \punkt{\x}{0} -- \punkt{\x}{1};
+ }
+ \node[color=darkgreen] at \punkt{-0.5}{0.5} {\texttt{0}};
+ \node at \punkt{0.5}{0.5} {\texttt{0}};
+ \node at \punkt{1.5}{0.5} {\texttt{0}};
+ \node at \punkt{2.5}{0.5} {\texttt{1}};
+ \node at \punkt{3.5}{0.5} {\texttt{1}};
+ \node at \punkt{4.5}{0.5} {\texttt{1}};
+ \node at \punkt{5.5}{0.5} {\texttt{0}};
+ \node at \punkt{6.5}{0.5} {\texttt{1}};
+ \node at \punkt{7.5}{0.5} {\texttt{0}};
+
+% \draw[->,color=darkgreen]
+% \punkt{-0.5}{0.1} -- \punkt{-0.5}{-0.5} -- \punkt{3.1}{-0.5};
+% \node[color=darkgreen] at \punkt{3.5}{-0.5} {\texttt{1}};
+% \node[color=darkgreen] at \punkt{4.5}{-0.5} {\texttt{1}};
+% \node[color=darkgreen] at \punkt{6.5}{-0.5} {\texttt{1}};
+% \node[color=darkgreen] at \punkt{7.5}{-0.5} {\texttt{1}};
+ \node[color=darkgreen] at \punkt{4}{-0.5} {$\|$};
+
+ \draw \punkt{0}{-2} rectangle \punkt{8}{-1};
+ \foreach \x in {1,...,7}{
+ \draw \punkt{\x}{-2} -- \punkt{\x}{-1};
+ }
+ \node at \punkt{0.5}{-1.5} {\texttt{0}};
+ \node at \punkt{1.5}{-1.5} {\texttt{0}};
+ \node at \punkt{2.5}{-1.5} {\texttt{1}};
+ \node at \punkt{3.5}{-1.5} {\texttt{1}};
+ \node at \punkt{4.5}{-1.5} {\texttt{1}};
+ \node at \punkt{5.5}{-1.5} {\texttt{0}};
+ \node at \punkt{6.5}{-1.5} {\texttt{1}};
+ \node at \punkt{7.5}{-1.5} {\texttt{0}};
+
+ \pfeile
+\end{scope}
+
+\begin{scope}[yshift=-13cm]
+ \draw[<-] \punkt{8.2}{-1.3} arc (-30:30:1.8);
+ \node at \punkt{9.3}{0.6} {$\mathstrut\cdot X$};
+ \fill[color=blue!20] \punkt{-1}{0} rectangle \punkt{0}{1};
+ \draw \punkt{0}{0} rectangle \punkt{8}{1};
+ \foreach \x in {1,...,7}{
+ \draw \punkt{\x}{0} -- \punkt{\x}{1};
+ }
+ \node[color=darkgreen] at \punkt{-0.5}{0.5} {\texttt{0}};
+ \node at \punkt{0.5}{0.5} {\texttt{0}};
+ \node at \punkt{1.5}{0.5} {\texttt{1}};
+ \node at \punkt{2.5}{0.5} {\texttt{1}};
+ \node at \punkt{3.5}{0.5} {\texttt{1}};
+ \node at \punkt{4.5}{0.5} {\texttt{0}};
+ \node at \punkt{5.5}{0.5} {\texttt{1}};
+ \node at \punkt{6.5}{0.5} {\texttt{0}};
+ \node at \punkt{7.5}{0.5} {\texttt{0}};
+
+% \draw[->,color=darkgreen]
+% \punkt{-0.5}{0.1} -- \punkt{-0.5}{-0.5} -- \punkt{3.1}{-0.5};
+% \node[color=darkgreen] at \punkt{3.5}{-0.5} {\texttt{1}};
+% \node[color=darkgreen] at \punkt{4.5}{-0.5} {\texttt{1}};
+% \node[color=darkgreen] at \punkt{6.5}{-0.5} {\texttt{1}};
+% \node[color=darkgreen] at \punkt{7.5}{-0.5} {\texttt{1}};
+ \node[color=darkgreen] at \punkt{4}{-0.5} {$\|$};
+
+ \draw \punkt{0}{-2} rectangle \punkt{8}{-1};
+ \foreach \x in {1,...,7}{
+ \draw \punkt{\x}{-2} -- \punkt{\x}{-1};
+ }
+ \node at \punkt{0.5}{-1.5} {\texttt{0}};
+ \node at \punkt{1.5}{-1.5} {\texttt{1}};
+ \node at \punkt{2.5}{-1.5} {\texttt{1}};
+ \node at \punkt{3.5}{-1.5} {\texttt{0}};
+ \node at \punkt{4.5}{-1.5} {\texttt{1}};
+ \node at \punkt{5.5}{-1.5} {\texttt{1}};
+ \node at \punkt{6.5}{-1.5} {\texttt{1}};
+ \node at \punkt{7.5}{-1.5} {\texttt{1}};
+
+% \pfeile
+\end{scope}
+
+\begin{scope}[xshift=9cm]
+
+\begin{scope}[yshift=0.1cm]
+ \draw[->] \punkt{-11.8}{0.5} -- \punkt{-0.1}{0.5};
+ \draw \punkt{0}{0} rectangle \punkt{8}{1};
+ \foreach \x in {1,...,7}{
+ \draw \punkt{\x}{0} -- \punkt{\x}{1};
+ }
+ \draw \punkt{4}{-0.1} -- \punkt{4}{-3};
+ \node at \punkt{0.5}{0.5} {\texttt{1}};
+ \node at \punkt{1.5}{0.5} {\texttt{0}};
+ \node at \punkt{2.5}{0.5} {\texttt{0}};
+ \node at \punkt{3.5}{0.5} {\texttt{1}};
+ \node at \punkt{4.5}{0.5} {\texttt{0}};
+ \node at \punkt{5.5}{0.5} {\texttt{1}};
+ \node at \punkt{6.5}{0.5} {\texttt{0}};
+ \node at \punkt{7.5}{0.5} {\texttt{1}};
+\end{scope}
+
+\def\summation#1#2#3#4#5#6#7#8{
+ \draw[->] \punkt{4}{2.3} -- \punkt{4}{1};
+
+ \draw[->] \punkt{-11.8}{0.5} -- \punkt{3.5}{0.5};
+
+ \draw \punkt{4}{0.5} circle[radius=0.2];
+ \draw \punkt{4}{0.20} -- \punkt{4}{0.80};
+ \draw \punkt{3.7}{0.5} -- \punkt{4.3}{0.5};
+
+ \draw[->] \punkt{4}{-0.05} -- \punkt{4}{-0.95};
+ \draw \punkt{0}{-2} rectangle \punkt{8}{-1};
+ \foreach \x in {1,...,7}{
+ \draw \punkt{\x}{-2} -- \punkt{\x}{-1};
+ }
+
+ \node at \punkt{0.5}{-1.5} {\texttt{#1}};
+ \node at \punkt{1.5}{-1.5} {\texttt{#2}};
+ \node at \punkt{2.5}{-1.5} {\texttt{#3}};
+ \node at \punkt{3.5}{-1.5} {\texttt{#4}};
+ \node at \punkt{4.5}{-1.5} {\texttt{#5}};
+ \node at \punkt{5.5}{-1.5} {\texttt{#6}};
+ \node at \punkt{6.5}{-1.5} {\texttt{#7}};
+ \node at \punkt{7.5}{-1.5} {\texttt{#8}};
+}
+
+\begin{scope}[yshift=-1.9cm]
+ \summation{1}{0}{0}{1}{0}{1}{0}{1}
+\end{scope}
+
+\begin{scope}[yshift=-3.9cm]
+ \summation{1}{1}{1}{1}{0}{1}{1}{1}
+\end{scope}
+
+\begin{scope}[yshift=-5.9cm]
+ \summation{1}{1}{1}{1}{0}{1}{1}{1}
+\end{scope}
+
+\begin{scope}[yshift=-7.9cm]
+ \summation{0}{1}{1}{0}{0}{1}{0}{0}
+\end{scope}
+
+\begin{scope}[yshift=-9.9cm]
+ \summation{0}{1}{0}{1}{1}{0}{0}{1}
+\end{scope}
+
+\begin{scope}[yshift=-11.9cm]
+ \summation{0}{1}{0}{1}{1}{0}{0}{1}
+\end{scope}
+
+\begin{scope}[yshift=-13.9cm]
+ \summation{0}{0}{1}{1}{0}{1}{1}{0}
+ \node at \punkt{0}{-1.5} [left] {$p(X)\cdot q(X)=\mathstrut$};
+\end{scope}
+
+\end{scope}
+
+\begin{scope}[xshift=5cm]
+
+\begin{scope}[yshift=2cm]
+ \node at \punkt{0}{0.5} [left] {$q(X)=\mathstrut$};
+ \draw \punkt{0}{0} rectangle \punkt{8}{1};
+ \foreach \x in {1,...,7}{
+ \draw \punkt{\x}{0} -- \punkt{\x}{1};
+ }
+ \node at \punkt{0.5}{0.5} {\texttt{1}};
+ \node at \punkt{1.5}{0.5} {\texttt{0}};
+ \node at \punkt{2.5}{0.5} {\texttt{1}};
+ \node at \punkt{3.5}{0.5} {\texttt{1}};
+ \node at \punkt{4.5}{0.5} {\texttt{0}};
+ \node at \punkt{5.5}{0.5} {\texttt{1}};
+ \node at \punkt{6.5}{0.5} {\texttt{0}};
+ \node at \punkt{7.5}{0.5} {\texttt{1}};
+
+ \draw[->] \punkt{7.5}{-0.1} -- ({7.5*\s},{-1.3});
+ \node at ({7.5*\s},{-1.2}) [below] {$\mathstrut\cdot\texttt{1}$};
+
+ \def\y{1.2}
+
+ \draw[->] \punkt{6.5}{-0.1} -- ({6.5*\s},{-1*2-\y-0.1});
+ \node at ({6.5*\s},{-1*2-\y}) [below] {$\mathstrut\cdot\texttt{0}$};
+
+ \draw[->] \punkt{5.5}{-0.1} -- ({5.5*\s},{-2*2-\y-0.1});
+ \node at ({5.5*\s},{-2*2-\y}) [below] {$\mathstrut\cdot\texttt{1}$};
+
+ \draw[->] \punkt{4.5}{-0.1} -- ({4.5*\s},{-3*2-\y-0.1});
+ \node at ({4.5*\s},{-3*2-\y}) [below] {$\mathstrut\cdot\texttt{0}$};
+
+ \draw[->] \punkt{3.5}{-0.1} -- ({3.5*\s},{-4*2-\y-0.1});
+ \node at ({3.5*\s},{-4*2-\y}) [below] {$\mathstrut\cdot\texttt{1}$};
+
+ \draw[->] \punkt{2.5}{-0.1} -- ({2.5*\s},{-5*2-\y-0.1});
+ \node at ({2.5*\s},{-5*2-\y}) [below] {$\mathstrut\cdot\texttt{1}$};
+
+ \draw[->] \punkt{1.5}{-0.1} -- ({1.5*\s},{-6*2-\y-0.1});
+ \node at ({1.5*\s},{-6*2-\y}) [below] {$\mathstrut\cdot\texttt{0}$};
+
+ \draw[->] \punkt{0.5}{-0.1} -- ({0.5*\s},{-7*2-\y-0.1});
+ \node at ({0.5*\s},{-7*2-\y}) [below] {$\mathstrut\cdot\texttt{1}$};
+\end{scope}
+
+\end{scope}
+
+\end{tikzpicture}
+\end{document}
+
diff --git a/buch/chapters/90-crypto/images/sbox.m b/buch/chapters/90-crypto/images/sbox.m
index 1f0c2ce..973ffc9 100644
--- a/buch/chapters/90-crypto/images/sbox.m
+++ b/buch/chapters/90-crypto/images/sbox.m
@@ -1,52 +1,52 @@
-#
-# sbox.m
-#
-# (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
-#
-A=[
-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;
-]
-
-R = zeros(8,16);
-R(:,1:8) = A;
-R(:,9:16) = eye(8);
-
-for k = (1:5)
- for i=(k+1:8)
- pivot = R(i,k);
- R(i,:) = R(i,:) + pivot * R(k,:);
- end
- R = mod(R, 2)
-end
-
-P = [
-1,0,0,0,0,0,0,0;
-0,1,0,0,0,0,0,0;
-0,0,1,0,0,0,0,0;
-0,0,0,1,0,0,0,0;
-0,0,0,0,1,0,0,0;
-0,0,0,0,0,0,0,1;
-0,0,0,0,0,1,0,0;
-0,0,0,0,0,0,1,0;
-]
-
-R = P * R
-
-for k = (8:-1:2)
- for i = (1:k-1)
- pivot = R(i,k);
- R(i,:) = R(i,:) + pivot * R(k,:);
- end
- R = mod(R, 2)
-end
-
-B = R(:,9:16)
-
-A * B
+#
+# sbox.m
+#
+# (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
+#
+A=[
+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;
+]
+
+R = zeros(8,16);
+R(:,1:8) = A;
+R(:,9:16) = eye(8);
+
+for k = (1:5)
+ for i=(k+1:8)
+ pivot = R(i,k);
+ R(i,:) = R(i,:) + pivot * R(k,:);
+ end
+ R = mod(R, 2)
+end
+
+P = [
+1,0,0,0,0,0,0,0;
+0,1,0,0,0,0,0,0;
+0,0,1,0,0,0,0,0;
+0,0,0,1,0,0,0,0;
+0,0,0,0,1,0,0,0;
+0,0,0,0,0,0,0,1;
+0,0,0,0,0,1,0,0;
+0,0,0,0,0,0,1,0;
+]
+
+R = P * R
+
+for k = (8:-1:2)
+ for i = (1:k-1)
+ pivot = R(i,k);
+ R(i,:) = R(i,:) + pivot * R(k,:);
+ end
+ R = mod(R, 2)
+end
+
+B = R(:,9:16)
+
+A * B
diff --git a/buch/chapters/90-crypto/images/sbox.tex b/buch/chapters/90-crypto/images/sbox.tex
index fefb823..41f8812 100644
--- a/buch/chapters/90-crypto/images/sbox.tex
+++ b/buch/chapters/90-crypto/images/sbox.tex
@@ -1,241 +1,241 @@
-%
-% sbox.tex -- template for standalon tikz images
-%
-% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
-%
-\documentclass[tikz]{standalone}
-\usepackage{amsmath}
-\usepackage{times}
-\usepackage{txfonts}
-\usepackage{pgfplots}
-\usepackage{csvsimple}
-\usetikzlibrary{arrows,intersections,math}
-\begin{document}
-\def\skala{1}
-\begin{tikzpicture}[>=latex,thick,scale=\skala]
-
-\def\s{0.2}
-\def\punkt#1#2{({#1*\s},{(8-(#2))*\s})}
-
-\definecolor{b}{rgb}{0,0,0}
-\definecolor{w}{rgb}{1,1,1}
-
-\def\feld#1#2#3{
- \fill[color=#3] \punkt{#1}{#2} rectangle \punkt{(#1+1)}{(#2-1)};
-}
-
-\def\zeile#1#2#3#4#5#6#7#8#9{
- \feld{0}{#1}{#2}
- \feld{1}{#1}{#3}
- \feld{2}{#1}{#4}
- \feld{3}{#1}{#5}
- \feld{4}{#1}{#6}
- \feld{5}{#1}{#7}
- \feld{6}{#1}{#8}
- \feld{7}{#1}{#9}
-}
-\def\inverse#1#2#3#4#5#6#7#8#9{
- \feld{8}{#1}{#2}
- \feld{9}{#1}{#3}
- \feld{10}{#1}{#4}
- \feld{11}{#1}{#5}
- \feld{12}{#1}{#6}
- \feld{13}{#1}{#7}
- \feld{14}{#1}{#8}
- \feld{15}{#1}{#9}
-}
-\def\rechteck{
- \draw (0,{1*\s}) rectangle ({16*\s},{(8+1)*\s});
- \draw ({8*\s},{1*\s}) -- ({8*\s},{(8+1)*\s});
-}
-
-\def\pivot#1#2{
- \draw[color=red,line width=1.2pt]
- \punkt{(#1+\inset)}{(#2-\inset)}
- rectangle
- \punkt{(#1+1-\inset)}{(#2-1+\inset)};
-}
-\def\inset{0.1}
-\def\cleanup#1#2#3{
- \pgfmathparse{(#3-#2)/abs(#3-#2)}
- \xdef\signum{\pgfmathresult}
- \draw[color=blue!50,line width=1.2pt]
- \punkt{(#1+\inset)}{#3}
- --
- \punkt{(#1+\inset)}{(#2-1+\inset*\signum)}
- --
- \punkt{(#1+1-\inset)}{(#2-1+\inset*\signum)}
- --
- \punkt{(#1+1-\inset)}{#3}
- ;
-}
-
-\begin{scope}
- \zeile0bwwwbbbb \inverse0bwwwwwww
- \zeile1bbwwwbbb \inverse1wbwwwwww
- \zeile2bbbwwwbb \inverse2wwbwwwww
- \zeile3bbbbwwwb \inverse3wwwbwwww
- \zeile4bbbbbwww \inverse4wwwwbwww
- \zeile5wbbbbbww \inverse5wwwwwbww
- \zeile6wwbbbbbw \inverse6wwwwwwbw
- \zeile7wwwbbbbb \inverse7wwwwwwwb
- \rechteck
- \pivot{0}{0}
- \cleanup{0}{1}{7}
-\end{scope}
-
-\begin{scope}[xshift=4cm]
- \draw[->,shorten >= 0.05cm,shorten <= 0.05cm]
- \punkt{-4}{3} -- \punkt{0}{3};
- \zeile0bwwwbbbb \inverse0bwwwwwww
- \zeile1wbwwbwww \inverse1bbwwwwww
- \zeile2wbbwbbww \inverse2bwbwwwww
- \zeile3wbbbbbbw \inverse3bwwbwwww
- \zeile4wbbbwbbb \inverse4bwwwbwww
- \zeile5wbbbbbww \inverse5wwwwwbww
- \zeile6wwbbbbbw \inverse6wwwwwwbw
- \zeile7wwwbbbbb \inverse7wwwwwwwb
- \rechteck
- \pivot{1}{1}
- \cleanup{1}{2}{7}
-\end{scope}
-
-\begin{scope}[xshift=8cm]
- \draw[->,shorten >= 0.05cm,shorten <= 0.05cm]
- \punkt{-4}{3} -- \punkt{0}{3};
- \zeile0bwwwbbbb \inverse0bwwwwwww
- \zeile1wbwwbwww \inverse1bbwwwwww
- \zeile2wwbwwbww \inverse2wbbwwwww
- \zeile3wwbbwbbw \inverse3wbwbwwww
- \zeile4wwbbbbbb \inverse4wbwwbwww
- \zeile5wwbbwbww \inverse5bbwwwbww
- \zeile6wwbbbbbw \inverse6wwwwwwbw
- \zeile7wwwbbbbb \inverse7wwwwwwwb
- \rechteck
- \pivot{2}{2}
- \cleanup{2}{3}{7}
-\end{scope}
-
-\begin{scope}[xshift=12cm,yshift=0cm]
- \draw[->,shorten >= 0.05cm,shorten <= 0.05cm]
- \punkt{-4}{3} -- \punkt{0}{3};
- \zeile0bwwwbbbb \inverse0bwwwwwww
- \zeile1wbwwbwww \inverse1bbwwwwww
- \zeile2wwbwwbww \inverse2wbbwwwww
- \zeile3wwwbwwbw \inverse3wwbbwwww
- \zeile4wwwbbwbb \inverse4wwbwbwww
- \zeile5wwwbwwww \inverse5bwbwwbww
- \zeile6wwwbbwbw \inverse6wbbwwwbw
- \zeile7wwwbbbbb \inverse7wwwwwwwb
- \rechteck
- \pivot{3}{3}
- \cleanup{3}{4}{7}
- \draw[->,shorten >= 0.05cm,shorten <= 0.05cm]
- \punkt{8}{7} -- \punkt{8}{11};
-\end{scope}
-
-\begin{scope}[xshift=12cm,yshift=-2.4cm]
- \draw[<-,shorten >= 0.05cm,shorten <= 0.05cm]
- \punkt{-4}{3} -- \punkt{0}{3};
- \zeile0bwwwbbbb \inverse0bwwwwwww
- \zeile1wbwwbwww \inverse1bbwwwwww
- \zeile2wwbwwbww \inverse2wbbwwwww
- \zeile3wwwbwwbw \inverse3wwbbwwww
- \zeile4wwwwbwwb \inverse4wwwbbwww
- \zeile5wwwwwwbw \inverse5bwwbwbww
- \zeile6wwwwbwww \inverse6wbwbwwbw
- \zeile7wwwwbbwb \inverse7wwbbwwwb
- \rechteck
- \pivot{4}{4}
- \cleanup{4}{5}{7}
-\end{scope}
-
-\begin{scope}[xshift=8cm,yshift=-2.4cm]
- \draw[<-,shorten >= 0.05cm,shorten <= 0.05cm]
- \punkt{-4}{3} -- \punkt{0}{3};
- \zeile0bwwwbbbb \inverse0bwwwwwww
- \zeile1wbwwbwww \inverse1bbwwwwww
- \zeile2wwbwwbww \inverse2wbbwwwww
- \zeile3wwwbwwbw \inverse3wwbbwwww
- \zeile4wwwwbwwb \inverse4wwwbbwww
- \zeile5wwwwwwbw \inverse5bwwbwbww
- \zeile6wwwwwwwb \inverse6wbwwbwbw
- \zeile7wwwwwbww \inverse7wwbwbwwb
- \rechteck
-\end{scope}
-
-\begin{scope}[xshift=4cm,yshift=-2.4cm]
- \draw[<-,shorten >= 0.05cm,shorten <= 0.05cm]
- \punkt{-4}{3} -- \punkt{0}{3};
- \zeile0bwwwbbbb \inverse0bwwwwwww
- \zeile1wbwwbwww \inverse1bbwwwwww
- \zeile2wwbwwbww \inverse2wbbwwwww
- \zeile3wwwbwwbw \inverse3wwbbwwww
- \zeile4wwwwbwwb \inverse4wwwbbwww
- \zeile5wwwwwbww \inverse5wwbwbwwb
- \zeile6wwwwwwbw \inverse6bwwbwbww
- \zeile7wwwwwwwb \inverse7wbwwbwbw
- \rechteck
- \cleanup{7}{7}{-1}
-\end{scope}
-
-\begin{scope}[xshift=0cm,yshift=-2.4cm]
- \zeile0bwwwbbbw \inverse0bbwwbwbw
- \zeile1wbwwbwww \inverse1bbwwwwww
- \zeile2wwbwwbww \inverse2wbbwwwww
- \zeile3wwwbwwbw \inverse3wwbbwwww
- \zeile4wwwwbwww \inverse4wbwbwwbw
- \zeile5wwwwwbww \inverse5wwbwbwwb
- \zeile6wwwwwwbw \inverse6bwwbwbww
- \zeile7wwwwwwwb \inverse7wbwwbwbw
- \rechteck
- \cleanup{6}{6}{-1}
- \draw[->,shorten >= 0.05cm,shorten <= 0.05cm]
- \punkt{8}{7} -- \punkt{8}{11};
-\end{scope}
-
-\begin{scope}[xshift=0cm,yshift=-4.8cm]
- \zeile0bwwwbbww \inverse0wbwbbbbw
- \zeile1wbwwbwww \inverse1bbwwwwww
- \zeile2wwbwwbww \inverse2wbbwwwww
- \zeile3wwwbwwww \inverse3bwbwwbww
- \zeile4wwwwbwww \inverse4wbwbwwbw
- \zeile5wwwwwbww \inverse5wwbwbwwb
- \zeile6wwwwwwbw \inverse6bwwbwbww
- \zeile7wwwwwwwb \inverse7wbwwbwbw
- \rechteck
- \cleanup{5}{5}{-1}
-\end{scope}
-
-\begin{scope}[xshift=4cm,yshift=-4.8cm]
- \draw[->,shorten >= 0.05cm,shorten <= 0.05cm]
- \punkt{-4}{3} -- \punkt{0}{3};
- \zeile0bwwwbwww \inverse0wbbbwbbb
- \zeile1wbwwbwww \inverse1bbwwwwww
- \zeile2wwbwwwww \inverse2wbwwbwwb
- \zeile3wwwbwwww \inverse3bwbwwbww
- \zeile4wwwwbwww \inverse4wbwbwwbw
- \zeile5wwwwwbww \inverse5wwbwbwwb
- \zeile6wwwwwwbw \inverse6bwwbwbww
- \zeile7wwwwwwwb \inverse7wbwwbwbw
- \rechteck
- \cleanup{4}{4}{-1}
-\end{scope}
-
-\begin{scope}[xshift=8cm,yshift=-4.8cm]
- \draw[->,shorten >= 0.05cm,shorten <= 0.05cm]
- \punkt{-4}{3} -- \punkt{0}{3};
- \zeile0bwwwwwww \inverse0wwbwwbwb
- \zeile1wbwwwwww \inverse1bwwbwwbw
- \zeile2wwbwwwww \inverse2wbwwbwwb
- \zeile3wwwbwwww \inverse3bwbwwbww
- \zeile4wwwwbwww \inverse4wbwbwwbw
- \zeile5wwwwwbww \inverse5wwbwbwwb
- \zeile6wwwwwwbw \inverse6bwwbwbww
- \zeile7wwwwwwwb \inverse7wbwwbwbw
- \rechteck
-\end{scope}
-
-\end{tikzpicture}
-\end{document}
-
+%
+% sbox.tex -- template for standalon tikz images
+%
+% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
+%
+\documentclass[tikz]{standalone}
+\usepackage{amsmath}
+\usepackage{times}
+\usepackage{txfonts}
+\usepackage{pgfplots}
+\usepackage{csvsimple}
+\usetikzlibrary{arrows,intersections,math}
+\begin{document}
+\def\skala{1}
+\begin{tikzpicture}[>=latex,thick,scale=\skala]
+
+\def\s{0.2}
+\def\punkt#1#2{({#1*\s},{(8-(#2))*\s})}
+
+\definecolor{b}{rgb}{0,0,0}
+\definecolor{w}{rgb}{1,1,1}
+
+\def\feld#1#2#3{
+ \fill[color=#3] \punkt{#1}{#2} rectangle \punkt{(#1+1)}{(#2-1)};
+}
+
+\def\zeile#1#2#3#4#5#6#7#8#9{
+ \feld{0}{#1}{#2}
+ \feld{1}{#1}{#3}
+ \feld{2}{#1}{#4}
+ \feld{3}{#1}{#5}
+ \feld{4}{#1}{#6}
+ \feld{5}{#1}{#7}
+ \feld{6}{#1}{#8}
+ \feld{7}{#1}{#9}
+}
+\def\inverse#1#2#3#4#5#6#7#8#9{
+ \feld{8}{#1}{#2}
+ \feld{9}{#1}{#3}
+ \feld{10}{#1}{#4}
+ \feld{11}{#1}{#5}
+ \feld{12}{#1}{#6}
+ \feld{13}{#1}{#7}
+ \feld{14}{#1}{#8}
+ \feld{15}{#1}{#9}
+}
+\def\rechteck{
+ \draw (0,{1*\s}) rectangle ({16*\s},{(8+1)*\s});
+ \draw ({8*\s},{1*\s}) -- ({8*\s},{(8+1)*\s});
+}
+
+\def\pivot#1#2{
+ \draw[color=red,line width=1.2pt]
+ \punkt{(#1+\inset)}{(#2-\inset)}
+ rectangle
+ \punkt{(#1+1-\inset)}{(#2-1+\inset)};
+}
+\def\inset{0.1}
+\def\cleanup#1#2#3{
+ \pgfmathparse{(#3-#2)/abs(#3-#2)}
+ \xdef\signum{\pgfmathresult}
+ \draw[color=blue!50,line width=1.2pt]
+ \punkt{(#1+\inset)}{#3}
+ --
+ \punkt{(#1+\inset)}{(#2-1+\inset*\signum)}
+ --
+ \punkt{(#1+1-\inset)}{(#2-1+\inset*\signum)}
+ --
+ \punkt{(#1+1-\inset)}{#3}
+ ;
+}
+
+\begin{scope}
+ \zeile0bwwwbbbb \inverse0bwwwwwww
+ \zeile1bbwwwbbb \inverse1wbwwwwww
+ \zeile2bbbwwwbb \inverse2wwbwwwww
+ \zeile3bbbbwwwb \inverse3wwwbwwww
+ \zeile4bbbbbwww \inverse4wwwwbwww
+ \zeile5wbbbbbww \inverse5wwwwwbww
+ \zeile6wwbbbbbw \inverse6wwwwwwbw
+ \zeile7wwwbbbbb \inverse7wwwwwwwb
+ \rechteck
+ \pivot{0}{0}
+ \cleanup{0}{1}{7}
+\end{scope}
+
+\begin{scope}[xshift=4cm]
+ \draw[->,shorten >= 0.05cm,shorten <= 0.05cm]
+ \punkt{-4}{3} -- \punkt{0}{3};
+ \zeile0bwwwbbbb \inverse0bwwwwwww
+ \zeile1wbwwbwww \inverse1bbwwwwww
+ \zeile2wbbwbbww \inverse2bwbwwwww
+ \zeile3wbbbbbbw \inverse3bwwbwwww
+ \zeile4wbbbwbbb \inverse4bwwwbwww
+ \zeile5wbbbbbww \inverse5wwwwwbww
+ \zeile6wwbbbbbw \inverse6wwwwwwbw
+ \zeile7wwwbbbbb \inverse7wwwwwwwb
+ \rechteck
+ \pivot{1}{1}
+ \cleanup{1}{2}{7}
+\end{scope}
+
+\begin{scope}[xshift=8cm]
+ \draw[->,shorten >= 0.05cm,shorten <= 0.05cm]
+ \punkt{-4}{3} -- \punkt{0}{3};
+ \zeile0bwwwbbbb \inverse0bwwwwwww
+ \zeile1wbwwbwww \inverse1bbwwwwww
+ \zeile2wwbwwbww \inverse2wbbwwwww
+ \zeile3wwbbwbbw \inverse3wbwbwwww
+ \zeile4wwbbbbbb \inverse4wbwwbwww
+ \zeile5wwbbwbww \inverse5bbwwwbww
+ \zeile6wwbbbbbw \inverse6wwwwwwbw
+ \zeile7wwwbbbbb \inverse7wwwwwwwb
+ \rechteck
+ \pivot{2}{2}
+ \cleanup{2}{3}{7}
+\end{scope}
+
+\begin{scope}[xshift=12cm,yshift=0cm]
+ \draw[->,shorten >= 0.05cm,shorten <= 0.05cm]
+ \punkt{-4}{3} -- \punkt{0}{3};
+ \zeile0bwwwbbbb \inverse0bwwwwwww
+ \zeile1wbwwbwww \inverse1bbwwwwww
+ \zeile2wwbwwbww \inverse2wbbwwwww
+ \zeile3wwwbwwbw \inverse3wwbbwwww
+ \zeile4wwwbbwbb \inverse4wwbwbwww
+ \zeile5wwwbwwww \inverse5bwbwwbww
+ \zeile6wwwbbwbw \inverse6wbbwwwbw
+ \zeile7wwwbbbbb \inverse7wwwwwwwb
+ \rechteck
+ \pivot{3}{3}
+ \cleanup{3}{4}{7}
+ \draw[->,shorten >= 0.05cm,shorten <= 0.05cm]
+ \punkt{8}{7} -- \punkt{8}{11};
+\end{scope}
+
+\begin{scope}[xshift=12cm,yshift=-2.4cm]
+ \draw[<-,shorten >= 0.05cm,shorten <= 0.05cm]
+ \punkt{-4}{3} -- \punkt{0}{3};
+ \zeile0bwwwbbbb \inverse0bwwwwwww
+ \zeile1wbwwbwww \inverse1bbwwwwww
+ \zeile2wwbwwbww \inverse2wbbwwwww
+ \zeile3wwwbwwbw \inverse3wwbbwwww
+ \zeile4wwwwbwwb \inverse4wwwbbwww
+ \zeile5wwwwwwbw \inverse5bwwbwbww
+ \zeile6wwwwbwww \inverse6wbwbwwbw
+ \zeile7wwwwbbwb \inverse7wwbbwwwb
+ \rechteck
+ \pivot{4}{4}
+ \cleanup{4}{5}{7}
+\end{scope}
+
+\begin{scope}[xshift=8cm,yshift=-2.4cm]
+ \draw[<-,shorten >= 0.05cm,shorten <= 0.05cm]
+ \punkt{-4}{3} -- \punkt{0}{3};
+ \zeile0bwwwbbbb \inverse0bwwwwwww
+ \zeile1wbwwbwww \inverse1bbwwwwww
+ \zeile2wwbwwbww \inverse2wbbwwwww
+ \zeile3wwwbwwbw \inverse3wwbbwwww
+ \zeile4wwwwbwwb \inverse4wwwbbwww
+ \zeile5wwwwwwbw \inverse5bwwbwbww
+ \zeile6wwwwwwwb \inverse6wbwwbwbw
+ \zeile7wwwwwbww \inverse7wwbwbwwb
+ \rechteck
+\end{scope}
+
+\begin{scope}[xshift=4cm,yshift=-2.4cm]
+ \draw[<-,shorten >= 0.05cm,shorten <= 0.05cm]
+ \punkt{-4}{3} -- \punkt{0}{3};
+ \zeile0bwwwbbbb \inverse0bwwwwwww
+ \zeile1wbwwbwww \inverse1bbwwwwww
+ \zeile2wwbwwbww \inverse2wbbwwwww
+ \zeile3wwwbwwbw \inverse3wwbbwwww
+ \zeile4wwwwbwwb \inverse4wwwbbwww
+ \zeile5wwwwwbww \inverse5wwbwbwwb
+ \zeile6wwwwwwbw \inverse6bwwbwbww
+ \zeile7wwwwwwwb \inverse7wbwwbwbw
+ \rechteck
+ \cleanup{7}{7}{-1}
+\end{scope}
+
+\begin{scope}[xshift=0cm,yshift=-2.4cm]
+ \zeile0bwwwbbbw \inverse0bbwwbwbw
+ \zeile1wbwwbwww \inverse1bbwwwwww
+ \zeile2wwbwwbww \inverse2wbbwwwww
+ \zeile3wwwbwwbw \inverse3wwbbwwww
+ \zeile4wwwwbwww \inverse4wbwbwwbw
+ \zeile5wwwwwbww \inverse5wwbwbwwb
+ \zeile6wwwwwwbw \inverse6bwwbwbww
+ \zeile7wwwwwwwb \inverse7wbwwbwbw
+ \rechteck
+ \cleanup{6}{6}{-1}
+ \draw[->,shorten >= 0.05cm,shorten <= 0.05cm]
+ \punkt{8}{7} -- \punkt{8}{11};
+\end{scope}
+
+\begin{scope}[xshift=0cm,yshift=-4.8cm]
+ \zeile0bwwwbbww \inverse0wbwbbbbw
+ \zeile1wbwwbwww \inverse1bbwwwwww
+ \zeile2wwbwwbww \inverse2wbbwwwww
+ \zeile3wwwbwwww \inverse3bwbwwbww
+ \zeile4wwwwbwww \inverse4wbwbwwbw
+ \zeile5wwwwwbww \inverse5wwbwbwwb
+ \zeile6wwwwwwbw \inverse6bwwbwbww
+ \zeile7wwwwwwwb \inverse7wbwwbwbw
+ \rechteck
+ \cleanup{5}{5}{-1}
+\end{scope}
+
+\begin{scope}[xshift=4cm,yshift=-4.8cm]
+ \draw[->,shorten >= 0.05cm,shorten <= 0.05cm]
+ \punkt{-4}{3} -- \punkt{0}{3};
+ \zeile0bwwwbwww \inverse0wbbbwbbb
+ \zeile1wbwwbwww \inverse1bbwwwwww
+ \zeile2wwbwwwww \inverse2wbwwbwwb
+ \zeile3wwwbwwww \inverse3bwbwwbww
+ \zeile4wwwwbwww \inverse4wbwbwwbw
+ \zeile5wwwwwbww \inverse5wwbwbwwb
+ \zeile6wwwwwwbw \inverse6bwwbwbww
+ \zeile7wwwwwwwb \inverse7wbwwbwbw
+ \rechteck
+ \cleanup{4}{4}{-1}
+\end{scope}
+
+\begin{scope}[xshift=8cm,yshift=-4.8cm]
+ \draw[->,shorten >= 0.05cm,shorten <= 0.05cm]
+ \punkt{-4}{3} -- \punkt{0}{3};
+ \zeile0bwwwwwww \inverse0wwbwwbwb
+ \zeile1wbwwwwww \inverse1bwwbwwbw
+ \zeile2wwbwwwww \inverse2wbwwbwwb
+ \zeile3wwwbwwww \inverse3bwbwwbww
+ \zeile4wwwwbwww \inverse4wbwbwwbw
+ \zeile5wwwwwbww \inverse5wwbwbwwb
+ \zeile6wwwwwwbw \inverse6bwwbwbww
+ \zeile7wwwwwwwb \inverse7wbwwbwbw
+ \rechteck
+\end{scope}
+
+\end{tikzpicture}
+\end{document}
+
diff --git a/buch/chapters/90-crypto/images/schieberegister.tex b/buch/chapters/90-crypto/images/schieberegister.tex
index 49302ac..7c24e52 100644
--- a/buch/chapters/90-crypto/images/schieberegister.tex
+++ b/buch/chapters/90-crypto/images/schieberegister.tex
@@ -1,120 +1,120 @@
-%
-% schieberegister.tex -- template for standalon tikz images
-%
-% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
-%
-\documentclass[tikz]{standalone}
-\usepackage{amsmath}
-\usepackage{times}
-\usepackage{txfonts}
-\usepackage{pgfplots}
-\usepackage{csvsimple}
-\usetikzlibrary{arrows,intersections,math}
-\begin{document}
-\def\skala{1}
-\begin{tikzpicture}[>=latex,thick,scale=\skala]
-
-\definecolor{darkgreen}{rgb}{0,0.6,0}
-
-\def\s{0.8}
-
-\def\punkt#1#2{({#1*\s},{#2*\s})}
-
-\fill[color=blue!20] \punkt{0}{0} rectangle \punkt{8}{1};
-
-\node at \punkt{0.5}{1} [above] {$X^7\mathstrut$};
-\node at \punkt{3}{1} [above] {$+\mathstrut$};
-\node at \punkt{3.5}{1} [above] {$X^4\mathstrut$};
-\node at \punkt{5}{1} [above] {$+\mathstrut$};
-\node at \punkt{5.5}{1} [above] {$X^2\mathstrut$};
-\node at \punkt{7}{1} [above] {$+\mathstrut$};
-\node at \punkt{7.5}{1} [above] {$1\mathstrut$};
-
-\node at \punkt{0}{1} [above left] {\llap{$p(X)=\mathstrut$}};
-
-\node at \punkt{0.5}{0.5} {\texttt{1}};
-\node at \punkt{1.5}{0.5} {\texttt{0}};
-\node at \punkt{2.5}{0.5} {\texttt{0}};
-\node at \punkt{3.5}{0.5} {\texttt{1}};
-\node at \punkt{4.5}{0.5} {\texttt{0}};
-\node at \punkt{5.5}{0.5} {\texttt{1}};
-\node at \punkt{6.5}{0.5} {\texttt{0}};
-\node at \punkt{7.5}{0.5} {\texttt{1}};
-
-\draw \punkt{0}{0} rectangle \punkt{8}{1};
-\foreach \x in {1,...,7}{
- \draw \punkt{\x}{0} -- \punkt{\x}{1};
-}
-
-\fill[color=blue!20] \punkt{-1}{-3} rectangle \punkt{7}{-2};
-\fill[color=darkgreen!20] \punkt{0}{-4} rectangle \punkt{8}{-3};
-
-\node[color=darkgreen] at \punkt{-1}{-1.5} [left]
- {$m(X) = X^8+X^4+X^3+X+1$};
-
-\node[color=darkgreen] at \punkt{-1}{-2.7} [left]
- {$\underbrace{X^4+X^3+X+1}_{}= X^8=\mathstrut$};
-
-\coordinate (A) at ({-4.15*\s},{-3*\s});
-\coordinate (B) at ({0*\s},{-3.5*\s});
-
-\draw[->,color=red,shorten >= 0.1cm] (A) to[out=-90,in=180] (B);
-\node[color=red] at \punkt{-3.1}{-3.8} [below] {Feedback};
-
-\node at \punkt{-0.5}{-2.5} {\texttt{1}};
-\node at \punkt{0.5}{-2.5} {\texttt{0}};
-\node at \punkt{1.5}{-2.5} {\texttt{0}};
-\node at \punkt{2.5}{-2.5} {\texttt{1}};
-\node at \punkt{3.5}{-2.5} {\texttt{0}};
-\node at \punkt{4.5}{-2.5} {\texttt{1}};
-\node at \punkt{5.5}{-2.5} {\texttt{0}};
-\node at \punkt{6.5}{-2.5} {\texttt{1}};
-\node at \punkt{7.5}{-2.5} {\texttt{0}};
-
-\node[color=darkgreen] at \punkt{0.5}{-3.5} {\texttt{0}};
-\node[color=darkgreen] at \punkt{1.5}{-3.5} {\texttt{0}};
-\node[color=darkgreen] at \punkt{2.5}{-3.5} {\texttt{0}};
-\node[color=darkgreen] at \punkt{3.5}{-3.5} {\texttt{1}};
-\node[color=darkgreen] at \punkt{4.5}{-3.5} {\texttt{1}};
-\node[color=darkgreen] at \punkt{5.5}{-3.5} {\texttt{0}};
-\node[color=darkgreen] at \punkt{6.5}{-3.5} {\texttt{1}};
-\node[color=darkgreen] at \punkt{7.5}{-3.5} {\texttt{1}};
-
-\draw \punkt{0}{-4} rectangle \punkt{8}{-2};
-\draw \punkt{0}{-3} -- \punkt{8}{-3};
-\foreach \x in {1,...,7}{
- \draw \punkt{\x}{-4} -- \punkt{\x}{-2};
-}
-
-\foreach \x in {0.5,1.5,...,7.5}{
- \draw[->,color=blue] \punkt{\x}{-0.1} -- \punkt{(\x-1)}{-1.9};
-}
-
-\draw \punkt{0}{-6} rectangle \punkt{8}{-5};
-\foreach \x in {1,...,7}{
- \draw \punkt{\x}{-6} -- \punkt{\x}{-5};
-}
-
-\node at \punkt{0.5}{-5.5} {\texttt{0}};
-\node at \punkt{1.5}{-5.5} {\texttt{0}};
-\node at \punkt{2.5}{-5.5} {\texttt{1}};
-\node at \punkt{3.5}{-5.5} {\texttt{1}};
-\node at \punkt{4.5}{-5.5} {\texttt{0}};
-\node at \punkt{5.5}{-5.5} {\texttt{0}};
-\node at \punkt{6.5}{-5.5} {\texttt{0}};
-\node at \punkt{7.5}{-5.5} {\texttt{1}};
-
-\node at \punkt{4}{-4.5} {$\|$};
-
-\node at \punkt{10.3}{-3} [left]
- {$\left.\begin{matrix}\\ \\ \\ \end{matrix}\right\} + = \text{XOR}$};
-
-\draw[<-,shorten >= 0.1cm, shorten <= 0.1cm]
- \punkt{8.0}{-2.0} arc (-30:30:{2.0*\s});
-\node at \punkt{8.3}{-1} [right] {$\mathstrut \cdot X$};
-
-\node at \punkt{8.1}{-5.5} [right] {$=X\cdot p(X)\mathstrut$};
-
-\end{tikzpicture}
-\end{document}
-
+%
+% schieberegister.tex -- template for standalon tikz images
+%
+% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
+%
+\documentclass[tikz]{standalone}
+\usepackage{amsmath}
+\usepackage{times}
+\usepackage{txfonts}
+\usepackage{pgfplots}
+\usepackage{csvsimple}
+\usetikzlibrary{arrows,intersections,math}
+\begin{document}
+\def\skala{1}
+\begin{tikzpicture}[>=latex,thick,scale=\skala]
+
+\definecolor{darkgreen}{rgb}{0,0.6,0}
+
+\def\s{0.8}
+
+\def\punkt#1#2{({#1*\s},{#2*\s})}
+
+\fill[color=blue!20] \punkt{0}{0} rectangle \punkt{8}{1};
+
+\node at \punkt{0.5}{1} [above] {$X^7\mathstrut$};
+\node at \punkt{3}{1} [above] {$+\mathstrut$};
+\node at \punkt{3.5}{1} [above] {$X^4\mathstrut$};
+\node at \punkt{5}{1} [above] {$+\mathstrut$};
+\node at \punkt{5.5}{1} [above] {$X^2\mathstrut$};
+\node at \punkt{7}{1} [above] {$+\mathstrut$};
+\node at \punkt{7.5}{1} [above] {$1\mathstrut$};
+
+\node at \punkt{0}{1} [above left] {\llap{$p(X)=\mathstrut$}};
+
+\node at \punkt{0.5}{0.5} {\texttt{1}};
+\node at \punkt{1.5}{0.5} {\texttt{0}};
+\node at \punkt{2.5}{0.5} {\texttt{0}};
+\node at \punkt{3.5}{0.5} {\texttt{1}};
+\node at \punkt{4.5}{0.5} {\texttt{0}};
+\node at \punkt{5.5}{0.5} {\texttt{1}};
+\node at \punkt{6.5}{0.5} {\texttt{0}};
+\node at \punkt{7.5}{0.5} {\texttt{1}};
+
+\draw \punkt{0}{0} rectangle \punkt{8}{1};
+\foreach \x in {1,...,7}{
+ \draw \punkt{\x}{0} -- \punkt{\x}{1};
+}
+
+\fill[color=blue!20] \punkt{-1}{-3} rectangle \punkt{7}{-2};
+\fill[color=darkgreen!20] \punkt{0}{-4} rectangle \punkt{8}{-3};
+
+\node[color=darkgreen] at \punkt{-1}{-1.5} [left]
+ {$m(X) = X^8+X^4+X^3+X+1$};
+
+\node[color=darkgreen] at \punkt{-1}{-2.7} [left]
+ {$\underbrace{X^4+X^3+X+1}_{}= X^8=\mathstrut$};
+
+\coordinate (A) at ({-4.15*\s},{-3*\s});
+\coordinate (B) at ({0*\s},{-3.5*\s});
+
+\draw[->,color=red,shorten >= 0.1cm] (A) to[out=-90,in=180] (B);
+\node[color=red] at \punkt{-3.1}{-3.8} [below] {Feedback};
+
+\node at \punkt{-0.5}{-2.5} {\texttt{1}};
+\node at \punkt{0.5}{-2.5} {\texttt{0}};
+\node at \punkt{1.5}{-2.5} {\texttt{0}};
+\node at \punkt{2.5}{-2.5} {\texttt{1}};
+\node at \punkt{3.5}{-2.5} {\texttt{0}};
+\node at \punkt{4.5}{-2.5} {\texttt{1}};
+\node at \punkt{5.5}{-2.5} {\texttt{0}};
+\node at \punkt{6.5}{-2.5} {\texttt{1}};
+\node at \punkt{7.5}{-2.5} {\texttt{0}};
+
+\node[color=darkgreen] at \punkt{0.5}{-3.5} {\texttt{0}};
+\node[color=darkgreen] at \punkt{1.5}{-3.5} {\texttt{0}};
+\node[color=darkgreen] at \punkt{2.5}{-3.5} {\texttt{0}};
+\node[color=darkgreen] at \punkt{3.5}{-3.5} {\texttt{1}};
+\node[color=darkgreen] at \punkt{4.5}{-3.5} {\texttt{1}};
+\node[color=darkgreen] at \punkt{5.5}{-3.5} {\texttt{0}};
+\node[color=darkgreen] at \punkt{6.5}{-3.5} {\texttt{1}};
+\node[color=darkgreen] at \punkt{7.5}{-3.5} {\texttt{1}};
+
+\draw \punkt{0}{-4} rectangle \punkt{8}{-2};
+\draw \punkt{0}{-3} -- \punkt{8}{-3};
+\foreach \x in {1,...,7}{
+ \draw \punkt{\x}{-4} -- \punkt{\x}{-2};
+}
+
+\foreach \x in {0.5,1.5,...,7.5}{
+ \draw[->,color=blue] \punkt{\x}{-0.1} -- \punkt{(\x-1)}{-1.9};
+}
+
+\draw \punkt{0}{-6} rectangle \punkt{8}{-5};
+\foreach \x in {1,...,7}{
+ \draw \punkt{\x}{-6} -- \punkt{\x}{-5};
+}
+
+\node at \punkt{0.5}{-5.5} {\texttt{0}};
+\node at \punkt{1.5}{-5.5} {\texttt{0}};
+\node at \punkt{2.5}{-5.5} {\texttt{1}};
+\node at \punkt{3.5}{-5.5} {\texttt{1}};
+\node at \punkt{4.5}{-5.5} {\texttt{0}};
+\node at \punkt{5.5}{-5.5} {\texttt{0}};
+\node at \punkt{6.5}{-5.5} {\texttt{0}};
+\node at \punkt{7.5}{-5.5} {\texttt{1}};
+
+\node at \punkt{4}{-4.5} {$\|$};
+
+\node at \punkt{10.3}{-3} [left]
+ {$\left.\begin{matrix}\\ \\ \\ \end{matrix}\right\} + = \text{XOR}$};
+
+\draw[<-,shorten >= 0.1cm, shorten <= 0.1cm]
+ \punkt{8.0}{-2.0} arc (-30:30:{2.0*\s});
+\node at \punkt{8.3}{-1} [right] {$\mathstrut \cdot X$};
+
+\node at \punkt{8.1}{-5.5} [right] {$=X\cdot p(X)\mathstrut$};
+
+\end{tikzpicture}
+\end{document}
+
diff --git a/buch/chapters/90-crypto/images/shift.tex b/buch/chapters/90-crypto/images/shift.tex
index af225a7..bcdf819 100644
--- a/buch/chapters/90-crypto/images/shift.tex
+++ b/buch/chapters/90-crypto/images/shift.tex
@@ -1,131 +1,131 @@
-%
-% shift.tex -- template for standalon tikz images
-%
-% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
-%
-\documentclass[tikz]{standalone}
-\usepackage{amsmath}
-\usepackage{times}
-\usepackage{txfonts}
-\usepackage{pgfplots}
-\usepackage{csvsimple}
-\usetikzlibrary{arrows,intersections,math}
-\begin{document}
-\def\skala{1}
-\begin{tikzpicture}[>=latex,thick,scale=\skala]
-
-\definecolor{darkgreen}{rgb}{0,0.6,0}
-
-\def\s{0.8}
-\def\punkt#1#2{({#1*\s},{#2*\s})}
-
-\def\feld#1#2#3#4{
- \fill[color=#3] \punkt{#1}{#2} rectangle \punkt{(#1+1)}{(#2+1)};
- \node at \punkt{(#1+0.5)}{(#2+0.5)} {$\mathstrut #4$};
-}
-\def\gitter{
- \draw \punkt{0}{0} rectangle \punkt{8}{4};
- \foreach \x in {1,...,7}{
- \draw \punkt{\x}{0} -- \punkt{\x}{4};
- }
- \foreach \y in {1,...,3}{
- \draw \punkt{0}{\y} -- \punkt{8}{\y};
- }
-}
-
-\begin{scope}
- \feld{0}{3}{red!20}{b_{0}}
- \feld{0}{2}{red!20}{b_{1}}
- \feld{0}{1}{red!20}{b_{2}}
- \feld{0}{0}{red!20}{b_{3}}
-
- \feld{1}{3}{red!10}{b_{4}}
- \feld{1}{2}{red!10}{b_{5}}
- \feld{1}{1}{red!10}{b_{6}}
- \feld{1}{0}{red!10}{b_{7}}
-
- \feld{2}{3}{yellow!20}{b_{8}}
- \feld{2}{2}{yellow!20}{b_{9}}
- \feld{2}{1}{yellow!20}{b_{10}}
- \feld{2}{0}{yellow!20}{b_{11}}
-
- \feld{3}{3}{yellow!10}{b_{12}}
- \feld{3}{2}{yellow!10}{b_{13}}
- \feld{3}{1}{yellow!10}{b_{14}}
- \feld{3}{0}{yellow!10}{b_{15}}
-
- \feld{4}{3}{darkgreen!20}{b_{16}}
- \feld{4}{2}{darkgreen!20}{b_{17}}
- \feld{4}{1}{darkgreen!20}{b_{18}}
- \feld{4}{0}{darkgreen!20}{b_{19}}
-
- \feld{5}{3}{darkgreen!10}{b_{20}}
- \feld{5}{2}{darkgreen!10}{b_{21}}
- \feld{5}{1}{darkgreen!10}{b_{22}}
- \feld{5}{0}{darkgreen!10}{b_{23}}
-
- \feld{6}{3}{blue!20}{b_{24}}
- \feld{6}{2}{blue!20}{b_{25}}
- \feld{6}{1}{blue!20}{b_{26}}
- \feld{6}{0}{blue!20}{b_{27}}
-
- \feld{7}{3}{blue!10}{b_{28}}
- \feld{7}{2}{blue!10}{b_{29}}
- \feld{7}{1}{blue!10}{b_{30}}
- \feld{7}{0}{blue!10}{b_{31}}
-
- \gitter
-
- \draw[->] \punkt{8.1}{2} -- \punkt{9.3}{2};
-\end{scope}
-
-
-\begin{scope}[xshift=7.5cm]
-
- \feld{0}{3}{red!20}{b_{0}}
- \feld{1}{2}{red!20}{b_{1}}
- \feld{2}{1}{red!20}{b_{2}}
- \feld{3}{0}{red!20}{b_{3}}
-
- \feld{1}{3}{red!10}{b_{4}}
- \feld{2}{2}{red!10}{b_{5}}
- \feld{3}{1}{red!10}{b_{6}}
- \feld{4}{0}{red!10}{b_{7}}
-
- \feld{2}{3}{yellow!20}{b_{8}}
- \feld{3}{2}{yellow!20}{b_{9}}
- \feld{4}{1}{yellow!20}{b_{10}}
- \feld{5}{0}{yellow!20}{b_{11}}
-
- \feld{3}{3}{yellow!10}{b_{12}}
- \feld{4}{2}{yellow!10}{b_{13}}
- \feld{5}{1}{yellow!10}{b_{14}}
- \feld{6}{0}{yellow!10}{b_{15}}
-
- \feld{4}{3}{darkgreen!20}{b_{16}}
- \feld{5}{2}{darkgreen!20}{b_{17}}
- \feld{6}{1}{darkgreen!20}{b_{18}}
- \feld{7}{0}{darkgreen!20}{b_{19}}
-
- \feld{5}{3}{darkgreen!10}{b_{20}}
- \feld{6}{2}{darkgreen!10}{b_{21}}
- \feld{7}{1}{darkgreen!10}{b_{22}}
- \feld{0}{0}{darkgreen!10}{b_{23}}
-
- \feld{6}{3}{blue!20}{b_{24}}
- \feld{7}{2}{blue!20}{b_{25}}
- \feld{0}{1}{blue!20}{b_{26}}
- \feld{1}{0}{blue!20}{b_{27}}
-
- \feld{7}{3}{blue!10}{b_{28}}
- \feld{0}{2}{blue!10}{b_{29}}
- \feld{1}{1}{blue!10}{b_{30}}
- \feld{2}{0}{blue!10}{b_{31}}
-
- \gitter
-
-\end{scope}
-
-\end{tikzpicture}
-\end{document}
-
+%
+% shift.tex -- template for standalon tikz images
+%
+% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
+%
+\documentclass[tikz]{standalone}
+\usepackage{amsmath}
+\usepackage{times}
+\usepackage{txfonts}
+\usepackage{pgfplots}
+\usepackage{csvsimple}
+\usetikzlibrary{arrows,intersections,math}
+\begin{document}
+\def\skala{1}
+\begin{tikzpicture}[>=latex,thick,scale=\skala]
+
+\definecolor{darkgreen}{rgb}{0,0.6,0}
+
+\def\s{0.8}
+\def\punkt#1#2{({#1*\s},{#2*\s})}
+
+\def\feld#1#2#3#4{
+ \fill[color=#3] \punkt{#1}{#2} rectangle \punkt{(#1+1)}{(#2+1)};
+ \node at \punkt{(#1+0.5)}{(#2+0.5)} {$\mathstrut #4$};
+}
+\def\gitter{
+ \draw \punkt{0}{0} rectangle \punkt{8}{4};
+ \foreach \x in {1,...,7}{
+ \draw \punkt{\x}{0} -- \punkt{\x}{4};
+ }
+ \foreach \y in {1,...,3}{
+ \draw \punkt{0}{\y} -- \punkt{8}{\y};
+ }
+}
+
+\begin{scope}
+ \feld{0}{3}{red!20}{b_{0}}
+ \feld{0}{2}{red!20}{b_{1}}
+ \feld{0}{1}{red!20}{b_{2}}
+ \feld{0}{0}{red!20}{b_{3}}
+
+ \feld{1}{3}{red!10}{b_{4}}
+ \feld{1}{2}{red!10}{b_{5}}
+ \feld{1}{1}{red!10}{b_{6}}
+ \feld{1}{0}{red!10}{b_{7}}
+
+ \feld{2}{3}{yellow!20}{b_{8}}
+ \feld{2}{2}{yellow!20}{b_{9}}
+ \feld{2}{1}{yellow!20}{b_{10}}
+ \feld{2}{0}{yellow!20}{b_{11}}
+
+ \feld{3}{3}{yellow!10}{b_{12}}
+ \feld{3}{2}{yellow!10}{b_{13}}
+ \feld{3}{1}{yellow!10}{b_{14}}
+ \feld{3}{0}{yellow!10}{b_{15}}
+
+ \feld{4}{3}{darkgreen!20}{b_{16}}
+ \feld{4}{2}{darkgreen!20}{b_{17}}
+ \feld{4}{1}{darkgreen!20}{b_{18}}
+ \feld{4}{0}{darkgreen!20}{b_{19}}
+
+ \feld{5}{3}{darkgreen!10}{b_{20}}
+ \feld{5}{2}{darkgreen!10}{b_{21}}
+ \feld{5}{1}{darkgreen!10}{b_{22}}
+ \feld{5}{0}{darkgreen!10}{b_{23}}
+
+ \feld{6}{3}{blue!20}{b_{24}}
+ \feld{6}{2}{blue!20}{b_{25}}
+ \feld{6}{1}{blue!20}{b_{26}}
+ \feld{6}{0}{blue!20}{b_{27}}
+
+ \feld{7}{3}{blue!10}{b_{28}}
+ \feld{7}{2}{blue!10}{b_{29}}
+ \feld{7}{1}{blue!10}{b_{30}}
+ \feld{7}{0}{blue!10}{b_{31}}
+
+ \gitter
+
+ \draw[->] \punkt{8.1}{2} -- \punkt{9.3}{2};
+\end{scope}
+
+
+\begin{scope}[xshift=7.5cm]
+
+ \feld{0}{3}{red!20}{b_{0}}
+ \feld{1}{2}{red!20}{b_{1}}
+ \feld{2}{1}{red!20}{b_{2}}
+ \feld{3}{0}{red!20}{b_{3}}
+
+ \feld{1}{3}{red!10}{b_{4}}
+ \feld{2}{2}{red!10}{b_{5}}
+ \feld{3}{1}{red!10}{b_{6}}
+ \feld{4}{0}{red!10}{b_{7}}
+
+ \feld{2}{3}{yellow!20}{b_{8}}
+ \feld{3}{2}{yellow!20}{b_{9}}
+ \feld{4}{1}{yellow!20}{b_{10}}
+ \feld{5}{0}{yellow!20}{b_{11}}
+
+ \feld{3}{3}{yellow!10}{b_{12}}
+ \feld{4}{2}{yellow!10}{b_{13}}
+ \feld{5}{1}{yellow!10}{b_{14}}
+ \feld{6}{0}{yellow!10}{b_{15}}
+
+ \feld{4}{3}{darkgreen!20}{b_{16}}
+ \feld{5}{2}{darkgreen!20}{b_{17}}
+ \feld{6}{1}{darkgreen!20}{b_{18}}
+ \feld{7}{0}{darkgreen!20}{b_{19}}
+
+ \feld{5}{3}{darkgreen!10}{b_{20}}
+ \feld{6}{2}{darkgreen!10}{b_{21}}
+ \feld{7}{1}{darkgreen!10}{b_{22}}
+ \feld{0}{0}{darkgreen!10}{b_{23}}
+
+ \feld{6}{3}{blue!20}{b_{24}}
+ \feld{7}{2}{blue!20}{b_{25}}
+ \feld{0}{1}{blue!20}{b_{26}}
+ \feld{1}{0}{blue!20}{b_{27}}
+
+ \feld{7}{3}{blue!10}{b_{28}}
+ \feld{0}{2}{blue!10}{b_{29}}
+ \feld{1}{1}{blue!10}{b_{30}}
+ \feld{2}{0}{blue!10}{b_{31}}
+
+ \gitter
+
+\end{scope}
+
+\end{tikzpicture}
+\end{document}
+
diff --git a/buch/chapters/90-crypto/uebungsaufgaben/9001.tex b/buch/chapters/90-crypto/uebungsaufgaben/9001.tex
index 9cda25e..7ed1e57 100644
--- a/buch/chapters/90-crypto/uebungsaufgaben/9001.tex
+++ b/buch/chapters/90-crypto/uebungsaufgaben/9001.tex
@@ -1,31 +1,31 @@
-$A$ und $B$ einigen sich darauf, das Diffie-Hellman-Verfahren für
-$p=2027$ durchzuführen und mit $g=3$ zu arbeiten.
-$A$ verwenden $a=49$ als privaten Schlüssel und erhält von $B$
-den öffentlichen Schlüssel $y=1772$.
-Welchen gemeinsamen Schlüssel verwenden $A$ und $B$?
-
-\begin{loesung}
-Der zu verwendende gemeinsame Schlüssel ist
-$g^{ab}=(g^b)^a = y^a\in\mathbb{F}_{2027}$.
-Diese Potenz kann man mit dem Divide-and-Conquer-Algorithmus effizient
-berechnen.
-Die Binärdarstellung des privaten Schlüssels von $A$ ist
-$a=49_{10}=\texttt{110001}_2$.
-Der Algorithmus verläuft wie folgt:
-\begin{center}
-\begin{tabular}{|>{$}r<{$}|>{$}r<{$}|>{$}r<{$}|>{$}r<{$}|}
-\hline
-i&g^{2^i}&a_i& x\\
-\hline
-0& 3& 1& 3\\
-1& 9& 0& 3\\
-2& 81& 0& 3\\
-3& 480& 0& 3\\
-4& 1349& 1& 2020\\
-5& 1582& 1& 1088\\
-\hline
-\end{tabular}
-\end{center}
-Der gemeinsame Schlüssel ist daher $s=1088$.
-\end{loesung}
-
+$A$ und $B$ einigen sich darauf, das Diffie-Hellman-Verfahren für
+$p=2027$ durchzuführen und mit $g=3$ zu arbeiten.
+$A$ verwenden $a=49$ als privaten Schlüssel und erhält von $B$
+den öffentlichen Schlüssel $y=1772$.
+Welchen gemeinsamen Schlüssel verwenden $A$ und $B$?
+
+\begin{loesung}
+Der zu verwendende gemeinsame Schlüssel ist
+$g^{ab}=(g^b)^a = y^a\in\mathbb{F}_{2027}$.
+Diese Potenz kann man mit dem Divide-and-Conquer-Algorithmus effizient
+berechnen.
+Die Binärdarstellung des privaten Schlüssels von $A$ ist
+$a=49_{10}=\texttt{110001}_2$.
+Der Algorithmus verläuft wie folgt:
+\begin{center}
+\begin{tabular}{|>{$}r<{$}|>{$}r<{$}|>{$}r<{$}|>{$}r<{$}|}
+\hline
+i&g^{2^i}&a_i& x\\
+\hline
+0& 3& 1& 3\\
+1& 9& 0& 3\\
+2& 81& 0& 3\\
+3& 480& 0& 3\\
+4& 1349& 1& 2020\\
+5& 1582& 1& 1088\\
+\hline
+\end{tabular}
+\end{center}
+Der gemeinsame Schlüssel ist daher $s=1088$.
+\end{loesung}
+