From 5125e2d9711ffd6904384159829673155cab683d Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Andreas=20M=C3=BCller?= Date: Tue, 2 Feb 2021 21:31:33 +0100 Subject: new stuff --- buch/chapters/90-crypto/chapter.tex | 2 + buch/chapters/90-crypto/ff.tex | 298 ++++++++++++++++++++- buch/chapters/90-crypto/rechnungen/elliptic.maxima | 42 +++ buch/chapters/90-crypto/rechnungen/tangent.maxima | 67 +++++ 4 files changed, 408 insertions(+), 1 deletion(-) create mode 100644 buch/chapters/90-crypto/rechnungen/elliptic.maxima create mode 100644 buch/chapters/90-crypto/rechnungen/tangent.maxima 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); -- cgit v1.2.1