a few commas etc
[ach-master.git] / src / theory / ECC.tex
1 \section{A note on Elliptic Curve Cryptography}
2 \label{section:EllipticCurveCryptography}
3
4 %\epigraph{``Mathematics is the queen of the sciences and number theory is the queen of mathematics.''}{-- Carl Friedrich Gauss}
5
6 \epigraph{``Everyone knows what a curve is, until he has studied enough
7 mathematics to become confused through the countless number of possible
8 exceptions.''}{-- Felix Klein }
9
10 \todo{cm says: factoring primes is impossible by definition!}
11 Elliptic Curve Cryptography (simply called ECC from now on) is a branch of
12 cryptography that emerged in the mid-1980s.  The security of the RSA
13 algorithm is based on the assumption that factoring large primes is infeasible.
14 Likewise, the security of ECC, DH and DSA is based on the discrete logarithm
15 problem\cite{Wikipedia:Discrete,McC90,WR13}.  Finding the discrete logarithm of
16 an elliptic curve from its public base point is thought to be infeasible. This
17 is known as the Elliptic Curve Discrete Logarithm Problem (ECDLP). ECC and the
18 underlying mathematical foundation are not easy to understand - luckily, there
19 have been some great introductions on the topic lately
20 \footnote{\url{http://arstechnica.com/security/2013/10/a-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography}}
21 \footnote{\url{https://www.imperialviolet.org/2010/12/04/ecc.html}}
22 \footnote{\url{http://www.isg.rhul.ac.uk/~sdg/ecc.html}}.
23
24 ECC provides for much stronger security with less computationally expensive
25 operations in comparison to traditional asymmetric algorithms (See the Section
26 \ref{section:keylengths}).
27
28
29 The security of ECC relies on the elliptic curves and curve points chosen as
30 parameters for the algorithm in question. Well before the NSA-leak scandal
31 there has been a lot of discussion regarding these parameters and their
32 potential subversion. A part of the discussion involved recommended sets of
33 curves and curve points chosen by different standardization bodies such as the
34 National Institute of Standards and Technology (NIST)
35 \footnote{\url{http://www.nist.gov}} which were later widely implemented in
36 most common crypto libraries. Those parameters came under question repeatedly
37 from cryptographers\cite{BL13,Sch13b,W13}.  At the time of writing, there is
38 ongoing research as to the security of various ECC parameters\cite{DJBSC}.
39 Most software configured to rely on ECC (be it client or server) is not able to
40 promote or black-list certain curves. It is the hope of the authors that such
41 functionality will be deployed widely soon.  The authors of this paper include
42 configurations and recommendations with and without ECC - the reader may choose
43 to adopt those settings as he finds best suited to his environment. The authors
44 will not make this decision for the reader.
45
46
47 \textbf{A word of warning:} One should get familiar with ECC, different curves
48 and parameters if one chooses to adopt ECC configurations. Since there is much
49 discussion on the security of ECC, flawed settings might very well compromise
50 the security of the entire system!
51
52 %% mention different attacks on ECC besides flawed parameters!
53