1Implementing Elliptic CurveCryptographyUsing Normal and Polynomial BasisECE 636Sarah MiersMay 3,20012ContentsI Introduction to Elliptic Curve Cryptography. 3II Introduction to the Elliptic Curve Project. 4III Introduction to Normal Basis 5IV Introduction to Polynomial Basis 6V Implementing Menezes-Qu-Vanstone (MQV) 7VI Results 9VII Conclusions 12VIII Testing Procedures 12ReferencesAPPENDIX3I. Introduction to Elliptic Curve CryptographyAs our digital communication applications diversify, so must our securityrequirements and algorithms. With the introduction of phone cards and personal accesssystems, our system requirements have been modified to require shorter response timesand smaller memory sizes. This can be quite difficult with cryptographic systems thatrequire large key sizes to satisfy security requirements. Because elliptic curvecryptography utilizes smaller key sizes while still maintaining the same security,implementing an elliptic curve cryptography system has become an attractive alternative.The variety of choices of curves available with elliptic curve cryptography also addsincreased security to the system.Elliptic curves are curves that are formed as a solution to the following equation:y2..a1x y.a3y x3.a2x2.a4x a6where x and y form field elements, which can be complex, real, integers, polynomials, ornormal basis. The field composed of points P=(xi,yi) which solve the above equationform the foundation of elliptic curve cryptography. For the purposes of discussion, thefield type will be limited to polynomial and normal basis.4II. Introduction to the Elliptic Curve ProjectThe goal of this project was to implement the Menezes-Qu-Vanstone keyagreement scheme using elliptic curves with both polynomial and normal basis. Thepurpose of this project was to gain an understanding of both polynomial and normal basiselliptic curve cryptography systems, how to implement them, and the timing issuesinvolved in such an implementation.The Menezes-Qu-Vanstone key agreement scheme was designed to performauthentication of key holders, and to prevent the man in the middle attack. Using thisscheme will prevent gaining information that will help crack a future message from beingobtained by cracking the current message. The Menezes-Qu-Vanstone key agreementscheme is a superset of the Diffie-Hellman protocol.The Menezes-Qu-Vanstone key agreement scheme consists of three basic parts;generating system parameters, creating public and ephemeral keys, and authenticating thesecret. The goal of this project was to understand what type of operations are required toimplement each of these operations, and to gain an understanding of where the majorityof time was spent during these operations. The relationship of the key size to time spentprocessing was studied, and a comparison of timing between normal basis andpolynomial basis operations was done.5III. Introduction to Normal BasisA normal basis in GF(pm) is a basis formed from the set containing the followingelements:Each element in the field can be expressed as a summation of elements found in this set.For example if A is an element in the field:A= 0m 1i.aiβpiMultiplying two elements A and B in the field is the same as solving the double sum:.A B= 0m 1i = 0m 1j...aibjβpiβpjThe greatest advantage to using the normal basis representation comes from the fact thatsquaring a normal basis number or taking the square root of a normal basis number is aseasy as rotating a number right or left. This can be shown from the following twoequations:βpi2βpi 1βpmβThe first relationship is a result of simple exponent operations, and the secondrelationship comes from the definition of a generating element.The trace (A) is defined to beTR( )A A ApAP2... Apm 1{}6IV. Introduction to Polynomial BasisA polynomial basis is a basis formed from elements of the form:= 0ni.aixiAll operations in a polynomial basis must be computed modulo an irreduciblepolynomial defined for that basis. An irreducible polynomial is a polynomial that canonly be factored using a polynomial of degree 0.Multiplying two elements A and B in the polynomial field consists of computing:.A B= 0n mk.CkxkwhereCkk.aibjand k = i+j for i between 0 and n and j between 0 and m. Like all operations in apolynomial basis multiplication must be computed modulo the irreducible polynomial.The trace for the polynomial basis is computed the same as it is for the normal basis, butagain it must be computed modulo the irreducible polynomial.7V. Implementing Menezes-Qu-Vanstone (MQV)The Menezes-Qu-Vanstone key agreement scheme was designed to prevent theman in the middle attack. It accomplishes this by passing a secret between two parties Aand B that the man in the middle doesn’t have the ability to understand, or to use as anaid in gaining information to understand future secrets. The Menezes-Qu-Vanstone keyagreement scheme consists of three basic parts; generating system parameters, creatingpublic and ephemeral keys, and authenticating the secret.Generating system parameters for MQV involves maintaining a predetermined setof elliptic curves, and generating a base point for a selected elliptic curve. If working in apolynomial basis an irreducible polynomial is also required. Determining a base point Pon an elliptic curve requires selecting an arbitrary X and solving the elliptic curveequation for Y. The elliptic curve equation may be simplified by substituting y=xz,y2..a1xy.a3y x3.a2x2.a4x a6and multiplying both sides of the equation by x-2 . The final result isz2z c0where c represents the value of the terms on the right hand side of the original equation.It is possible to determine if such a point P actually exists on the curve by checking if thetrace(C) equals zero, or by using Euler’s criterion. If the point exists, a solution may befound by using a brute force approach, or by using Euler’s criterion.MQV requires that each party have both a public and ephemeral key. Generating apublic key K involves computing a new point on the elliptic curve using the private keyx, and the base point P defined for the curve. The public key is determined using ellipticmultiplicationK.xP8Elliptic multiplication in this example is defined as adding the point P to itself x times.Computing R=(x3,y3) the sum of points P and Q where P=(x1,y1) and Q=(x2,y2) involvessolving the following equations.x3λ2x1x2y3.λx1x3y1whereλy2y1x2x1if P doesn’t equal Q andλ.3 x12a2.2 y1if P equals Q.Ephemeral keys are