11Implementing Elliptic Curve CryptographyImplementing Elliptic Curve CryptographySarah MiersMay 3,2001Sarah MiersMay 3,20012Three Classes of Elliptic CurvesK=GF(p) K=GF(2m)Polynomial BasisNormalBasis23ContentsContents•Mathematical Background•Implementation•Results4Mathematical BackgroundMathematical Background35Normal Basis RepresentationA normal basis in GF(pm) can be formed usingthe set:{ }where β is an element in the field.Each element ε in the field can be represented as:6Squaring a Normal Basis Numberβ( )2mββ( )2t2β2( )t11.2.Squaring is equivalent to a rotationx y x y47Multiplying in a Normal Basis (1)Multiply two number A and B to find C=ABA=02m1i.aiβ( )2iB=02m1i.biβ( )2iC=02m1i =02m1j...aiβ( )2ibjβ( )2i8Substituting.β( )2iβ( )2j=02m1k.λijkβ( )2kYieldsCk=02m1i =02m1j..λijaibjMultiplying in a Normal Basis (2)59ImplementationImplementation10Menezes-Qu-Vanstone (MQV)Key Agreement Scheme•Prevents the man in the middle attack•Performs authentication of key holders•Cracking one message does not provide an an advantage in cracking the next message611Select BaseCurve & PointCreate private& public keysCreate Ephemeral dataAuthenticateSecret12Selecting a Base CurveSelecting an equation of the form:y2..a1xy.a3y x3.a2x2.a4x a6713Determining a Base Point Determining a base point P=(x,y) requires Selecting an x and then solving the followingequation for yy2xy x3.a2x2a614Solving the Quadraticy2xy x3.a2x2a6z2z cSubstitute y=xz and multiply by x-2Substitute c for the value of the terms on theright side of the equation orZ Z12c12815The point exists if the Trace(C) equals 0Where the trace of C is defined asfollowsDetermining if the point existsTrace( )c c c2c22c23... c2m 116Creating Private and Public KeysGenerating a public key Y involves computing a new point on the elliptic curve using theprivate key x and the base point PY=xP The ephemeral key is generated in the samemanner.917Computing elliptic multiplicationx3λ2x1x2y3.λx1x3y1Y=xP = P+P+P+P…Where the point P is added to itself X timesCompute R=(x3,y3) = P+Q where P and Qare points (x1,y1) and (x2,y2) respectivelyas follows:λy2y2x2x1P Qλ.3 x12a2.2 y1PQ18Speeding up the MultiplicationUsed balanced representation to speed upthe multiplicationExample:15P....2 P 2 2 2P1019Operations involved in keygeneration•2 elliptic multiplication20Authenticating the SecretAssume: The two public keys and the two ephemeral keys to be:K=(x,y) and E =(u,v) where K=dP and E=kPfor both A and BAuthenticate the secret by:mod 2m1.2.W EB..xBuBKB3.S.s Ws kA..xAuAdA1121Why Authentication WorksS.s WS.kA..xAuAdAEB..xBuBKBBegin with S:Substitute for s and W:Substitute for E=kP and K=dP:S..kA..xAuAdAkB..xBuBdBP22Operations involved inAuthentication•Two elliptic multiplications•One elliptic sum•Miscellaneous scalar operations1223ResultsResults24Timing results for various keysizes using a normal basis051015202530Seconds83 95 134 155 270 338 386 466BitsPublic Key GenerationAuthenticating Secret1325Timing results for various keysizes using polynomial basis0123456789Seconds33 64 79 93 134 155Bitspublic key generationsecret authentication26Comparing Normal basis andPolynomial Basis Timing0123456789Seconds134 155BitsNormal BasisPolynomial Basis1427Percent of time required tocomplete algorithm stepsParameter GenerationCreating Base PointCreating keysAuthenticating Secret28Problems Encountered•It’s difficult to obtain an exact comparison of the timing results for polynomial and normal basis operations since system default parameters in each care are different •Since the code was built without the aid of optimized libraries, the timing statistics should not be considered optimal1529Conclusions•Elliptic multiplies using a Normal Basis are significantly faster than elliptic multiplies using a Polynomial Basis•The length of time to compute elliptic multiplies increases quadratically with the key size•Elliptic multiplication plays a key role in the amount of time it takes to perform key exchange and verification
View Full Document
Unlocking...