aboutsummaryrefslogtreecommitdiffstats
path: root/buch/chapters/90-crypto
diff options
context:
space:
mode:
authorAndreas Müller <andreas.mueller@ost.ch>2021-09-25 20:41:52 +0200
committerAndreas Müller <andreas.mueller@ost.ch>2021-09-25 20:41:52 +0200
commit39f232312a86c70c271f8edef77b233e1dd40c1c (patch)
treed63150486a2f97a810b63a8f3cdd4c3cb7afb851 /buch/chapters/90-crypto
parentzweite Lesung (diff)
downloadSeminarMatrizen-39f232312a86c70c271f8edef77b233e1dd40c1c.tar.gz
SeminarMatrizen-39f232312a86c70c271f8edef77b233e1dd40c1c.zip
2. Lesung
Diffstat (limited to 'buch/chapters/90-crypto')
-rw-r--r--buch/chapters/90-crypto/aes.tex28
-rw-r--r--buch/chapters/90-crypto/arith.tex118
-rw-r--r--buch/chapters/90-crypto/chapter.tex2
-rw-r--r--buch/chapters/90-crypto/elliptisch.tex26
-rw-r--r--buch/chapters/90-crypto/ff.tex86
5 files changed, 137 insertions, 123 deletions
diff --git a/buch/chapters/90-crypto/aes.tex b/buch/chapters/90-crypto/aes.tex
index f726e24..0ece6b1 100644
--- a/buch/chapters/90-crypto/aes.tex
+++ b/buch/chapters/90-crypto/aes.tex
@@ -9,7 +9,7 @@
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
+entstehen könnte, dass sich dahinter nicht 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.
@@ -51,12 +51,13 @@ 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
+Die Elemente können dargestellt werden als Polynome
\[
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$.
+Das Byte $\texttt{63}_{16}$ entspricht also dem Polynom
+$X^6+X^5+X+1$ in $\mathbb{F}_2[X]/(m)$.
Die Interpretation der Bytes als Elemente eines Körpers bedeutet,
dass jede Multiplikation mit einem nicht verschwindenden Byte
@@ -66,7 +67,7 @@ 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.
+Für die Operation der sogenannten $S$-Box wird wie folgt zusammengesetzt.
Zunächst wird ein Byte $x$ durch das zugehörige multiplikative
inverse Element
\[
@@ -135,7 +136,7 @@ Die $S$-Box-Operation kann also vektoriell geschrieben werden als
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.
+und ebenso nur 256 mögliche Werte.
\subsection{Block-Operationen
\label{buch:subsection:block-operationen}}
@@ -171,8 +172,8 @@ 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
+nur auf Spalten wirkt.
+Die Zeilen\-misch\-ope\-ra\-tion 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:shift}
@@ -342,7 +343,7 @@ macht.
\subsubsection{Schlüsseladdition}
Nach jeder Spaltenmischoperation wird ein Rundenschlüssel
-zum Blockhinzuaddiert.
+zum Block hinzuaddiert.
Beim ersten Mal wird dazu einfach das vom Benutzer vorgegebene
Schlüsselmaterial verwendet.
Für die folgenden Runden muss aus diesem Schlüssel neues
@@ -366,10 +367,10 @@ Die Erzeugung der Rundenschlüssel ist in Abbildung
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 Blöcke $K_0$ bis $K_7$ enthalten den ursprünglichen Schlüssel.
Die Erzeugung eines neuen Blocks Schlüsselmatrial beginnt damit,
-dass der letzte Vektor des vorangegangenblocks drei Operationen
-unterworfen werden.
+dass der letzte Vektor des vorangegangen Blocks drei Operationen
+unterworfen wird.
\begin{itemize}
\item
Die Operation $\pi$ vertauscht die Bytes des Vektors zyklisch:
@@ -401,9 +402,10 @@ Die Operation $\pi$ vertauscht die Bytes des Vektors zyklisch:
\end{tikzpicture}
\end{center}
\item
-Die $S$-Operation wendet die $S$-Box auf alle Bytes eines Vektors an.
+Die $S$-Operation wendet die $S$-Box auf jedes Byte eines Vektors an.
\item
-Die $r_i$ Operation addiert in Runde $i$ 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 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}
diff --git a/buch/chapters/90-crypto/chapter.tex b/buch/chapters/90-crypto/chapter.tex
index 829a718..d7e248a 100644
--- a/buch/chapters/90-crypto/chapter.tex
+++ b/buch/chapters/90-crypto/chapter.tex
@@ -15,7 +15,7 @@ Die Eigenschaften dieser Körper sind reichhaltig genug, um
kryptographisch 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.
+In diesem Abschnitt soll dies an einigen Beispielen illustriert werden.
\input{chapters/90-crypto/arith.tex}
\input{chapters/90-crypto/ff.tex}
diff --git a/buch/chapters/90-crypto/elliptisch.tex b/buch/chapters/90-crypto/elliptisch.tex
index 99ed4cd..f5bf579 100644
--- a/buch/chapters/90-crypto/elliptisch.tex
+++ b/buch/chapters/90-crypto/elliptisch.tex
@@ -11,11 +11,11 @@ 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, fir die
-die Gleichung $a^x=b$ schwierig zu lösen ist.
+die Gleichung $a^x=b$ schwierig nach $x$ aufzulösen ist.
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.
+$S^1=\{z\in\mathbb{C} \mid |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.
@@ -42,7 +42,7 @@ 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.
+über endlichen Körpern genau die verlangten Eigenschaften haben.
\subsection{Definition}
Elliptische Kurven sind Lösungen einer Gleichung der Form
@@ -70,7 +70,7 @@ die Menge
\[
E_{a,b}(\Bbbk)
=
-\{(X,Y)\in\Bbbk^2\;|\;Y^2+XY=X^3+aX+b\},
+\{(X,Y)\in\Bbbk^2 \mid Y^2+XY=X^3+aX+b\},
\]
für $a,b\in\Bbbk$.
\end{definition}
@@ -150,7 +150,7 @@ Abbildung~\ref{buch:crypto:fig:elliptischekurve}
zeigt eine elliptische Kurve in der Ebene $\mathbb{R}^2$.
\subsection{Geometrische Definition der Gruppenoperation}
-In der speziellen Form \ref{buch:crypto:ellvereinfacht} ist die
+In der speziellen Form \eqref{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.
@@ -165,7 +165,7 @@ 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
+auf der elliptischen Kurve indem man 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.
@@ -186,10 +186,10 @@ Punkte die gleiche $u$-Koordinaten haben.
\subsection{Gruppenoperation, algebraische Konstruktion}
Nach den geometrischen Vorarbeiten zur Definition der Gruppenoperation
-kann können wir die Konstruktion jetzt algebraisch über einem
+können wir jetzt die Konstruktion algebraisch über einem
beliebigen Körper umsetzen.
-Wir gehen jetzt wieder von der elliptischen Kurve in der Form
+Wir gehen wieder von der elliptischen Kurve in der Form
\begin{equation}
Y^2+XY=X^3+aX+b
\label{buch:crypto:eqn:grupopgl}
@@ -377,7 +377,7 @@ 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
+Die Werte $u$ und $v$ 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
@@ -490,7 +490,7 @@ Diffie-Hellmann-ähnlichen Verfahrens, wird das neutrale Element
nicht wirklich benötigt.
Um den Potenz-Algorithmus~\ref{buch:crypto:teile-und-hersche}
durchzuführen, brauchen wir nur die beiden Operationen
-Multiplizieren und quadrieren, für die wir bereits
+Multiplizieren und Quadrieren, für die wir bereits
geeignete Formeln gefunden haben.
\subsubsection{Gruppenstruktur auf einer elliptischen Kurve}
@@ -502,7 +502,7 @@ E_{a,b}(\mathbb{F}_{p^l})
=
\{
(X,Y)\in\mathbb{F}_{p^l}
-\;|\;
+\mid
Y^2+XY = X^3-aX-b
\}
\]
@@ -510,7 +510,7 @@ trägt eine Gruppenstruktur, die wie folgt definiert ist:
\begin{enumerate}
\item Es gibt ein neutrales Element, welches man manchmal als $(0,0)$
schreibt, obwohl dieser Punkt nicht auf der Kuve liegt.
-\item Das inverse Element von $(x,y)$ ist $(-x,-y-x)$.
+\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}
@@ -556,7 +556,7 @@ die die elliptische Kurve definieren.
Als Elemente $g$ für den Diffie-Hellmann-Algorithmus wird ein Punkt
der elliptischen Kurve verwendet, dessen $X$-Koordinaten durch das
-Polynom $g_x = x^4+x^3$ gegeben ist.
+Polynom $g(x) = x^4+x^3$ gegeben ist.
Der Standard spezifiziert die $Y$-Koordinate nicht, diese kann aus
den gegebenen Daten abgeleitet werden.
Die entstehende Gruppe hat etwa $4.9040\cdot10^{55}$ Elemente, die
diff --git a/buch/chapters/90-crypto/ff.tex b/buch/chapters/90-crypto/ff.tex
index 066b9d2..3cdc748 100644
--- a/buch/chapters/90-crypto/ff.tex
+++ b/buch/chapters/90-crypto/ff.tex
@@ -12,11 +12,34 @@ endlichen Körpern Algorithmen zu konstruieren erlaubt, mit denen sich
zum Beispiel sehr effizient kryptographische Schlüssel aushandeln
lassen.
Der klassische Diffie-Hellmann-Algorithmus in einem Galois-Körper
-$\mathbb{F}_p$ wird in Abschnitt~\ref{buch:subsection:elliptische-kurven}
+$\mathbb{F}_p$ wird in Abschnitt~\ref{buch:section:elliptische-kurven}
verallgemeinert auf eine sogenannte elliptische Kurve.
Diese Version des Algorithmus ist sehr effizient was die Bitlänge der
Schlüssel betrifft.
+\begin{table}
+\centering
+\begin{tabular}{|>{$}r<{$}|>{$}r<{$}|>{$}r<{$}|>{$}r<{$}|}
+\hline
+ i& q& k_i& f\\
+\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}
+\caption{Potenzen von 7 im Körper $\mathbb{F}_{1291}$.
+\label{buch:crypto:fig:f1291}}
+\end{table}
+
\subsection{Potenzen in $\mathbb{F}_p$ und diskreter Logarithmus
\label{buch:subsection:potenzen-diskreter-logarithmus}}
Für kryptographische Anwendungen wird eine einfach zu berechnende
@@ -28,6 +51,7 @@ 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.
Dank dem Algorithmus~\ref{buch:crypto:teile-und-hersche} ist auch
sie effizient durchführbar.
@@ -87,38 +111,20 @@ sie effizient durchführbar.
%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:teile-und-hersche} in der folgenden
-Tabelle
-\begin{center}
-\begin{tabular}{|>{$}r<{$}|>{$}r<{$}|>{$}r<{$}|>{$}r<{$}|}
-\hline
- i& q& k_i& f\\
-\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}
+Algorithmus~\ref{buch:crypto:teile-und-hersche} in der
+Tabelle~\ref{buch:crypto:fig:f1291}
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}
-Die Tabelle suggeriert, dass die Potenzen von $g$ ``wild'', also
-scheinbar ohne System in $\mathbb{F}_p$ herumspringen.
+Die Tabelle~\ref{buch:crypto:fig:f1291} 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
@@ -164,6 +170,21 @@ Funktion.
%berechnet werden.
%\end{algorithmus}
+\begin{figure}
+\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
+$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}
%
% Diffie-Hellman Schlüsseltausch
@@ -179,7 +200,7 @@ ausgehandelten Schlüssel zu ermitteln.
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
+Weiter erzeugen sie je 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$
@@ -199,21 +220,6 @@ 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.
-\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
-$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$.