Elliptic Curve Cryptography

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 Swinnerton-Dyer 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:

  1. The definition of an elliptic curve.

  2. The elliptic curve group.

  3. Scalar multiplication over the elliptic curve group.

  4. Finite field arithmetic.

Essentially, elliptic curves are points on that satisfy an equation with the form:

y2 = x3 + 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 x-axis. To negate a point, you just negate the y-coordinate 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 x-coordinates, 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 double-and-add 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:

  1. The coefficients in the elliptic curve equation.

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

  3. A base point that is a point of the curve to be used when calling scalar multiplication.

______________________

Joe Hendrix is a security researcher who works in Portland, Oregon, for Galois, Inc. His main interest is in applying formal verification techniques to real security problems.

Comments

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

interesting article!

anonymous's picture

To the author:

This is a very interesting article! Question - I saw in Star Trek TNG episode cmdr. Data used Fractal Algorithm for encryption.

Is it realistic to use such an algorithm in real life or was it totally made up?

Thanks.

The basis for Web site

MaureenGoodin's picture

The basis for Web site encryption via SSL/TLS, server administration via SSH, secure e-mail and IP encryption.

hello !!!

linda99's picture

I like your work a lot. On the same occasion I invite you to visit my website prefer

Voyance sérieuse par telephone

Several things wrong here...

MHW's picture

Over all, I found this article somewhat interesting (the ECC math part at least) and somewhat misleading (the recommendations part).

The table of key bit strengths is flat out wrong. It's really hand waving to compare bit lengths of symmetric algorithms with PK algol's in anything other than very general terms. It's really comparing apples and oranges and what tastes better.

DES key sizes, in particular, are not "recommended" and are, in fact, fixed by the algorithm and that table got them all very wrong. Single DES (insanely weak and not in the table) is a 56 bit key. 3-DES ede (triple DES encrypt-decrypt-encrypt aka 2 key DES) is 112 bits. Full blown 3-DES with three completely independent keys is 168 bits. There's no such thing as 80 bit DES (1 key, 2 keys, or 3 keys) even if you consider violating the parity in the key bytes. The original DES had 8 byte keys but only considered 7 bits per byte with the high order bit as a "parity" bit (harken back to ASCII tty days?). 8 bytes with 7 bits per byte was 56 bits, period. Two key DES utilized two 56 bits keys, first "encrypting" with one and then "decrypting" (reverse algo) with the other, and then reencrypting with the first key again. Sounds strange but, if you think about it, it makes sense for backwards compatibility with single DES where both keys are the same. 80 bits keys for DES in any form at all makes no sense at all.

No DES variants are recommended in the modern Internet environment.

It's also misleading to argue about the smaller key size of ECC having better security. It's generally been recognized that ECC is more processor intensive than an equivalent strength RSA key and ECC doesn't have the track records that RSA has.

RSA keys up to 2048 bits are well supported on common crypto hardware such as smartcards. ECC support is generally poor to non-existent at best, particularly in consumer grade smart-cards.

The editing remark in the middle of some of the math was "amusing". Doesn't anybody read these bloody things before posting??? Yes, it's in the middle of a pile of math that some people may find mind numbing (the real math is worse - I can quote RSA off the top of my head, it's that simple, but ECC is bad) but still... I actually found the math part to be the bright spot and the faux paux editor remark to be worth a belly laugh at least.

The article contained no references to double check to see if they are valid or even still current! In particular, I would love to review the corresponding NIST recommendation, in particular given how often NIST standards, in regards to security in particular, are behind the times and out of date or have been updated as the state of the art progresses.

People are still quoting out-of-date NIST standards that are no longer even supported by NIST and didn't make sense even back when NIST supported them. They eliminated the whole "7 pass overwrite erase" recommendation back in 2001 or there abouts and people STILL quote that ridiculous recommendation as if it were a standard.

Article feedback

Joseph Hendrix's picture

Hi MWH,

Thanks for the feedback. I just saw this comment.

The comparison of different key lengths comes from NIST 800-57 rev 3, which was published in July, 2012. Here's a link: http://csrc.nist.gov/publications/PubsSPs.html.

I'm sorry if some of the information in the table was confusing. The table was not meant to suggest that DES used 80bit or 112bit keys. You are correct that DES key sizes are 56bits, and using triple DES with 2 keys and 3 keys respectively would involve keys with 112 and 168bits respectively. However, due to known cryptanalysis techniques, they're are likely faster attacks than exploring the entire keyspace. Hence, many cryptographers feel that 3DES offers a lower level of security than the full key size would suggest.

Your point that ECC is newer than RSA, and hence less time has been taken to evaluate it is true, but ECC is almost 2 decades old, and has been subject to significant cryptoanalysis efforts. I don't think this article makes recommendations that are out of alignment with what NIST or the NSA have publicly stated. If so, I'll try to see that the article is corrected.

I disagree with your assertion that it's hand waving to compare key sizes of different algorithms. All the algorithms mentioned in this article have been extensively studied, and systems that use cryptography often use multiple algorithms in concert. For example, browsers use public key crypto for key exchange and digital signatures, symmetric key for encryption, and secure hash functions for digital signatures and identity.

Guidance from standards organizations such as NIST, helps system designers make informed decisions about what algorithms and keysizes to use.

Ehem

NightwishPT's picture

You editing notes as showing.

Garrick, in this paragraph and a few paragraphs down, there were some really long numbers. "

White Paper
Linux Management with Red Hat Satellite: Measuring Business Impact and ROI

Linux has become a key foundation for supporting today's rapidly growing IT environments. Linux is being used to deploy business applications and databases, trading on its reputation as a low-cost operating environment. For many IT organizations, Linux is a mainstay for deploying Web servers and has evolved from handling basic file, print, and utility workloads to running mission-critical applications and databases, physically, virtually, and in the cloud. As Linux grows in importance in terms of value to the business, managing Linux environments to high standards of service quality — availability, security, and performance — becomes an essential requirement for business success.

Learn More

Sponsored by Red Hat

White Paper
Private PaaS for the Agile Enterprise

If you already use virtualized infrastructure, you are well on your way to leveraging the power of the cloud. Virtualization offers the promise of limitless resources, but how do you manage that scalability when your DevOps team doesn’t scale? In today’s hypercompetitive markets, fast results can make a difference between leading the pack vs. obsolescence. Organizations need more benefits from cloud computing than just raw resources. They need agility, flexibility, convenience, ROI, and control.

Stackato private Platform-as-a-Service technology from ActiveState extends your private cloud infrastructure by creating a private PaaS to provide on-demand availability, flexibility, control, and ultimately, faster time-to-market for your enterprise.

Learn More

Sponsored by ActiveState