1. Preliminariesand Literature Review1.1. IntroductionN.

Koblitz 1 and V. Miller 2 have introduced Elliptic CurveCryptography (ECC) for a public-key cryptography. ECC provides same level ofsecurity with smaller key sizes which lead to a better performance inperforming encryption and decryption algorithm.

In other word, the interest inthe ECC is growing because the implementations of ECC have produced betterperformance in term of calculation time, processing time, power consumption andmemory usage. There are many schemes work based on elliptic curves such as keysexchange, encryption/decryption and digital signature. The security of ECC schemes is based on theresolution of an underlying mathematical problem called the Elliptic CurveDiscrete Logarithm Problem (ECDLP) which is very hard to solve. In ECC, publicand private keys allows encryption and decryption the cryptographic system.Locking and unlocking algorithms are based on point multiplications. Thisoperation is considered as the basis of any ECC structure.

Point multiplicationhas been implemented based on the basic operations of point addition anddoubling. These two operations are implemented based on finite-fieldsarithmetic. The figure 1 illustrates these dependencies. Fig.

1. Layersof Point multiplication implementationThere are several forms of elliptic curves used in ECC such as theWeierstrass, Hessian and Edwards and kolbitz curves. Each curves has differentcharacteristics.

Koblitz curves 27 are a family of curves on which pointmultiplication is noticeably faster than on other curves and also it can be computed very efficiently in hardware. Points on elliptic curves can be representedby different coordinate systems. There are many coordinate systems like Affine,Projective and mixed coordinates are in ECC for number representation. Thechoice of the curve and point coordinate system are very important and have asignificant effect on the performance of the elliptic curve arithmeticoperations. In fact, point multiplication operations can be accelerated andsecured when efficient representation of elliptic curve points is used. In thefollowing sections, we review mathematical background needed for the ellipticcurve cryptography which are categorized below:1.

Finitefields. 2. Implementationof the field operations 3. EllipticCurves over 4. Implementationof the point multiplication algorithm.

1.2. FiniteFieldsA Finite Field contains of a Finite set of objects called fieldelements together with the description of two operations, Finite Fieldarithmetic plays an important role in ECC and all the low-level operations arecarried out in these Fields. Finite fields regularly used in cryptography areeither prime fields or binary filed.

1.3. BinaryFields 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 abasis. As the two elements of can be represented with a bit, bits are required to represent elements of.

Addition oftwo elements in is simply performed but the multiplicationdepends on the Field basis and dependencies between the Field elements. Finitefields regularly used in cryptography are either prime fields or binary filed.These fields has been used in conventional hardware and software applicationsand recommended by the international standards such as IEEE and NIST. Normal basis is the most efficient Field as it is offering free squaring in hardwarearchitecture 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 forour implementation.

1.4. NormalBasis It is shown that there exists a normal basis for the binaryextension field for allpositive integers . The normalbasis is constructed by finding a normal element, where ? is aroot of an irreducible polynomial of degree m Then set N= is a basis for and its elements are linearly independent. Inthis 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 NIST41 standards for the Elliptic Curve Digital Signature Algorithm (ECDSA) andexists whenever is not divisible by 8 31. For such a givenm, there always exists a type , , GNB. Type TGNB provides low complexity multiplication as compared with other normal basesover.1.5. Implementationof the Binary field operationsHere, we review the basic field operations in a binary field.Specifically, the operations of addition, multiplication, squaring andinversion are reviewed with their Implementation in over GNB.

1.5.1.

FieldAdditionAddition of two field elements, say, where are in can be obtained by pair-wise addition of thecoordinates of and over .Thus, this isa simple addition of each linearly independent digit. Each digit is representedas a single bit and there are no carries. The identity element of addition, i.

e., 0, is (0, 0, · · ·, 0, 0).1.5.

2. FieldSquaringFinite-field squaring performs, where where are in. Squaringoperation is performed by right cyclic shift of the coordinates of:It is free in hardware if all coordinates are available inparallel.1.5.3.

FieldMultiplication Let A and B be elements in in, and assumetheir product is , .Then, we canobtain 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 inputoperands 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-levelmultipliers in which the digit size can be chosen depending on the amount ofthe resources available. There are some Low-complexity GNB multipliers havebeen 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. FieldInversionInversion for a given element, finding anelement such that , is consideredan expensive operation. It is commonly required in cryptographic applicationsof finite fields and its efficient implementation is important. Based on FermatLittle Theorem, an inversion can be calculated by the inversionbased on Fermat’s Little Theorem uses consecutive squaring and multiplicationand is more suitable while field elements are represented by normal basis.

Thecomplexity of it can be further reduced by using the Itoh-Tsujii method. InItoh and Tsujii algorithm (ITA) 4, the number of multiplications is reducedbased on decomposing Itoh-Tsujiireduces the complexity of the exponentiation to squarings and the Hamming weight of (m-1)multiplications, 1.6.

BinaryKoblitz curvesThe most standard binary ellipticcurves is called Binary Weierstrass curves (BWCs) and the curve is defined byfollowing equationIn this equation: and . This equationis suitable for cryptographic applications. For this family of curves, NISTrecommended standard elliptic curves over fields consist of {B-163, B-233, B-283, B-409and B-571}. In following point addition and point doubling on BWCs in affinecoordinate 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 andpoint doubling are computed by , where , and are cost of computation field inversion, fieldmultiplication and field squaring respectivelyIn the binary Weierstrass curves if and , it is calledKoblitz curves 11. Therefore, the Koblitz curves are defined over by following equation:Koblitz curves offer considerable computational advantages comparedto the binary Weierstrass curves. They have special attractiveness amongelliptic curves, because point doublings can be replaced by efficientlycomputable Frobenius endomorphism 27.

Mapping in Frobenius endomorphism is performedby 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 raisesevery element to its power of two, therefore, Frobenius maps cost or dependingon the coordinate system. Notice that squaring is cheap, as squaring in with NBis only a cyclic shift of the bit vector.