1 files changed, 62 insertions, 56 deletions

diff --git a/buch/chapters/90-crypto/arith.tex b/buch/chapters/90-crypto/arith.tex
index d140489..4b0828b 100644
--- a/buch/chapters/90-crypto/arith.tex
+++ b/buch/chapters/90-crypto/arith.tex
@@ -24,7 +24,7 @@ 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
+Dafür geeignete Methoden werden in den Abschnitten
 \ref{buch:subsection:rechenoperationen-in-fp}
 und
 \ref{buch:subsection:rechenoperatione-in-f2l}
@@ -40,11 +40,11 @@ sein, dies wird zum Beispiel in Implementationen der Potenzfunktion
 in Programmierbibliotheken verwendet.
 Für kryptographische Anwendungen ist $G$ die multiplikative Gruppe
 eines endlichen Körpers oder eine elliptische Kurve
-(siehe Abschnitt~\ref{buch:subsection:elliptische-kurven}).
+(siehe Abschnitt~\ref{buch:section:elliptische-kurven}).
 
 Zur Berechnung von $a^k$ in $\mathbb{F}_p$ sind bei einer naiven Vorgehen
 $k-1$ Multiplikationen nötig, immer sofort gefolgt
-von einer Reduktion $\mod p$ um sicherzustellen, dass die Resultate
+von einer Reduktion modulo $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)$ Operationen, die Laufzeit wächst
@@ -127,44 +127,19 @@ werden also genau $5$ Multiplikationen ausgeführt statt die
 16 Multiplikationen, die bei der naiven Vorgehensweise nötig wären.
 \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$
+also typischerweise ungefähr verdoppelt.
+In $\mathbb{F}_p$ muss anschliessend das Resultat modulo $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<{$}}
@@ -201,12 +176,48 @@ Divisionsalgorithmus.
 \label{buch:crypto:fig:reduktion}}
 \end{figure}
 
+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 nach jeder Addition des 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.
+
+
 Es ist also möglich, mit gleichem Aufwand an Operationen
-aber mit halbe Speicherplatzbedarf die Multiplikationen in $\mathbb{F}_p$
+aber mit halbem 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.
 
+\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}
+
 \subsection{Rechenoperationen in $\mathbb{F}_{2^l}$
 \label{buch:subsection:rechenoperatione-in-f2l}}
 Von besonderem praktischem Interesse sind die endlichen Körper
@@ -214,6 +225,19 @@ $\mathbb{F}_{2^l}$.
 Die arithmetischen Operationen in diesen Körpern lassen sich besonders
 effizient in Hardware realisieren.
 
+\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}
+
 \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$ 
@@ -229,9 +253,11 @@ dargestellt werden, 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$
+In einer Maschine kann ein Elemente von $\mathbb{F}_2[X]/(m)$
+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.
@@ -243,9 +269,10 @@ 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
+Die Subtraktion, die für die Reduktionsoperation modulo $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
@@ -255,15 +282,6 @@ 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.
@@ -274,25 +292,13 @@ $X^4+X^3+X+1$ ersetzen und addieren kann.
 Ein Produkt $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)$ 
+Mit einem 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}