INTRODUCTION
In the modern informationoriented society, various devices are connected to the Internet as terminals, which necessitate technology for information security. Today, the world continues to witness an explosion of technology designed to help people communicate faster and more easily. We carry powerful digital computers in our pockets, exchange digital information in addition to voice data with our mobile phones and surf the Web with highend PDAs. In the near future, especially the coming of age of 3G wireless devices, every type of electronic data channel will be used to exchange every type of electronic information. One of the great challenges of the ability to communicate digitally is securing the increased amount of electronic information now exchanged over the network.
Over the last three decades the traditional cryptosystems like DES, DLP, RSA, DSA etc. have thus far been the answer to the wide range of issues that impact modern communication, including the assurance of privacy, the certainty of the transmitter or receiver’s identity and the integrity of the communication^{[1,2]}. Today, these traditional cryptoalgorithms which were once considered effective have become in impractical in light of recent technological development of constrained environment devices. These conventional cryptotech approaches cannot support the new generation of digital communication and information access devices with their low power, small form factor and high performance requirements. The emerging breed of laptops, handhelds, mobile phones, PDAs and wireless devices require a nextgeneration cryptosecurity technology.
However, it is important to note that traditional cryptographic algorithms like DLP^{[3]}, RSA^{[4]} etc. are not particularly efficient in small form factor, lowpower, resource constrained devices, as they require memory intensive power hungry big integer computation coprocessor to complete the calculations in a timely manner^{[1]}. Adding such a coprocessor significantly raises the cost of manufacture, rendering many devices impractical. The cost of producing a smartcard, for example, is increased by as much as 400% when an additional processor is required^{[5]}. For embedded systems or telecommunications applications characterized by extremely high volumes and a wide variety of devices, many of which have limited computing resources, the trend has been towards alternate cryptoalgorithms.
One technology in particular, called Elliptic Curve Cryptography (ECC), has become the cryptography of choice for mobile computing and communications devices due to its size and efficiency benefits. Elliptic curve cipher uses very small keys and is computationally very efficient, which makes it ideal for the smaller, less powerful devices being used today by majority of individuals to access network services. Its efficiency enables constrained, wireless devices to establish secure endtoend connections. Hence, the serverside cryptosecurity networks have to be enabled to perform ECC operations for the next generation of wireless devices that use variable parameters in an efficient way to reduce systems cost. In Koblitz^{[6]} and Miller^{[7]}, independently proposed the Elliptic Curve Cryptosystem (ECC)a cryptoalgorithm method of utilizing a Discrete Logarithm Problem (DLP) over the points on an elliptic curve. By their proposal, ECC could be used to provide both digital signatures and an encryption scheme. Over the past decade, ECC and later ECDLP (Elliptic Curve Discrete Logarithm Problem)^{[8,9]} has received considerable attention from mathematicians around the world and no significant breakthroughs have been made in determining weaknesses in the algorithm and todate has weathered umpteen mathematical attacks. Elliptic curve cryptosystems have thereby come to be accepted today as the most viable publickey technology for highsecurity applications. They are also most suitable for constrained environment devices such as those in which smartcards and personal wireless devices are typically deployed. Over the coming years, there will continue to be a great need for designing and implementing ECC enabled cryptosystems ranging from software, protocols and hardware solutions to secure cuttingedge technologies such as: smartcards, mobile phones, browsers, servers, Radio Frequency Identification (RFID) tags and environmental sensors.
The ECC provides higher strengthperbit than any other current publickey cryptosystems^{[10]}. If you compare elliptic curves to RSA and DLP you find many advantages: to obtain the same security one can use smaller fields for elliptic curves^{[11,12]}. Therefore, elliptic curves can be implemented easier and faster. Furthermore, because of its higher strengthperbit, ECCs are being increasingly used in practical applications in embedded systems (e.g., IC card and mobile devices) instead of RSA, which today is the most used publickey cryptosystems. The Elliptic Curve Cryptoschemes are also used for implementing protocols such as ECdigital signature scheme (ECDSA)^{[13]}, DiffieHellman key exchange scheme^{[14]}, EC ElGamal cryptoschemes^{[15]} and so on. Following in the footsteps of DES^{[16]}; ECC in conjunction with advance symmetric algorithm, AES^{[17]}, has already been incorporated into a number of key international standards, including ANSI X9.63, IEEE 13632000, IETF RFC 3278, ISO 159463 and NIST SP 80056^{[18]}. Further evidence of widespread acceptance are the inclusion of ECC in IPsec, TLS and OpenSSL^{[19,20]}. Adoption into global standards will assist in pushing ECC into wider commercial usage. This integration in to the standard cryptosecurity systems will greatly enhance the overall usage of the next generation of wireless devices like 3G, which are extremely powerful but must still conserve their power consumption to achieve a longer working battery cycle. This is another advantage for using ECC which uses very small keys and is computationally very efficient which makes it ideal for the smaller, less powerful devices being used today by majority of individuals to access network services. With the commercialgrade implementations of ECC, developers should also expect to see an overall speed increase introduced by computational optimizations.
Today RSA is the powerhouse cryptosecurity of choice for ecommerce transactions, but its key size must double by the end of this decade to provide the same level security. At this point RSA cryptotechnology become an extreme heavyweight for constrained environment devices (Fig. 1). Another factor going against the future of RSA is they are too slow compared to ECC, due to their dependence on computational involving two large prime integers, while the latter does not. The future of Internet security will also be greatly enhanced when they finally switch to elliptic curve based cryptoserver security. With ECC smaller keysize requirements and enhanced computational efficiency, IT connectivity providers will be able to utilize fewer cryptoserver security for providing secure network connections. Table 1 compares the equivalent security level for some commonly considered cryptographic key sizes.
As ECC becomes more important and more widely used, we foresee the following scenario. Commercial entities such as financial services or online stores running ebusiness will carry out transaction with users over the wireless conveniently and securely. The servers are required to perform cryptooperations such as signature generation and verification and key exchange. Most of these operations will employ standardized settings such as the NIST recommended elliptic curves^{[20]}. However, there may be users that generate curves themselves, or Certificate Authorities (CA) that issue certificates over nonstandardized curves that promise a performance gain. For example, they might want to use a curve defined over GF(2^{155}) as described by Schroeppel et al.^{[21]}, a curve over GF(2^{178}) as presented by Schroeppel et al.^{[22]}, or curves suited to special field element representations by De Win et al.^{[23]}. There may also be standards which are rarely used and thus do not justify the implementation of a special case and future standards may introduce new curves. Still, a server must be able to handle all requests efficiently to reduce computing time and hence efficiency and cost.
It should be stressed, however, that there are also potential drawbacks associated
with ECC from a practical perspective: RSA operations involving public keys
(i.e., signature verification or encryption) can be performed with very short
keys (Table 2). This leads to very fast operations which are
usually faster than the corresponding ECC operations. However, RSA operations
with private keys are usually much slower. In addition, the performance advantage
for public key will decrease in future as longer bit length will become more
common place for both RSA and ECC, (Fig. 1 and Table
1).
Table 1: 
Comparison of the equivalent security level for some commonly
used cryptographic key sizes 

Table 2: 
Comparisons of ECC vs. RSA vs. DH* 

*Timings were taken on BlackBerry 7230 at 128bit security
level. Timings at a 256bit security level would show even greater differences
between ECC, RSA and DH. **Time was too long to measure^{[22]} 

Fig. 1: 
Proposed the minimum key sizes (in bits) to be regarded as
safe for RSA and ECC 
In this study we analyze the elliptic curve operations of these ECC protocols
and design procedure of the Elliptic Curve Cryptographic defined over binary
finite field GF(2^{m}).
GENERAL ELLIPTIC CURVES
Elliptic curve cryptology uses mathematical ideas such as: groups, Abelian
groups, operations with groups, fields, operations with fields, elliptic curves
and elliptic curve arithmetic using fields and groups. Let k be a field,
its algebraic closure and K* its multiplicative group. An elliptic curve over
K will be defined as the set of solution in projective plane ^{2
} ()
of a homogeneous Weierstrass equation of the form:
With a_{1}, a_{2}, a_{3}, a_{4}, a_{6 ∈} K. This equation is referred to as long Weierstrass form. Such a curve should be nonsupersingular in the sense that, if the equation is written in the form F(X, Y, Z) = 0, then the partial derivatives of the curve equation ∂F/∂X, ∂F/∂Y and ∂F/∂Z should not vanish simultaneously at any point on the curve.
Let
be a field satisfying K ⊆
⊆ .
A point(X, Y, Z) on the curve is
rational if (X, Y, Z) = α
for some α ∈ ,
i.e. up to projective equivalence, the coordinates of the point are in
. The set of
rational points on E is denoted by ().
When the field of definition of the curve, K, is clear from the context, we
will refer to
rational points simply as rational points. The curve has exactly one rational
point with coordinate Z equal to zero, namely (0,1,0). This is the point at
infinity, which will be denoted by O.
For convenience, we will most often use the affine version of Weierstrass equation, given by:
Where, a_{i } ∈ K. The
rational points in the affine case are the solutions to E in
^{2 }and the point at infinity O. For curves over the reals, this point
can be thought of as lying infinitely far up the yaxis^{[8]}. We will
switch freely between the projective and affine presentations of the curve,
denoting the equation in both cases by E. For Z ≠ 0, a projective point (X,
Y, Z) satisfying Eq. 1 corresponds to the affine point (X/Z,Y/Z)
satisfying Eq. 2.
Finite field selections: Key in implementation of ECC is selection of
elliptic curve groups over the finite fields of the form GF(p) or
_{p }and GF(p^{m}) or
where, p is prime and m is a positive integer. By definition elliptic curve
groups are additive groups. Various finite field can be generated using values
of p, m and f(x), where ,
f_{i}∈ GF(p^{m}). Also using generic algorithm for different
kind of field faster efficiency rate can be achieved.
Field over GF(p) is also known as integer modulo p, even, or odd prime^{[8]}.
Using GF(p) will require a coprocessor to perform the modular operation. Hence,
obviously the performance with a GF(p) will be lower compared to that over binary
field GF(2^{m}). Furthermore, addition of a coprocessor in small form
factor devices like smartcard increases the cost by 20 to 40%. Hence, for practical
applications finite field of the form
are very important. For such elliptic curves the theory as developed by Rabah^{[8]}
has to be modified.
ELLIPTIC CURVE OVER CHARACTERISTIC 2 (BINARY FINITE FIELD), GF(2^{m})
We now specialize on finite field _{q
}where, q = 2^{m}, m ≥ 1. Elements of the finite field are binary of fixed length m. There are several ways to define arithmetic in
this field, but the most common are polynomial representation. Up till now,
no experiments have suggested a link between the field representation and the
complexity of the resulting elliptic curves. So the choice of representation
for the finite field does not appear to affect the security level of the elliptic
curves defined over it.
Under these assumptions, a representative for each isomorphism class elliptic
curves over _{q
} is given by:
Where, a_{1 }= 1,
and a_{2} ∈{0, γ} with γ a fixed element in _{q
} of trace (
γ) = 1 , where, Tr_{q2} is the linear trace from _{q
} to _{2}.
This function is not directly related to trace of Frobenius and no confusion
should arise since they are used in quite different context. In this case, the
expression for the jinvariant reduces to .
In characteristic two, the condition j(E) = 0, i.e., a_{1 }= 0, is equivalent
to the curve being supersingular, which is a very special type of curve and
is avoided in cryptography. We assume, therefore, that j(E) ≠ 0.
The finite field ,
called a binary field, can be viewed as a vector space of dimension
m over
That is, there exists a set of m elements {e_{0}, e_{1},…e_{m1}}
in such that each
can be written uniquely in the form
where,
i.e., a_{i }= 0 or 1. The set {e_{0}, e_{1}, …e_{m1}}
is called a basis of
over
We can then represent a as a binary vector a = (a_{0}, a_{1},…a_{m1}).
There are many different basis of .
The most natural basis are, of course, polynomial basis, normal basis and optimal
normal basis. In polynomial basis, we just have e_{i} = t^{i }
where, t is he fixed complex (or whatever) root of our reduction trinomial :
t^{m} + t^{k} + 1. (Note that it is possible to chose another
basis, called a normal basis, of the form:
where,
It is well known that such a basis always exists). The most natural basis are,
of course, polynomial basis, normal basis and optimal normal basis (Table
3).
Optimal extension finite field : Field of
uses p = 2 such that it gives implementer f(x) of form trinomial or polynomial.
An alternative representation of
is the Optimal Extension Fields (OEFs). OEFs is an alternative construction
to the
where, p = 2^{n ±} c, where c is arbitrary positive rational
number log_{2}c = n/2. Also p is prime less than but close to the word
size of the processor. In addition, m is chosen such that, f(x) = x^{m}w,
is an irreducible. The goal is to select parameters which provide adequate security
without incurring excessive computation time.
Lenstra and Verheul^{[24]} showed that under certain assumptions, 925bit RSA and DSA systems may be considered equivalent in security to a 132bit ECC system. The field GF((2^{8}17)^{17}), for example, a security level of 134bits which is far more secure than 512bit RSA system which has been popular for smartcard applications. Optimal Extension Fields (OEF) are computationally more efficient than other field types offering roughly the same level of security^{[25]}. Table 4 displays three fields of similar field order, which implies a similar security strength of the cryptosystem based on these fields^{[26]}. The third column denotes the number of cycles for one field multiplication which is the crucial operation determing the efficiency of the system. One can see that the OEF displayed in the third row performs more efficient than the binary field displayed in the first row.
Composite extension finite fields and subfields: When m is a composite number, m = rs, then the composite extension finite field GF(2^{m}) can be considered an extension field of degree s over finite field GF(2^{r}). The finite field GF(2^{r}) is called a subfield of GF(2^{m}). The elliptic curve over a subfield is also used in computing the order of an elliptic curve over a composite extension finite field using HasseWeil’s theorem^{[8]}. We can also represent elements in a composite extension finite field over its subfield using either one of the two basis discussed earlier.
We should point out that the finite field GF((2^{r})^{s}) is isomorphic to the finite field GF(2^{m}), but their field operations (additions and multiplications) are different depending on the irreducible field polynomials, f(x) of GF((2^{r})^{s}) over GF(2^{r}) and GF(2^{r}) over GF(2). It also depends on the possible factorizations of m (other than factors r and s). The choice of those field polynomials are essential to determine the algorithmic complexity of arithmetic operation of GF((2^{r})^{s}). However, a recent attack on ECCs over composite fields makes them inappropriate for use in practice^{[25]}.
Table 3: 
Comparisons of different finite fields for implementing ECC 

Table 4: 
ECC field performance 

ARITHMETIC OVER FINITE FIELD GF(2^{m}) USING POLYNOMIAL BASIS EPRESENTATION
A good understanding of the complexity of the mathematics in the field is necessary to appreciate the difficulty of solving equations of elliptic curves
defined over this field^{[8,9]}. The elements of the finite field are binary strings of fixed length m. As indicated above there are many ways
to construct a finite field with a prime power number elements, but the most
common are polynomial representation, normal and optimal normal representation.
The polynomial basis representation: Polynomial basis representation can be used to implement addition, multiplication, division and remainder or modulus operation. This being the case, implementation presented in this section, uses field polynomial representation because of its relatively easy arithmetic operations.
Let
where, each .
We call f(x) the reduction polynomial (or sometimes, field polynomial). The
polynomial f(x) must be irreducible; that is, it cannot be factored into two
polynomials over
, each of degree less than m. In polynomial basis form, the elements of
are treated as polynomials of degree m, with the individual bits representing
coefficients in
of each term. So elements are of the form:
These elements
can be written in binary strings or vector form as (a_{m1}…a_{1},a_{0})
of length m. has 2^{m} elements, i.e.,
Particularly, we can write the zero element 0 = (0, 0,…0) and the multiplicative
identity 1 = (0, 0, …0, 1).
Let denote the set of all nonzero elements in .
The field
is cyclic, which means: G = {g^{0}, g^{1}, …, g^{n}}where,
g^{n }= I, with n = 2^{m }1 and I is the identity element.
Here g ∈ G, where, g ≠ 0, is called a generator (or primitive) element.
By definition, this means that any group element can be expressed as a power
of g. The multiplicative inverse of an element: a = g^{i} is .
This method of representing is called a polynomial basis representation.
Since is a mathematical ’field’, it has the binary operations of addition and multiplication.
Table 5 shows bittobinarytopolynomial representation and
their decimal equivalence. Note that the presence of the coefficient is marked
by a digit 1 and the absence is marked by a digit zero, 0, e.g g = {a_{3}x^{3}+a_{2}x^{2}+1},
will be written as:(a_{3}a_{2}a_{1}a_{0}) =
(1101).
Irreducible polynomials: A polynomial f(x) is said to be irreducible
if we cannot write, f(x) = h(x).u(x), for any polynomials h(x), u(x) of degree
strictly less than the degree of f(x). An irreducible polynomial
of degree m over
should satisfy these necessary conditions:
• 
The constant term f_{0 }= 1; otherwise, we can factor
x out. Hence, from now on we always write the general form as: 
• 
There is an odd number (≥3) of nonzero terms; otherwise,
f(x) whose number of nonzero terms is even has a factor (x+1). 
• 
There must be at least one term of odd degree; otherwise,
f(x) of all even powers is a square of a polynomial of degree (m/2). 
• 
It is easy to verify this property: If
is an irreducible polynomial of degree m, then so are polynomials h(x) =
f(x+1) and 
• 
The compositions of h(x) and u(x) will give us a few more
irreducible polynomials. 
Table 5: 
Implement of binarytopolynomial basis representation 

Primitive polynomials: If the period of f(x) is (2^{m}1), that
is the order of the multiplicative subgroup ,
then f(x) is called a primitive polynomial. For example, if
is an irreducible polynomial of degree m over
and r is a root of f(x) in an extension field of
(that is a finite field ),
then
are all roots of f(x). Indeed, if f(r) = 0, then for any d, we have
since f_{i} equals to 0 or 1. Hence:
Note that all the roots of the polynomial f(x) have the same multiplicative
order, that is called the period (or order) of the function f(x).
All roots of a primitive polynomial f(x) are primitive elements of . For example, the polynomial u(x) = x^{m }+…+ x + 1 divides (x^{m+1}+1).
Hence, its period is equal to (m+1) or less and u(x) is not a primitive polynomial
of , unless m = 2.
A primitive polynomial can be built from a primitive element a of a finite
field by the formula:
If another primitive polynomial
is built from a primitive element b, such that
then h(x) ≠ f(x).
In other words, each primitive element is a root of only one primitive polynomial
of .
In fact, the set of roots of all primitive polynomials for a finite field are
exactly all primitive elements in .
Hence, there can be many primitive polynomials for a finite field , when m≥3. And in fact, a primitive polynomial cannot be reducible over
.
Rules for selecting a reduction polynomial
• 
A trinomial over
is a polynomial of the form: T_{m,k}(x) = x^{m}+x^{k}+1,
where 1 ≤ k ≤ m1. In fact, a trinomial: T_{m,k}(x) = x^{m}+x^{k}+1
is irreducible if and only if its reciprocal trinomial T_{m,mk}(x)
= x^{m}+x^{mk}+1 is irreducible. Hence, we should be interested
in trinomials of the following form only: T_{m,k}(x) = x^{m}+x^{k}+1,
where, 1 ≤ k ≤ m/2. 
• 
A pentanomial over
is a polynomial of the form:
where 1 ≤ k_{1 }< k_{2 }< k_{3 ≤} m1.
Such polynomials always exists for m ≥ 4. In practice, it is recommended
to use pentanomials whose coefficient triples (k_{1}, k_{2},
k_{3}) or (k_{3}, k_{2}, k_{1}) will have
the first coefficient as small as possible and next coefficients are kept
as small as possible after fixing the previous one or ones in the triple
order. These polynomials would have more efficient computations of finite
field operations. 
ANSI X9.62 specifies the following rules for selecting the reduction polynomial
for representing the elements of ^{
[13]}:
• 
If there exists an irreducible trinomial of degree m over
, then the reduction polynomial f(x) must be an irreducible trinomial of
degree m over
. To maximize the chances for interoperability, ANSI X9.62 recommends that
the trinomial used should be, x^{m}+x^{k}+1, for the smallest
possible k. 
• 
If there does not exist an irreducible trinomial of degree
m over
, then the reduction polynomial f(x) must be an irreducible pentanomial
of degree m over .
To maximize the chances for interoperability, ANSI X9.62 recommends that
the pentanomial used should be:
, chosen according to the following criteria: (i) k_{3} is as small
as possible; (ii) for this particular value of k_{3} and k_{2}
is a small as possible and (iii) for these particular values of k_{3},
k_{2} and k_{1 }is as small as possible. 
Field addition and multiplication over binary finite field GF(2^{m}): Field elements are added and multiplied as follows:
Field addition (+): Is performed componentwise by XORing (XOR symbol:
⊕, but here for simplicity we will use + instead). Addition in
is
where each c=a_{i}+b_{i} over
. That is, addition is just the componentwise XOR. In the field
, each element (a_{m1}…a_{1}a_{0}) is its own additive
inverse, since (a_{m1}…a_{1}a_{0})+ (a_{m1}…a_{1}a_{0})=(0…00),
the additive identity. Thus, addition and subtraction are equivalent operations
in . Since
for all binary elements, then g+g = 0 = gg. So we note that addition and subtraction
are equivalent in this field, Fig. 2a on how to perform XOR
operation. In hardware, a bitparallel adder requires mtuples as in a = (a_{m1},
a_{m2},…a_{0}). In hardware, a bitparallel adder requires
m XOR gates and addition can be generally computed in one clock cycles.
Field multiplication (•): Multiplication of field elements in uses the same shiftandadd algorithm as is used for multiplication of integers,
except that the “add” is replaced with “XOR”. This has the
virtue that the operation can no longer generate carriers, simplifying the implementation.
That is,
where, the polynomial
is the remainder when the product polynomial
is divided by the polynomial f(x) over
, where, the operation (•) is carried out Fig. 2b. (Note
that all polynomial coefficients are reduced modulo 2.)
Field exponentiation: The exponentiation (a_{m1}…a_{1}a_{0})^{e} is performed by multiplying together e copies of (a_{m1}…a_{1}a_{0}).
Multiplicative inversion: The rules for doubling an elliptic curve point
and for adding two elliptic curve points, involve computing reciprocal, either
1/x or 1/(x_{1}+x_{2}). Multiplicative inversion of elements
in a field is usually so slow that people have gone to great lengths to avoid
it. Menezes et al.^{[5]} and Beth and Schaefer^{[27]}
discuss projective schemes, which use about nine multiplications per elliptic
curve step , but use very few reciprocals. An efficient algorithm for computing
an inverse of an element in
was proposed by Itoh et al.^{[28]}.

Fig. 2: 
(a) Addition rule and (b) Multiplication rule under finite
field, 
Rule to perform multiplicative inverse: We need to discuss also some methods of computing the inverse of a nonzero element. This operation obviously has an important role in field arithmetic, these are:
• 
The general method is using this identity:
Recall that:
In implementations, we can even analyze further the power exponent (2^{m1}1)
of a to reduce our computation to a few multiplications. For m even or odd,
we have: 
Odd: 2^{m1} 1 = (2^{(m1)/2}1)×(2^{(m1)/2
}+ 1) and Even:
2^{m1} 1 = 2×(2^{(m2)/2 } 1)×(2^{(m2)/2
}+ 1) 
These formulae yield an algorithm for computing inverse by factorization of
the exponent. Consider the field, GF(2^{155}):
It requires 10 multiplications to compute an inverse in GF(2^{155}).
In general, the method requires:
field multiplications.
• 
Alternatively, using the extended Euclidean algorithm: finding
polynomials u(x) and v(x) such that ged(f(x), a(x)) = f(x)×u(x)+a(x)×v(x).
When ged(f(x), a(x)) = 1, we can write 1 º a(x)×v(x)(mod f(x)).
In other words, the polynomial v(x) is the inverse of a(x), modulo f(x). 
Squaring: In particular, the squaring operation of a polynomial
that is performed in modulo 2 is in fact a linear operation, i.e.,:
In terms of bit strings, we write: (a_{m1}…a_{1}a_{0})
= (a_{2(m1)}, 0, a_{2(m2)}, 0 ,…0, a_{1}, 0, a_{0}).
Then we reduce the resulting polynomial by modulo f(x). In hardware, a bitparallel
realization of this squarer requires at most (r1)(m1) gates^{[29,30]},
where, r represents the number of nonzero coefficients of the polynomial when
implemented using Elliptic Curve Processor (ECP) architecture (Fig.
3 and 4) field arithmetic module. The components are the
Main Controller (MC), the Arithmetic Unit Controller (AUC) and Arithmetic Unit
(AU). The MC is the ECP’s main controller which performs the computation of
the scalar multiplication, kP.
The AUC controls the AU and performs the computation of point additions, point doublings and coordinate conversions. The AU also performs GF(2^{m}) field additions, squares, multiplications and inverses under AUC control^{[31]}.
Orlando and Paar^{[31]} proposed a design for the standard basis field representation and it is based on the transformation from squaring operation into an addition and a multiplication by a constant that depends only on the field polynomial. For example, squaring a polynomial in a modulo 2 field is a linear operations. In the formula for squaring a binomial, (a+b)^{2 }=a^{2}+2ab+b^{2}, the crossterm vanishes modulo 2 and the square reduces to a^{2}+b^{2}. Consequently, we can square a sum by squaring the individual terms. For example, (u^{3}+u+1)^{2 }= u^{6}+u^{2}+1.
In terms of bitstrings, to square a polynomial, we spread it out by interleaving a 0 bit between each polynomial bit. For example, x^{3}+x+1 is represented as 1011 and the square (x^{3})^{2}+x^{2}+1^{2 }= x^{6}+x^{2}+1 is represented by 1000101 (Table 5). Sadly, computer manufacturers have largely ignored the need for an instruction to carry out this operation; nonetheless, it can be done quickly using table lookup to convert each byte to its 15bit square. The squared polynomial is then reduced modulo f(x). Squaring is so much faster than regular multiplication that it can be ignored in rough comparisons of the timings.
THE ELLIPTIC CURVE OVER FINITE FIELD GF(2^{m})
Elements of the field are mbit string. The rules in can be defined by either polynomial representation and by normal or optimal
normal basis representation as started earlier. Let be a characteristic 2 finite field and let satisfy b≠0 in . Then an elliptic curve over defined by the parameters consists of the set of solutions or points P = (x, y) for to the equation:

Fig. 3: 
Elliptic Curve Processor (ECP) architecture 

Fig. 4: 
Elliptic curve Arithmetic Unit (AU) 
together with an extra point O called the point at infinity. (Here the only
elliptic curves over of interest are nonsupersingular elliptic curves^{[27]}.) Since operates on the bit strings, computers can perform arithmetic in this field
very efficiently. The number of points on is denoted by .
Counting points on elliptic curves: A user of ECC will be interested
to know the structure of the group, especially he would like to know the number
of the points,
. If he knows he knows whether the PohligHellmanattack can be applied. It
is
impossible to write down all the points for large q. But it is not necessary
at all. The formula of HesseWeil can be applied, which reduces the amount of
work enormously, which states that if E is an elliptic curve over ^{[8,32]}, then, then:
such that
is called the trace of the curve.
Note that E ()
(where, q = 2^{m}) is called the group of rational points i.e., points
that are rational over the ground field . Not to be confused with E(Q)! the knowledge of the rational points on the
curve is essential to cryptosystems because we often desire curves E with a
large prime dividing
. So we can either construct curves with the right properties (like
) containing a large prime) or generate curves randomly and check if they have
the desired properties. Hence, efficient computation of is an important question.
Both approaches are useful depending on the application. For example EC factoring
algorithms search for curves where the number to be factored, decomposes smoothly.
The order n of a point P ≠ O on an elliptic curve is a positive integer
such that nP = O and mP≠O for any integer m such that 1 ≤ m < n. The
order n of a point must divide the order N of the elliptic curve. In fact, it
is true for any group. If the elliptic curve order N =
is a prime number, then the group is cyclic and obviously all points except
the point at infinity O are of order N.
Elliptic curve arithmetic over finite field : It is again as is the case with elliptic curve over ^{
[8]}, there is a chordandtangent rule for adding point on an elliptic
curve E()to
give a third elliptic point. Together with this addition operation, the set
of points on E()
forms a group with O serving as its identity.
The algebraic formula for the addition of points and the double of a point are specified as follows:
• 
Rule to add the point at infinity to itself: O+O=O 
• 
Rule to add the point at infinity to any other point: 
• 
Rule to add two points with the same xcoordinates when the
points are either distinct or have xcoordinate 0: (x, y)+(x, x+y)=O for
all (x, y) ∈ E()
. That is, the negative of the point (x, y) is (x, y) = (x, x+y) 
• 
Rule to add a point to itself (double a point): Let
and
be two points such that x_{1 ≠} 0. Then P_{1}+P_{2
}= (x_{1}, y_{1})+(x_{2}, y_{2}) =
(x_{3}, y_{3}) = P_{3 ≠} O, where: 
and
• 
Rule to add two points with different xcoordinates: Again
let
and
be two points such that x_{1≠}x_{2}. Then: P_{1}+P_{2
}= (x_{3}, y_{3}) = P_{3 ≠} O, where: 
and
In either case, when P_{1}+P_{2} (doubling) and P_{1 ≠}
P_{2} (point addition), major operations are field multiplication and
field inversion. (Squaring and field addition are enough ignorable because of
its less computation time.) From these formulas of point addition or doubling,
we can determine the number of field operations required for each kind of elliptic
curve operation. We see that an addition step usually requires eight additions,
two multiplications, one squaring, three reductions mod f(x) and one inversion.
A Doubling step usually requires four additions, two multiplications, two squaring,
four reductions mod f(x) and one inversion. A Negation step requires one addition.
The important contributors to the run time are the multiplications and inversions^{[28,33]}.
Just as modular exponentiation determines the efficiency of RSA cryptographic
systems^{[1,4]}, scalar multiplication dominates the execution time
of ECC systems. In all the protocols that are fundamental implementation of
ECC, say ECDH, ECDSA, ECAES etc. the most time consuming part of the computations
are scalar multiplications^{[33]}. Elliptic curves have some properties
that allow optimization of scalar multiplications. Thus, far the efficiency
of the finite field arithmetic, especially multiplication, determines the overall
efficiency of the elliptic curve cryptosystem.
THE FINITE FIELD GF(2^{4}) USING POLYNOMIAL BASIS REPRESENTATION
Let us consider the elliptic curve defined over
which from Eq. 6, we have a = g^{4} and b = g^{0
}= 1 is given by:
Table 6: 
16 elements of
obtained using the primitive irreducible Polynomial: f(x) = x^{4}+x+1 

Table 7: 
Powers of g using the element g = (0010) as the generator,
including the elements of
using trinomial basis: {1, g, g ^{2}, g ^{3}} 

Note that b ≠ 0, so E is indeed an elliptic curve.
is constructed using the primitive irreducible polynomial f(x) = x^{4}+x+1
and a root g. The set of points on E()
forms an abelian group under this addition rule. Notice that the addition rule
can always be computed efficiently using simple field arithmetic. The element
g = x = (0010) (i.e., g = x(mod f(x)), is a root of f(x) in
) is a generator of
since the number of elements
and it is cyclic, the powers of g obtained are (Table 6).
Note that all the 15 nontrivial powers of g are primitive elements of the
multiplicative subgroup
. The following are sample calculations to demonstrate the property of :
Addition: (0110)+(0101) = (0011).
Multiplication:
(1101)×(1001) = (x^{3}+x^{2} +1)×(x^{3}+1)
mod f(x)
= x^{6}+x^{5} +2x^{3} +x^{2} +1 mod f(x)
= x^{6}+x^{5} +x^{2} +1 mod f(x)
(coefficients are reduced modulo 2)
=(x^{4}+x+1)×(x^{2}+x)+(x^{3}+x^{2}+x+1)
mod f(x)
= x^{3}+x^{2} +x+1 = (1111)
Exponentiation: To compute (0010)^{5}, first find (0010)^{2}: ⇒ (0010)(0010)⇒ xx(mod f(x)) ⇒ (x^{4}+x+1)(0)+(x^{2}) modf(x) ⇒ x^{2} ⇒ (0100)
Then: (0010)^{4⇒} (0010)^{2}(0010)^{2} ⇒ (0100)(0100) ⇒ x^{2}x^{2} mod f(x) ⇒ (x^{4}+x+1)(1)+(x+1) mod f(x) ⇒ (x+1) ⇒ (0011) ⇒ (x+1) ⇒ (0011)
Finally: (0010)^{5} ⇒ (0010)^{4×}(0010)⇒ (0011)×(0010) ⇒ (x+1), (x^{2}+x) mod f(x) ⇒ (x^{4}+x+1)(0) + (x^{2}+x) mod f(x) ⇒ x^{2}+x ⇒ (0110)
Multiplicative inversion: Rule to perform multiplicative inverse: There
exists at least one element g in such that all nonzero elements in can be expressed as a power of g. Such an element g is called a generator of . The multiplicative inverse of an element a = g^{i} is .
The element g = (0010) is a generator for the field. The powers of g are listed
in Table 7. The multiplicative identity for the field is g^{0
}= (0001). The multiplicative inverse of g^{7 }= (1011) is g^{7mod15}
= g^{8mod15 }= (0101). To verify this, we see that:
Which is the multiplicative identity.
Table 7 shows the use of generator notation (g^{e}) rather than bit notation, as used in the examples above. Also, using generator notation allows multiplication without reference to the irreducible polynomial f(x) = x^{4}+x+1. In a true cryptographic application, the parameter m must be large enough to preclude the efficient generation of such a table otherwise the cryptosystem can be broken. In today’s practice, m = 163 is a minimum suitable choice.
TRACE OF A FINITE FIELD ELEMENT
Trace of an element a is a linear mapping
defined by:
Basic properties: Tr(a^{p}) = Tr(a) and Tr(a+b) = Tr(a)+Tr(b)
and more generally:
Tr(v×a) = v×Tr(a) for
When p = 2, Tr(0) = 0 and Tr(1) = 1 if m is odd and Tr(1) = 0 if m is even.
These properties can be checked easily from definition and the equality formula
for finite fields of characteristic p: (a+b)^{p} = a^{p}+b^{p}
for all
, with following properties:
• 
For an element
, Tr(a) equals 0 for one half of the elements in and equals 1 for the other half. When p > 2, there are p^{m1}
elements of trace 0 in .
In fact, there is also equal distribution of values of trace function Tr(•)
in the finite field . 
• 
For an element
, its trace Tr(a) = 0 if the polynomial (x^{2}+x+a) is reducible
over or, in other words, has two roots over . Conversely, Tr(a) = 1 if the polynomial (x^{2}+x+a) is irreducible
over or it has no root over . 
Properties on order of an elliptic curve: The following are the Properties on Order of an Elliptic Curve:
• 
Let E be a nonsupersingular elliptic curve, E: y^{2}+xy
= x^{3}+ax^{2}+b, over the finite field . Then the order of the elliptic curve E is #E = 2Tr(a) mod 4^{[34]}. 
• 
Let E be a nonsupersingular elliptic curve: E: y^{2}+xy
= x^{3}+ax^{2}+b, over the finite field . Then for any point P of order other than 2 on E, the point Q = 2p = (x_{Q},
y_{Q}) will satisfy the condition: Tr(x_{Q}) = Tr(a). This
property later gives a way to represent a point of an elliptic curve over
a finite field using only m bits^{[35]}. 
• 
The elliptic curve: E: y^{2 }= x^{3}+x^{2},
over a prime finite field
has its order satisfying the modular condition:
. 
Example:
Then Tr(g^{i}) = 1, when i = 3, 6, 7, 9, 11, 12, 13 and 14; and Tr(g^{i})
= 0, if otherwise; implemented using trinomial basis notation.
We can verify that two selfdual basis for the finite field
are: {g^{3}, g^{7}, g^{12}, g^{13}} and {g^{6},
g^{9}, g^{11}, g^{14}}. For example: Tr(g^{7x2})
= 1, Tr(g^{7}g^{3}) = Tr(g^{10}) = 0 They are not normal
basis. The above trinomial basis is not a dual basis since we have Tr(1) = 0.
Now define
Then the permutation {1, g, g^{2}, g^{3}} is its dual basis
with respect to the linear function h(•).
In fact, there are seven other elements of
using trinomial basis: {1, g, g^{2}, g^{3}} multiplicative subgroup
. They are: g^{2}, g^{4}, g^{7}, g^{11}, g^{13}
and g^{14}. The polynomial f(x) = x^{4}+x+1 is primitive and
its roots are: g, g^{2}, g^{4} and g^{8}. The only other
primitive polynomial for the finite field is:
Here’s an example using
with generator notation to show that the point (g^{3},g^{8})
satisfy Eq. 10 over , i.e.
Other than the simple integer multiplication of exponents, XOR is the only other operation required. All the fifteen points which satisfy Eq. 10 are as follows:

Fig. 5: 
Elliptic curve E: y^{2}+xy = x^{3}+g^{4}x^{2}+1
defined over 
Figure 5 shows the graphical representation of all the points
which satisfy Eq. 11. For a given point P = (x_{p},
y_{p}), x_{p} and y_{p} are called the x and y coordinates
of P, respectively. We now discuss efficient algorithms to expedite implementation
procedures in elliptic curve cryptosystems over binary finite field,
.
ALGORITHM FOR ELLIPTIC CURVE SCALAR MULTIPLICATION OVER BINARY FINITE FIELD
Cryptographic schemes based on ECC rely on scalar multiplication of elliptic
curve points as demonstrated above. As before given an integer k and a point
, scalar multiplication is the process of adding P to itself k times. The result
of this scalar multiplication is denoted by Q = kP = P+P+…+P (ksummands). Here
P is a fixed point that generates a large subgroup of ().
Let P = (g^{12}, g^{12}) be the generator of E()
, which we use for scalar multiplication to determine all the points using Eq.
8 and 9 as follows:
Let P = (x_{1}, y_{1}) = (g^{12}, g^{12}). Then 2P = P+P = (x_{3}, y_{3}) is computed as follows:
and
Hence, 2P = (g^{5}, g^{11}).
Let
and
. Then
is computed as follows:
and
Hence, P+Q º P+2P = 3P = (g^{6}, g^{8}). Using the above
two operations, we can double point P to obtain 2P. We can then add P to 2P
to obtain 3P and continue in this manner until we eventually reach nP = O, the
identity point. Since O+P = P, there are n distinct multiples of P. Below we
demonstrate this procedure:
Next by again taking P = (g^{12}, g^{12}) and 3P = (g^{6}, g^{8}) we can calculate for 4P = P+3P = (x_{4}, y_{4}) as follows:
and
Hence, P+3P = 4P = (1, g^{6}). Continuing with the similar computational
procedure, we can obtain all the points in E() , expressed as multiples of P (Table
8).
We note that since point coordinates are elements of , all arithmetic in the equations above follows the complex rules of
. So the multiplication is done modulo the irreducible polynomial f(x) and the
division operation (’/’) in the calculation for λ is actually a field inversion
operation. Thus, computing curve points is quite timeconsuming for machines
to perform and makes it infeasible for a hacker to use a bruteforce attack
by calculating all multiples of P which is equivalent to solving discrete logarithm
in elliptic curve arithmetic, i.e. elliptic curve discrete logarithm problem,
ECDLP^{[8]}.
Table 8: 
Scalar multiplication of elliptic curve points of E()
using generator P = (g^{12}, g^{12}) 

NORMAL AND OPTIMAL NORMAL BASIS REPRESENTATION PRIMITIVE NORMAL BASIS
A normal basis
of the finite field GF(q^{m}) over a finite field where q is any prime power, is called a primitive normal basis if β is
a primitive root of the multiplicative subgroup GF(q^{m})^{*}.
According to the theorem by Lenstra and Schoof^{[36]} for every prime
power q > 1 and every positive integer m, there exists a primitive normal
basis of finite field GF(q^{m}) over .
Normal basis representation: Normal basis are not special only for finite
fields of characteristic 2. More generally, the field
can be viewed as a vector space of dimension m over . That is, there exists a set of m elements g_{0}, g_{1},..,
g_{m1 }in such that each
can be written uniquely in the form:
where,
We can then represent g as the 01 vector (a_{0}a_{1}…a_{m1}). Addition of the field elements is performed by bitwise XORring the vector representation
In fact, they are defined for any finite field
where, q is a prime power. A normal basis of over
is a basis of the form:
, where,
. Such a basis always exists. Then g = (a_{0}, a_{1},…, a_{m1})
will represent the element:
By convention, the ordering of bits in normal basis representation is different
from that in polynomial basis representation. Particularly, we can write the
zero element 0= (0,0,…,0) and multiplicative identity 1 = (1,1,…,1).
Addition of field elements in normal basis is performed by bitwise XORing the vector representations. However, the most important property of a normal basis is that the square of a field element can be computed easily and implemented efficiently on hardware by just a right 1cyclic shift on the register. Indeed, given an element g = (a_{0},a_{1},…,a_{m1}) represented in a normal basis, we have:
With indices reduced modulo m. Then for any integer s, 1 ≤ s ≤ m1, the
2^{s}th power of element g can be computed quickly by a right scyclic
shift. That is
. We can verify again the relationship: .
Similarly, the square root of g can be computed simply by left 1cyclic shift:
g_{1/2 }= (a_{1}, a_{2}, …,a_{m1}, a_{0}).
This is useful for recovering points when using the point compression technique
for embedding messages for encryption. Hence, a normal basis representation
over is advantageous because squaring a field element can then be accomplished
by a simple rotation of the vector representation, an operation that is easily
implemented in hardware.
Multiplication in a normal basis: Take, for example, the product C=AB is given by:
Since
is also an element in , it can be expressed as:
Where, .
This yields a formulae
for
We also notice that:
Which implies that:
Thus, we have a formula for C_{r} as:
This formula has remarkable properties. Consider a circuit built for computing
C_{0}, which receives the inputs as (in this order):
Uses the formulae to compute:
The same circuit can be used to compute C_{1}:
Unfortunately, as can be seen above multiplication in a normal basis is somehow
complicated. Fortunately, multiplication can be easily implemented in hardware
when the normal basis used is of a special type called an optimal normal basis^{[37]},
which appear to give the most efficient implementation of field arithmetic (with
respect to speed and complexity of hardware architecture).
Current implementation of elliptic curves: The algebraic representation
of elliptic curves in is far more efficient than the geometric representation when computing group
operations. However, even the simplified algebraic representation of is more than a simple computer can handle in reasonable time. It is possible
to represent an elliptic curve in so that multiplication can be performed by a few simple linear equations and
exponentiation by a left bit rotation. This representation is based on a linear
algebraic representation and is called the optimal normal basis representation
 a less insightful way to construct the field , but is computational nicer
and easy handling by computers.
Optimal normal basis representation: For many values of m, the finite
field has an optimal basis representation as well as the polynomial representation
described above. An optimal basis gives an alternative way of defining multiplication
on the elements of a field. While optimal normal basis multiplication is less
insightful than polynomial multiplication, it is in practice much more efficient.
Further information on using an optimal basis representation also given by Ron
et al.^{[38]}.
Construction of optimal normal basis representation: Optimal normal
basis representation (ONB) can be used for a large number of values of m in
. This representation views field elements as linear combinations of the basis
matrix for the field. The value of m determines whether a Type I or Type II
representation will be used. The determination of the optimal normal basis is
as follows:
If has only a Type I representation, then define f(x) = x^{m}+x^{m1}+x^{m2}+…+x^{2}+x+1.
Otherwise, define f(x) by the recursive formula (Type II):
Note that f will be reduced in every iteration and will have coefficients in
. The set of polynomials
form a basis of over
, called a normal basis. Form A, a mxm matrix, where each row i is the bit string
of length m corresponding to,
. Find Aˉ^{1}.
Next construct
, a m x m matrix, where each row i is the bit string of length m corresponding
to,
. Compute T =
.Tˉ^{1 }. Determine the product terms, L_{ij} = T(ji,1),
for: i, j = 0, 1,…,m1. These product terms specify the set of equations by
which to perform all operations in
.
The generation of the optimal normal basis will be clearer with an example.
(Field addition is done as is the case with polynomial basis.) However, for
field multiplication let’s consider again our field
, which has a Type I ONB so that: f(x)=x^{4}+x^{3}+x^{2}+x+1.
Thus, {x, x^{2}, x^{4}, x^{8}} forms a basis for
over .
Construct A as:
Construct T as:
Row 0: 
v = x×x mod f(x) = x^{2} = (0100) 
Row 1: 
v = x×x^{2} mod f(x) = x^{3} = (0100) 
Row 2: 
v = x×x^{4} mod f(x) = x^{5} mod f(x) = 1 = (0001) 
Row 3: 
v = x×x^{8} mod f(x) = x^{9} mod f(x) = x^{3}+x^{2}+x
= (1111) 
Finally, the L_{ij} terms which are 1 are: L_{0,2}, L_{1,2}, L_{1,3}, L_{2,0}, L_{2,1}, L_{3,1 } and L_{3,3},
How do we use L to define operations in
? Recall that {x, x^{2}, x^{4}, x^{8}}spans and L is a optimal normal basis for . We will write a general formula for multiplication
in
:
Let A×B = C = (a_{0}a_{1}a_{2}a_{3})×(b_{0}b_{1}b_{2}b_{3})
= (c_{0}c_{1}c_{2}c_{3}), all in . Write (a_{0}a_{1}a_{2}a_{3})
and (b_{0}b_{1}b_{2}b_{3}) in terms of the basis
{x, x^{2}, x^{4}, x^{8}}, i.e.,
Where, each squaring results in a cyclic shifts.
The elements of C are the inner products of the corresponding rows and columns
of A and B:
With these definitions of addition and multiplication, the 16 binary 4tuples
form a field, although this fact is not obvious.
Note:
• 
The multiplicative identity is (1111) (cf. polynomial basis
which was (0001)) 
• 
Notice that: (a_{0}a_{1}a_{2}a_{3})×(a_{0}a_{1}a_{2}a_{3})
= (a_{0}a_{1}a_{2}a_{3})^{2} = (a_{3}a_{0}a_{1}a_{2})
and so the square of a field element is simply a right cyclic shift of its
vector representation. 
• 
The formula for c_{1} in the multiplication can be
obtained by adding a 1 to each subscript in the formula for c_{0}
(where the subscripts are reduced modulo 4). The formula for c_{2}
can be obtained by adding 2 to each subscript in the formula for c_{0}
and reducing the formula modulo 4. The formula for c_{3} can likewise
be obtained. 
• 
From the preceding remark we see that a circuit to compute
c_{0} from (a_{0}a_{1}a_{2}a_{3})
and (b_{0}b_{1}b_{2}b_{3}) can be used to
compute c_{1} by applying (a_{0}a_{1}a_{2}a_{3})
and (b_{0}b_{1}b_{2}b_{3}) to it. Similarly,
c_{2} and c_{3} can be computed by shifting to the left
input vectors. 
Thus: (a_{0}a_{1}a_{2}a_{3})×(b_{0}b_{1}b_{2}b_{3}) = (c_{0}c_{1}c_{2}c_{3}), is implemented as follows:
and
Also,
and
Once the multiplication algorithms are computed, they need not be recomputed
ever again. The optimal normal basis greatly simplifies multiplication in , but there is an even greater benefit. The square of any field element is computed
to the left cyclic shift of that element, a trivial operation!
Additionally, since an element has a cycle of length m, we have the following
consequence as by example:
(0010)^{161}= (0010)^{161(mod 4) .}
(0010)^{1} = (0010) 
Exponentiation can be simplified and reduced! Consider the finite field
using a normal basis. The reduction polynomial is f(x) = x^{4}+x+1,
which you may recall is a primitive polynomial. The optimal normal basis of
Type II consists of four polynomials: x, x^{2}, x^{4} and x^{8}(mod
f(x)). A generator for nonzero elements of multiplicative subgroup
is chosen to be g = x(mod f(x))
In this representation can be generated by the powers of g = (1100). We can write them explicitly in the Table 9, where:
(a_{0}, a_{1}, a_{2}, a_{3})
= a_{0}x+a_{1}x^{2}+a_{2}x^{4}+a_{3}x^{8}(mod
f(x)) 
For instance, 1 = (1111) = x + x^{2 }+ x^{4 }+ x^{8}.
(All polynomials of modulo f(x) and reduced modulo 2.) We can compute the following
intermediate terms and the next repeated squares of each term (by simple right
shifts). For example:
x^{5 }= x^{2 }+ x = x + x^{4 }= (1010) and x^{10}(0101)
x^{9 }= x^{3 }+ 2×x^{2 }+ x = x^{3 }+ x
= x = (1000)
x^{12 }= x^{3 }+ 3×x^{2 }+ 3.x + 1 = x^{3 }+
x^{2 }+ x + 1 = x^{8 }= (0001)
Arithmetic in the finite field can be performed efficiently both in hardware
and in software when the field elements are represented with respect to an optimal
normal basis.
Table 9: 
Powers of g using the element g=(1100) as the generator. This
method of representation is called optimal normal basis representation,
of Type II (g, g^{2}, g^{4}, g^{8}) 

Table 10: 
Scalar multiplication of elliptic curve points of
using generator P = (g^{3}, g^{5}) 

Since we have demonstrated an example of elliptic curve over
using polynomial basis representation, here we will now give an illustration
using optimal normal basis representation. Consider the field where the elements
are the set of all binary 4tuples with multiplication given by the formulae.
Recall that g = (1100) is a generator for the nonzero elements and (1111) is
the multiplicative identify.
Consider the nonsupersingular curves over
defined by the equation:
E: y^{2}+xy = x^{3}+g^{3} 
(Note that to be absolutely precise with our notation, we should write this
equation as:
(1111)y^{2}+(1111)xy = (1111)x^{3}+(0100) 
Since (1111) is the multiplicative identity, we simplify our notation as above).
The solutions over to the elliptic curve equation are:
Since there are 19 solutions to the equation in
, the group
has 19+1=20 elements, i.e. the group order
. This group turns out to be a cyclic group of order 20. If we take P=(g^{3},
g^{5}) and use the addition formulae, we find group points as listed
in (Table 10).
Implementing an elliptic curve in with an optimal normal basis greatly speeds computation and lowers storage requirements.
In addition to its speed, the elliptic curve resists breaking by current number
field sieve methods and the index calculus method used by many such techniques
has not been formulated for the elliptic curve. It is very likely that elliptic
curve cryptography will dominate cryptosystems in the near future. Recall that
in a true cryptographic application, the parameter m must be large enough to
preclude the efficient generation of such a table otherwise the cryptosystem
can be broken. In today’s practice, m = 163 is considered acceptable.
DESIGN AND IMPLEMENTATION OF CRYPTOSECURE COMMUNICATION PROTOCOL
Design and implementation of the right cryptoalgorithm, in general, will provide the fundamental security, however, improper management of the algorithms can lead to insecure applications^{[1,39]}. The prevention of such mishaps often lies in welldefined cryptoprotocols. Perhaps the most famous in public key cryptography is the DiffieHellman (DH) key exchange protocol. This protocol introduced the public key concept to the world in 1976^{[40]} and has remained a very popular protocol for strong authentication of entities. More recently, driven by needs of the embedded systems world, DH analog haven been introduced for ECC.
The DiffieHellman (DH) key agreement protocol is the basic publickey crypto system proposed for secretkey sharing. ECDH is the elliptic curve analog of the traditional DiffieHellman key agreement algorithm^{[40]}. The DiffieHellman method requires no prior contact between the two parties. Each party generates a dynamic, or ephemeral, public key and private key. They exchange these public keys. Each party then combines its private key with the other party’s public key to form the shared secret. This method is also known as carrying out an ECDH key agreement^{[14]}.
The publickey cryptoschemes like RSA and ECC, when used for communication protocols for data encryption are extremely computationally demanding and thereby slower than the symmetric ones but provide arbitrary high levels of security and do not require an initial privatekey exchange between two communicating parties. However, many symmetric key schemes can encrypt 1000 times faster than public key cryptosystems but are, however, poor at providing nonrepudiation and key establishment functionality^{[39]}.
In real applications, however, most practical cryptoprotocols are hybrid protocols, which incorporate integrated coupled symmetric and public key schemes. The publickey cryptoalgorithm is first used for establishing a common symmetrickey over insecure channel^{[40,41]}. Then the symmetric cryptosystem is used for secure communication with high throughput. Due to comparative slowness of the publickey algorithms, dedicated hardware is desirable for efficient implementation and operation of the cryptographic systems. In most applications symmetric key cryptosystems e.g., RC5, IDEA, DES/3DES and AES are today commonly integrated with existing public key cryptosystem like RSA or ECC for efficient cryptonetwork security.
Cryptokey length considerations: The security of the elliptic curve
cryptographic schemes hinges on the apparent difficulty of the discrete logarithm
problem in elliptic curve (DLP)^{[8]}. The best algorithm known for
the elliptic curve logarithm for nonsupersingular curves is the Pollardρalgorithm^{[42]}
which takes
, steps, where, r is the largest prime divisor of the order n of the elliptic
curve point P. Thus, to thwart an attack, the underlying field , the curve E and base point P should be selected so that the order n of P is
divisible by a prime number r, which is sufficiently large for the purpose at
hand.
Keys in ECC are generated by relying on the Elliptic Curve Discrete Logarithm Problem (ECDLP) which is the problem of determining an integer k (provided it exists ) such that kP = Q (or equivalently, K = log_{P}Q), where, P and Q are points on the elliptic curve^{[8]}. ECC does not involve exponentiation, but uses multiplication, hence is not as computationally costly as RSA, which relies on exponentiation computation. Also, the underlying mathematical problem of ECC, ECDLP is fully exponential, whereas subexponential algorithms exist for IFP used in RSA^{[4]}. Because it is more ’infeasible’to solve ECDLP the same level of security, can be provided with shorter keys in ECC compared with RSA.
Menezes^{[11]} gives comparisons of the difficulty of these problems.
His conclusion is that the ECDLP is computationally more difficult than the
DLP or the IFP, hence, cryptosystem based on elliptic curve can be as secure
as their more traditional counterparts with significantly smaller fields (Fig.
6). The expected time to solve the ECDLP with a point P as the generator
having order of a 160bit prime is approximately equal to the time required
to solve the DLP with a 1024bit modulus or to factor a 1024bit n into primes
p and q(= 2^{m}) (Table 1).

Fig. 6: 
Comparison of security levels of ECC/ECDLP and RSA/DLP/IFP 
These estimates are based on the currently bestknown algorithms for the problems:
for the ECDLP this is Pollard’sρmethod; for the DLP and the IFP the best
algorithm is the number field sieve. The reason for the large difference in
field size for the different systems is because of the running times of the
algorithms for the problems. No subexponential time algorithm for the ECDLP
has been found that applies to general curves; the fastest for the DLP are not
applicable in the elliptic curve setting. Due to these factors, ECC is better
suited for low bandwidth, computational power and memory situations especially
in mobile and wireless environment.
Secure key establishment and generation: Cryptosecurity communication network protocols usually consist of two phases. The first one is the key establishment phase, which is done initially to exchange the keys. Thereafter, in normal mode application data is transmitted over the insecure network. In key establishment phase one may use ECDH or MQV key agreement scheme. Pure DH or ECDH applications are, however, susceptible to impersonation or "man in the middle" attack, whereby an adversary establishes digital facades between two parties in order to obtain private information. Advanced key exchange protocols such as the MenezesQuVanstone (MQV) introduce mutual strong authentication which allows both parties to confidently identify each other before exchanging sensitive information^{[5,8,11]}. It is a method of key agreement, which is related to DiffieHellman, but offers some significant advantages. MQV offers attributessuch as keycompromise impersonation resilience and unknown keyshare resilience (the unknown keyshare resilience property has been demonstrated unachievable in this version of protocol)that are not found with ECDH. However, ECDH offers a very simple and efficient way of creating a shared secret between two entities.
Trusted third party: Certificate Authority (CA): For a added level of transaction security, a Certificate Authority (CA) can be used. A CA is a third part that is trusted to perform the service of validating information about each user and creating signed certificates to that effect. A certificate is a packet of information which includes the users (e.g. Bank’s) public key, email address, name, address and other useful information, such as expiration date of the certificate and user privileges. A CA creates, distributes, revokes and generally manages these certificates. For, example, Jane wants to obtain the Bank’s public key, she retrieves its certificate from the public key server directory and verifies the C’s signature on the certificate itself. Provided this signature verifies correctly, she has the C’s assurance that the Bank’s identity, its public key and all other information in the certificate is correct. Jane can now go ahead and use Bank’s public key to encrypt confidential information transaction to send to the Bank or to verify the Bank’s signature, protected by the assurance of the certificate.
THE ELLIPTIC CURVE DIFFIEHELLMAN (ECDH) KEY AGREEMENT SCHEME
In Elliptic Curve DiffieHellman (ECDH) key exchange, the two communicating parties, sever S and client C, agree beforehand to use the same curve parameters and base point P, which generates all the points on the elliptic curve E or the order of curve #E. Each party generates their private keys k_{S} (server) and k_{C} (client), respectively and the corresponding public keys: Q_{S }= k_{S}P and Q_{C }= k_{C}P.
Both the client and server then exchange their public keys and each multiplies its private key with the other party’s public key to derive a common shared secret key: Q_{SC }= k_{S}Q_{C }= k_{S}(k_{C}P) = k_{SC}P, where, (k_{SC º} k_{CS}) = k_{Msec }is the shared master private key. The shared master private key, k_{Msec}, may now be used to encrypt or decrypt a shared message over the insecure network. An attacker cannot determine the shared private key k_{Msec} from the curve parameters, P or the public keys of the parties.
If, however, the attacker can recover k_{Msec} from this data then he is said to solve DiffieHellman Problem (DHP). However, it turns out that if the numbers are all sufficiently large , it is very hard to calculate the discrete logarithm in a reasonable time, i.e., finding. k_{MSec} = log_{P }Q_{SC}. The security of the DiffieHellman algorithm depends on this fact. It is believed for most groups in use in cryptography that DHP and the DLP are equivalent^{[43,44]}, in complexitytheoretic sense (there is a polynomial time reduction of one problem to the other and vice versa. Maurer et al.^{[45]} has shown that breaking the DiffieHellman protocol was equivalent to computing discrete logarithms under certain assumptions.
Key establishment phase for wireless transaction: The client initiates
a connection by relaying a ClientHello with its precomputed public key Q_{C}
on the insecure wireless channel (Fig. 7).

Fig. 7: 
ECDH key exchange protocol 
The gate, which is in receive mode, on receiving the client public key passes
it to the server through the wired interface and waits for the server’s public
key. The server daemon, upon receiving the connection request sends a ServerHello
with its public key Q_{S} to the gateway and then starts computing the
shared master secret key from the received public key Q_{C} and the
server’s secret key k_{S}:
Where, Q_{MSecret} is the master secret, to be strictly kept away from
the enemy. The gateway transmits the server’s public key to the client and waits
for the data transmission to begin. The client, on receiving the server’s public
key Q_{S} from the gateway computes the master secret:
The client and server now have the same shared master secret Q_{MSecret}
of mbits using the ECDH key exchange. The key for the symmetric cryptoscheme
operation is then derived from this mbit master secret.
Normal mode of operation: Once the keys are set up, the client and the sever can commence transmission of application data encrypted with symmetriccrypto scheme, e.g. TripleDES in CBC mode^{[16]}. To close the cryptonetwork connection securely, we use a close connection control message which deletes the previously generated keys.
Practical application: In a practical application, for example wireless
point of sale systems, an exchange begins when a user swipes a smartcard, such
as a credit, on the client devicea point of sale terminal. The client first
saves the data encoded on the magnetic strip or IC device on the smartcard and
then initiates the ECDH key exchange protocol.
Table 11: 
NIST Guidelines for publickey sizes with equivalent security
levels^{[13]} 

Table 12: 
Hardware implementations of ECC and RSA 

After the shared master secret key is established, a symmetric cryptoalgorithm
like 3DES engine is fired. The card data is then encrypted with 3DES in CFB
mode on the client side and the application data exchange can commence which
must be securely terminated on completion of communication protocol.
Relative cryptokey sizes: So what does this mean in practice? NIST has recommended that 128bit protection is necessary to achieve relatively lasting security (to the year 2036 and beyond) for the symmetric key cryptoschemes. This means moving from 3DES to AES^{[16]}. To avoid compromising the security of the system, NIST's FIPS 1402 standard^{[46]} indicates that keys for symmetric ciphers such as AES must be matched in strength by publickey algorithms such as RSA and ECC. For example, a 128bit AES key demands an RSA key size of 3,072bits for equivalent security but for the same strength, the ECC key size is only 256bits (Table 11).
ECC key sizes scale linearly, RSA does not. The result is that the gap between systems grows as the key sizes increase. This is especially relevant to implementations of AES where at 256bit security you need an RSA key size of 15,360bits compared to 512bits for ECC (Table 11).
This will have a significant impact on a communication system as the relative computational performance advantage of ECC versus RSA is not indicated by the key sizes but by the cube of the key sizes. The difference becomes even more dramatic as the greater increase in RSA key sizes leads to an even greater increase in computational cost. So going from 1024bit RSA key to 3072bit RSA key requires about 27 times (3^{3}) as much computation while ECC would only increase the computational cost by just over 4 times (1.6^{3}).
Even in systems that use 1024bit RSA, this has important design implications. For example, ECC160 has a 6X smaller keysize than RSA1024 and can generate a signature 12 times faster on StrongARM7. The performance advantage of ECC stands out even more when we look at higher security levels or when looking at hardware implementations. Table 12 makes clear the relative advantages of ECC on the hardware side of things, in terms of speed and gate count.
IMPLEMENTATION OF ELLIPTIC CURVE ENCRYPTION SCHEME (ECES) OVER FINITE FIELD
GF(2^{m}) System setup: An underlying finite field is chosen, where, q = 2^{m}. An elliptic curve E defined over and a point P∈E are chosen. The order of the point P is denoted by n. The
field , curve E, point P and the order n, comprise the system parameters and
are publickey information.
Key generation: Each communicating entity shall perform the following operations:
• 
Entity A selects a random integer k_{A} from[1, n1]
and compute: A: = k_{A}P. 
• 
’s public key chain is (E, P, A) placed in public keyserver,
’s private key is k_{A} kept secrete. 
• 
Entity B selects a random integer k_{B} from [1, n1]
and computes: B: = k_{B}P. 
• 
B’s public key chain is (E, P, B) placed in publickeyserver,
B’s private key is k_{B} kept secrete 
Encryption process (B): Entity B sends a message M to entity A and entity B performs the following steps:
• 
Look up ’s publickey: (E, P, A) or A. 
• 
Represent the message M as a pair of field elements (m_{1},
m_{2}), where
, not necessarily a point on the curve. 
• 
Accesses its private key k_{B}. 
• 
Compute his public key point: B: = k_{B}P: = (x_{1},
y_{1}) 
• 
Compute the session key: S_{BA}: = k_{B}A:
= k_{B}(k_{A})P: = k_{BA}P: = (x_{2}, y_{2}),
where, k_{BA} is the shared key. 
• 
Combines the field elements m_{1}, m_{2} and
x_{2}, y_{2} in a predetermined manner to obtain two ciphertext
field elements c_{1} and c_{2}. 
• 
Transmit the data C: = (B, c_{1}, c_{2}) to
A. 
Decryption process (A): Entity A decrypts the ciphertext C: = (B, c_{1}, c_{2}) received from B, by performing the following steps:
• 
Look up B’s publickey: (E, P, B) or B. 
• 
Compute the session key: S_{AB}: = k_{A}B:
= k_{A}(k_{B})P: = k_{AB}P: = (x_{2}, y_{2}),
using her privatekey k_{A}. 
• 
Recover the message m_{1} and m_{2} from c_{1},
c_{2} and x_{2}, y_{2}. 
ELLIPTIC CURVE SIGNATURE SCHEME (ECSS)
In this age of digital piracy it is extremely important to make sure that participants of a given transaction are really who they say they are and that the communicated content is not altered in any way during the transaction. Authentication of both parties, as well as encryption of the content in transit, is critical to limit exposure on both ends of the transaction via encryption and finally signing the messages^{[13,39]}.
Digital Signatures (DS) are the electronic equivalent of handwritten signatures. A Digital Signature Algorithm (DSA) is the specific mechanism within cryptography that provide the benefits of authentication, data integrity and nonrepudiation. Traditionally, handwritten signatures have provided security services because each individual has distinctive handwriting, making their signature unique and hence difficult to forge. Similarly, securing electronic information requires the equivalent of handwritten signature that cannot be duplicated. A public key construct called digital signature, a message that is unique and exclusive to the original signer, provides the solution to this problem. A digital signature’s make up is a function of both signer’s identity and the data being signed, so that any changes to the message data will effect a detectable change to the digital signature, for more detail info^{[39]}.
Two signature schemes are described in ECSS standard. In this scheme the message to be signed is first hashed to a message digest of fixed length and then this digest is signed. Verification of the signature requires both the signature and the original message^{[39]}. Elliptic curve digital signature scheme (ECDSA) is the elliptic curve analogue of the NIST digital signature scheme (DSA)^{[13,47]}. System Setup and Key generation as performed in a similar manner to ECES.
Signature generation for ECSS: Entity A signs a message M for entity B, by performing the following steps:
• 
Represent the message M as a binary string. 
• 
Use hash algorithm to compute the hash value e: = H(M). 
• 
Select a random number integer k where,1≤ k ≤ n1. 
• 
Compute its public key R: = kP: = (x_{R}, y_{R}). 
• 
Compute r: = x_{R }+ e mod q 
• 
Use the private key k_{A} to compute s: = kk_{A
}r mod n 
• 
A sends to B the message M and the signature: (r, s). 
Signature verification for ECSS: Entity B verifies ’s signature (r, s) for a message M by performing the following steps:
• 
Look up ’s publickey, A. 
• 
Compute the point V = sP+rA: = (x_{R}, y_{R}) 
• 
Compute the hash value e: = H(M) 
• 
Compute : = x_{R}+e mod q. 
• 
Accepts ’s signature for message M if and only if r: = . 
Note: the hash value e reduced modulo q and then modulo n. Hence, for security reasons it is necessary that the hash function H, q and n be chosen so that, (H mod q) mod n, is also a cryptographically secure hash function. Similar operation and implementation of elliptic curve digital signature can be done using ECDSA^{[13]} and also ECElGamal Signature scheme^{[15]}.
SIMPLE IMPLEMENTATION OF (ECES) OVER FINITE FIELD GF(2^{4}) System
setup: The underlying finite field will be
and using the generator point P = (g^{3}, g^{5}) which has order
, the data from tables 9 and 10. The system parameters (public information placed
in the publickey server), are .
Key generation: Entity A (Alice) performs the following operations:
• 
A selects a random integer k_{A }= 9 from[1, n1]. 
• 
A computes the point A = k_{A}P = 9P = (g^{6},
0) = ((0010), (0000)). 
• 
’s publickey is the point A and privatekey is the integer
k_{A }= 9. 
Encryption process (B): (Entity B sends a message M=10101011 to entity A). Entity B performs the following steps:
• 
Looks up ’s publickey from publickey server: A = (g^{6},0). 
• 
Represents M as a pair of field elements M = (m_{1},
m_{2}) = ((1010), (1011)) = (g^{5}, g^{14}) 
• 
Selects a random integer k_{B }= 14 from^{[1,19]} 
• 
Computes his public key: B = k_{B}P = 14P = (g^{8},
g^{13}) = ((1001), (1101)). 
• 
Compute shared key: S_{BA}: = k_{B}A = k_{B}(k_{A}P)
= 14(9)P = 6P = (x_{2}, y_{2}) = (g^{8}, g^{3})
= ((1001), (0100)). 
• 
Compute the field element:
. 
• 
Now B forms x_{4 }= (1000) = g^{9} by concatenating
the high order 2bits of
with the low order 2bits of
. Next B forms y_{4 }= (1001) = g^{8 }by concatenating the
high order 2bits of
with low order 2bits of
. (Note that in general the probability that (x_{4}, y_{4})
= (g^{9}, g^{8}) = ((1000), (1001)) is a point on the curve,
or that x_{4}, or y_{4} equals 0, will be negligibly small.) 
• 
B forms the field elements: 
• 
B transmits the data the ciphertext C: = (B, c_{1},
c_{2}) parameters to A, i.e.,: 
C: = (g^{6}, 0, g^{13}, g^{8})
= ((0010), (0000), (1101), (1001)) 
Decryption process (A): Entity A decrypts the ciphertext, C: = (g^{6}, 0, g^{13}, g^{8}), received from B, by performing the following steps:
• 
A computes the session key: S_{AB}: = k_{A}B
= 14(9P) = 6P = ( g^{8}, g^{3}) = ((1001), (0100)).. 
• 
A forms x_{4 }= (1000) = g^{9 }and y_{4
}= (1001) = g^{8 }just as B did. 
• 
A recovers the pair (m_{1}+x_{2},m_{2}+y_{2})
by computing: 
• 
A recovers the message pair: m_{1 }= (0011) + g^{8
}= 1010 and m_{2 }= (1111) + g^{3 }= 1011, which is
the original message: M = (m_{1}, m_{2}) = (g^{5},
g^{14}) 
Simple implementation of EC Signature Scheme (ECSS) Signature generation
scheme: Entity A signs the message M = 777 = 1100001001. Suppose that the
hash value of
A performs the following steps:
• 
Select a random integer k = 13 in the range^{[1,n 1]}. 
• 
Compute R = 13P = (g^{11}, g^{11}) = (x_{R},
y_{R}) 
• 
Represent x_{R }= g^{11 }= (1110) as the integer:
x_{R }= 8 + 4 + 2 = 14 
• 
Compute 
• 
Use its private key k_{A}=9 to compute: S = kk_{A}r(mod
n) = 13 = 9(7) mod 20 = 10 
• 
The signature on message M is: (r, s) = (7, 10). 
Signature verification for ECSS: Entity B verifies signature (r, s) = (7, 10) on M as follows:
• 
B looks up ’s publickey: A = (g^{6}, 0) = 9P. 
• 
B computes the point: V = sP + rA = 10P + 7(9P) = 13P = (g^{11},
g^{11}) = (x_{V}, y_{V}) 
• 
Represent x_{V }= g^{11 }= (1110) as the integer:
x_{R }= 8 + 4 + 2 = 14 
• 
B computes 
• 
B accepts ’s signature on M since
= 7 = r. 
THE PRACTICAL APPLICATION OF ECC
Implementing ElGamal ECC over finite field GF(2^{163}): Cryptoscientist
T. ElGamal was the first mathematician to propose a publickey cryptosystem
based on the Discrete Logarithm Problem (DLP) modulo prime p^{[48]}.
He in fact proposed two distinct cryptosystems: one for encryption and the other
for digital signature scheme in 1984, well before elliptic curves were introduced
in cryptography. Since then, many variations have been made on the digital signature
system to offer improved efficiency over the original system. In 1991, Claus
Schnorr discovered a variant of the ElGamal digital signature scheme, which
offers better efficiency, compared to the original systems. In turn, the U.S.
government’s Digital Signature Algorithm (DSA) is based on ElGamal’s work^{[39]}
The ElGamal publickey encryption scheme can be viewed as DiffieHellman key
agreement protocol in key transfer mode^{[49]}. Its security is based
on the intractability of the Discrete Logarithm Problem (DLP) and the DiffieHellman
problem. These systems are the best known of a large number of systems whose
security is based on the DLP. The prime p used in the DL systems should also
be at least 150 decimal digits (500 bits) in lengthto provide shortterm security.
The elliptic curve cryptosystems as applied to ElGamal protocols were first
proposed in 1985^{[49]}.
In implementing ElGamal elliptic curve cryptosystems, suppose that two entities, the eBusiness (B) and the customer Alice (A) wants to communicate between each other over an insecure communication network. Next let’s assume that the two entities have decided to use the protocol of ECElGamal encryption protocol to implement their secure communication. One basic point to note is unlike ECDH protocol^{[8,14]}, this protocol does not create a common key, but using ECElGamal protocol a message M = M_{1}+M_{2}, not necessarily a point on elliptic curve, can be sent from eBusiness to Alice and vice versa.
Let the fixed point P = (x_{P}, y_{P}) ∈ GF(2^{m}) be the generator point such that the multiples kP of the generator point P are (for 1 ≤ k ≤ n1) including point O located at infinity. Now suppose entity A chooses publickey set: A = k_{A}P, where the secretkey k_{A} is selected from [1, n1], giving rise to its publickey ring (E, P, A), which is kept in the publickey server. Next entity B selects a random secretkey k_{B} from [1, n1] such that: B = k_{B}P giving rise to its publickey ring (E, P, B) kept in the publickey server.
The sender A encrypts her message M = M_{1 }+ M_{2} by making use of the key exchange protocol e.g. ECDH key agreement scheme to generate a shared key: S_{AB }= k_{A}(k_{B}P) = k_{AB}P = k_{BA}P = (x_{S}, y_{S}). She then performs the message encryptions as follows: C = (c_{1}, c_{2}) = MS_{AB}, preferably, c_{1 }= M_{1}x_{S } and c_{2}=M_{2}x_{S}, where M = M_{1}+M_{2}. The encrypted ciphertext message is then sent as a package: (A, C).
Once the encrypted ciphertext is received by entity B, it looks up ’s publickey
from the publickey server and computes: S_{BA }= k_{B}(k_{A}P)
= k_{BA}P = (x_{S}, y_{S}). Subsequently
and
and the original plaintext message is M = M_{1}+M_{2} is recovered.
It should be noted that for the message communication between the parties to
take place each must exchange their public key for the purpose of key agreement
computation. Secondly, in obtaining the original message, two inversion multiplications
are performed. Note that in setting up the parties public keys, we can also
compute hk_{A}P and hk_{B}P, which can resist the attack on
small subgroup. Where, h is a cofactor defined in P1363^{[19]}.
Hardware design and implementation for ECC: The current state of global
communication coupled with global economy requiring the global prime movers
to be in contact at all times with the business point is driving the world of
wireless communication powered by embedded constrained environment devices technology
to a new high.

Fig. 8: 
Encryption and decryption schemes when the encrypter and decrypter
are sitting aside 
But the world of embedded constrained systems with its limited power, memories
and storage capabilities is limiting effective implementation of better cryptoalgorithms.
However, with the advent of ECC coupled with AESa symmetric key crypto, the
world of embedded constrained devices is beginning to enjoy better cryptosecurity
network connections, thereby allowing secure business transactions overtheair
on the fly.
The elliptic curve cryptoschemes offer the highest security per bit ratio compared to any other currently known publickey cryptosystems. This is a plus point for embedded systems where the cost increases significantly with every extra memory chip. ECC hardware implementation uses fewer transistors, e.g., currently implementation of 155bit ECC uses only 11,000 transistors compared to RSA 512bits implementation with 50,000 transistors.
The elliptic curve cryptoschemes with key size in the range of 155210 bits is currently considered acceptable for practical cryptosecurity protocols which compares favorably with similar security level as the Discrete Logarithm Problem (DLP) and IFP cryptoschemes with the key size of 5121024 bits. Thus, ECC is superior to DLP/IFP cryptosystems in terms of block length and storage requirements. Our practical implementation is based on the key size of 163bits where GF(2^{163}). The procedure required for successful implementation of hardware based protocols is as follows:
• 
To minimize the hardware complexity (circuitry complexity,
feedback loops and the number of XORgates), the irreducible polynomial,
f(x) = x^{163 }+ x^{7 }+ x^{6 }+ x^{3 }+
1, was chosen. 
• 
The integers a, b ∈ GF(2^{163}) required for
the obtaining the elliptic curve, E: y^{2}+xy = x^{3}+ax^{2}+b
were chosen arbitrarily as: 
a =4 
FEEE CE35 5F00 D401 875F E2C0 FFF3 EE2F 64FC B30D 
b =1 
31C8 335B 7F5A D1C5 EEA0 8316 0E10 C9C8 C3B3 D39A 
• 
With a and b chosen as above, there could be a possible solution
to the elliptic curve E, which yields an arbitrary fixed point P = (x_{P},
y_{P}) on the curve: 
x_{P} = 
5 5968 5D73 DD75 4D33 7FF7 3319 706C FF36 8212 25AF 
y_{P} = 
3 6F4D 089A 3FA0 C2CB F84E 0D6E FCB4 1033 362A 5B97 
Which we use as the generator of the point of order #E the number of points on the curve.
• 
At this point and regardless of the computing complexity at
this step, sender chooses her private k_{A} and looks up at the
receivers publickey B = k_{B}P with k_{B} being its private
key which are given by: 
k_{A }= 95 and k_{B }= 250 both from [1,
n1], respectively. 
• 
The encrypter entity A computes, S_{AB }= k_{A}(k_{B}P)
= k_{AB}P = (x_{S}, y_{S}), where: 
x_{S} = 
4 A0AF DCE6 AFB4 2309 D155 BFBA 9D49 6178 07B5 885D. 
y_{S} = 
459E 2437 4FB9 1C44 D5F4 42E3 57E2 BB32 F6B6 91C9 
• 
The ciphertext messages are then computed as: c_{1 }=
M_{1}x_{S} and c_{2 }= M_{2}x_{S}
where M_{1} and M_{2} are consecutive blocks of which the
data length is mbits (163 bits), in this case we have a single block: 
M = 
M_{1 }+ M_{2} = 33E1 3366 8832 5566 5CCA +
3FE1 3CE6 8832 5577 5CEA 
c_{1 }= 
M_{1}x_{S} =1EF DB1F 61D8 AF59 AD11 F520 723C F6C2 AC96
364C 
c_{2 }= 
M_{2}x_{S} =5 AD61 C6F5 869E BAC1 AB1E F1F1 C272 8FD4
6567 380E 
• 
The encrypted messages are next feed and stored in the array
of Flash ROMs, which can be part of an Integrated Chip (IC) module or can
be on a separate module. 
The last two operations can be repeated many times until all the data messages are encrypted and stored (or sent). To recover the encrypted messages, the receiver performs the following operations:
• 
The shared key agreement S_{BA }= k_{B}(k_{A}P)
= k_{BA}P = (x_{S}, y_{S}) is already precomputed
as above. 
• 
Step (1) and (2) could be omitted since the encrypter and
decrypter are in the same module. From above (x_{P})ˉ^{1}
and (y_{P})ˉ^{1} can be computed as: 
(x_{P})ˉ^{1 }= 5 6468 AAC3 D57A 35E0
E19F BF40 5F1B 18F1 C861 6C5E
(y_{P})ˉ^{1 }= 7 223D BA66 4DAA 8495 603B C053 B084
2A3A 82C0 5CAE 
M_{1 }= c_{1}(x_{S})ˉ^{1}
= 33E1 3366 8832 5566 5CCA
M_{2 }= c_{2}(y_{S})ˉ^{1} = 3FE1
3CE6 8832 5577 5CEA 
The last operation is to be repeated until all the plaintext is recovered from the transmitted ciphertext messages in case of large volume message.
The hardware design considerations: The elliptic curve ElGamal cryptosystems
discussed above can be implemented in hardware using a simplified circuit in
which the encrypter and the decrypter circuit modules are integrated aside within
the same IC hardware. Therefore, x_{S}, y_{S}, (x_{S})ˉ^{1}
and (y_{S})ˉ^{1} can be precomputed in advance and stored
in the registers. The encrypter task is then just to compute:
c_{1 }= M_{1}x_{S} and c_{2
}= M_{2}y_{S} 
At the receiving end, the decrypter has then to compute:
c_{1}(x_{S})ˉ^{1 }= M_{1}x_{S}(x_{S})ˉ^{1
}= M_{1} and c_{2}(y_{S})ˉ^{1 }=
M_{2}y_{S}(y_{S})ˉ^{1 }= M_{2} 
To recover the original plaintext. The complete operation is illustrated in
the schematic hardware design concept shown in Fig. 8.
The advantage of this coupled encrypterdecrypter architecture approach is that only minimum hardware is required, such that a single fixcoefficient multiplier can be used to perform encryption or decryption depending on the mode of operation the chip is programmed to undertake. The multiplier can also be used in half duplex mode to perform an alternate encryption or decryption. Note that multiplication is performed over Galois field, therefore, the selection of the irreducible polynomial can affect the circuitry complexity. In practice, select the one that has small number of terms (pentanomial, or 5terms). The IC module capability can be improved using additional circuitry capable of solving elliptic curve equations, inversion and multiplication, thereby enabling it to generate/change the private and/or public keys onthefly (Fig. 3 and 4). This additional circuitry no longer allows for a simple circuit and has added complexity which requires VLSI technology which by today’s standard is not difficulty to achieve. Hardware based elliptic curve cryptosystems have already been implemented under various constrains and applications. Sutiko et al.^{[50]} have implemented the ElGamal ECC processor in 32 bitwide bus with 155 bitwide register. Paar^{[51]} looked at the implementation of the multiplier which is applicable to a composite field.
CONCLUSIONS
In this study we have shown how to implement elliptic curve cryptosystems over
binary finite field,
using polynomial basis representation and; normal and optimal normal basis representations.
We have shown that the elliptic curve cryptoschemes offer the highest security
per bit ratio compared to any other currently known publickey cryptosystems.
This is a plus point for embedded systems where the cost increases significantly
with every extra memory chip. ECC hardware implementation uses fewer transistors,
e.g., currently implementation of 155bit ECC uses only 11,000 transistors compared
to RSA 512bits implementation with 50,000 transistors. Elliptic curve cryptoschemes
offer a lot of promise in terms of security and memory requirement than any
other present cryptoschemes. However, more research is needed in this field
for better understanding and effective implementation of ECC.