Elliptic Curve Cryptography
When it comes to public key cryptography, most systems today are still stuck in the 1970s. On December 14, 1977, two events occurred that would change the world: Paramount Pictures released Saturday Night Fever, and MIT filed the patent for RSA. Just as Saturday Night Fever helped popularize disco through its choreography and soundtrack, RSA helped popularize cryptography by allowing two parties to communicate securely without a shared secret.
Public key techniques, such as RSA, have revolutionized cryptography and form the basis for Web site encryption via SSL/TLS, server administration via SSH, secure email and IP encryption (IPsec). They do this by splitting the shared secret key used in traditional cryptography into two parts: a public key for identifying oneself and a secret key for proving an identity electronically. Although the popularity of disco has waned, most Web sites today that use encryption still are using RSA.
Since the 1970s, newer techniques have been developed that offer better security with smaller key sizes than RSA. One major breakthrough is the development of cryptography based on the mathematical theory of elliptic curves, called ECC (Elliptic Curve Cryptography). Although ECC has a reputation for being quite complex, it has been integrated into popular opensource cryptographic software including OpenSSH and OpenSSL, and it's not inherently any more difficult to use than RSA. In this article, I describe ECC and show how it can be used with recent versions of OpenSSH and OpenSSL.
Not all cryptographic algorithms are equal. For a fixed key or output length, one algorithm may provide much more security than another. This is particularly true when comparing different types of algorithms, such as comparing public and symmetric key algorithms. To help make sense of this, the National Institute of Standards and Technology (NIST) reviews the academic literature on attacking cryptographic algorithms and makes recommendations on the actual security provided by different algorithms (see Table 1 from 2011).
Table 1. NIST Recommended Key Sizes
Bits of Security  Symmetric Key Algorithm  Corresponding Hash Function  Corresponding RSA Key Size  Corresponding ECC Key Size 
80  Triple DES (2 keys)  SHA1  1024  160 
112  Triple DES (3 keys)  SHA224  2048  224 
128  AES128  SHA256  3072  256 
192  AES192  SHA384  7680  384 
256  AES256  SHA512  15360  512 
Note: for new applications, I think AES128 should be used over triple DES even if 128bit security isn't needed. Attacks have been found on SHA1, and NIST now estimates that SHA1 provides only 69 bits of security in digital signature applications.
If the system you are designing is expected to protect information only until 2030, NIST recommends that you use cryptography providing at least 112 bits of security. For applications that need longerterm protection, NIST recommends at least 128 bits of security.
Department of Defense Requirements
Although NIST guidance is well respected, the Department of Defense has stronger requirements for classified information. For the Defense Department, 128 bits is only good enough for protecting information classified SECRET. Use of RSA isn't approved, and TOP SECRET information requires use of AES256, SHA384 and ECC with a 384bit key size. Furthermore, systems must use two separate encryption implementations for protection. For example, use both IPsec and TLS, so that the information is still protected by one layer if a flaw in the other is found. Although this may not be very practical for most Internet applications, it's interesting to see what the requirements are when security is paramount.
Just because NIST makes these recommendations, doesn't mean that applications follow them. Many Web sites, including online banks, still will use SHA1 and pair it with AES 128 and a 1024 or 2048bit RSA key. According to NIST, achieving true 128bit security means that the RSA key should be at least 3072 bits—a size most Internet certificate authorities don't even offer. At present, Verisign will sell you an SSL certificate that it claims offers "256bit security", because you can use it with AES256. The signature itself uses SHA1 and a 2048bit RSA key.
At present, the security on the Internet is still sufficiently weak that it almost always will be easier to find a vulnerability that allows an attacker to bypass security rather than directly attack the encryption. However, it is still worthwhile to be aware of how much security the overall encryption implementation provides. In cryptography, more bits are usually better, but an implementation is only as strong as its weakest length. Both ECC and SHA2 represent essential algorithms to getting real 128bit or 256bit security.
The Mathematics of Elliptic Curve Cryptography
Elliptic Curve Cryptography has a reputation for being complex and highly technical. This isn't surprising when the Wikipedia article introduces an elliptic curve as "a smooth, projective algebraic curve of genus one". Elliptic curves also show up in the proof of Fermat's last theorem and the Birch and SwinnertonDyer conjecture. You can win a million dollars if you solve that problem.
To get a basic understanding of ECC, you need to understand four things:

The definition of an elliptic curve.

The elliptic curve group.

Scalar multiplication over the elliptic curve group.

Finite field arithmetic.
Essentially, elliptic curves are points on that satisfy an equation with the form:
y^{2} = x^{3} + ax + b
Figure 1 shows a picture of an elliptic curve over the real numbers where a is –1 and b is 1. Elliptic curves satisfy some interesting mathematical properties. The curve is symmetric around the x axis, so that if (x,y) is a point on the curve, then (x,–y) is also on the curve. If you draw a line between any two points on the line with different x coordinates, they will intersect the line at a unique third point. Finally, for each point on the curve, if you draw a straight line tangent to the cover from that point, it will intersect the curve once again at another point.
Figure 1. Elliptic Curve over Real Numbers
Mathematicians use these properties to form a structure called a group from the points on the elliptic curve. A group consists of a set of elements containing a special point (denoted 0), an operation for negating an element (denoted –x), and an operation for adding two elements (denoted x + y). The elements in the group defined by an elliptic curve consist of the points on the curve plus an additional point for 0 that is not on the curve, but as you'll see below is easiest to visualize as a line on the xaxis. To negate a point, you just negate the ycoordinate of the point, and adding a point to its negation is defined to return 0 (Figure 2). To add two points P and Q with different xcoordinates, draw a line connecting the two points and extending beyond them. This line should intersect the curve at a third point. The sum R = P + Q is the negation of the third point. Finally, to add a point P to itself, draw the line tangent to P (Figure 3). The sum R = 2P is the negation of the point that line intersects (Figure 4).
Figure 2. Negating a Point
Figure 3. Adding Two Points
Figure 4. Doubling a Point
Once the group is defined, we can talk about scalar multiplication—the fundamental operation that makes elliptic curves useful in cryptography. The kth scalar multiple of P is the point obtained by adding P to itself k times. This can be done efficiently by representing k as a binary number and using a doubleandadd multiplication method. If you are familiar with RSA, scalar multiplication plays a similar role in ECC that modular exponentiation plays in RSA.
The real numbers used in diagrams for explaining ECC are not practical to use in actual implementations. Real numbers can have an arbitrary number of digits, and computers have only a finite amount of memory. Most applications, including OpenSSL, use elliptic curves over coordinates that use modular arithmetic, where the modulus is a large prime number. Figure 5 shows the elliptic curve with the same equation as in Figure 1, but where arithmetic is performed modulo 19.
Figure 5. Elliptic Curve over Prime Field (mod 19)
For the different key sizes in Table 1, NIST recommends a specific elliptic curve with a prime modulus for that key size (see the Binary Fields sidebar). For each key size, NIST specifies three things:

The coefficients in the elliptic curve equation.

The size of the underlying field for representing x and y.

A base point that is a point of the curve to be used when calling scalar multiplication.
Binary Fields
For each bit size, NIST also recommends two other elliptic curves over a type of field called a binary field. Although prime fields are more common in software, binary fields are common when implementing ECC in lowpower hardware. I focus on prime curves in this article, because that's what OpenSSL uses, and there are a lot more patents on binary curve implementations than prime curves. Unless you have some specific hardware needs and also money to spend on lawyers to deal with patents, I'd recommend sticking to prime curves.
To see how big the numbers for a 256bit curve are, the NIST P256 curve equation has the coeffients a=–3 and b = 41058363725152142129326129780047268409114441015993725554835256314039467401291.
The coordinates are in a prime field modulo p_256 where:
p_256 = 2^{256} – 2^{224} +2^{192} +2^{96} – 1
The base point is G=(xG,yG) and defined by:
xG = 48439561293906451759052585252797914202762949526041747995844080717082404635286
yG = 36134250956749795798585127919587881956611106672985015071877198253568414405109
If these numbers look big to you, just think that the 256bit elliptic curve is equivalent to RSA with 3072bit numbers. RSA public keys contain more than 12 times the number of digits.
If you'd like to learn more about Elliptic Curve Cryptography, there are many references available. Certicom, a company founded by some of the inventors of ECC, hosts an online tutorial at http://www.certicom.com/ecctutorial. For a more comprehensive understanding of cryptography, the book Understanding Cryptography by Christof Paar, Jan Pelzl and Bart Preneel has a chapter about ECC and also covers the AES and SHA. I've just touched the basic definitions here, and I've not discussed the optimizations used to make a highperformance implementation like the one in OpenSSL. For a quite comprehensive reference on fast ECC algorithms, the "Handbook of Elliptic and Hyperelliptic Curve Cryptography" (http://www.hyperelliptic.org/HEHCC) has yet to let me down.
Using Elliptic Curve Cryptography in OpenSSH
A little more than a year ago, OpenSSH 5.7 added support for ECCbased cryptography. Although it's still not in every Linux distribution, support for ECC finally is becoming widespread enough that it's starting to be worth considering a migration. Support for ECC requires OpenSSH version 5.7 or later and OpenSSL version 0.9.8g or later. OpenSSH can use ECC both to help you authenticate that you really are talking to the server you want and to help the server perform keybased authentication of users.
Host authentication is used by the client to authenticate the server. It is used
to detect maninthemiddle attacks and normally is set up automatically and
used by OpenSSH. When OpenSSH is installed, it should create one or more host
keys, which normally are stored in /etc/ssh. The ECC private key normally
is named ssh_host_ecdsa_key
, and the corresponding
public key normally is named
ssh_host_ecdsa_key.pub
. See the man pages for
sshd_config
if you would like
to change this path. Just make sure that the private key can be read only by
authorized admins; anybody with access to the host private key potentially
could impersonate the server.
Client authentication is used to authenticate the client against the server.
Using keys to authenticate rather than passwords is both more convenient
(because
you can use sshagent
or another program to cache
the key) and more secure (because
the password is never sent in plain text to the server). If you have used SSH for
significant work in the past, you've probably set this up using RSA keys, and
the exact same process, namely using sshkeygen
, is used to create ECC keys.
The only difference is to pass tecdsa
to create the key. The man page for
sshkeygen
will have more details, and there are many tutorials for setting
up SSH keys available online if you need a walkthrough.
For most people, once encryption software supporting ECC is more widely deployed, converting to ECC should be quick and painless. RSA still is probably "good enough" for most applications, but ECC is significantly more secure, and it may be essential to getting strong security on tiny, lowpower, networked devices that are becoming more widespread. Its introduction into opensource tools like OpenSSL and OpenSSH is definitely a great step toward gaining more widespread use.
Limited Time Offer
Take Linux Journal for a test drive. Download our September issue for FREE.