FAQ
THE ECC FAQ v.1.0
info@certicom.com
Copyright (c) 1999
Certicom Corporation - All Rights Reserved

All information contained in this work is provided "as is." All warranties--expressed, implied, or statutory--concerning the accuracy of the information or the suitability for any particular use are hereby specifically disclaimed. While every effort has been taken to ensure the accuracy of the information contained in this work, the authors assume no responsibility for errors or omissions or for damages resulting from the use of the information contained herein.

This work may be copied in any printed or electronic form for non-commercial, personal, or educational purposes if the work is not modified in any way, provided that the copyright notice, the notices of any other author included in this work, and this copyright agreement appear on all copies.

Certicom Corporation also grants permission to distribute this work in electronic form over computer networks for other purposes, provided that, in addition to the terms and restrictions set forth above, Certicom Corporation and/or other cited authors are notified and that no fees are charged for access to the information in excess of normal online charges that are required for such distribution.

This work may also be mentioned, cited, referred to or described (but not copied or distributed, except as authorized above) in printed publications, on-line services, other electronic communications media, and otherwise, provided that Certicom Corporation and any other cited author receives appropriate attribution.

Comments about, suggestions about, or corrections to this document are welcomed.
1) Public-Key Cryptography: The Basics
ECC is a type of public-key cryptography. This section explain what public-key cryptography is and how it works.
1.1) What is cryptography?
Cryptography is the science of ciphers.

Remember, back in grade school, when you'd encode messages by shifting letters one to the right? A's would become B's, B's would become C's, and so one. Ju xbt fbtz boe gvo. That's a basic cipher. It's also fairly easy to break.

Computers can calculate much more complex ciphers, changing messages around in such a way that they're utterly unrecognizable, even to other, sophisticated computer programs. By encoding your computer data in this way you can ensure that no one else can read that data. Even if someone manages to intercept your message, they can't read it unless you give them the secret key (usually a large number) required to decipher the message.
1.2) What is public-key cryptography?
Most cryptography is "symmetric." This means that you use the same secret key to encode and decode a message.

However, symmetric cryptography has a "chicken and egg" problem when it is used to encode networked communications. You can't securely distribute a secret key to remote sites without being able to encrypt your messages, which requires a secret key. Public-key cryptography gets around this problem.

Public-key cryptography is "asymmetric." This means that different keys are used to encode and decode a message. There is a "public key" which is widely distributed and a "private key" which only the owner has access to.

If a message has been encoded with a public key, it can only be decoded with the matching private key. Often the reverse is true too: if something is encoded with a private key, it can only be decoded with the matching public key.

Public-key cryptography is actually rarely used for straight encryption, primarily because it is computationally expensive. Instead it serves two other purposes: key establishment and digital authentication.
1.2.1) What is key establishment?
Because public-key cryptography is more computationally expensive than symmetric cryptography, public-key cryptography is usually used on networks to encode a secret key for symmetric cryptography; then the system falls back on a faster symmetric cryptography system.

Using asymmetric cryptography to exchange a secret (symmetric) key is called key establishment. There are actually two types of key establishment. In key transport, one user creates the symmetric key, then passes it on to another user. In key agreement, two users work together in order to generate a shared symmetric key.

The term key agreement is used more frequently than key establishment.
1.2.2) What is digital authentication?
Public-key cryptography also allows for authentication. You do this by making something called a digital hash of your message. This is a short mathematical representation of your message as a whole. Then, you encrypt that hash with your private key and form what's called a digital signature.

To reverse the process, the recipient of your message must do two things. First, he applies your public key to decrypt the hash. Second, he makes a new digital hash of the message and compares it to the digital hash he just decrypted to make sure it is the same.

This digital signature serves two major purposes: authentication and verification.

Only you have your private key, thus if the (correct) hash decodes with your public key, you must have sent it. This is authentication.

Only you have your private key, thus if the hash is encoded with it, it can not be changed en route. If the encrypted hash matches with a fresh hash made of the received message, it could not have been changed. This is verification.

Digital signatures can also be used for non-repudiation: proving without a doubt that someone sent a message.
1.3) How does public-key cryptography work mathematically?
Public-key cryptography depends upon something called a "trap-door one-way function." A one-way function is easy to compute but difficult to undo. A trap door provides an easy way to undo your one-way function--if you know a certain secret.

The Rubik's Cube, that infernal toy of a decade ago, is a fair example of a trap-door one-way function. Starting with a solved cube, it is fairly easy to scramble it. With a score or two random turns, the colored sides of the cube descend into chaos. Reversing the function, to return the cube to its solved state, is substantially more difficult. However, there is a trap door--a screwdriver. It can be used to pop a cube apart, then put it back together. With knowledge of this secret and cunning method, it's very easy to return the cube to its original state.

Traditional public-key cryptography, which is to say RSA, has depended upon the factoring of large numbers into primes: it's easy to multiply two large prime numbers together to get a sum, but difficult to figure out two prime multiples given just the end result. As we'll see ECC offers an alternative to this particular trap-door one-way function and also provides some unique advantages.
1.4) What good is public-key cryptography?
As has already been discussed (see 1.2), public-key cryptography provides two big wins: encryption and authentication.

These are important because the internet can be a dangerous place. It's still like those unknown areas marked on old maps: "There be monsters here!" Malicious users might get their hands on anything that you send out across public networks or they might use the public networks to forge messages. There are three main dangers: interception of messages, modification of messages, and impersonation of persons.

Interception of messages simply means that a hacker listens in on your conversations. You might find whatever you said--be it business plans, trade secrets, or just your home address--broadcast across the net as a result--or maybe just transmitted to your competitors. Encryption, specifically key establishment followed by symmetric cryptography, offers proof against this.

Modification of messages involves some hacker changing your messages after you sent them, but before they're received. The damage this could cause should be obvious. Digital authentication via messages hashes provides proof against this.

Impersonation of persons is when someone else says they're you, or, alternatively, someone pretends they're another person when they're talking to you. Digital authentication also offers proof against this.

Besides protecting you from all those bad things, public-key cryptography can also offer some positive things. Because of the non-repudiation aspect of digital signatures, for example, you can digitally sign a contract... as was recently done by President Clinton in Ireland.
1.5) Why are certificates required for public-key cryptography?
There's still one problem related to public-key cryptography: how do you know for sure that a public key really belongs to a specific user? If someone is handing out fradulent public keys, you can encrypt data in a perfectly safe way, only to have it read by an imposter. It's as if you whispered a secret into someone's ear because he identified himself as a FBI agent, only to discover that he's actually a mole for a communist government.

Certificates Authorities (CAs) take care of this problem with certificates. CAs use some trusted means to verify that a person is who he says he is, then write out a certificate that contains the person's name and his public key. Finally, the CA signs the message with its own private key. Provided that you trust a specific CA, you can look at the certificate, verify that the CA sent it, and so be sure that a public key really belongs to a certain user.

Returning to our earlier example, the FBI acts as a sort of CA for its agents. It does background checks, verifies that potential agents aren't communist sympathizers, then issues FBI badges. If you'd thought to ask for that supposed agent's certificate (badge), you could have verified that he was not who he claimed to be.
2) ECC: THE BASICS
This section explain what ECC is and how it differs from other types of public-key cryptography that are out there.
2.1) What is ECC?
ECC stands for Elliptic Curve Cryptography. It represents a different way to do public-key cryptography--an alternative to the older RSA system--and also offers certain advantages.

The idea behind ECC is that you take an elliptic curve, you define it over a certain field, and then you solve a certain "hard" problem (specifically, a trap-door one-way function) over the curve that you've defined. This is all described better in the math section, below, as well as in the tutorial that the math section refers to.
2.2) What are the advantages of ECC?
The big win with ECC, as compared to other public-key algorithms, is key size. A fairly typical key size for RSA is 1024 bits--this would take approximately 10^11 MIPs-years to break. A mere 160-bit ECC key offers the same level of security. This advantage only increases with security level--something which will be important as computer power continually grows. A 2048-bit RSA key and a 210-bit ECC key are equivalent, jumping the ECC:RSA key-size ratio from 1:7 to 1:10.

ECC also has less computational overhead than RSA, primarily because it does not have to analyze prime numbers, a fairly expensive operation.

Together, these facts allow for a more efficient cryptosystem. ECC devices will require less storage, less power, less memory, and less bandwidth. This allows you to implement cryptography in platforms that are constrained, such as wireless devices, handheld computers, smart cards, and thin-clients. It also provides a big win in situations where efficiency is extremely important, such as on a bottlenecked web server supporting e-commerce.
2.2.1) Doesn't RSA verify faster than ECC?
RSA only verifies faster than ECC when using low exponents. Dan Boneh has written some papers on the security problems with low exponent RSA, which may be found at: http://theory.stanford.edu/~dabo/pubs.html
2.3) Is ECC secure?
ECC has not been as extensively researched as RSA, but it does have a rich history. Elliptic curves have been studied for over 150 years. Elliptic curve cryptography has been the subject of intense research for 10 years.

To date, all research has confirmed ECC to be secure.
2.4) Is ECC patented?
Unlike RSA, the general category of ECC is not patented. Individual companies, however, may have patented specific efficiency or security algorithms that are related to ECC.
2.5) What ECC Toolkits are available?
The oldest ECC security kit is Security Builder SDK, from Certicom Corp. It has offered ECC functionality for [X?] years. More information on Security Builder can be found at: http://www.certicom.com/products/sec_builder.html
As of BSAFE 4.0, RSA has also opted to adopt ECC, though their implementation is relatively recent. More information on BSAFE can be found at: http://www.rsa.com/rsa/products/cryptoc/
2.6) What export restrictions are there on ECC?
As with all cryptography, there are export restrictions on ECC, depending on the country that you are exporting from. ECC has a big win, however, with digital signatures; traditionally export of digital signatures has not been restricted. However, under the RSA system it was very difficult to separate the encryption and the signatures; thus RSA signatures are more difficult to export. Under ECC, signatures and encryption are very different, thus ECC signatures can usually be exported freely.

The prime publisher of ECC, Certicom Corp, is located in Canada. This may allow some addition flexibility with exports due to Canada's slightly relaxed cryptography export laws.
3) ECC: INTEROPERABILITY
3.1) Are different flavors of ECC interoperable?
Yes. ECC has been standardized (see below), and thus different flavors of ECC should interoperate, no matter which company coded them.
3.2) What standards is ECC part of?
Standards are important because it allows products from different companies to interoperate. In addition it allows various experts to combine their knowledge to produce the best implementations possible.

ECC is a part of numerous standards. Some of the most notable are listed here.
ANSI X9.62: THE ELLIPTIC CURVE DIGITAL SIGNATURE ALGORITHM
This standard defines digital signatures over elliptic curves. It is related to X9.40. A white paper which compares DSA and ECDSA may be found at: wecdsa.html
ANSI X9.63: ELLIPTIC CURVE KEY AGREMEENT AND KEY TRANSPORT
This standard defines Diffie-Hellman and MQV key establishment methods for elliptic curves and is related to X9.42.
IEEE P1363: STANDARD SPECIFICATIONS FOR PUBLIC KEY CRYPTOGRAPHY
This standard defines "discrete logarithm in the group of points on an elliptic curve over a finite field (EC)" as one of the three major families of cryptography. Included in the standard are EC implementations of Diffie-Hellman, DSA, MQV, and Nyberg-Rueppel. More information on the P1363 standard can be found at: http://grouper.ieee.org/groups/1363/
NIST DSS: DIGITAL SIGNATURE STANDARD
The National Institute for Standards & Technology offers a Digital Signature Standard which is incoporating ECC.

PKCS #13: ELLIPTIC CURVE CRYPTOGRAPHY STANDARDS
This is a general standard related to ECC that also tracks X9.62, X9.63, and P1363. An overview of the project may be found at: http://www.rsa.com/rsalabs/pubs/PKCS/html/pkcs-13.html

Additional Information on all of these standards, as well as a listing of numerous others, can be found at: standards.html
3.3) Can ECC be used with SSL?
Yes. However it will only interoperate with other versions of SSL also built to use ECC. This will work great if you're building some type of internal application where you'll be controlling both sides of the connection.

SSL Plus 3.0 has built in support for the Certicom ECC toolkit, Security Builder.
3.4) Can ECC be used with certificates?
Yes. Several vendors offer ECC-specific certificates. They include: Baltimore Technologies, Diversinet, Motorola, and Xcert International.
4.) ECC: THE TERMINOLOGY
This section explains additional ECC terminology.
4.1) What is EC*?
A number of different types of cryptography have been defined over elliptic curves. Each is named starting with EC.
ECDH the Elliptic Curve Diffie-Hellman Key Agreement
ECDSA the Elliptic Curve Digital Signature Algorithm
ECES the Elliptic Curve Encryption Scheme
ECMQV the Elliptic Curve MQV Key Agreement
ECNRA the Elliptic Curve Nyberg-Rueppel Signature Scheme
with Appendix

4.2) What is ECDLP?
ECDLP is the Elliptic Curve Discrete Logarithm Problem. As earlier noted, you need a tough math problem to implement cryptography. ECDLP is the particular problem that is used in ECC.

A more complete mathematical description of ECDLP appears in part 4.
4.3) What is F(p)? What is F(2^m)?
When you draw an elliptic curve for use with cryptography you want to choose a limited field of numbers to draw it over; this prevents round-off errors and other annoyances that could mess up your cryptographic calculations. F(p) and F(2^m) are both sets of numbers (fields) which are frequently used in ECC. F(p) is the set of whole numbers less than some prime number (p). F(2^m) is a more complex field related to polynomials whose coefficients are all 0 or 1.

A more mathematical explanation for F(p) and F(2^m) can be found in part 4 of this FAQ, which is all about ECC math.
4.4) What is m composite?
When you're choosing a number, m, to define the field F(2^m), you can either select an m that's a prime or an m that's composite (which is to say, not prime). m composite is, thus, an elliptic curve drawn over F(2^m) where the m chosen is a composite number.

Some people like m composite because it offers cryptographic speedups. However, many cryptographic experts, including mathematicians at Certicom, Entrust, RSA, Darmstadt University, Essen University, and Leuven University, have publically questioned the security of F(2^m) selected over m composite. The technical reason for this has to do with the existence of "non-trivial subfields" in m composite; these are subfields in the larger 2^m sized field which contain 2^n elements, for each divisor n of m.

For this reason, most people prefer to choose an m that is prime when defining a field F(2^m).
4.5) What is MQV?
MQV is short for Menezes-Qu-Vanstone, the names of the author of this protocol. It is a method of key agreement which is related to Diffie-Hellman, but offers a few advantages. Namely, MQV can be modified to work with the finite fields required for ECC.

Like other types of key agreement, MQV allows use of public-key cryptography to exchange symmetric keys.

There are also variants of MQV which can be used when only one user is online or which allow for key confirmation (where you make sure both users end up with the symmetric key--something which is useful for defeating certain types of active attacks). "An Efficient Protocol for Authenticated Key Agreement", a paper describing MQV, can be found at: http://csrc.nist.gov/cc/t4/wg2/MQV/mqv.pdf
When it is explicitly used with ECC, MQV is typically called ECMQV.
4.6) What is SECG?
SECG is the Standards for Efficient Cryptography Group. Its charter is to develop the Standards for Efficient Cryptography (SEC), a family of commercial standards that will specify completely interoperable, easily implemented, and cost-effective security solutions based on ECC technology.

The founding members of the SECG include 3Com, Baltimore Technologies, Certicom, Diversinet, Ernst & Young, Fujitsu, Giesecke & Devrient, GlobeSet, GTE CyberTrust, Hewlett-Packard, Motorola, NTT Electronics Corporation, Rainbow Technologies, Thawte Consulting, and Xcert International. The group has also created a Cryptographic Advisory Board, comprised of Dr. Ian Blake of Hewlett-Packard, Simon Blake-Wilson of Certicom, Dr. Dan Boneh of Stanford University, Don Johnson of Certicom, Dr. Alfred Menezes of the University of Waterloo, Larry Puhl of Motorola, Dr. Phil Rogaway of the University of California at Davis, Bruce Schneier of Counterpane, Dr. Gadiel Seroussi of Hewlett-Packard, Dr. Nigel Smart of Hewlett-Packard, and Dr. Scott Vanstone of Certicom.

More information is available at: secg.html
5) ECC: THE MATH
This section offers a broad overview of the math involved with elliptic curves. A complete tutorial which goes into more depth can be found at: math.html
5.1) What is an Elliptic Curve?
An elliptic curve is a curve defined by the following formula:

y^2 = x^3 + ax + b

Each different set of values for a and b defines a different elliptic curve. For example, for a=2 and b=1, you get the following formula for an elliptic curve:

y^2 = x^3 + 2x + 1

You'll recall from your high school algebra that a curve is formed by all points which satisfy a formula, such as the one above. So, for the above example, if x=1, you get:

y^2 = 1^3 + 2*1 + 1
y^2 = 1 + 2 + 1
y^2 = 4
y = SQRT (4)
y = 2 or -2


This defines two points on our particular elliptic curve, (1,2) and (1,-2). If you had a large amount of time you could solve for a number of points like this and eventually figure out what a particular elliptic curve looks like. Fortunately, you can use a computer program or a graphing calculator to do the same tedious job.

There's one more constraint for an elliptic curve. Besides fitting the above formula, it must also be true that x^3 + ax + b (the right-hand side of our equation) has "no repeating factors." You can determine this by solving the following equation:

4a^3 + 27b^2

Providing that the sum of those numbers is NOT zero, you have chosen a legal elliptic curve. For the above example of a=2, b=1, we get:

4*2^3 + 27*1^2
4*8 + 27*1
32 + 27
59


59 is not equal to 0, so a=2, b=1 is a legal choice of coefficients for an elliptic curve.

Once we've determined an elliptic curve we can define certain mathematical operations on it: namely addition and multiplication. The precise way in which this is done is technical--it can be determined geometrically, but there are also algebraic equations which can be used, and it's the latter which computer programs will depend upon. See the tutorial if you'd like all the specifics. The basic thing to understand is this: whenever you add two points on a curve, the result will be either another point on the curve or a special point in space called the "point at infinity." (The point at infinity is a special point that is defined especially to take care of cases when an addition would otherwise be undefined.)

All of the above explanations relate to elliptic curves over the field of real numbers. As we'll see, when elliptic curves are solved over other fields, the formulas for them will change a little.
5.2) What is a field?
A field is a set of numbers for which certain arithmetic operations, usually addition and subtraction, are defined. We've been talking so far about the infinite field of real numbers which contains all non-imaginary numbers: 4, 1/3, -3, and 2.183, to name a few examples. This field is infinite in size. Numerous other infinite fields exist, including whole numbers, fractional numbers, and imaginary numbers.

However, infinite fields like real numbers work poorly for cryptography. You end up with infinitely repeating fractions and round-off errors, and none of that is acceptable for cryptography.

So, in ECC cryptography, the curves tend be defined over specific finite fields instead: fields which are more easily constrained. The ones in most common usage are F(p) and F(2^m).
5.3) What is F(p)?
F(p) is a finite field commonly used for ECC. It is defined as the field of whole numbers from 0 to p - 1, where p must be a prime number. Recall that a prime number is a number whose only factors are 1 and the number itself. 23 is a prime number, because its only factors are 1 and 23. 22 is not because its factors are 1, 22, 2, and 11.

Any calculations in F(p) must be made modula p so that the result still falls into the F(p) space. Recall that modula is a remainder function. 25 mod 23 is 2. 48 mod 23 is also 2. 49 mod 23 is 3.

As a result of this, our ECC formula is modified as follows:

( y^2 ) mod p = ( x^3 + ax + b ) mod p

Likewise, our formula to determine the legality of an a & b pair becomes:

( 4a^3 + 27b^2 ) mod p

Elliptic Curves drawn in F(p) look a lot different from those drawn in the field of real numbers. Instead of nice, smooth curves you end up with disjoint points--since you're only allowing a small set of whole numbers--and it might not even be obvious how all the points connect together. Fortunately, the mathematical formulas for addition and multiplication still work. Even better, this more constrained curve space provides the preciseness that cryptography requires.
5.4) What is F(2^m)?
F(2^m) is another finite field over which elliptic curves are commonly defined. Its definition is fairly complex. F(2^m) consists of polynomials of degree less than m whose coefficients fall into the field of F(2).

Recall that a polynomial consists of a sum of various exponents, like this:

12x^3 + 5x^1 + 1

The degree of a polynomial is equal to its highest power of exponentiation, so in the above example the power would be three.

Recall that coefficients are those numbers to the left of exponents--multipliers. In the following example, the coefficient is 17:

17x^3

Finally, F(2) is just part of the F(p) field that was defined in the previous question (4.3). It consists of all the whole numbers less than 2, which is to say 0 and 1.

Putting that all together, when we say that F(2^m) consists of all polynomials of a degree less than m whose coefficients fall into the field of F(2), we mean that we have a polynomial, whose highest exponent is m-1, and that all the coefficients in the polynomial are either 0 or 1. Following are a few examples of polynomials in F(2^m):
x^2 + 1 <-- an element of F(2^3)
x^7 + x^5 + x^4 + x^2 <-- an element of F(2^8)
x^19 + x <-- an element of F(2^20)
Any field, F(2^m), has exactly 2^m elements.

One quick digression: clever computer scientists will quickly realize that these polynomials can easily be represented in binary, simply by listing the coefficients. This is usually done as a vector. Our above three polynomials would be represented as such:

x^2 + 1 = (1 0 1)
x^7 + x^5 +x^4 + x^2 = (1 0 1 1 0 1 0 0)
X^19 + x = (1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0)

Stepping back to F(2^m): as we've already mentioned, for each field, F(2^m), there are exactly 2^m elements. There's another interesting property, which is that every field, F(2^m), also has a generator, g, which is a specific element of F(2^m) which can be used to generate all of the other elements of that field via exponentiation.

For example, for F(2^4), we have 2^4 elements, or 16. Further we have a generator, which happens to be:

x = (0 0 1 0)

How exactly this generator is determined, and how the exponentiation works, is beyond the scope of this document. The important thing to note is that the generator to a specific power can also be used to represent any specific element in F(2^m). In our above example, g^1 is (0 0 1 0) or x, g^2 is (0 1 0 0) or x^2, g^3 is (1 0 0 0) or x^3, g^4 is (0 0 1 1) or x + 1, etc. Whenever points are denoted in F(2^m), they're usually marked as powers of the generator, g, for ease of notation.

In the field of F(2^m) our elliptic curve equation once more has to be slightly changed, to take into account polynomials. It becomes:

y^2 + xy = x^3 + ax^2 + b

So, at this point we can finally draw an elliptic curve over F(2^m). In order to do so, we must choose a and b which are elements of F(2^m), then we must find x and y values, which will also be elements of F(2^m). Whew.

For example, if we choose a=g^2 and b=g^3, we would use the following formula:

y^2 + xy = x^3 + g^2x^2 + g^3

We could then insert a value of x, say x=g^1 and solve for y:

y^2 + g^1y = (g^1)^3 + g^2(g^1)^2 + g^3

We won't carry this example any further, but the end result is that we'll have a graph of disjoint points, just as we did with F(p); once we have the entire graph defined, we can then calculate additions, subtractions, etc., just as we did with F(m) and earlier with real numbers. The only real difference is that our calculations are much more complex, because of the fact that each element in F(2^m) is a full polynomial equation rather than a simple point.

5.5) What is the Elliptic Curve Discrete Logarithm Problem (ECDLP)?
Defining curves and fields doesn't do any good without actually having a problem to solve. In the case of cryptography, we need a trap-door one-way function, so it's easy to encode things, but difficult to decode them--unless you know a specific secret.

The ECDLP is based upon the Discrete Logarithm Problem (DLP) which is used by DSA. However, because of the use of Elliptic Curves, the ECDLP offers the distinct advantage of smaller keys.

ECDLP is built upon the difficulty to reverse scalar multiplication, which is a type of multiplication defined over a elliptic curve. The problem is written as such:

Given Pk = Q, and given P and Q, find k. P and Q will both be points on our elliptic curve, while k will be some large number, typically 160+ bits.
6) ECC: SECURITY BUILDER
This section contains basic q&a for Security Builder, one ECC toolkit.