ellipticcurves.tex

a very popular packet of cryptography tools,it encloses the most common used algorithm and protocols

% ..............................................................................
%                         E L L I P T I S C H E  K U R V E N
% ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

\newpage
\section{Elliptische Kurven}
\index{Elliptische Kurven}
\label{Chapter_EllipticCurves} %be_2005: \label immer NACH \section !
\hypertarget{ellcurve}{}
(Filipovics B. / B"uger M. / Esslinger B. / Oyono R., April 2000, Updates: Dez. 2001, Juni 2002, M"arz 2003)

% -----------------------------------------------------------------------------
\subsection{Elliptische Kurven -- ein effizienter Ersatz f"ur RSA?}
\index{Performance}   %be_2005: wenn in gl. Zeile wie \subsection, springt man von Inhalt zu einer Seite zu weit vorne!
\label{ECAlternative}


Bei Daten"ubertragungen kommt es auf Sicherheit und Effizienz an.  Viele
Anwendungen verwenden den RSA-Algorithmus als asymmetrisches Signatur- und
Verschl"usselungsverfahren.

Solange die verwendeten Schl"ussel hinreichend lang sind, bestehen keinerlei
Bedenken gegen die {\em Sicherheit} des RSA-Verfahrens. Allerdings hat die
Entwicklung der Rechnerleistungen in der vergangenen Jahren dazu gef"uhrt,
dass die ben"otigten Schl"ussell"angen mehrfach angehoben werden mussten 
(vergleiche Kapitel \ref{SecurityRSA}).
Da die meisten Chips auf Smartcards\index{Smartcard} nicht in der Lage sind,
l"angere Schl"ussel als 1024 Bit zu verarbeiten, besteht Bedarf f"ur 
Alternativen zum RSA. Elliptische Kurven k"onnen eine solche Alternative bieten.

Die {\em Effizienz} eines kryptographischen Algorithmus h"angt wesentlich
von der ben"otigten \linebreak[4]Schl"ussell"ange und vom Rechenaufwand ab,
um ein vorgeschriebenes Sicherheitsniveau zu erreichen.
Der entscheidende Vorteil Elliptischer Kurven im Vergleich zum
RSA-Algorithmus liegt in der Tatsache, dass die sicheren Schl"ussell"angen
erheblich k"urzer sind. 

Setzt man den Trend, dass sich die Leistung der verf"ugbaren Rechner im 
Schnitt alle 18 Monate verdoppelt (Gesetz von Moore\index{Gesetz von Moore}\index{Moore, Gordon E.}%
\footnote{empirische Erkenntnis von Gordon Moore, Mitbegr"under von Intel,
1965.} ), in die Zukunft fort, so kann man von einer Entwicklung der
sicheren Schl"ussell"angen wie in Abbildung~\ref{RSAKeylength} ausgehen
\cite{Lenstra1999} (Quelle: Arjen Lenstra und Eric Verheul:
\href{http://cryptosavvy.com/table.htm}
{\texttt{http://cryptosavvy.com/table.htm}}).

% -> Figur 1
\begin{figure}[h]
\begin{center}
\includegraphics[scale=0.7]{figures/RSAKeyLength-2}
\caption{Prognose f"ur die Entwicklung der als sicher betrachteten
  Schl"ussell"angen f"ur RSA und Elliptische Kurven\vspace{1ex}} 
\label{RSAKeylength}
\end{center}
\vskip -30 pt
\end{figure}

\newpage

Bei der digitalen Signatur muss man differenzieren: f"ur die {\em
  Erstellung} einer digitalen Signatur ben"otigen auf Elliptischen
Kurven basierende Verfahren im Vergleich zu RSA nur gut ein Zehntel des
Rechenaufwandes (66 zu 515 Ganzzahlmultiplikationen). Siehe hierzu
Abbildung~\ref{ThousandBitMultiplications} (Quelle: Dr. J.  Merkle,
Elliptic Curve Cryptography Workshop, 2001). Betrachtet man die f"ur eine
{\em Verifikation} durchzuf"uhrenden Rechenschritte, dreht sich dieses Bild
jedoch zu Gunsten von RSA um (112 zu 17 Ganzzahlmultiplikationen). Der 
Grund liegt darin, dass es bei Verwendung des RSA m"oglich ist, einen sehr 
kurzen Exponent f"ur den "offentlichen Schl"ussel zu w"ahlen, solange der 
private Exponent nur hinreichend lang ist.

% -> Figur 2
\begin{figure}[h]
\vskip -40 pt
\begin{center}
\vspace{1.5cm}\includegraphics[scale=0.7]{figures/ECCRSA}
\caption{Gegen"uberstellung des Aufwands der Operationen Signieren und Verifizieren bei
  RSA und Elliptischen Kurven} 
\label{ThousandBitMultiplications}
\end{center}
\vskip -10 pt
\end{figure}

Da bei Smartcards, die auf RSA basieren, stets der lange (private)
Schl"ussel auf der Karte gespeichert werden muss und die Erstellung
der digitalen Signatur, nicht aber die Verifikation, auf der Karte
stattfindet, treten hier deutlich die Vorteile Elliptischer Kurven zutage. 
\par
\smallskip
Das gr"o"ste Problem bei der Implementierung von Verfahren, die auf Elliptischen Kurven beruhen, ist bislang die
mangelnde {\em Standardisierung\index{Standardisierung}}. Es gibt nur eine RSA-Implementierung, aber viele Arten, Elliptische Kurven einzusetzen.
So k"onnen verschiedene Zahlk"orper zugrunde gelegt, eine Vielzahl von (Elliptischen) Kurven --- durch
Parameter beschrieben\footnote{%
Siehe Kapitel \ref{ECC-Crypto}
} --- eingesetzt und unterschiedliche Darstellungen der Kurvenpunkte verwendet werden.
Jede Wahl hat ihre Vorz"uge, so dass f"ur jede Anwendung eine andere Implementierung optimal sein kann. Dies
hat jedoch zur Konsequenz, dass Systeme, die auf Elliptischen Kurven beruhen, oftmals nicht interoperabel
sind. Um mit einer beliebigen auf Elliptischen Kurven basierenden Anwendung kommunizieren zu k"onnen, m"usste man
eine Vielzahl von Implementierungen vorhalten, was den Effizienzvorteil gegen"uber der Verwendung von RSA
zunichte macht.

Deshalb bem"uhen sich internationale Organisationen um Standardisierung:
IEEE (P1363), ASC (ANSI X9.62, X9.63), ISO/IEC sowie 
RSA Laboratories\index{RSA Laboratories} und Certicom\index{Certicom}. 
Im Gegensatz zur IEEE, die bisher nur eine Beschreibung der verschiedenen
Implementierungen vorgenommen hat, hat die ASC konkret 10 Kurven ausgew"ahlt
und empfiehlt deren Verwendung. Der Vorteil des ASC-Ansatzes ist,
dass ein einziges Byte ausreicht, um die verwendete Kurve zu spezifizieren.
Zur Zeit ist jedoch nicht absehbar, ob es der ASC gelingen wird, einen
de-facto-Standard durchzusetzen.

Obwohl aktuell kein Handlungsbedarf besteht\footnote{%
Aktuelle Informationen zur Sicherheit des RSA-Verfahrens finden Sie in 
Kapitel \ref{SecurityRSA}.}, laufende RSA-Anwendungen umzustellen, 
sollte man bei der Neuimplementierung ernsthaft den Einsatz von Verfahren
erw"agen, die auf Elliptischen Kurven basieren.
Dies gilt insbesondere, wenn es sich um Anwendungen im Finanzsektor
handelt, die noch nach 2005\footnote{%
BSI-Empfehlung: ``Geeignete Kryptoalgorithmen'' vom 24. Oktober 2002.
} operativ sein sollen.


% -----------------------------------------------------------------------------
\subsection{Elliptische Kurven -- Historisches}

Auf dem Gebiet der Elliptischen Kurven wird seit "uber 100 Jahren geforscht. Im Laufe der Zeit hat man
viele weitl"aufige und mathematisch tiefgr"undige Resultate im Zusammenhang mit Elliptischen Kurven gefunden
und ver"offentlicht. Ein Mathematiker w"urde sagen, dass die Elliptischen Kurven
(bzw.\ die dahinterstehende Mathematik) gut verstanden sind. Urspr"unglich war diese Forschung reine
Mathematik, das hei"st Elliptische Kurven wurden zum Beispiel in den mathematischen Teilgebieten
Zahlentheorie und algebraische Geometrie untersucht, die allgemein sehr abstrakt sind. Auch in der
nahen Vergangenheit spielten Elliptische Kurven eine bedeutende Rolle in der reinen Mathematik. In den
Jahren 1993 und 1994 ver"offentlichte Andrew Wiles\index{Wiles, Andrew} mathematische Arbeiten, die weit "uber das Fachpublikum
hinaus auf gro"se Begeisterung gesto"sen sind. In diesen Arbeiten bewies er die Richtigkeit einer --- in
den sechziger Jahren des 20. Jahrhunderts von zwei Japanern aufgestellten --- Vermutung. Dabei geht es
kurz und grob gesagt um den Zusammenhang zwischen Elliptischen Kurven und sogenannten Modulformen.
Das f"ur die meisten eigentlich Interessante daran ist, dass Wiles mit seinen Arbeiten auch den ber"uhmten
zweiten Satz von Fermat\index{Fermat!letzter Satz} bewiesen hat. Dieser Satz hatte sich seit Jahrhunderten
(Fermat\index{Fermat, Pierre} lebte von 1601 bis 1665) einem umfassenden Beweis durch die Mathematik entzogen. Dementsprechend
gro"s war die Resonanz auf den Beweis durch Wiles. In der Formulierung von Fermat lautet der nach ihm
benannte Satz so (Fermat hat folgende Worte an den Rand des 1621 von Bachet herausgegebenen Werks Diophants geschrieben):

\begin{quote} {\em
Cubum autem in duos cubos, aut quadratoquadratum in duos quadratoquadratos, et
generaliter nullam in infinitum ultra quadratum potestatem in duos ejusdem nominis
fas est dividere: cujus rei demonstrationem mirabilem sane detexi. Hanc marginis
exiguitas non caperet.
} \end{quote}

Frei "ubersetzt und mit der Schreibweise der heutigen Mathematik bedeutet dies: \\
Es gibt keine positiven ganzen Zahlen $x, y$ und $z$ gr"o"ser als Null, so dass
$x^n + y^n = z^n$ f"ur $n>2$ gilt.
Ich habe einen bemerkenswerten Beweis f"ur diese Tatsache gefunden, aber es ist
nicht genug Platz am Rand [des Buches], um ihn niederzuschreiben.

Dies ist schon bemerkenswert: Eine relativ einfach zu verstehende Aussage
(gemeint ist Fermats zweiter Satz) konnte erst nach so langer Zeit bewiesen werden, obwohl
Fermat selber angab, schon einen Beweis gefunden zu haben.
Im "ubrigen ist der Beweis von Wiles sehr umfangreich (alle im Zusammenhang mit dem Beweis
stehenden Ver"offentlichungen von Wiles ergeben schon ein eigenes Buch). Man sollte sich daher
im klaren sein, dass die Elliptischen Kurven im allgemeinen sehr tiefgreifende Mathematik ber"uhren.

Soweit zur Rolle der Elliptischen Kurven in der reinen Mathematik.
Im Jahr 1985 haben Neal Koblitz\index{Koblitz, Neal} und Victor Miller
\index{Miller, Victor} unabh"angig voneinander vorgeschlagen, 
Elliptische Kurven in der Kryptographie einzusetzen. Damit haben die 
Elliptischen Kurven auch eine ganz konkrete praktische Anwendung gefunden.
Ein weiteres interessantes Einsatzgebiet f"ur Elliptische Kurven ist die
Faktorisierung von ganzen Zahlen \index{Faktorisierung}
(auf der \index{Komplexit""at} Schwierigkeit/Komplexit"at, die Primfaktoren
einer sehr gro"sen Zahl zu finden, beruht das RSA-Kryptosystem: 
vergleiche Kapitel \ref{SecurityRSA}
). 
In diesem Bereich werden seit 1987 Verfahren untersucht und eingesetzt,
die auf Elliptischen Kurven basieren
(vergleiche Kapitel \ref{ECC-Factorisation}). \\
Es gibt auch Primzahltests\index{Primzahltest}, die auf Elliptischen 
Kurven basieren.
% (s. Anmerkung U. Kuehn)

Elliptische Kurven werden in den verschiedenen Gebieten unterschiedlich
eingesetzt.
Kryptographische Verfahren auf Basis von Elliptischen Kurven beruhen auf der
Schwierigkeit eines als Elliptische Kurven Diskreter Logarithmus bekannten 
Problems.

Ferner gibt es einen Zusammenhang zwischen Faktorisierung von ganzen Zahlen und
Elliptischen Kurven, der in Abschnitt \ref{ECC-Factorisation} n"aher beschrieben 
wird.




% -----------------------------------------------------------------------------
\subsection{Elliptische Kurven -- Mathematische Grundlagen}

In diesem Abschnitt erhalten Sie Informationen "uber
\index{Gruppen} {\em Gruppen} und \index{K""orper} {\em K"orper}.


% -----------------------------------------------------------------------------
\subsubsection{Gruppen}

Da der Begriff der {\em Gruppe} umgangssprachlich anders als in der Mathematik eingesetzt wird, soll der
Vollst"andigkeit halber an dieser Stelle die wesentliche Aussage der formalen Definition einer Gruppe
kurz eingef"uhrt werden:
\begin{itemize}
   \item Eine Gruppe ist eine nichtleere Menge $G$ mit einer Verkn"upfung ``$\cdot$''. Die Menge $G$ ist unter der
         Verkn"upfung $\cdot $ abgeschlossen, d.h, sind $a,b$ Elemente aus $G$, so ist auch ihre Verkn"upfung $ab=a\cdot  b$ ein Element aus $G$.
   \item F"ur alle Elemente $a, b$ und $c$ aus $G$ gilt: $(ab)c = a(bc)$ (Assoziativgesetz).
   \item Es gibt ein Element $e$ in $G$, das sich bez"uglich der Verkn"upfung $\cdot$ neutral verh"alt