1 files changed, 493 insertions, 490 deletions

diff --git a/buch/chapters/90-crypto/ff.tex b/buch/chapters/90-crypto/ff.tex
index d13fe62..b295db8 100644
--- a/buch/chapters/90-crypto/ff.tex
+++ b/buch/chapters/90-crypto/ff.tex
@@ -227,493 +227,496 @@ $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}}
-\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, fir die
-die Gleichung $a^x=b$ schwierig zu lö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.
-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
-\index{Kurve}%
-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 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)
-=
-\{(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 $\mathbb{R}^2$.
-
-\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)
-=
-XXX
-\]
-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 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
-\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 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
-\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.
-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
-\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{Diffie-Hellman in einer elliptischen Kurve}
-Der klassische Diffie-Hellmann-Schlüsselalgorithmus in einem Körper
-$\mathbb{F}_p$ basiert darauf, dass man beliebige Potenzen eines 
-Elementes berechnen kann, und dass es schwierig ist, diese Operation
-umzukehren.
-Die Addition in $\mathbb{F}_p$ wird für diesen Algorithmus überhaupt
-nicht benötigt.
-
-In einer elliptischen Kurve gibt es ebenfalls eine Multiplikation,
-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
-\cite{buch:rfc2409}
-definierte Oakley-Gruppe 4
-zum Beispiel verwendet einen Galois-Körper $\mathbb{F}_{2^{185}}$ 
-mit dem Minimalpolynom $m(x)=x^{185}+x^{69}+1\in \mathbb{F}_2[x]$
-und den Koeffizienten
-\begin{align*}
-a&=0\\
-b&=x^{12}+x^{11} + x^{10} + x^9 + x^7 + x^6 + x^5 + x^3 +1,
-\end{align*} 
-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.
-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
-für einen brute-force-Angriff durchprobiert werden müssten.
-
-
-
-
-
-
-
-
+%%
+%% elliptisch.tex
+%%
+%% (c) 2021 Prof Dr Andreas Müller, OST Ostshweizer Fachhochschule
+%%
+%\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, fir die
+%die Gleichung $a^x=b$ schwierig zu lö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.
+%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
+%\index{Kurve}%
+%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 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)
+%=
+%\{(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 $\mathbb{R}^2$.
+%
+%\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)
+%=
+%XXX
+%\]
+%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 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
+%\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 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
+%\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.
+%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
+%\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{Diffie-Hellman in einer elliptischen Kurve}
+%Der klassische Diffie-Hellmann-Schlüsselalgorithmus in einem Körper
+%$\mathbb{F}_p$ basiert darauf, dass man beliebige Potenzen eines 
+%Elementes berechnen kann, und dass es schwierig ist, diese Operation
+%umzukehren.
+%Die Addition in $\mathbb{F}_p$ wird für diesen Algorithmus überhaupt
+%nicht benötigt.
+%
+%In einer elliptischen Kurve gibt es ebenfalls eine Multiplikation,
+%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
+%\cite{buch:rfc2409}
+%definierte Oakley-Gruppe 4
+%zum Beispiel verwendet einen Galois-Körper $\mathbb{F}_{2^{185}}$ 
+%mit dem Minimalpolynom $m(x)=x^{185}+x^{69}+1\in \mathbb{F}_2[x]$
+%und den Koeffizienten
+%\begin{align*}
+%a&=0\\
+%b&=x^{12}+x^{11} + x^{10} + x^9 + x^7 + x^6 + x^5 + x^3 +1,
+%\end{align*} 
+%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.
+%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
+%für einen brute-force-Angriff durchprobiert werden müssten.
+%
+%
+%
+%
+%
+%
+%
+%