DOC PREVIEW
MASON ECE 646 - The Project Specifications

This preview shows page 1 out of 4 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 4 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 4 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

The Project Specifications ECE 646 Cryptography and Network Security Instructor: Kris Gaj Author: Chang Shu Title: Implementation of the optimal normal basis operations in Elliptic Curve Cryptography in VIVA Design entry method The operation is described in schematic. The target hardware is Star Bridge Systems. The developing tool is VIVA. Additional Library The additional library is metalib defined in VIVA. Metalib includes most of basic logic objects for schematic description. A system description file, FAI.sd, is also necessary in which the physical attributes and computing resources are defined. Description of elliptic curve cryptography It is a public-key cryptography based on cubic equations that usually take the form: edxcxxaxyy +++=+232. ECC is defined over finite field such as GF(p) or GF(2n.) GF(p) contains p elements where p is a prime. GF(2n) contains 2n elements and each element is an n-bit string. Different elliptic curves are chosen according to different finite field. For GF(2n): 6232axaxxyy ++=+ The operations in ECC (GF(2n)) Considering the equation 6232axaxxyy ++=+ (1) P Q 131322123)( yxxyaxxx++≡++++≡λλλ ++=1212xxyyλ (1) (2) P=Q 3311112132121163)()(xxxyxxyxxax+++≡+≡−−(2) 1. Addition in ECC includes multiplication, squaring, and inversion 2. Doubling includes multiplication, squaring and inversion 3. Scalar multiplication includes doubling and addition Hardware implementation The addition and multiplication in GF(p) is time costly. So GF(2n) is selected for hardware implementation. Each element in GF(2n) is a binary string whose length is n.In this project, normal basis representation is selected. Normal basis: ∑−=∈=102)1,0(,niiieeEiβ Basic Addition (in GF(2n)) is one-bit to one-bit xor for both 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ββββ (3) So operation of squaring in normal basis representation can be implemented with one cycle shift. Figure 1 Multiplication in optimal normal basis representation (TypeII) ),...,,(110 −=naaaA ; ),...,,(110 −=nbbbB ),...,,(110 −==ncccABC ∑∑−=−==1010)0(0ninjjiijbacλ ∑∑−=−=++=1010)0(ninjkikiijkbacλ, )1,0()0(∈ijλ (4) njimod122±≡±, 1)0(=ijλ else 0)0(=ijλ So the multiplication could be implemented with only one logical function after n cycle shifting c0,c1…cn-1 Figure 2 e0 e1a0 a1b0 b1 Logical FunctionInversion in optimal normal basis representation (Type II) Fact: 1222 −−=⇒=aaaann Itoh’s method: =−=−===+−+−+−−−−−−−−evennaoddnaaaannnnnn1,1,)1)12)(12(2(2)12)(12(2)12(2221222221211 So one can get the inversion of any elements through some squarings and multiplications. Addition in ECC P+O=P P=-Q, P+Q=O If P Q, the addition includes one inversion, two multiplications and one squaring according to formula(1). Doubling in ECC If P=Q, the doubling includes one inversion, three multiplications and two squarings according to formula(2). Scalar multiplication in ECC k is a large integer denoted by a n-bit string )...,(110 −nkkk. In each cycle, a doubling operation will be done, if ki is equal to 1, an addition in ECC will be executed. So it will cost [log2k] doublings and w(k)-1 additions to complete a scalar multiplication in ECC ( w(k) is the hamming distance of k). Each doubling has two inversions, each addition has one inversion, and each inversion has many multiplications. Using projective coordinate, we have just one inversions at the end of computation rather than process one or two inversion for each addition or doubling. So the times of multiplications will be reduced. I/O specifications Different operations have different I/O. Simulation and test environment The simulation environment is VIVA and Star Bridge System, test vector will be generated by some existing software. Plan of this project Implement the basic operations, such as multiplications, inversions Implement addition in ECC Implement doubling in ECC Implement scalar multiplication in ECC Projective coordinate operation * I will try to implement multiplication, inversions, addition, doubling. If I haveenough time, I will finish the rest two operations for the course project. Uncertain points The choice of n for GF(2n) Bibliography [1] Constantinos Dovrolis, Kris Gaj, EE492-Sprint 1996, Department of Electrical Engineering, University of Rochester [2] R.C. MULLIN, I.M. ONYSZCHUK and S.A. VANSTONE, R.M.WILSON, Optimal Normal Basis in GF(2n), Discrete Applied Mathematics 22(1988/89) 149-161, North-Holland, Department of Combinatories and Optimization, University of Waterloo, Canada N2L 3GI. Department of Mathematics, California Institute of Technology, Pasadena, CA 91125, USA [3] Soonhak Kwon1, Heuisu Ryu2, Efficient Bit Serial Multiplication Using Optimal Normal Bases of Type II in GF(2m), 1Institute of Basic Science, Sungkyunkwan University, 2Electronics and Telecommunications Research Institute. [4] Soonhak Kwon, A Low Complexity and a Low Latency Bit Parallel Systolic Multiplier for GF(2m) Using an Optimal Normal Basis of Type II, 1Institute of Basic Science, Sungkyunkwan


View Full Document

MASON ECE 646 - The Project Specifications

Documents in this Course
Load more
Download The Project Specifications
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view The Project Specifications and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view The Project Specifications 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?