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