Implementation of Elliptic Curve Cryptography in Wireless Sensor Networks - Security for Wireless Sensor Networks Using Identity-Based Cryptography - page 176

The Non-Adjacent Forms (NAF) method was exploited for recoding the positive
integer k in point multiplication in order to reduce point additions. Shantz (2001) pre-
sented an efficient technique to calculate a modular division. The idea is to compute y / x
in one operation, instead of computing 1/x first and then multiplying it with y . This
scheme has eliminated one multiplication in modular division operations. The new
algorithm can be applied in both F p and 2 F fields.
In addition to prime fields (Section 3.3) and binary fields (Section 3.4), ECC sys-
tems can be evaluated over extension fields. Extension fields can be derived from the
polynomial basis representation of binary fields. For a finite field F q where q = p m
(Section 3.2.3), if m ≥ 2, then the field F is called an extension field. Woodbury et al.
(2000) introduced another ECC system over an optimal extension field, where p is cho-
sen of the form 2 n ± c ( n and c are arbitrary positive rational integers). The general idea
with the optimal extension fields

p F is to select p (chosen as a small pseudo-Mersenne
prime), m , and the reduction polynomial f(z) to more closely match the underly-
ing hardware characteristics. Usually, p fits in a single computer word, and such an
approach simplifies the handling of carries in arithmetic operations. Although optimal
extension fields have some advantages over prime and binary fields, standardization
of such fields is still not actively pursued as compared to the prime and binary fields.
ECC systems mainly consist of elliptic curve exponentiations. Generally, elliptic
curve exponentiations are influenced by the coordinate—exponentiation for a fixed
point and a random point. In the case of the coordinate, elliptic curve exponentiation
can be computed by repeated addition and doubling operations. Furthermore, a suit-
able and optimized algorithm can be used to realize the repeated number of addition
operations. However, realizing the doubling operations (in the case of the exponen-
tiation for a random point) with a suitable algorithm is not possible. Coordinates on
elliptic curves can be defined that provide different addition formulas. Miyaji et al.
(1997) investigated the efficiency of addition formula in a Jacobian coordinate and
concluded that it offers a slower addition but a faster doubling operation. In the case of
exponentiation for a fixed point, a precomputation method that computes an elliptic
curve exponentiation by repeating the addition operation, not the doubling operation,
was initially proposed (Brickell et al. 1993). Later, Lim and Lee (1994) showed that
the algorithm described in Brickell et al. (1993) can be accelerated at the cost of some
extra point-doubling operations (Lim and Lee 1994). In the case of the exponentiation
for a random point, a window method is used to realize the addition and subtraction
operations (Koyama and Tsuruoka 1993). In this method, an interval between two
windows can determine the computation amount, i.e., the longer the interval, the lesser
the computation amount.
The practicality of ECC on sensor networks was first demonstrated with the intro-
duction of the EccM library (Malan et al. 2004). EccM provided ECC over binary
fields with 163-bit key sizes. To achieve better performance, it used a y 2 + xy = x 3 +
x 2 +1 Koblitz curve and a fixed base point. Although EccM showed the applicability of
PKC on sensor nodes, the time taken to run ECC primitives was too high for practi-
cal applications. For instance, the time taken to generate a private and public key pair
was equal to 34.2 seconds averaged over 100 trials. Furthermore, when this library
was released, it was unclear if we would require hardware accelerators to improve the

m