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