%hide
%latex
\section*{1. Introduction and Overview}
The study of elliptic curves is an ancient discipline in algebraic geometry. Elliptic curves also play a significant role in number theory, where they constitute a major area of current research. Many old and new number theoretical problems have been solved with the help of the theory of elliptic curves. For example, Andrew Wiles' proof from 1995 of the famous assertion called {\it Fermat's last theorem}, which had remained unproven for over three centuries, makes extensive use of the theory of elliptic curves. Moreover, elliptic curves find applications in integer factorization and cryptography.
Elliptic curve cryptography (ECC) was discovered in 1985 by Neal Koblitz and Victor Miller. ECC algorithms are public-key mechanisms that offer the same functionality as RSA schemes. While they provide a level of security similar to that of RSA, they use much shorter keys, allowing faster computations and hence a more efficient use of power, bandwidth and storage. This is especially useful in applications where these resources are limited, such as smart cards, and in high security environments. [LenstraVerheul2001] shows that in the future, when computation power grows, RSA key lengths will increase at a much faster rate than ECC key lengths. For this reason, most experts (NIST, NSA, BSI) see the future of cryptography in elliptic curves and are recommending the replacement of RSA systems by ECC schemes in high security scenarios. The US National Security Agency (NSA) writes ``The best assured group of new public key techniques is built on the arithmetic of elliptic curves. [...] Elliptic curves begin to offer dramatic savings over the old, first generation techniques.'' They clearly make ``a case for moving to elliptic curves as a foundation for future Internet security.'' (see [NSA ECC])
|
%hide
%latex
\subsection*{1.1 This Document}
The goal of this document is to provide a high-level overview as well as a mathematical understanding of elliptic curve cryptography. It covers the basics of elliptic curves relevant for cryptography and the most important mathematical prerequisites, assuming that the reader is familiar with the topics covered in the German Mathe-Abitur. Many references to more detailed explanations of the mathematical prerequisites are provided. It also shows how ECC builds on conventional public key techniques and points out the major advantages, explaining why many see the future of cryptography in ECC. Finally, it provides an overview of ECC protocols, how they may be employed in a safe manner, and some examples of where they are already in use today.
The document is meant for anyone interested in how elliptic curve cryptography works and why it is good, and willing to dig into the mathematical and exciting world of ECC. Understanding part of the content, especially in Chapter 3, requires some effort by the reader; we can't relieve the reader of this task since elliptic curves are naturally a highly mathematical topic. Nevertheless the effort will surely pay off when connections become clear and the understanding of the topic grows. That's the beauty of mathematics: Everything connects back to something else and as we learn more and more, the picture starts to become more complete and we understand things that previously seemed to belong to only distantly related areas.
Some paragraphs are marked by ``$**$'', which designate extra knowledge. The information contained therein is not essential for the understanding of the rest of the document, but they provide just that extra knowledge that might help getting the big picture.
Unfortunately, SAGE is a bit buggy sometimes. It is developing quickly and problems are fixed regularly, but for now, here are solutions to two common problems that you may run into. Firstly, some of the applications do not always work after opening a worksheet. Instead of nice output, they show lots of blue error messages. In such a case, simply click on the gray {\tt \%hide} above the program and execute the code again by typing {\tt Shift+Enter.} Doing this once or twice should solve the problem. Secondly, after doing this, the code does not always disappear. Instead, it sometimes turns gray. Should this happen, click on the gray text, then click somewhere outside of the text box. The code will then disappear and leave you with a nice layout of the worksheet.
We would like to thank Prof. Hsieh from NSU for useful feedback.
|
%hide
%latex
\subsection*{1.2 Roadmap}
{\it Chapter 2} motivates the use of elliptic curves in cryptography by introducing a simple example, the Diffie-Hellman key exchange protocol. It discusses what the security of this protocol is based on and how it may be attacked. For a better understanding, it introduces some basic concepts of mathematical group theory as well as complexity theory (a topic in computer science). With the help of the Diffie-Hellman key exchange, the chapter explains how conventional public key methods can be generalized to a setting where elliptic curves become useful.
{\it Chapter 3} introduces elliptic curves in general and explains which types of curves are useful in cryptography. For this purpose, it starts out with a section on finite fields, which give the basis for such curves. It also covers the structure of such curves, which is essential when employing them in ECC protocols.
{\it Chapter 4} gives an overview of the most important ECC protocols for the three major areas of cryptography: key establishment, public-key encryption, and digital signatures. It mentions the most common algorithms, what techniques they use and which organizations they have been standardized by.
{\it Chapter 5} covers known attacks on ECC systems and how they can be circumvented. It discusses techniques of choosing all parameters in a way that the resulting system becomes secure.
{\it Chapter 6} provides a summary of the entire document, again emphasizing the advantages of ECC over other public-key systems, as well as a short overview of where ECC techniques are currently in use. Finally, it mentions some further topics that were not covered.
|
|
|