INTRODUCTIONONB Operations in ECCElliptic CurvesBasic Operations in ONBDefinition of ONB:Final StageFigure 8. FSM of inverseTEST ENTRYSynthesis resultsCONCLUSION1Implementation of the Optimal Normal Basis Operations in Elliptic Curve Cryptography in VIVA Chang Shu Abstract—The aim of this project is to implement the operations of Elliptic Curve Cryptography built over GF(218) represented with optimal normal basis in VIVA System. These operations include multiplication, inverse, point addition, point doubling and scalar multiplication. The target device is Xilinx 4062 embedded in the FAI board of HAL-15 hypercomputer. The synthesis results using VIVA and VHDL are compared at the end of this report and a conclusion is drawn from comparison. Index Terms— Elliptic Curve Cryptography (ECC), optimal normal basis (ONB), multiplication, inverse, point addition, point doubling, scalar multiplication, VIVA, FPGA I. INTRODUCTION LLIPTIC Curve Cryptography is a kind of public key scheme. Compared with RSA and other public key system, ECC could provide the same strength of security with fewer bits. There exist three classes of elliptic curves. One is built over GF(p). The other two are built over GF(2n) represented with polynomial basis or normal basis which are easy for fast and compact hardware implementation. For this project, the optimal normal basis operations with 18-bit length are implemented in VIVA system. These operations include multiplication, inverse, point addition, point doubling and scalar multiplication. [1]VIVA can be used as the development environment that can be defined in a system description. A system description defines the physical attributes and resources of a computing platform. In VIVA system, a high-level system description is stored in a system description file with an .sd file extension. VIVA is targeted at Reconfigurable Computing (RC) hardware platforms. Usually RC hardware platforms are built on Field Programmable Gate Arrays (FPGAs). Hypercomputers are the most comprehensive RC platform. A hypercomputer contains one or more FAI boards. A FAI board contains some FPGA chips associated with communication buses, memories, I/Os and multi-clocks. The System description of FAI board is contained in the file FAI.sd. HAL-15 is a kind of hypercomputer and its FAI.sd contains 10 FPGA subsystems. They are XPoint and PE1 through PE9. These subsystems represent the resources and structures that the FPGAs on the FAI board contain. All VIVA behavior is mapped to the logics of these FPGA. The VIVA behavior description is schematic. Users can use the objects provided in VIVA such as gates, registers, and so on for behavior description and can also convert the behavior sheet to a new object for further use. So hierarchy and object-oriented are the features of VIVA system. During the build process, VIVA performs a formal recursive synthesis on all application objects and expands complex variant objects to gate logics. The additional library is metalib defined in VIVA. Metalib includes most basic logic objects such gates, registers, multiplexer and so on for schematic descriptions. II. ONB OPERATIONS IN ECC A. Elliptic Curves Given a field K and an equation of the form[2]y2+a1xy+a3y=x3+a2x2+a4x+a6 (1) where the parameters a1,a2,…a6∈K. An elliptic curve E defined over is the set E(K) of all the solutions (x, y) ∈(KxK) of this equation with a special point called point at infinity O, where (x, y) is called points of the curve. Definition of point addition: Given the equation of elliptic curve y2+xy=x3+a2x2+a6, where a2∈{0, 1}, a6∈K, and two different points P(x1, y1) and Q(x2, y2) on the elliptic curve, the sum of P and Q, i.e. (x3, y3) is also a point on the curve whose coordinates satisfy the following equations: 131322123)( yxxyaxxx++≡++++≡λλλ⎩⎨⎧++=1212xxyyλ(2) Definition of point doubling: Given the same elliptic curve and a point P(x1, y1) on the curve, 2P=(x3, y3) is also a point on the curve whose coordinates satisfy the following equations 3311112132121163)()(xxxyxxyxxax+++≡+≡−−(3) E2 Definition of scalar multiplication: Given the same elliptic curve, a point P(x1, y1) on the curve and a large positive integer k, kP is also a point on the curve, where kP=P+P…+P. The hierarchy of operations in ECC Scalar multiplication includes point addition and point doubling. Point addition and point doubling include multiplication, squaring and inverse. Projective coordinate and affine coordinate According to the equations in optimal normal basis (4), 1222 −−=⇒= aaaannInverse could be performed with some multiplications. Since multiplications is timing costly, the times performing inverse should be as few as possible. The solution of eliminating intermediate inverse when computing scalar multiplication (i.e. no inverse is performed in point addition and point doubling) is to introduce projective coordinate, i.e. the point on elliptic curve is represented with ( x, y, z) instead of (x ,y) where x, y and z∈K, y’=zy, x’=zx. And the equation becomes: y2z+xyz=x3+a2x2z+a6z3 (5) The previous coordinate is called affine coordinate. The hierarchy of operations in ONB is shown as following: Scalar Multiplication Point Addition Point Doubling Inverse Multiplication Squaring Figure 1. The hierarchy of operations in ONB using projective coordinates B. Basic Operations in ONB Definition of normal basis: An (ordered) basis N of K=GF(2n) is said to be normal if it is of the form 122,...,,−nβββNormal basis representation: (6) ∑−=∈=102)1,0(,niiieeEiβ Basic Addition (in GF(2n)) is one-bit to one-bit xor for normal basis representation, so it’s easy for hardware implementation and little time costly. Squaring: In normal basis, we have two facts: (A+B)2=a2+b2, AAn=2),...,,()()()(210120211022102211−−−=−−=−==+===∑∑∑++nnniinniiniieeeeeeeeEiiiββββ (7) So operation of squaring in normal basis representation can be implemented with one cycle shift. e0 e1 en-1 Figure 2. Square Definition of ONB: ),...,,(110 −=naaaA; ),...,,(110 −=nbbbB ),...,,(110 −==ncccABC ∑∑−=−==1010)0(0ninjjiijbacλ [5]∑∑−=−=++=1010)0(ninjkikiijkbacλ, (8) )1,0()0(∈ijλAn (ordered) basis N of K=GF(2n) is said to be optimal normal basis if the number of item of aibj in ck is 2n-1. And there are 2 types optimal normal basis, i.e. Type I and Type II. For
View Full Document
Unlocking...