1.

Preliminaries

and Literature Review1.1.

Introduction

N. Koblitz 1 and V. Miller 2 have introduced Elliptic Curve

Cryptography (ECC) for a public-key cryptography. ECC provides same level of

security with smaller key sizes which lead to a better performance in

performing encryption and decryption algorithm. In other word, the interest in

the ECC is growing because the implementations of ECC have produced better

performance in term of calculation time, processing time, power consumption and

memory usage. There are many schemes work based on elliptic curves such as keys

exchange, encryption/decryption and digital signature. The security of ECC schemes is based on the

resolution of an underlying mathematical problem called the Elliptic Curve

Discrete Logarithm Problem (ECDLP) which is very hard to solve. In ECC, public

and private keys allows encryption and decryption the cryptographic system.

Locking and unlocking algorithms are based on point multiplications. This

operation is considered as the basis of any ECC structure. Point multiplication

has been implemented based on the basic operations of point addition and

doubling. These two operations are implemented based on finite-fields

arithmetic. The figure 1 illustrates these dependencies. Fig. 1. Layers

of Point multiplication implementationThere are several forms of elliptic curves used in ECC such as the

Weierstrass, Hessian and Edwards and kolbitz curves. Each curves has different

characteristics. Koblitz curves 27 are a family of curves on which point

multiplication is noticeably faster than on other curves and also it can be computed very efficiently in hardware. Points on elliptic curves can be represented

by different coordinate systems. There are many coordinate systems like Affine,

Projective and mixed coordinates are in ECC for number representation. The

choice of the curve and point coordinate system are very important and have a

significant effect on the performance of the elliptic curve arithmetic

operations. In fact, point multiplication operations can be accelerated and

secured when efficient representation of elliptic curve points is used. In the

following sections, we review mathematical background needed for the elliptic

curve cryptography which are categorized below:1.

Finite

fields. 2.

Implementation

of the field operations 3.

Elliptic

Curves over 4.

Implementation

of the point multiplication algorithm. 1.2.

Finite

FieldsA Finite Field contains of a Finite set of objects called field

elements together with the description of two operations, Finite Field

arithmetic plays an important role in ECC and all the low-level operations are

carried out in these Fields. Finite fields regularly used in cryptography are

either prime fields or binary filed. 1.3.

Binary

Fields The binary Field of characteristic two is a Finite Field 3 that contains different elements. The elements of is are represented as a vector space over is which contains 0 and 1 with respect to a

basis. As the two elements of can be represented with a bit, bits are required to represent elements of. Addition of

two elements in is simply performed but the multiplication

depends on the Field basis and dependencies between the Field elements. Finite

fields regularly used in cryptography are either prime fields or binary filed.

These fields has been used in conventional hardware and software applications

and recommended by the international standards such as IEEE and NIST.

Normal basis is the most efficient Field as it is offering free squaring in hardware

architecture using just cycle shift. However, the multiplication is so complex.

But there is a special subset of NB which is classed Gaussian Normal Basis

(GNB) which present more efficient multiplication. We have used GNB for

our implementation.1.4.

Normal

Basis It is shown that there exists a normal basis for the binary

extension field for all

positive integers . The normal

basis is constructed by finding a normal element, where ? is a

root of an irreducible polynomial of degree m Then set N= is a basis for and its elements are linearly independent. In

this case, can be represented as, where. Gaussian normal basis (GNB) 5 is a special class of normal basis which is included in the IEEE 1363 and NIST

41 standards for the Elliptic Curve Digital Signature Algorithm (ECDSA) and

exists whenever is not divisible by 8 31. For such a given

m, there always exists a type , , GNB. Type T

GNB provides low complexity multiplication as compared with other normal bases

over.1.5.

Implementation

of the Binary field operationsHere, we review the basic field operations in a binary field.

Specifically, the operations of addition, multiplication, squaring and

inversion are reviewed with their Implementation in over GNB.1.5.1.

Field

AdditionAddition of two field elements, say, where are in can be obtained by pair-wise addition of the

coordinates of and over .Thus, this is

a simple addition of each linearly independent digit. Each digit is represented

as a single bit and there are no carries. The identity element of addition, i.e., 0, is (0, 0, · · ·, 0, 0).1.5.2.

Field

SquaringFinite-field squaring performs, where where are in. Squaring

operation is performed by right cyclic shift of the coordinates of:It is free in hardware if all coordinates are available in

parallel.1.5.3.

Field

Multiplication Let A and B be elements in in, and assume

their product is , .Then, we can

obtain can be obtained as 1,

13: where , , , and denotes the th element of matrix. Then, the other coordinates of could be obtained by shifting the input

operands A and B. Bit-level multipliers provide the lowest possible area complexity.

Massey and Omura invented the first bit-level normal basis multiplier 12. Digit-level multipliers are alternatives for bit-level

multipliers in which the digit size can be chosen depending on the amount of

the resources available. There are some Low-complexity GNB multipliers have

been proposed in 13, 9,

4, 11. The results of such schemes are available after clock cycles,

where d is the digit-size in digit-level architectures, , and is the field size. 1.5.4.

Field

InversionInversion for a given element, finding an

element such that , is considered

an expensive operation. It is commonly required in cryptographic applications

of finite fields and its efficient implementation is important. Based on Fermat

Little Theorem, an inversion can be calculated by the inversion

based on Fermat’s Little Theorem uses consecutive squaring and multiplication

and is more suitable while field elements are represented by normal basis. The

complexity of it can be further reduced by using the Itoh-Tsujii method. In

Itoh and Tsujii algorithm (ITA) 4, the number of multiplications is reduced

based on decomposing Itoh-Tsujii

reduces the complexity of the exponentiation to squarings and the Hamming weight of (m-1)

multiplications, 1.6.

Binary

Koblitz curvesThe most standard binary elliptic

curves is called Binary Weierstrass curves (BWCs) and the curve is defined by

following equationIn this equation: and . This equation

is suitable for cryptographic applications. For this family of curves, NIST

recommended standard elliptic curves over fields consist of {B-163, B-233, B-283, B-409

and B-571}. In following point addition and point doubling on BWCs in affine

coordinate are presented. Let and be two points on the BWCs with Then the addition of points is the point denoted by

, Where

And also for the point doubling we have , Where

In this case, point addition and

point doubling are computed by , where , and are cost of computation field inversion, field

multiplication and field squaring respectivelyIn the binary Weierstrass curves if and , it is called

Koblitz curves 11. Therefore, the Koblitz curves are defined over by following equation:

Koblitz curves offer considerable computational advantages compared

to the binary Weierstrass curves. They have special attractiveness among

elliptic curves, because point doublings can be replaced by efficiently

computable Frobenius endomorphism 27. Mapping in Frobenius endomorphism is performed

by raising every element to the power of two. Therefore in normal basis,

Frobenius endomorphism can be computed very efficiently 11. Frobenius map ? is an endomorphism that raises

every element to its power of two, therefore, Frobenius maps cost or depending

on the coordinate system. Notice that squaring is cheap, as squaring in with NB

is only a cyclic shift of the bit vector.