typos Kapitel 10

3 files changed, 164 insertions, 146 deletions

diff --git a/buch/chapters/90-crypto/aes.tex b/buch/chapters/90-crypto/aes.tex
index acdda22..f726e24 100644
--- a/buch/chapters/90-crypto/aes.tex
+++ b/buch/chapters/90-crypto/aes.tex
@@ -29,9 +29,9 @@ 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.
+In diesem Abschnitt soll gezeigt werde, wie sich die im AES
+spezifizierten Operationen mit der Arithmetik 
+eines endlichen Körpers beschreiben lassen.
 Im Abschnitt~\ref{buch:subsection:byte-operationen} werden
 Bytes als Elemente in einem endlichen Körper $\mathbb{F}_{2^8}$
 interpretiert.
@@ -128,7 +128,7 @@ 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
+Die $S$-Box-Operation kann also vektoriell geschrieben werden als
 \[
 	S(x) = A\overline{x}+q.
 \]
@@ -175,7 +175,7 @@ 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}
+um 3 Bytes, wie in Abbildung~\ref{buch:crypto:fig:shift}
 dargestellt.
 Diese Operation könnte mit einer Permutationsmatrix beschrieben werden,
 dies wäre jedoch keine effiziente Implementation.
@@ -183,7 +183,7 @@ 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$.
+vierdimensionalen Vektorraumes $\mathbb{F}_{2^8}^4$ angesehen werden.
 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}$.
@@ -335,7 +335,7 @@ die natürlich ebenfalls umkehrbar ist.
 
 \subsection{Schlüssel
 \label{buch:subsection:schlüssel}}
-Die von den Byte- und Blockoperationen mischen die einzelnen Bits
+Die 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.
@@ -343,7 +343,8 @@ macht.
 \subsubsection{Schlüsseladdition}
 Nach jeder Spaltenmischoperation wird ein Rundenschlüssel
 zum Blockhinzuaddiert.
-Beim ersten Mal wird dazu einfach das Schlüsselmaterial verwendet.
+Beim ersten Mal wird dazu einfach das vom Benutzer vorgegebene
+Schlüsselmaterial verwendet.
 Für die folgenden Runden muss aus diesem Schlüssel neues
 Material, die sogenannten Rundenschlüssel, gewonnen werden.
 
@@ -402,7 +403,7 @@ Die Operation $\pi$ vertauscht die Bytes des Vektors zyklisch:
 \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.
+Die $r_i$ Operation addiert in Runde $i$ 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}$
diff --git a/buch/chapters/90-crypto/arith.tex b/buch/chapters/90-crypto/arith.tex
index b05110f..2d7de90 100644
--- a/buch/chapters/90-crypto/arith.tex
+++ b/buch/chapters/90-crypto/arith.tex
@@ -34,22 +34,23 @@ besprochen.
 \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.
+beliebigen Halbgruppe $G$ haben.
+Die Halbgruppe $G$ kann die Multiplikation der ganzen oder reellen Zahlen
+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.
+eines endlichen Körpers oder eine elliptische Kurve
+(siehe Abschnitt~\ref{buch:subsection:elliptische-kurven}).
 
-Zur Berechnung von $a^k$ sind bei einer naiven Durchführung des
-Algorithmus $k-1$ Multiplikationen nötig, immer sofort gefolgt
+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
 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
+naive Algorithmus $O(2^l)$ Operationen, die Laufzeit wächst
 also exponentiell mit der Bitlänge von $k$ an.
 Der nachfolgend beschriebene Algorithmus reduziert die Laufzeit auf
-die $O(l)$.
+$O(l)$.
 
 Zunächst schreiben wir den Exponenten $k$ in binärer Form als
 \[
@@ -78,12 +79,15 @@ 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
+
+Wenn $a\in\mathbb{R}$ und $k$ keine Ganzzahl ist sondern auch noch
+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,
+k=k_l2^l + \dots + k_12^1 + k_02^0 + {\color{red}k_{-1}2^{-1} + k_{-2}2^{-2}+\dots,}
 \]
-dann können die Potenzen $a^{2^{-i}}$ durch wiederholtes Wurzelziehen
+dann können die Potenzen ${\color{red}a^{2^{-i}}}$ durch wiederholtes Wurzelziehen
 \[
+\color{red}
 a^{2^{-i}} = a^{\frac12\cdot 2^{-i+1}} = \sqrt{a^{2^{-i+1}}}
 \]
 gefunden werden.
@@ -95,8 +99,8 @@ implementieren.
 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 Initialisiere $f=1$ und $q=a$
+\item Falls $k$ ungerade ist, also $k_i=1$, setze $f:=f\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.
@@ -106,8 +110,8 @@ am effizientesten als Rechtsshift implementiert werden kann.
 \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 $f=1$, $q=1.1$
+\item $k$ ist ungerade: $f:=1.1$
 \item $q:=q^2=1.21$, $k := 8$
 \item $k$ ist gerade
 \item $q:=q^2=1.4641$, $k := 4$
@@ -115,11 +119,12 @@ Die Berechnung von $1.1^{17}$ mit diesem Algorithmus ergibt
 \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$ ist ungerade: $f:=f\cdot q=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.
+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$
@@ -167,29 +172,26 @@ des Divisionsalgorithmus.
 	&\text{Summanden}&\text{Summe}&\text{reduziert}
 \\
 \hline
-\texttt{101111}               &                &\texttt{101111} 
-	&\texttt{101111}&\texttt{101111}&\texttt{101111}
+\texttt{101111}               &                &\texttt{101111} &\texttt{101111}&\texttt{101111}&\texttt{101111}
 \\
-\texttt{101111\phantom{0}}    &\texttt{{\color{red}1011110}}&\texttt{101001}
-	&               &               &
+\texttt{101111\phantom{0}}    &\texttt{{\color{red}1011110}}&\texttt{101001} &               &               &
 \\
-\texttt{101111\phantom{00}}   &\texttt{0{\color{red}111010}}&\texttt{011101}
-	&               &               &
+\texttt{101111\phantom{00}}   &\texttt{{\color{red}1010010}}&\texttt{011101} &               &               &
 \\
-\texttt{101111\phantom{000}}  &\texttt{0001010}&\texttt{000101}
-	&\texttt{000101}&\texttt{110100}&\texttt{110100}
+\texttt{101111\phantom{000}}  &\texttt{0111010}&\texttt{111010} &\texttt{000101}&\texttt{110100}&\texttt{110100}
 \\
-\texttt{101111\phantom{0000}} &\texttt{0010100}&\texttt{001010}
-	&               &               &
+\texttt{101111\phantom{0000}} &\texttt{\color{red}1110100}&\texttt{111111} &               &               &
 \\
-\texttt{101111\phantom{00000}}&\texttt{0101000}&\texttt{010100}
-	&\texttt{010100}&\texttt{{\color{red}1001000}}&\texttt{10011}\rlap{$\mathstrut=19$}
+\texttt{101111\phantom{00000}}&\texttt{\color{red}1111110}&\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
+\caption{Multiplikation von $41=\texttt{101001}_2$ mit $47=\texttt{101111}_2$
+in $\mathbb{F}_{53}$.
+Um die Länge des Resultates zu kontrollieren, wird nach jeder
+Multplikation mit $2$ modulo $p=53$ reduziert.
+Falls das Resultat
 $>p$ ist, wie in den rot markierten Zeilen $p=53=\texttt{110101}_2$
-durchgeführt.
+so lange nötig subtrahiert.
 Bei der Bildung der Summe wird ebenfalls in jedem Schritt falls nötig
 reduziert, angezeigt durch die roten Zahlen in der zweitletzten
 Spalte.
@@ -221,8 +223,9 @@ 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
+Ein Element in $\mathbb{F}_2[X]/(m)$ kann
+durch ein Polynom vom Grad $l-1$
+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.
 \]
@@ -268,7 +271,7 @@ 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
+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)$ 
diff --git a/buch/chapters/90-crypto/ff.tex b/buch/chapters/90-crypto/ff.tex
index a1cb747..d13fe62 100644
--- a/buch/chapters/90-crypto/ff.tex
+++ b/buch/chapters/90-crypto/ff.tex
@@ -29,71 +29,74 @@ 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}
+Dank dem Algorithmus~\ref{buch:crypto:teile-und-hersche} ist auch
+sie effizient durchführbar.
+
+%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
+Algorithmus~\ref{buch:crypto:algo:teile-und-hersche} in der folgenden
 Tabelle
 \begin{center}
 \begin{tabular}{|>{$}r<{$}|>{$}r<{$}|>{$}r<{$}|>{$}r<{$}|}
 \hline
- i&   f& a_i&    x\\
+ i&   q& k_i&    f\\
 \hline
  0&   7&   1&    7\\
  1&  49&   0&    7\\
@@ -109,6 +112,8 @@ Tabelle
 \hline
 \end{tabular}
 \end{center}
+In der Spalte $q$ stehen die Potenzen $a^{i+1}=7^{i+1}$, in Spalte $f$ die
+ausgerechneten Produkte.
 Daraus liest man ab, dass $7^{2021}=333\in\mathbb{F}_{1291}$.
 \end{beispiel}
 
@@ -125,39 +130,39 @@ 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}
+%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}
 
 
 %
@@ -200,6 +205,8 @@ $y=g^b\in\mathbb{F}_p$.
 \centering
 \includegraphics{chapters/90-crypto/images/dh.pdf}
 \caption{Schlüsselaustausch nach Diffie-Hellman.
+\index{Diffie-Hellmann}%
+\index{Schlüsseltausch}%
 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
@@ -224,12 +231,13 @@ werden.
 
 \subsection{Elliptische Kurven
 \label{buch:subsection:elliptische-kurven}}
+\index{elliptische Kurve}%
 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
+Es reicht, eine Menge mit einer Multiplikation zu haben, fir die
 die Gleichung $a^x=b$ schwierig zu lösen ist.
-Ein Gruppe wäre also durchaus ausreichend.
+Ein Halbgruppe 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.
@@ -255,6 +263,7 @@ 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
+\index{Kurve}%
 Koordinaten in einem endlichen Körper.
 
 In diesem Abschnitt wird gezeigt, dass sogenannte elliptische Kurven
@@ -276,11 +285,12 @@ 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.
+lösen, zum Scheitern verurteilt ist.
 
 \begin{definition}
 \label{buch:crypto:def:ellipticcurve}
 Die {\em elliptische Kurve} $E_{a,b}(\Bbbk)$ über dem Körper $\Bbbk$ ist 
+\index{elliptische Kurve}%
 die Menge
 \[
 E_{a,b}(\Bbbk)
@@ -361,7 +371,7 @@ 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.
+zeigt eine elliptische Kurve in der Ebene $\mathbb{R}^2$.
 
 \subsubsection{Geometrische Definition der Gruppenoperation}
 In der speziellen Form \ref{buch:crypto:ellvereinfacht} ist die
@@ -520,8 +530,9 @@ 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$.
+Es bleibt noch der für den Algorithmus~\ref{buch:crypto:teile-und-hersche}
+wichtige Fall des Quadrierens in der Gruppe zu
+behandeln, also der Fall $g_1=g_2$.
 In diese Fall sind die Formeln
 \eqref{buch:crypto:eqn:x3}
 und
@@ -556,7 +567,7 @@ ergibt die Gleichung
 (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
+Damit bei $t=0$ eine doppelte Nullstelle müssen 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
@@ -567,7 +578,7 @@ y_1^2+x_1y_1&=x_1^3+ax_1+b
 +(y_1
 -3x_1^2
 -a)u
-&=0
+&=0.
 \label{buch:crypto:eqn:rest2}
 \end{align}
 Die erste Gleichung \eqref{buch:crypto:eqn:rest1} drückt aus,
@@ -624,7 +635,7 @@ y
 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}
@@ -646,6 +657,7 @@ 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.
+XXX (0,0) muss erst definiert werden
 \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
@@ -671,9 +683,11 @@ Die Addition in $\mathbb{F}_p$ wird für diesen Algorithmus überhaupt
 nicht benötigt.
 
 In einer elliptischen Kurve gibt es ebenfalls eine Multiplikation,
-aus der sich mit dem 
-Algorithmus~\ref{buch:crypto:teile-und-hersche} eine effizienter
-Potenzieralgorithmus konstruieren lässt.
+für die sich mit Algorithmus~\ref{buch:crypto:teile-und-hersche}
+eine effizienter Potenzieralgorithmus konstruieren lässt.
+Die resultierende Potenzfunktion stellt sich ebenfalls als 
+schwierig zu invertieren heraus, kann also ebenfalls für einen
+Diffie-Hellmann-Schlüsseltausch verwendet werden.
 
 Die im Internet Key Exchange Protokol
 in RFC 2409