The principal attraction of ECC, compared to RSA, is that it appears to offer equal security for a far smaller key size, thereby reducing processing overhead.

**ELLIPTIC CURVE
ARITHMETIC**

Most of the products and standards that use
public-key cryptography for encryp- tion and digital signatures use RSA. As we
have seen, the key length for secure RSA use has increased
over recent years,
and this has put a heavier processing load on applications using RSA. This burden has ramifications, especially for electronic
commerce sites that conduct large numbers of secure transactions. A competing system challenges RSA: elliptic
curve cryptography (ECC).
ECC is showing up in standardization
efforts, including the
IEEE P1363 Standard for Public-Key
Cryptography.

The principal attraction of ECC, compared to RSA, is that it
appears to offer equal security for a far smaller key size, thereby
reducing processing overhead. On the other hand, although the theory of ECC has been around
for some time, it is only recently that products have begun to appear and that
there has been sustained
cryptanalytic interest in probing for weaknesses. Accordingly, the confidence level in
ECC is not yet as high as that in RSA.

ECC is fundamentally more difficult to
explain than either RSA or Diffie- Hellman, and
a full mathematical description is beyond the scope
of this book. This section and the next give some background on elliptic
curves and ECC. We begin with a
brief review of the concept of abelian group. Next, we examine the concept
of elliptic curves
defined over the real numbers.
This is followed
by a look at elliptic curves defined over finite fields. Finally, we
are able to examine elliptic curve ciphers.

The reader may wish to review the material on finite fields
in Chapter 4 before
proceeding.

Abelian Groups

A number of public-key ciphers
are based on the use of an abelian group. For example, Diffie-Hellman key exchange
involves multiplying pairs of nonzero
inte- gers modulo a prime number *q*.
Keys are generated by exponentiation over the group, with exponentiation defined as repeated
multiplication. For example,

determine *k *given
*a *and *a**k*; this is the
discrete logarithm problem.

For elliptic curve
cryptography, an operation over elliptic curves,
called addi- tion, is used. Multiplication is defined by repeated addition.
For example,

where the addition is performed over an elliptic curve.
Cryptanalysis involves determining *k *given *a *and (*a ** *k*).

An **elliptic
curve **is defined by an equation
in two variables with coefficients. For cryptography, the variables and
coefficients are restricted to elements in a finite field, which results in the definition of a finite abelian group. Before looking at this, we first look at elliptic curves in
which the variables and coefficients are real numbers.
This case is perhaps easier to visualize.

Elliptic Curves
over Real Numbers

Elliptic curves are not ellipses. They are
so named because they are described by cubic
equations, similar to those used
for calculating the
circumference of an ellipse.
In general, cubic equations for elliptic curves take the following form, known
as a **Weierstrass equation**:

*y*2 + *axy *+ *by *= *x*3
+ *cx*2
+ *dx *+ *e*

where *a*, *b*, *c*, *d*, *e *are real numbers and *x *and *y *take
on values in the real numbers.4 For our purpose,
it is sufficient to limit
ourselves to equations of the form

Such equations are said to be cubic, or of degree 3, because the highest expo- nent they contain is a 3. Also included
in the definition of an elliptic curve is a single
element denoted *O *and called the
*point
at infinity *or the *zero
point*, which we discuss subsequently. To plot such a curve, we need to compute

For given values
of *a *and *b*, the plot consists
of positive and negative values
of *y *for each value
of *x*. Thus, each curve
is symmetric about *y *= 0. Figure 10.4 shows
two examples of elliptic
curves. As you can see, the formula
sometimes produces weird- looking curves.

Now, consider the set of points E(*a*, *b*)
consisting of all of the points (*x*, *y*) that satisfy Equation (10.1) together
with the element *O*. Using a different
value of the pair (*a*, *b*) results in a different set E(*a*, *b*).
Using this terminology, the two curves in Figure 10.4 depict the sets E(-1, 0) and E(1, 1),
respectively.

*GEOMETRIC **DESCRIPTION OF *** ADDITION **It can be shown that a group can be defined based on the
set E(

To define the group, we must define an operation, called addition and denoted by +,
for the set E(*a*, *b*), where *a *and *b *satisfy Equation (10.2). In geometric
terms, the rules for addition
can be stated as follows:
If three points
on an elliptic curve lie on
a straight line, their sum is *O*. From this definition, we can define the rules of addi- tion over an elliptic
curve.

**1.
***O *serves as the additive identity. Thus
*O
*= -*O*; for any point *P *on
the elliptic curve, *P *+ *O *= *P*. In what follows,
we assume *P *!= *O *and *Q *!= *O*.

The negative of a point *P *is the point with the same *x *coordinate but the negative
of the *y *coordinate; that is, if *P *= (*x*, *y*), then -*P**
*= (*x*, -*y*). Note that these two points can be joined
by a vertical line. Note that *P *+ (-*P*) = *P *- *P *= *O*.

**1.
**To
add two points *P *and *Q *with different *x *coordinates, draw a straight line
between them and find the third point of intersection *R*. It is easily seen that there
is a unique point *R *that
is the point of intersection (unless the line is tan-
gent to the curve at either *P *or
*Q*, in which case we take *R *= *P *or *R *= *Q*, respectively). To form a group structure, we need to
define addition on these three points: *P *+ *Q *= -*R*. That is, we define *P *+ *Q *to be the mirror image (with respect to the *x *axis) of the third point of intersection. Figure 10.4 illustrates
this construction.

**2.
**The geometric interpretation of the preceding
item also applies to two points, *P *and
-*P*, with the same *x *coordinate. The points are joined by a vertical line, which can be viewed as also intersecting the curve at the infinity
point. We there-
fore have *P *+ (-*P*) = *O*, which is consistent
with item (2).

**3.
**To
double a point *Q*, draw the tangent line and find the other point of inter- section
*S*. Then *Q *+ *Q *= 2*Q *= -*S*.

With the preceding list of rules, it can be
shown that the set *E*(*a*, *b*)
is an abelian group.

*ALGEBRAIC
**DESCRIPTION OF *** ADDITION **In this subsection, we present some results that enable
calculation of additions over elliptic curves.5 For two distinct points,

After some algebraic manipulation, we can
express the sum *R *= *P *+ *Q *as

Elliptic Curves over Z*p*

**Elliptic curve
cryptography **makes use of elliptic curves
in which the variables and coefficients are all restricted to
elements of a finite field. Two families
of elliptic curves are used in cryptographic
applications: prime curves over Z*p *and
binary

curves over GF(2*m*). For a **prime curve **over
Z*p*, we use a cubic
equation in which
the

variables and coefficients all take on values in the set
of integers from 0 through

*p *- 1 and in which calculations are performed modulo
*p*. For a **binary curve **defined over GF(2*m*), the variables and coefficients all take on values in GF(2*m*) and in cal-
culations are performed over GF(2*m*). [FERN99] points
out that prime curves are best for software
applications, because the extended bit-fiddling operations needed by
binary curves are not required; and that binary curves are best for hardware
applications, where it takes remarkably few logic gates to create a powerful,
fast cryptosystem. We examine these two families
in this section and the next.

There is no obvious geometric interpretation
of elliptic curve arithmetic over
finite fields. The algebraic interpretation used for elliptic curve
arithmetic over real numbers does readily carry
over, and this is the approach we take.

For elliptic curves over Z*p*,
as with real numbers, we limit ourselves to equa- tions of the form of Equation
(10.1), but in this case with coefficients and variables
limited to Z*p*:

Now consider the set E*p*(*a*, *b*) consisting of all pairs of integers (*x*, *y*)
that sat- isfy Equation (10.5), together with a point at infinity *O*. The coefficients *a *and *b *and the variables
*x *and *y *are all elements of Z*p*.

For example,
let *p *= 23 and consider the
elliptic curve *y*2
= *x*3 + *x *+ 1.
In

this case, *a *= *b *= 1. Note that this equation is the same as that of Figure
10.4b. The figure shows a continuous curve with all of the real points that
satisfy the equation. For the set E23(1, 1), we are only interested in the nonnegative integers
in the quadrant from (0, 0) through (*p *- 1,
*p *- 1) that satisfy the equation mod

*p*. Table 10.1
lists the points (other than *O*) that
are part of E23(1, 1). Figure 10.5 plots the points
of E23(1, 1); note that the points,
with one exception, are symmetric about *y *= 11.5.

It can be shown that a finite abelian group
can be defined based on the set E*p*(*a*, *b*)
provided that (*x*3 + *ax *+ *b*) mod *p *has no repeated factors. This is
equiva- lent to the condition

Note that Equation
(10.6) has the same form as Equation
(10.2).

The rules for addition over E*p*(*a*, *b*), correspond to the algebraic
technique described for elliptic
curves defined over real numbers. For all points *P*, *Q *Î E*p*(*a*, *b*):

The last step in the preceding equation
involves taking the multiplicative inverse of 4 in Z23. This can be done
using the extended Euclidean algorithm defined in Section 4.4. To confirm, note
that (6 * 4) mod 23
= 24
mod 23 = 1.

*xR *= (62 - 3 - 3) mod 23 = 30 mod 23 = 7

*yR *= (6(3 - 7) - 10) mod 23 = (-34) mod 23 = 12

and 2*P *= (7, 12).

For
determining the security of various elliptic curve ciphers, it is of some
inter- est to know the number of points in a finite abelian group defined over
an elliptic curve. In the case of the finite group EP(a, b), the number of
points N is bounded by

Note that the number of points in *E**p*(*a*, *b*) is approximately equal to the number of elements in *Z**p*, namely
*p
*elements.

Elliptic Curves over GF(2*m*)

Recall from Chapter 4 that a **finite field **GF(2*m*) consists of 2*m *elements, together
with addition and multiplication operations that can be defined over
polynomials. For elliptic
curves over GF(2*m*), we use a cubic equation
in which the variables and coefficients all take on values in GF(2*m*) for some number *m *and
in which calcula- tions are performed using the rules of arithmetic in GF(2*m*).

It turns out that the form of cubic equation
appropriate for cryptographic appli- cations for elliptic curves is somewhat
different for GF(2*m*) than for *Z**p*. The form is

where it is understood that the variables *x *and *y *and the coefficients *a *and
*b *are elements of GF(2*m*) and that calculations are performed in GF(2*m*).

Now consider
the set
*E*2*m*(*a*, *b*) consisting
of all
pairs of integers (*x*, *y*) that satisfy Equation (10.7), together with a point at
infinity *O*.

For example, let us use the finite field
GF(24) with the
irreducible polynomial *f*(*x*)
= *x*4 + *x *+ 1. This yields a generator *g *that satisfies *f*(*g*)
= 0 with a value of *g*4 = *g *+ 1
, or in binary, *g *= 0010.
We can develop the powers of *g *as
follows.

Table 10.2 lists the points (other than *O*) that are part of E241*g*4,
12 . Figure 10.6 plots the points of E241*g*4,
12 .

It can be shown that a finite abelian group
can be defined based on the set E2*m*(*a*, *b*), provided that *b *!= 0. The rules for addition can be stated as follows.
For all points *P*, *Q *Î *E*2*m*(*a*, *b*):

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

Cryptography and Network Security Principles and Practice : Asymmetric Ciphers : Other Public-Key Cryptosystems : Elliptic Curve Arithmetic |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright © 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.