/usr/share/doc/sks-ecc-doc/usersguide-es/ecc-faq.html

###
<HTML>
<HEAD>
<TITLE>Elliptic curve cryptography FAQ v1.12 22nd December 1997</TITLE>
</HEAD>
<BODY>
<H1>Elliptic curve cryptography FAQ v1.12 22nd December 1997</H1>

<H3>(1) What is an elliptic curve?</H3>

<P>Well for a start, it is not the same as an ellipse!</P>

<P>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</P>

<P>(x-a)^2 + (y-b)^2 = r^2</P>

<P>where x, y, a, b and r are real numbers.</P>

<P>An elliptic curve is also defined by an equation, but it has the
slightly more complicated form:</P>

<P>y^2 [ + x&#183;y ] = x^3 + a&#183;x^2 + b</P>

<P>Notation: &#183; means multiplication, and ^ means raising to a power,
so that y^2 means y&#183;y and x^3 means x&#183;x&#183;x. The square brackets
mean that the term is optional - sometimes it is there, sometimes
it isn't!</P>

<P>Again x and y are variables, a and b are constants.</P>

<P>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.</P>

<P>[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.]</P>

<H3>(2) What is a field?</H3>

<P>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.</P>

<P>Recall that complex numbers can be defined as b&#183;i + a with the
"reduction rule"  i^2 + 1 =&gt; 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.</P>

<P>It turns out that this construction works for other
"reduction rules" involving higher powers of i.</P>

<P>To avoid confusion, in what follows, t is used instead of i.</P>

<P>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.</P>

<P>For example, if we set p=2, m=4, and use the "reduction rule"
t^4 + t + 1 =&gt; 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.</P>

<P>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.</P>

<P>This construction works for all p and m, as long as p is prime;
in fact <EM>every</EM> 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.</P>

<P>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.)</P>

<P>The prime p is called the "characteristic" of the field - I won't
use this term, but sometimes it helps to know the jargon.</P>

<H3>(3) How are elliptic curves used?</H3>

<P>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.</P>

<P>The equations for the addition rule are given in (7) and (8).</P>

<P>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.</P>

<P>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.</P>

<P>Thus 2*P = P+P<BR>
     3*P = P+P+P<BR>
etc.</P>

<P>This is analagous to how we define "powers" in normal arithmetic,
where<BR>
      x^2 = x.x<BR>
      x^3 = x.x.x<BR>
etc.</P>

<P>Now we are in a position to do some cryptography!</P>

<P>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.</P>

<P>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).</P>

<P>Bob can compute the same number by calculating Bk * AP,
since Bk*AP = Bk*(Ak*F) = (Bk*Ak)*F = Ak*(Bk*F) = Ak*BP.</P>

<P>The security of the scheme is based on the assumption that it is
difficult to compute k given F and k*F.</P>

<H3>(4) How is the elliptic curve chosen?</H3>

<P>First of all, a finite field is chosen, see (9)</P>

<P>If the field is GF(p) where p is a large prime, the x&#183;y term is
omitted, leaving us with<BR>
  y^2 = x^3 + a&#183;x^2 + b<BR>
There is a requirement that 4&#183;a^3 + 27&#183;b^2 is non-zero.</P>

<P>If the field is GF(2^m) then we include the x&#183;y term to get<BR>
  y^2 + x&#183;y =  x^3 + a&#183;x^2 + b<BR>
There is a requirement that b is non-zero.</P>

<P>Fields GF(p^m) with both p&gt;2 and m&gt;1 are not considered here.</P>

<H3>(5) How is the fixed point chosen?</H3>

<P>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&gt;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.</P>

<P>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.</P>

<P>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).</P>

<P>For good security the order of the fixed point should also satisfy
the "MOV" condition to prevent certain possible attacks - see (15).</P>

<P>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.</P>

<P>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.</P>

<P>For example, if the order of F is a 240-bit prime, then an attack
would be expected to need 2^120 operations.</P>

<P>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.</P>

<H3>(6) What about digital signatures?</H3>

<P>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.</P>

<P>The Nyberg-Rueppel scheme works like this:</P>

<P>Let x(P) denote the x-coordinate of the elliptic curve point P
converted to an integer.</P>

<P>Alice chooses a random number k, and computes (mod order(F))<BR>
  r = x(k*F)+data<BR>
  s = k - Ak*r<BR>
where data is a hash of the data being signed.
The signature is the pair (r,s).</P>

<P>To verify the signature, Bob checks that (mod order(F))<BR>
  data == r - x(s*F + r*AP)</P>

<P>A little bit of algebra shows why this works.</P>

<P> [ 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. ] </P>

<H3>(7) What is the addition rule when the field is GF(p)?</H3>

<P>In this case the addition rule has the form<BR>
  (x1,y1) + (x2,y2) =&gt; (x3,y3)<BR>
where x3 = L^2 - x1 - x2<BR>
and   y3 = L&#183;(x1-x3) - y1<BR>
and   L = (y1-y2)/(x2-x1)</P>

<P>If x1=x2 and y1=y2 we must use instead,<BR>
  x3 = L^2 - 2&#183;x1<BR>
  y3 = L&#183;(x1-x3) - y1<BR>
  L = ( 3&#183;x1^2 + a ) / ( 2&#183;y1 )</P>

<P>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.</P>

<P>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.</P>

<H3>(8) What is the addition rule for when the field is GF(2^m)?</H3>

<P>In this case the addition rule has the form<BR>
  (x1,y1) + (x2,y2) = (x3,y3)<BR>
where<BR>
  x3 = L^2 + L + x1 + x2 + a<BR>
  y3 = L&#183;(x1+x3) + x3 + y1<BR>
  L = (y1+y2)/(x1+x2)</P>

<P>If x1=x2 and y1=y2 we must use instead<BR>
  x3 = L^2 + L + a<BR>
  y3 = x1^2 + (L+1)&#183;x3<BR>
  L = x1 + y1/x1</P>

<P>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.</P>

<H3>(9) How is the finite field chosen?</H3>

<P>The finite field needs to be chosen so that the prime order of the
fixed point is sufficiently large, say 150-300 bits.</P>

<P>In the case of GF(2^m) some fields have 
representations which are particularly efficient.</P>

<H3>(10) What are field representations?</H3>

<P>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.</P>

<P>An analogy is using different representations for integers - for
example base 10 or base 2.</P>

<P>Depending on the field, various tricks are possible, especially for
the case GF(2^m).</P>

<P>There are two main possibilities: polynomial and normal basis.
Polynomial basis is probably easier to understand.</P>

<P>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)]</P>

<P>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.</P>

<P>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.</P>

<H3>(11) How are field representations chosen?</H3>

<P>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.</P>

<P>For normal basis, one looks for an 'optimal' normal basis such that
field multiplication is efficient.</P>

<P>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).</P>

<P>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.</P>

<H3>(12) What is Weil's theorem and how can it be used?</H3>

<P>The order E of an elliptic curve y^2 + x&#183;y = x^3 + a&#183;x^2 + b over
GF(2^(L*K)) can be calculated using the magic formula:</P>

<P>      2^(L*K) + 1 - lucas( 2^L-(e-1), 2^L, K )</P>

<P>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<BR>
  V(0) = 2; V(1) = p; V(K) = p&#183;V(K-1) - Z&#183;V(K-2)</P>

<P>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.</P>

<P>Moreover, E is divisible by e - this useful fact is not always
mentioned.</P>

<P>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.</P>

<P>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.</P>

<P>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.</P>

<H3>(13) What is point compression?</H3>

<P>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).</P>

<P>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.</P>

<H3>(14) What is an irreducible polynomial?</H3>

<P>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):</P>

<PRE>int poly_irreducible( const vlong &amp; x )
{
  unsigned d = x.bits()-1;
  vlong u = 2;
  for (unsigned i=1;i&lt;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;
}</PRE>

<P>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.</P>

<P>Since irreducible polynomials are quite common (a bit like prime
numbers) it is quite easy to find them using this test.</P>

<P>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.</P>

<H3>(15) What is the MOV condition?</H3>

<P>Suppose that the field is GF(q) and the fixed point is F.
We check that the first T terms of the sequence
<BR>  q, q^2, q^3 .....<BR>
are not equal to 1 modulo the (prime) order of F.
A suitable value for T is log2(q)/8.</P>

<P> 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. </P>

<H3>(16) Suggestions for further reading</H3>

<P> A Course in Number Theory and Cryptography (2nd edition)<BR>
 by Neal Koblitz<BR>
 Springer-Verlag (New York) 1994<BR>
 ISBN 0-387-94293-9</P>

<P> Elliptic curve public key cryptosystem<BR>
 by A.J. Menezes<BR>
 Kluwer Academic Publications 1993</P>

<P> <A HREF="http://stdsbbs.ieee.org/groups/1363/index.html">
 IEEE P1363: (draft) Standard for Public-Key Cryptography</A>

<H3>(17) What patents are there?</H3>

<P>There are various patents concerning normal basis.
US patents 4587627 Omura-Massey (OMNET),
739220 Onyszchuk/Mullin/Vanstone.</P>

<P>US Patent 5272755 Miyaji-Tatebayashi (Matsushita)
relates to curves over GF(p).</P>

<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</P>

<P>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.</P>

<P>To summarise - using GF(2^m) with a polynomial basis
seems to avoid any patent problems.</P>

<P>In addition, there are various schemes, such as signature
and key agreement protocols, which may be subject to patents.</P>

<P>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.
</P>

<P>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.</P>

<P>The Nyberg-Rueppel signature scheme may be subject to
European patent 0639907 (I haven't seen this)</P>

<P>For information on US patents, consult the impressive IBM
patent server at <A HREF="http://patent.womplex.ibm.com/ibm.html">http://patent.womplex.ibm.com/ibm.html</A></P>

<P>Disclaimer: I cannot guarantee the accuracy or completeness
of the this information (as if this wasn't obvious!).</P>

<H3>(18) What software implementations are available?</H3>

<P>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!)</P>

<P>Pegwit is a complete program in 'C' with PGP-like functionality
using elliptic curves, and is available from
<A HREF="http://ds.dial.pipex.com/george.barwood/v8/pegwit.htm">http://ds.dial.pipex.com/george.barwood/v8/pegwit.htm</A></P>

<P>Equivalent C++ elliptic curve code, and the code used to
calculate the curve parameters is at
<A HREF="http://ds.dial.pipex.com/george.barwood/crypto.htm">http://ds.dial.pipex.com/george.barwood/crypto.htm</A></P>

<HR>

<P>The latest version of this FAQ can be found at
<A HREF="http://ds.dial.pipex.com/george.barwood/ec_faq.txt">http://ds.dial.pipex.com/george.barwood/ec_faq.txt</A></P>
or in html form at
<A HREF="http://ds.dial.pipex.com/george.barwood/ec_faq.htm">http://ds.dial.pipex.com/george.barwood/ec_faq.htm</A></P>

<P> A German translation by Ulf Möller is at
<A HREF="http://www.fitug.de/ulf/faq/ec_faq.html">http://www.fitug.de/ulf/faq/ec_faq.html</A></P>

<P>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.</P>

<P>Please send comments, corrections and suggestions to:
<A HREF="mailto:george.barwood@dial.pipex.com">george.barwood@dial.pipex.com</A></P>

<P>George Barwood</P>

</BODY>
</HTML>

### end pegwit v8 signed text
0356ff6c0ed8ebcc432895c7bb74976ee6cbc37058e9cd74607edc13e51a
ff5f2fd5f5970a6b4f420e05150be4c46ad9d3bfa9925e4a4dd92316f156
sks-ecc-doc 0.93-6 / usr / share / doc / sks-ecc-doc / usersguide-es / ecc-faq.html
