Well for a start, it is not the same as an ellipse!
But to be more positive: from school mathematics, you probably know the equation for a circle centred on the (a,b) of radius r, which is
(x-a)^2 + (y-b)^2 = r^2
where x, y, a, b and r are real numbers.
An elliptic curve is also defined by an equation, but it has the slightly more complicated form:
y^2 [ + x·y ] = x^3 + a·x^2 + b
Notation: · means multiplication, and ^ means raising to a power, so that y^2 means y·y and x^3 means x·x·x. The square brackets mean that the term is optional - sometimes it is there, sometimes it isn't!
Again x and y are variables, a and b are constants.
However, these quantities are not necessarily real numbers, instead they may be values from any field. For cryptographic purposes we always use a "finite" field - that is x, y, a and b are chosen from a finite set of distinct values.
[In fact the equation given here is not the most general possible, but it will serve for the purposes of this FAQ, and as far as I know for all cryptographic purposes.]
The familiar examples of fields are real numbers, complex numbers, rational numbers (fractions) and integers modulo a prime number. The latter is an example of a "finite field". The requirements of a field are normal addition and multiplication, plus the existence of both additive and multiplicative inverses (except that 0 doesn't have a multiplicative inverse). To put it another way, a field has addition, subtraction, multiplication and division - and these operations always produce a result that is in the field, with the exception of division by zero, which is undefined.
Recall that complex numbers can be defined as b·i + a with the "reduction rule" i^2 + 1 => 0. To multiply complex numbers we treat i as an "unknown", collect up powers of i, and apply the reduction rule to simplify the result.
It turns out that this construction works for other "reduction rules" involving higher powers of i.
To avoid confusion, in what follows, t is used instead of i.
The coefficients of the powers of t can be from any field - but if we take the field to be the integers modulo p, we get a finite field with p^m elements, where m is the degree of the "reduction rule" - that is the exponent of the highest power of t.
For example, if we set p=2, m=4, and use the "reduction rule" t^4 + t + 1 => 0, we get a field with 2^4=16 distinct elements: 0, 1, t, t+1, t^2, t^2+1, t^2+t, t^2+t+1, t^3, t^3+1, t^3+t, t^3+t+1, t^3+t^2, t^3+t^2+1, t^3+t^2+t, t^3+t^2+t+1.
Not all "reduction rules" work, we need to use an "irreducible" polynomial - see (14). Note that when multiplying elements of the field there are actually two reduction rules working simultaneously - the rule for reducing coefficients modulo p, and the rule for reducing high powers of t.
This construction works for all p and m, as long as p is prime; in fact every finite field can be constructed in this way; moreover two finite fields with the same number of elements are always isomorphic - that is there is a 1-1 map between them which preserves the addition and multiplication rules.
In the light of these facts, we refer to "the" Galois field with p^m elements, using the notation GF(p^m). (Evariste Galois was a French mathematician who died in a duel in 1832 when he was just 20 years old.)
The prime p is called the "characteristic" of the field - I won't use this term, but sometimes it helps to know the jargon.
The crucial property of an elliptic curve is that we can define a rule for "adding" two points which are on the curve, to obtain a 3rd point which is also on the curve. This addition rule satisfies the normal properties of addition. In math jargon, the points and the addition law form a finite Abelian group.
The equations for the addition rule are given in (7) and (8).
For addition to be well defined for any two points, we need to include an extra 'zero' point O, which does not satisfy the elliptic curve equation. This 'zero' point is taken to be a fully paid up point of the curve. The order of the curve is the number of distinct points on the curve, including the zero point.
Having defined addition of two points, we can also define multiplication k*P where k is a positive integer and P is a point as the sum of k copies of P.
Thus 2*P = P+P
3*P = P+P+P
etc.
This is analagous to how we define "powers" in normal arithmetic,
where
x^2 = x.x
x^3 = x.x.x
etc.
Now we are in a position to do some cryptography!
Alice, Bob, Cathy, David... agree on a (non-secret) elliptic curve and a (non-secret) fixed curve point F. Alice chooses a secret random integer Ak which is her secret key, and publishes the curve point AP = Ak*F as her public key. Bob, Cathy and David do the same.
Now suppose Alice wishes to send a message to Bob. One method is for Alice to simply compute Ak*BP and use the result as the secret key for a conventional symmetric block cipher (say DES).
Bob can compute the same number by calculating Bk * AP, since Bk*AP = Bk*(Ak*F) = (Bk*Ak)*F = Ak*(Bk*F) = Ak*BP.
The security of the scheme is based on the assumption that it is difficult to compute k given F and k*F.
First of all, a finite field is chosen, see (9)
If the field is GF(p) where p is a large prime, the x·y term
is omitted, leaving us with
y^2 = x^3 + a·x^2 + b
There is a requirement that 4·a^3 + 27·b^2 is non-zero.
If the field is GF(2^m) then we include the x·y term to get
y^2 + x·y = x^3 + a·x^2 + b
There is a requirement that b is non-zero.
Fields GF(p^m) with both p>2 and m>1 are not considered here.
If we carry on computing P+P+P... for long enough, since the number of curve points is finite, we must eventually get a result of O. [We will certainly have a*P = b*P for some a, b with b>a; This implies that c*P = O where c = b-a.] The least c for which this is true is called the order of the point, and a little group theory tells us that c must divide the order of the curve.
For good security, the curve and fixed point are chosen so that the order of the fixed point F is a large prime number. This is quite easy to do once we know the order of the curve, provided it has a large prime factor. However finding the order of an arbitrary curve is tricky - it involves what is known as Schoof's algorithm - and getting this algorithm to run in a reasonable time takes a lot of tricks.
There are two alternative methods which instead construct curves of known order, one based on Complex Multiplication (which is also pretty difficult maths - but not as tricky as Schoof!) and the other based on "Weil's theorem", which is much quicker to code: see (12).
For good security the order of the fixed point should also satisfy the "MOV" condition to prevent certain possible attacks - see (15).
Remark: if the finite field on which a curve is based has q elements, then the order of the curve must be also different from q. Curves with this order are called anomalous, and are susceptible to a recently discovered attack.
As far as is known, with the above provisions, if the order of the fixed point F is an n-bit prime, then computing k from k*F and F takes roughly 2^(n/2) operations.
For example, if the order of F is a 240-bit prime, then an attack would be expected to need 2^120 operations.
This is what makes the use of elliptic curves attractive - it means that public keys and signatures can be much smaller than with RSA for the same predicted security.
Using the Nyberg-Rueppel scheme is one possibility. The DSA scheme is another. Pretty much any cryptographic scheme/protocol based on discrete logarithms can be easily converted to elliptic curve form. In most cases it is necessary for the fixed point F to have known prime order.
The Nyberg-Rueppel scheme works like this:
Let x(P) denote the x-coordinate of the elliptic curve point P converted to an integer.
Alice chooses a random number k, and computes (mod order(F))
r = x(k*F)+data
s = k - Ak*r
where data is a hash of the data being signed. The signature is the pair
(r,s).
To verify the signature, Bob checks that (mod order(F))
data == r - x(s*F + r*AP)
A little bit of algebra shows why this works.
[ Note that IEEE P1363 recommends Alice avoiding r=0, and for Bob to check that r and s are in the expected range, although I don't see any good reason for this. ]
In this case the addition rule has the form
(x1,y1) + (x2,y2) => (x3,y3)
where x3 = L^2 - x1 - x2
and y3 = L·(x1-x3) - y1
and L = (y1-y2)/(x2-x1)
If x1=x2 and y1=y2 we must use instead,
x3 = L^2 - 2·x1
y3 = L·(x1-x3) - y1
L = ( 3·x1^2 + a ) / ( 2·y1 )
There are some other special cases which must be considered first: if x1=x2 and y1=-y2 then the result is zero, and if either point is zero, the result is the other operand.
By doing some algebra, you can check that the usual laws for addition apply, e.g. P+Q=Q+P and (P+Q)+R = P+(Q+R), and that the result of adding two points is indeed another curve point.
In this case the addition rule has the form
(x1,y1) + (x2,y2) = (x3,y3)
where
x3 = L^2 + L + x1 + x2 + a
y3 = L·(x1+x3) + x3 + y1
L = (y1+y2)/(x1+x2)
If x1=x2 and y1=y2 we must use instead
x3 = L^2 + L + a
y3 = x1^2 + (L+1)·x3
L = x1 + y1/x1
Again, there are some other special cases which must be considered first: if x1=x2 and y2=x1+y1 then the result is zero, and if either point is zero, the result is the other operand.
The finite field needs to be chosen so that the prime order of the fixed point is sufficiently large, say 150-300 bits.
In the case of GF(2^m) some fields have representations which are particularly efficient.
A field representation defines what bit-patterns are used to represent the various field elements. The representation (and the field) is chosen to make the field arithmetic operations efficient.
An analogy is using different representations for integers - for example base 10 or base 2.
Depending on the field, various tricks are possible, especially for the case GF(2^m).
There are two main possibilities: polynomial and normal basis. Polynomial basis is probably easier to understand.
With a polynomial basis, field elements are represented as polynomials. Usually a vector with m+1 components is used to represent a polynomial of degree m. When multiplying, the remainder is taken after dividing the result polynomial by an "irreducible" polynomial [see (14)]
If m has factors, the basis can be over a sub-field other than GF(2). This is analagous to performing multi-precision arithmetic on words instead of bits.
For small fields such as GF(2^9) field multiplication and division can be performed by simple table lookup, by taking 'logarithms'. It is always possible to find a field element, called a generator, such that the whole finite field is generated by the powers of the generator. In fact we can arrange that the single term polynomial t is a generator by using a "primitive" polynomial - this makes calculating the log tables marginally faster.
For polynomial basis, one looks for trinomial reduction polynomials to improve the speed of modular reduction. A trinomial is a polynomial with just three terms, for example x^29 + x^2 + 1.
For normal basis, one looks for an 'optimal' normal basis such that field multiplication is efficient.
For hardware, a normal basis over GF(2) may be attractive. For software, a polynomial basis, or a sub-field representation seems to be better (more efficient).
In principle, one may convert between different field representations, so looking for a field in which several different efficient representations are possible might be a good idea. One possible candidate is GF(2^261) which can be represented with an optimal normal basis, and also as a polynomials with coefficients in GF(2^9) using the trinomial x^29 + x^2 + 1 as the reduction polynomial.
The order E of an elliptic curve y^2 + x·y = x^3 + a·x^2 + b over GF(2^(L*K)) can be calculated using the magic formula:
2^(L*K) + 1 - lucas( 2^L-(e-1), 2^L, K )
where e is the order of the curve over GF(2^L), and the function lucas(p,Z,K)
= V(K), is defined by the recursion
V(0) = 2; V(1) = p; V(K) = p·V(K-1) - Z·V(K-2)
Note that GF(2^L) is a sub-field of GF(2^(L*K)) - a and b need to be elements of this sub-field for the theorem to apply.
Moreover, E is divisible by e - this useful fact is not always mentioned.
If L is fairly small, we can find e by "brute force", and quite often it turns out that E/e is a (large) prime - if it is, we can choose the fixed point F by choosing an arbitrary point R and setting F = e*R (if this is zero, try again). F then has order E/e.
Note that K needs to be prime, as otherwise there will be an intermediate sub-curve of larg(ish) order, and E/e will not be prime.
To apply the theorem, we need to identify a sub-field of GF(2^L*K) of order 2^L - depending on the field representation used this can be trivial, or some work may be needed.
If we know the x-coordinate of a point, we can find the y-coordinate by solving the curve equation. Since it is a quadratic equation, there will be two possible results (or none), so we need an extra bit to choose the correct solution. This technique can also be used to choose random points on the curve (a retry will be needed if the quadratic equation has no solution).
Point compression is nice because it reduces the size of public keys from say 510 bits to 256 bits. Solving quadratic equations over finite fields is a reasonably cheap operation.
Simply one that has no factors in the field under consideration. Note that the field matters - x^2 + 1 is irreducible over the real numbers, but has a perfectly good factorisation (x+i)(x-i) over the field of complex numbers. There is an efficient algorithm for testing for irreducibility over GF(2):
int poly_irreducible( const vlong & x )
{
unsigned d = x.bits()-1;
vlong u = 2;
for (unsigned i=1;i<d;i+=1)
{
u = poly_rem( poly_mul(u,u), x );
vlong g = poly_gcd( u^2, x );
if ( g != 1 ) return 0;
}
return 1;
}
Here poly_mul, poly_rem denote polynomial multiplication and remainder, and poly_gcd finds the greatest common factor of two polynomials (essentially Euclids algorithm). Note that the function is using a mixture of normal 2's complement arithmetic and polynomial routines in a slightly obscure way; x.bits() is 1+log2(x), and ^ is the 'C' exclusive-or operation not exponentiation.
Since irreducible polynomials are quite common (a bit like prime numbers) it is quite easy to find them using this test.
To see why a reduction polynomial G must not have factors, suppose for a moment that it did. Then we would have a*b = G for non-zero a,b; and after reduction, a*b = 0. But multiplying through by the inverse of b would give a=0, which is a contradiction.
Suppose that the field is GF(q) and the fixed point is F. We check that
the first T terms of the sequence
q, q^2, q^3 .....
are not equal to 1 modulo the (prime) order of F. A suitable value for
T is log2(q)/8.
MOV stands for Menezes, Okamoto and Vanstone - they wrote a paper "Reducing elliptic curve logarithms to logarithms in a finite field" IEEETIT,39(5):1639-1646,1993.
A Course in Number Theory and Cryptography (2nd edition)
by Neal Koblitz
Springer-Verlag (New York) 1994
ISBN 0-387-94293-9
Elliptic curve public key cryptosystem
by A.J. Menezes
Kluwer Academic Publications 1993
IEEE P1363: (draft) Standard for Public-Key Cryptography
There are various patents concerning normal basis. US patents 4587627 Omura-Massey (OMNET), 739220 Onyszchuk/Mullin/Vanstone.
US Patent 5272755 Miyaji-Tatebayashi (Matsushita) relates to curves over GF(p).
Richard Crandall of Next computers has patents concerning GF(p), where p is of the form 2^q - C for small C. US Patents 5463690,5271051,5159632
US Patent 5146500 Maura (Omnisec) concerns "elliptic curves over rings" (sic). I haven't any idea what this means, but it seems to only use integer arithmetic modulo a prime.
To summarise - using GF(2^m) with a polynomial basis seems to avoid any patent problems.
In addition, there are various schemes, such as signature and key agreement protocols, which may be subject to patents.
4,200,770 Diffie-Hellman expires Sept. 6, 1997, and 4,218,582 Hellman-Merkle expires Oct. 6, 1997. Hellman-Merkle is also patented outside the US. In many countries the patent will expire later than in the US, but the relevance of this patent is dubious.
The DSA signature scheme is now unencumbered in the U.S. after the owners lost a suit by the U.S. government (or settled out of court). It was patented, but now there are no royalties or licenses needed.
The Nyberg-Rueppel signature scheme may be subject to European patent 0639907 (I haven't seen this)
For information on US patents, consult the impressive IBM patent server at http://patent.womplex.ibm.com/ibm.html
Disclaimer: I cannot guarantee the accuracy or completeness of the this information (as if this wasn't obvious!).
Wei Dai's Crypto++ library has elliptic curve routines, but has a restricted choice of curves (AFAIK). If you are not U.S. resident you may have some trouble obtaining Crypto++ (but persevere and you will probably find it somewhere!)
Pegwit is a complete program in 'C' with PGP-like functionality using elliptic curves, and is available from http://ds.dial.pipex.com/george.barwood/v8/pegwit.htm
Equivalent C++ elliptic curve code, and the code used to calculate the curve parameters is at http://ds.dial.pipex.com/george.barwood/crypto.htm
The latest version of this FAQ can be found at http://ds.dial.pipex.com/george.barwood/ec_faq.txt
or in html form at http://ds.dial.pipex.com/george.barwood/ec_faq.htm
A German translation by Ulf Möller is at http://www.fitug.de/ulf/faq/ec_faq.html
Acknowledgments: Special thanks to Ulf Möller for many improvements, and also to Paulo Barreto, Glynne Casteel, Wei Dai, Michael Greene, Kris Van Hees, Bodo Möller, Paul Onions, Mike Rosing, Roger Schlafly and Don Taylor.
Please send comments, corrections and suggestions to: [email protected]
George Barwood
### end pegwit v8 signed text 0356ff6c0ed8ebcc432895c7bb74976ee6cbc37058e9cd74607edc13e51a ff5f2fd5f5970a6b4f420e05150be4c46ad9d3bfa9925e4a4dd92316f156