ellipticcurves.tex

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

% $Id: ellipticcurves.tex 1205 2005-07-04 13:58:13Z koy $
% ...........................................................................
%                  E L L I P T I S C H E  K U R V E N
% ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

\newpage
\section{Elliptic Curves}
\index{Elliptic curves}
\label{Chapter_EllipticCurves}
\hypertarget{ellcurve}{}
(Filipovics B. / B\"uger M. / Esslinger B. / Oyono R., April 2000, Updates: Dec. 2001, June 2002, Mar. 2003)

\subsection{Elliptic curve cryptography -- a high-performance substitute for RSA?}
\index{Performance}
\label{ECAlternative}


In many business sectors secure and efficient data transfer is essential.
In particular, the RSA algorithm is used in many applications. Although the
security of RSA is beyond doubt, the evolution in computing power has
caused a growth in the necessary key length.  Today, 1024-bit RSA keys are
standard, but the GISA\index{GISA} (German Information Security Agency)
recommends the usage of 2048-bit keys from 2006 on (compare
section~\ref{SecurityRSA}).  The fact that most chips on smart cards cannot
process keys extending 1024 bit shows that there is a need for
alternatives. Elliptic curve cryptography (ECC) can be such an
alternative in the area of asymmetric cryptography.

The efficiency of a cryptographic algorithm depends on the key length and
the calculation effort that is necessary to provide a prescribed level of
security. The major advantage of ECC compared to RSA is that it requires
much shorter key lengths. If we assume that the computing power increases
by Moore's law (i.~e.\ it doubles every 18 months)\footnote{empirical
knowledge by Gordon Moore, co-founder of Intel, 1965}, then the evolution of
the key lengths for secure communication will be as figure~\ref{RSAKeylength}
\cite{Lenstra1999} (source: Arjen Lenstra and Eric Verheul:
\href{http://cryptosavvy.com/table.htm}
{\texttt{http://cryptosavvy.com/table.htm}}).

% -> Figure 1
\begin{figure}[h]
\begin{center}
\includegraphics[scale=0.7]{figures/RSAKeyLength-2}
\caption{Prognosis of the key lengths to be regarded safe for RSA and
  Elliptic Curves\vspace{1ex}} 
\label{RSAKeylength}
\end{center}
\end{figure}

In addition, a digital signature can be processed 10-times faster with ECC
than with RSA.  However, verification of a given signature is still more
efficient with RSA than with ECC. Refer to
figure~\ref{ThousandBitMultiplications} (source: Dr.~J.\ Merkle, Elliptic
Curve Cryptography Workshop, 2001) for a comparison.  The reason is that
RSA public keys can be chosen relatively small as long as the secret key is
long enough.

% -> Figure 2
\begin{figure}[h]
\begin{center}
\vspace{1.5cm}\includegraphics[scale=0.7]{figures/ECCRSA}
\caption{Comparison of signing and verification time for RSA and Elliptic Curves} 
\label{ThousandBitMultiplications}
\end{center}
\end{figure}

Nevertheless, thin clients like smart cards usually have to store the (long)
secret key and have to process a digital signature rather than verify one.
Therefore, there is a clear advantage in using ECC in terms of efficiency.
\par
\smallskip
Nowadays, the major problem with ECC-implementations is the lack of standardization.
There is only one way to implement RSA, but there are many ways for ECC: One can work with
different sets of numbers, different (elliptic) curves --- described by parameters\footnote{%
see chapter \ref{ECC-Crypto}
} --- ,
and a variety of representations of the elements on the curve. Each choice has its
advantages and disadvantages, and one can certainly construct the most efficient for
each application. However, this causes problems in interoperability. But if all
ECC-tools should be able to communicate with each other, they will have to support
all different algorithms, which might put the advantage of efficient computation and
the need of less storage capacity to the contrary.

Therefore, international standardization organizations like IEEE (P1363),
ASC (ANSI X9.62, X9.63), ISO/IEC as well as major players like RSA labs or
Certicom have recently started standardization initiatives. While the IEEE
only describes the different implementations, the ASC has explicitly stated
10 elliptic curves and recommends their usage. The advantage of the ASC
approach is that one needs only a single byte to indicate which curve is
meant. However, it is not yet clear whether the ASC-curves will become a de
facto standard.

Although we see no need to replace RSA in any application today\footnote{%
Current informationen about the security of the RSA algorithm can be found in 
chapter \ref{SecurityRSA}.}, one should
take the usage of ECC-based tools into consideration whenever a new system
is set up --- in particular, when the tool should be available beyond 2005\footnote{%
Compare the recommendation of GISA: ``Fitting Crypto Algorithms'' from October 24th, 2002.
}.


\subsection{Elliptic curves -- history}

Mathematicians have been researching elliptic curves for over 100 years.
Over the course of time, many lengthy and mathematically complex results
have been found and published which are connected to elliptic curves. 
A mathematician would say that elliptic curves (or the mathematics behind
them) are widely understood. This research was originally purely 
mathematical. That is to say, elliptic curves were investigated, for 
example, in the mathematical areas of number theory and algebraic 
geometry, which are generally highly abstract. Even in the recent
past, elliptic curves played an important role in pure mathematics.
In 1993 and 1994, Andrew Wiles\index{Wiles, Andrew} published 
mathematical works that triggered enthusiasm far beyond the specialist
audience. In these works, he proved a conjecture put forward in the 1960's.
To put it short, this conjecture was concerned with the connection 
between elliptic curves and what are called module forms. What is
particularly interesting for most people is that the works of Wiles
also proved the famous second theorem of Fermat. Mathematicians had
spent centuries (Fermat lived from 1601 to 1665) trying to find a
strict proof of this theorem. Understandably, therefore, Wiles' proof
got a good response. Fermat formulated his theorem as follows 
(written in the border of a book):

\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}

With a free translation, using the denotation of modern mathematics, this means: \\
No positive whole numbers $x, y$ and $z$ greater than zero exist such that $x^n +y^n = z^n$ for $n>2$. I have found an amazing proof of this fact, but there is
too little space within the confines of this book to include it.

This is truly amazing: A statement that is relatively simple to understand (we
are referring to Fermat's second theorem here) could only be proved after such a
long period of time, although Fermat himself claimed to have found a proof.
What's more, the proof found by Wiles is extremely extensive (all of Wiles
publications connected with the proof made up a book in themselves). This should
therefore make it obvious that elliptic curves are generally based on highly
complex mathematics.

Anyway that's enough about the role of elliptic curves in pure mathematics. 
In 1985 Neal Koblitz\index{Koblitz, Neal} and Victor Miller\index{Miller, Victor}
independently suggested using elliptic curves in cryptography. Elliptic 
curves have thus also found a concrete practical application. 
Another interesting area of application for elliptic curves is for
factorising whole numbers \index{Factorisation} (the RSA cryptographic system
is based on the \index{Complexity} difficulty/complexity of finding prime
factors of an extremely large number;  compare section \ref{SecurityRSA}.).
In this area, procedures based on elliptic curves have been investigated and
used since 1987 (compare section \ref{ECC-Factorisation}). \\
There are also prime number tests\index{Prime number!test} based on elliptic
curves.
% (s. Anmerkung U. Kuehn)

Elliptic curves are used differently in the various areas. Encryption
procedures based on elliptic curves are based on the difficulty of a problem
known as elliptic curve discrete logarithm\index{Logarithm problem!discrete}.
The factorisation of whole numbers uses the fact that a large number of
elliptic curves can be generated for a natural composite number $n$ with
several prime factors; however, these curves are not then groups for composite
$n$. More information about this can be found under the chapter \ref{ECC-Factorisation}.

\subsection{Elliptic curves -- mathematical basics}

This section provides information about \index{Group} {\em groups} and
\index{Field} {\em fields}.

\subsubsection{Groups}

Because the term {\em group} is used differently in everyday language than in
mathematics, we will, for reasons of completeness, begin by introducing the
essential statement of the formal definition of a group:
\begin{itemize}
   \item A group is a non-empty set $G$ on which an operation ``$\cdot$''. The set $G$ is closed under this operation, which means that for any two elements $a, b$ taken from $G$, performing the operation on them gives an element in $G$, i.e. $ab=a\cdot b$ lies in $G$.
   \item For all elements $a, b$ and $c$ in $G$: $(ab)c = a(bc)$ (associative law).
   \item There exists an element $e$ in $G$ that behaves neutrally with respect
to the operation $\cdot$. That means that for all a in the set $G: ~ae = ea = a$.
   \item For each element $a$ in $G$ there exists a so-called inverse\footnote{The inverse is uniquely determined because if $x,y\in G$ are each inverse to $a$, i.e. $ax=xa=e$ and $ay=ya=e$, then $x=xe=x(ay)=(xa)y=ey=y$.} element $a^{-1}$ in $G$ such that: $aa^{-1} = a^{-1}a = e$.
\end{itemize}
If also $ab = ba$ (commutative law) for all $a, b$ in $G$, then we call the group an {\em Abelian} group.

Since we may define different operations on the same set, we distinguish them by giving them different names (e.g. $+$ addition or $\cdot$ multiplication).

The simplest example of an (Abelian) group is the group of whole numbers under
the standard operation of addition. The set of whole numbers is denoted as
${\mathbb Z}$. ${\mathbb Z}$ has an infinite number of elements, because
${\mathbb Z} = \{ \cdots, -4, -3, -2, -1, 0, 1, 2, 3, 4, \cdots\}$. For example, the
operation of $1+2$ lies in ${\mathbb Z}$, for $1+2 = 3$ and $3$ lies in
${\mathbb Z}$. The neutral element in the group ${\mathbb Z}$ is $0$. The
inverse element of $3$ is $-3$, for $3+(-3) = 0$.

For our purpose, so-called {\em finite} groups play an important role. This means that these exists a set
$\mathcal{M}$ with a fixed number of elements and an operation $+$ such that the
above conditions are fulfilled. One example of this is any set ${\mathbb Z}_n$
where ${\mathbb Z}_n = \{0, 1, 2, 3, \cdots, n-1\}, n$ is a positive whole number
and the operation is addition mod $n$, i.e. $a$ and $b$ in ${\mathbb Z}_n$ are
subject to the operation $a+b \;{\rm mod~} n$.

\paragraph{Cyclic groups}\index{Group!cyclic}
Cyclic groups\footnote{Cyclic groups can be in general also endless like the additive group of the integer numbers. We consider here only finite cyclic groups.} are those groups $G'$ that possess an element $g$
from which the group operation can be used to generate all other
elements in the group. This means that for each element $a$ in
$G'$ there exists a positive whole number $i$ such that if $g$ is
subject to the operation $i$ times (i.e. ``$g\cdot i$''),
$g+g+\cdots+g = a$ (additive group) or $g^i = g\cdot g \cdots g = a$
(multiplicative group). The element $g$ is the {\em generator} of
the cyclic group --- each element in $G