Elliptic Curve Cryptosystems (ECC) has gained increasing popularity in
public key cryptography since was first proposed independently by Miller
and Koblitz in mid of 1980's. In comparison with other established
systems such as RSA, ECC has become especially attractive for
applications due to its shorter key size requirement, which are
translated to less power and storage requirements, and reduced computing
times. For example, 160bits of ECC and 1024bits of RSA offer the same
level of security. These advantages make ECC beneficial for use in smart
cards and embedded systems where storage, power, and computing resources
are at a premium.In public key cryptography each user or the device
taking part in the communication generally have a pair of keys, a public
key and a private key, and a set of operations associated with the keys
to do the cryptographic operations. The operations of ECC is defined
over the elliptic curve $y^2 = x^3 + Ax + B$, where $4A^3 + 27b^2 \neq
0$. All points $(x, y)$ which satisfies the above equation plus a point
at infinity lies on the elliptic curve. The private key is a random
number $k$ and the public key is a point in the curve $Q$, where $Q$ is
obtained by multiplying the private key with the generator point $P$ in
the curve.The security of ECC depends on the Elliptic Curve Discrete
Logarithm Problem (ECDLP). Let $P$ and $Q$ be two points on an elliptic
curve such that $kP = Q$, where $k$ is a scalar. Given $P$ and $Q$, it
is computationally infeasible to obtain $k$, if $k$ is sufficiently
large. $k$ is the discrete logarithm of $Q$ to the base $P$. Therefore,
the most dominant computation part of ECC is the scalar multiplication
$kP$, i.e. multiplication of a scalar $k$ with any point $P$ on the
curve. The speed of scalar multiplication plays an important role in the
efficiency of ECC.
The running time of scalar multiplication is computed based on two
levels of complexity, elliptic curve point operations and finite filed
operations. Performing fast point operations on an elliptic curve is
crucial for efficient scalar multiplication. Computation time of point
operation depends on the coordinate system adapted. Point operations in
affine coordinate involves inversion, which is particularly a very
costly operation over prime fields. To avoid inversion for prime filed,
various coordinate systems have been proposed such as Projective
coordinate, Jacobian coordinate, modified Jacobian coordinate, and
Chudnovsky Jacobian coordinate. Using these coordinates, we can remove
inversions from the point operations at the cost of increase in the
other simpler filed operations. Computation cost of point operations are
different for various coordinates. Some coordinate systems such as
modified Jacobian coordinate have faster doubling than the other
coordinate systems and some coordinate systems such as Chudnovsky
Jacobian coordinate have faster addition. One possible way for an
efficient scalar multiplication is to use the mixed coordinate systems
for the computation of point operations.
The common method for scalar multiplication is performed by iterative
point additions and point doubling on an elliptic curve according to
bits $k_i$ of binary representation $k$, which is called binary method.
Various methods have been proposed for the efficient computation of $kP$
by reducing point operations (addition, doubling). One method can be
made by taking different binary representations of the multiplier $k$
such as nonadjacent form (NAF), window nonadjacent forms such as
(wNAF) and FracwNAF. Unfortunately that the aforementioned methods are
vulnerable to sidechannel attacks, which measure observable parameters
such as timings or power consumptions during cryptographic operations to
deduce the whole or partial secret information of a cryptosystem.
Sidechannel attacks were extended to elliptic curve cryptosystems. The
particular target of sidechannel attacks for elliptic curve
cryptosystems is the scalar $k$ in scalar multiplication, which is a
secret positive integer. Various methods to improve the security against
power analysis attacks have been proposed, such as Montgomery ladder and
the Joye's doubleandadd algorithm.
When extra memory is allowed, the window method (wNAF, FracwNAF) can
dramatically speed up the main computation of point multiplication with
the precomputation space. In this case, a table of points is built and
stored in advance (precomputation stage) for later use during the
execution of the scalar multiplication itself (evaluation stage).
Although these windowbased methods effectively reduce the number of non
zero terms in most representations, a potential drawback is the cost of
computing such a table, which grows with the window size. Thus, it is an
important research effort to minimize the cost of the precomputation
stage to reduce the total cost of scalar multiplication. Further,
although improved elliptic curve shapes with faster explicit formulae
are currently the focus of intense research, there is still a lack of
analysis of precomputation schemes that are efficient for these
settings. In this direction, Patrick Longa and Catherine Gebotys
proposes a efficient precomputation schemes based on ``conjugate''
addition (CA), which requires much fewer additional field operations by
computing the addition and subtraction of two distinct points together.
Later Sasahara, Miyaji and Yokogawa developed the precomputation
schemes using doublingandtripling formula (DT), which computes the
doubling and tripling of point parallel.
In this thesis, we improved the precomputation schemes based on the
following idea: compute all the precomputed points by only CA and DT,
without independent point addition. We refer to this strategy as making
``perfect'' conjugate pair. It will turn out that this strategy will
allow using the efficient point operations such as CA and DT as possible
as we can, thus computing precomputed tables very efficiently. Further,
our precomputation schemes compute the intermediate points in
Chudnovsky Jacobian coordinate which has faster addition. As
representing points in Chudnovsky Jacobian coordinate will require more
memory cost, we propose a new mode of addition formulae which keep the
data of one input point. With the proposed addition formulae, the extra
memory requirement due to Chudnovsky Jacobian coordinate representation
will be reduced. This thesis compares and analyses the performance of
the proposed schemes with the previous efficient methods by representing
precomputed tables in Jacobian coordinates. The analysis shows that the
proposed schemes offer the lowest computation costs for precomputation
tables for scalar multiplication. Then we proposed several ternary
method for scalar multiplication, representing the scalar $k$ in ternary
expansion $(k'_{n'1},\ldots ,k'_1,k'_0)_3$, where $k'_i\in \left\lbrace
0,1,2 \right\rbrace$, $k'_{n'1}\neq 0$. As the length of ternary
expansion is much shorter than binary one, we can improve time
efficiency by the ternary methods. And we use the addition formulae in
mixed coordinates to further reduce the computation time. Our propose
ternary signeddigit method and extended ternary signeddigit method
offer the lowest computation time with one extra register.
[ back ]
