new stuff

4 files changed, 408 insertions, 1 deletions

diff --git a/buch/chapters/90-crypto/chapter.tex b/buch/chapters/90-crypto/chapter.tex
index 829169f..c5f65a7 100644
--- a/buch/chapters/90-crypto/chapter.tex
+++ b/buch/chapters/90-crypto/chapter.tex
@@ -16,6 +16,8 @@ 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.
 
+TODO: Kapitel über Rechnen in den Körpern $\mathbb{F}_p$ und $\mathbb{F}_{2^l}$.
+
 \input{chapters/90-crypto/ff.tex}
 \input{chapters/90-crypto/aes.tex}
 \input{chapters/90-crypto/rs.tex}
diff --git a/buch/chapters/90-crypto/ff.tex b/buch/chapters/90-crypto/ff.tex
index d5d2fcf..9d92312 100644
--- a/buch/chapters/90-crypto/ff.tex
+++ b/buch/chapters/90-crypto/ff.tex
@@ -354,7 +354,303 @@ Gruppenoperation in der elliptischen Kurve.
 Abbildung~\ref{buch:crypto:fig:elliptischekurve}
 zeigt eine elliptische Kurve in der Ebene.
 
-\subsubsection{Gruppenoperation}
+\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}
 
diff --git a/buch/chapters/90-crypto/rechnungen/elliptic.maxima b/buch/chapters/90-crypto/rechnungen/elliptic.maxima
new file mode 100644
index 0000000..8c43e6c
--- /dev/null
+++ b/buch/chapters/90-crypto/rechnungen/elliptic.maxima
@@ -0,0 +1,42 @@
+/*
+ * elliptic.maxima
+ *
+ * (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
+ */
+
+p: Y^2+X*Y - X^3 - a*X -b;
+
+x: x1*t+(1-t)*x2;
+y: y1*t+(1-t)*y2;
+
+q: subst(x,X,p);
+q: subst(y,Y,q);
+q: ratsimp(expand(q));
+tex(q);
+
+qr: divide(q,t*(t-1),t);
+r: qr[2];
+q: qr[1];
+tex(q);
+
+subst(0,t,r);
+subst(1,t,r);
+
+tex(r);
+
+polydecomp(qr[2], t);
+
+s: solve(q = 0, t);
+tex(s);
+
+x3: ratsimp(expand(subst(s, x)));
+y3: ratsimp(expand(subst(s, y)));
+
+tex(x3);
+tex(y3);
+
+Y3: expand(y3 * (x2-x1)^3 - (y2-y1)^3 - (x2-x1)*(y2-y1)^2 );
+Y3: factor(expand(Y3));
+tex(Y3);
+
+
diff --git a/buch/chapters/90-crypto/rechnungen/tangent.maxima b/buch/chapters/90-crypto/rechnungen/tangent.maxima
new file mode 100644
index 0000000..aa7d236
--- /dev/null
+++ b/buch/chapters/90-crypto/rechnungen/tangent.maxima
@@ -0,0 +1,67 @@
+/*
+ * tangent.maxima
+ *
+ * (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule 
+ */
+
+p: Y^2+X*Y - X^3 - a*X -b;
+
+x: x1 + u * t;
+y: y1 + v * t;
+
+q: subst(x,X,p);
+q: subst(y,Y,q);
+q: ratsimp(expand(q));
+tex(q);
+tex(coeff(expand(q), t, 3));
+tex(coeff(expand(q), t, 2));
+tex(coeff(expand(q), t, 1));
+tex(coeff(expand(q), t, 0));
+qr: divide(q,t^2,t);
+r: qr[2];
+s: solve(qr[1] = 0, t);
+tex(s);
+
+T: subst(s, t);
+
+U: x1+2*y1;
+V: y1-3*x1^2-a;
+X: subst(U, u, x);
+Y: subst(V, v, y);
+T: subst(U, u, T);
+T: subst(V, v, T);
+ratsimp(expand(T));
+
+q: subst(U, u, q);
+q: subst(V, v, q);
+
+qr: divide(q,t^2,t);
+r: qr[2];
+q: qr[1];
+tex(q);
+
+tex(coeff(r, t, 3));
+tex(coeff(r, t, 2));
+tex(coeff(r, t, 1));
+tex(coeff(r, t, 0));
+
+subst(0,t,r);
+subst(0,t,diff(r,t));
+
+tex(r);
+
+polydecomp(qr[2], t);
+
+s: solve(q = 0, t);
+tex(s);
+
+/*
+x3: ratsimp(expand(subst(s, -X)));
+y3: ratsimp(expand(subst(s, -Y-X)));
+*/
+
+x3: ratsimp(expand(subst(s, X)));
+y3: ratsimp(expand(subst(s, Y)));
+
+tex(x3);
+tex(y3);