︠273d98c4-d140-4a54-b557-e96a3041efe6i︠
%hide
%latex
\section*{6. Conclusion and Further Topics}
\subsection*{6.1 A Comparison of ECC and RSA}
When all parameters are chosen securely as discussed in Chapter 5, ECC cryptosystems provide the same functionality and security features as the widely used RSA cryptosystem. However, they require much shorter key lengths for achieving a similar security level. For example, a 160-bit ECC-key (meaning that the underlying field is $\mathbb{F}_p$ for a 160-bit prime $p$) attains about the same level of security as a 1024-bit RSA key. In the future, when computers become more powerful and necessary key lengths become larger, this advantage grows disproportionally bigger. Recommended key lengths for RSA, ECC-systems and symmetric algorithms until 2040 are shown in the graphs below.
︡16daa1c4-d1f2-4592-a6ba-d8004568df8f︡︡
︠0da33b8d-b5b2-46d5-b0ec-f5cd643613a8i︠
%hide
html('<h3>Recommended Key Lengths</h3>')

#rsa = line([(2000,952),(2005,1149),(2010,1369),(2015,1613),(2020,1881),(2025,2174),(2030,2493),(2035,2840),(2040,3214)],rgbcolor="green")
#ecc = line([(2000,132),(2005,139),(2010,146),(2015,154),(2020,161),(2025,169),(2030,176),(2035,184),(2040,191)],rgbcolor="red")
#aes = line([(2000,70),(2005,74),(2010,78),(2015,82),(2020,86),(2025,89),(2030,93),(2035,97),(2040,101)],rgbcolor="blue")
#lol = line([2020,300],rgbcolor="white")

#RSA = text('RSA',(2030,2200),rgbcolor=[0,1,0])
#ECC = text('ECC',(2030,400),rgbcolor="red")
#ECC2 = text('ECC',(2030,200),rgbcolor="red")
#AES = text('symmetric',(2030,70),rgbcolor="blue")

#(rsa+ecc+RSA+ECC).save('bild1.png',xmin=2000,xmax=2040,axes_labels=['year','key length in bits'],figsize=5)
#(ecc+aes+lol+ECC2+AES).save('bild2.png',xmin=2000,xmax=2040,axes_labels=['year','key length in bits'],figsize=5)

import pylab
x1 = [2000,2005,2010,2015,2020,2025,2030,2035,2040]
rsa = [952,1149,1369,1613,1881,2174,2493,2840,3214]
ecc = [132,139,146,154,161,169,176,184,191]
aes = [70,74,78,82,86,89,93,97,101]

pylab.figure(figsize=(5.5,3.5))
pylab.clf() # clear the figure first
pylab.plot(x1,rsa, label="RSA",color='green')
pylab.plot(x1,ecc,label="ECC",color='red')
pylab.legend(loc=0) # print the legend
pylab.grid(True, linestyle='-', linewidth=.5, alpha=.2)
pylab.ylabel("key length in bits") # label the axes
pylab.xlabel("year")
pylab.savefig('bild1.png') # fire!

pylab.clf() # clear the figure first
pylab.plot(x1,aes, label="symmetric",color='blue')
pylab.plot(x1,ecc,label="ECC",color='red')
pylab.plot([2040],[300])
pylab.legend(loc=0) # print the legend
pylab.grid(True, linestyle='-', linewidth=.5, alpha=.2)
pylab.ylabel("key length in bits") # label the axes
pylab.xlabel("year")
pylab.savefig('bild2.png') # fire!

html('<table bgcolor=lightgrey cellpadding=2>')
html('<tr><td align="center"><img src="cell://bild1.png"></td>')
html('<td align="center"><img src="cell://bild2.png"></td></tr>')
html('</table>')

html('Figure 6.1 Recommended key lengths for RSA, ECC-systems and symmetric algorithms until 2040. Source: <a href="http://www.keylength.com">http://www.keylength.com</a>')
︡5b04ad10-f7bb-4371-8fc6-6b11617b7f56︡{"html": "<font color='black'><h3>Recommended Key Lengths</h3></font>"}︡{"html": "<font color='black'><table bgcolor=lightgrey cellpadding=2></font>"}︡{"html": "<font color='black'><tr><td align=\"center\"><img src=\"cell://bild1.png\"></td></font>"}︡{"html": "<font color='black'><td align=\"center\"><img src=\"cell://bild2.png\"></td></tr></font>"}︡{"html": "<font color='black'></table></font>"}︡{"html": "<font color='black'>Figure 6.1 Recommended key lengths for RSA, ECC-systems and symmetric algorithms until 2040. Source: <a href=\"http://www.keylength.com\">http://www.keylength.com</a></font>"}︡
︠dee02b8e-675d-4cf3-8a51-3afa762b9f87i︠
%hide
%latex

\noindent
The reason for this advantage of ECC lies in the fact that the best algorithms for solving the ECDLP are exponential, while the best factorization algorithm runs in sub-exponential-time. Hence the parameters for a cryptosystem based on the problem of factoring large integers, such as RSA, must be substantially larger.

These facts result in considerable advantages of ECC over traditional public-key algorithms. ECC cryptosystems provide high security using relatively short key lengths, which allows for faster computations and shorter signatures and thus results in a more efficient use of resources like processing power, bandwidth, storage capacity, and power consumption. This is especially relevant for smart card applications, where such resources are limited, as well as in high security environments.

\subsection*{6.2 Elliptic Curve Cryptography in Use Today}
In recent years, many experts have stood up for the spread of ECC techniques, and government organizations including the NSA, NIST and BSI (see [NSA ECC], [BSI ECC]) have recommended replacing RSA by ECC in security critical applications, such as government communications. One prominent example of where ECC is already used today is the Berlin-Bonn information network (see [IVBB]), which transfers highly confidential data between different German government organizations seated in the old capital city Bonn and the new capital city Berlin. ECC is also part of the cryptography on the new German biometric passport introduced in 2005, and the new German electronic identity card, which will be used from 2010 (see [ePass] and [eCard]). They use ECDH for key exchange and ECDSA for digital signatures. Austria has also massively launched ECC: the so-called "e-card" with a digital signature function, used for authentication in many different settings such as banks and the health care system (see [A-SIT ECC]). ECC is also used in a number of devices such as navigation systems, electricity and gas meters, and electronic scales. Because the signature generation process is about 10 times faster in ECDSA than in RSA-based digital signature schemes (for a discussion of this see Section 7.1 of [CrypToolScript]), ECC is used for electronic stamps (see [ePostage]) and reverse vending machines (see [ReverseVending]), which possess very little processing power. All of these show typical applications of ECC: devices with limited resources available, and high security solutions where interoperability only plays a minor role.

Moreover, ECC is slowly starting to find its way into more standard applications. [A-SIT Software] provides an interesting survey of where ECC is already part of standard software such as Microsoft Windows, SSL/TLS, and email applications.

Although the wide deployment of ECC may still be years away, ECC is a worthy and promising candidate for future applications. Elliptic curves broaden the range of methods in cryptography and give an alternative to conventional cryptography, thus preparing us for the case that attacks on established systems are found. In addition, as we have seen, ECC systems even provide many advantages over other cryptosystems. They significantly improve the security of existing cryptographic schemes, thus widening the range of possible applications.
︡6ba3e275-64b5-452e-bfee-d73d13e2ee57︡︡
︠4da0e62f-ad52-45f4-b389-ce9462c42ed2i︠
%hide
%latex
\subsection*{6.3 Further Topics}
Naturally, the scope of this document is limited and there are many interesting topics in ECC that we did not cover here. Implementation issues are a large and important area where much expertise has been acquired over the past few years. These implementation techniques are so important because ECC is often used in a context where the efficient use of the available resources is critical. There are numerous techniques of improving the efficiency and speed of elliptic curve arithmetic, such as using projective coordinates in order to save computationally expensive inversions. Also note that we have not really covered curves over binary finite fields $\mathbb{F}_{2^m}$ because they are mathematically complicated. Still they naturally provide much potential for efficient implementation because of their special structure, and thus make up the most relevant class of elliptic curves for cryptography. A means of further optimization is the reduction of required memory by methods like point compression, which makes use of the fact that there are only two possible $y$-coordinates for a given $x$-coordinate. Hence it suffices to save the $x$-coordinate and some indication of which of the corresponding $y$-coordinates is used, thus roughly halving the storage space of a point on an elliptic curve. Since the public key for each ECC system contains a point on an elliptic curve, this may significantly reduce the length of the public key. However, many such techniques are patented. [Hankerson2004] spends an entire chapter on implementation issues.

We have also not gone into detail on any of the ECC protocols. Their specifications can be found e.g. in [Hankerson2004]. They all build on general DLP-based cryptosystems (such as ElGamal), which are not specific to elliptic curves (rather, they work for general groups) and are therefore not part of this ECC-document. Describing the ECC specific algorithms in detail is very tedious because they contain much technical overhead, which makes their understanding difficult without much happening in reality.

Of course, there is much more to say about elliptic curve cryptography, but we hope to have given you a comprehensive overview of the topic. If you found this notebook helpful, please recommend CrypTool and SAGE to others.
︡8b2d699a-547c-4b6e-9aad-fe59c5dd0811︡︡


Collaborative Calculation and Data Science

colby

sagemath

cornellcollege

facebook

github

google

twitter

depaul

All published worksheets from http://sagenb.org