diff options
Diffstat (limited to 'buch/chapters/90-crypto')
| -rw-r--r-- | buch/chapters/90-crypto/Makefile.inc | 1 | ||||
| -rw-r--r-- | buch/chapters/90-crypto/chapter.tex | 1 | ||||
| -rw-r--r-- | buch/chapters/90-crypto/elliptisch.tex | 570 | ||||
| -rw-r--r-- | buch/chapters/90-crypto/ff.tex | 983 |
4 files changed, 1065 insertions, 490 deletions
diff --git a/buch/chapters/90-crypto/Makefile.inc b/buch/chapters/90-crypto/Makefile.inc index 508add5..d27e88d 100644 --- a/buch/chapters/90-crypto/Makefile.inc +++ b/buch/chapters/90-crypto/Makefile.inc @@ -7,5 +7,6 @@ CHAPTERFILES = $(CHAPTERFILES) \ chapters/90-crypto/arith.tex \ chapters/90-crypto/ff.tex \ + chapters/90-crypto/elliptisch.tex \ chapters/90-crypto/aes.tex \ chapters/90-crypto/chapter.tex diff --git a/buch/chapters/90-crypto/chapter.tex b/buch/chapters/90-crypto/chapter.tex index 2ea0932..829a718 100644 --- a/buch/chapters/90-crypto/chapter.tex +++ b/buch/chapters/90-crypto/chapter.tex @@ -19,6 +19,7 @@ In diesem Abschnitt soll dies an einigen Beispielen gezeigt werden. \input{chapters/90-crypto/arith.tex} \input{chapters/90-crypto/ff.tex} +\input{chapters/90-crypto/elliptisch.tex} \input{chapters/90-crypto/aes.tex} %\input{chapters/90-crypto/rs.tex} diff --git a/buch/chapters/90-crypto/elliptisch.tex b/buch/chapters/90-crypto/elliptisch.tex new file mode 100644 index 0000000..ed264d3 --- /dev/null +++ b/buch/chapters/90-crypto/elliptisch.tex @@ -0,0 +1,570 @@ +% +% elliptisch.tex +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostshweizer Fachhochschule +% +\section{Elliptische Kurven +\label{buch:section: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. + +\subsection{Definition} +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} + +\subsection{Visualisierung über dem Körper $\mathbb{R}$} +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$. + +\subsection{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. + +\subsection{Gruppenoperation, algebraische Konstruktion} +Nach den geometrischen Vorarbeiten zur Definition der Gruppenoperation +kann können wir die Konstruktion jetzt algebraisch über einem +beliebigen Körper umsetzen. + +Wir gehen jetzt wieder von der elliptischen Kurve in der Form +\begin{equation} +Y^2+XY=X^3+aX+b +\label{buch:crypto:eqn:grupopgl} +\end{equation} +aus. +Man kann dies auch mit dem Polynom mit zwei Variablen +\[ +P(X,Y) = Y^2+XY -X^3-aX-b +\] +schreiben. +Ein Punkt $g=(x,y)$ auf der elliptischen Kurve erfüllt die +Bedingung $P(x,y)=0$. + +\subsubsection{Involution} +Zunächst überlegen wir uns wieder eine Involution, welche als Inverse +dienen kann. +Dazu beachten wir, dass die linke Seite der definierenden Gleichung +\eqref{buch:crypto:eqn:grupopgl} +auch als $Y(Y+X)$ geschrieben werden kann. +Die Abbildung $Y\mapsto -X-Y$ macht daraus +\[ +(-X-Y)(-X-Y+X)=(X+Y)Y. +\] +Mit dem Punkt $(X,Y)$ ist automatisch auch $(X,-X-Y)$ +ein Punkt der elliptischen Kurve. +Dies ist die gesuchte Involution. + +\subsubsection{Gerade durch zwei Punkte} +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) += +td+(1-t)d += +(t+1-t)d +=d. +\] +Jeder Punkt $g$ der Geraden durch $g_1$ und $g_2$ erfüllt einerseits +$l(g)=d$, andererseits lässt er sich in dieser Form schreiben $g(t)$ +für ein geeignetes $t\in\Bbbk$ schreiben. + +\subsubsection{Dritter Schnittpunkt} +Setzt man jetzt $g(t)$ in die Gleichung~\eqref{buch:crypto:eqn:grupopgl} +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 +\begin{align*} +p(t) +&= +(t-1)^2y_2^2 ++ +((2t-2t^2) y_1 +(t^2-2t+1)x_2 + (t-t^2)x_1)y_2 ++ +t^2y_1^2 ++ +((t-t^2)x_2+t^2 x_1)y_1 +\\ +&\qquad ++ +(t^3-3t^2+3t-1)x_2^3 ++ +(-3 t^3+6t^2-3t)x_1x_2^2 ++ +((3t^3-3t^2)x_1^2+at-a)x_2 +- +t^3x_1^3 +- +atx_1-b +\end{align*} +Da die Punkte $g_1=g(0)$ und $g_2=g(1)$ auf der elliptischen Kurve +liegen, muss das Polynom durch die Nullstellen $t=0$ und $t=1$ +haben, es muss also durch $t(t-1)$ teilbar sein. +Teilt man durch $t(t-1)$ bleibt ein Polynom ersten Grades mit +einer einzigen Nullstelle, dem dritten Punkt. +Nach Division durch $t(t-1)$ erhält man als 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 +\label{buch:ecc:eqn:q(t)} +\end{align} +und den Rest +\begin{align*} +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) +\\ +&= +tP(x_1,y_1) ++ +(1-t)P(x_2,y_2) += +0. +\end{align*} +Die Klammerausdrücke verschwinden, da sie gleichbedeutend damit sind, +dass die Punkte Lösungen von \eqref{buch:crypto:eqn:grupopgl} sind. +Dies bestätigt nochmals, dass der Rest $r(t)=0$ ist, dass $p(t)$ +also durch $t(1-t)$ teilbar ist. + +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. + +\subsubsection{Quadrieren} +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 +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$. + +\subsubsection{Neutrales Element} +Das neutrale Element erhält man, wenn man das Produkt zweier Punkte +bildet, die durch die Involution auseinander hervorgehen. +Sie haben die gleiche $x$-Koordinate, also $x_1=x_2$. +Im Polynom $q(t)$ von \eqref{buch:ecc:eqn:q(t)} kommt dann aber an +der Stelle $0$ als Koeffizient von $t$ vor. +Das Polynom wird zu $q(t) = (y_2-y_1)^2$, es hat also keine weitere +Nullstelle. +Es scheint also in diesem Fall gar keinen dritten Punkt zu geben. +Ein neutrales Element kann daher nicht die Form eines Punktes $(x,y)$ +haben, welcher $P(x,y)=0$ erfüllt. +In der Tat muss man die $\Bbbk^2$-Ebene durch einen Punkt im ``Unendlichen'' +erweitern. + +Für unsere Zwecke, nämlich für die Konstruktion eines +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 +geeignete Formeln gefunden haben. + +\subsubsection{Gruppenstruktur auf einer elliptischen Kurve} + +\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 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 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} + +\subsection{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. + + + + + + + + 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. +% +% +% +% +% +% +% +% |