Elliptic Curve Scalar Multiplication Secure Against Power Analysis Attack

Elliptic curve public cryptosystems have wide application in Smart card and embed-ded systems which have limited recourses. As an important part of physical security, sidechannel attack menace the security of these systems, and the power analysis attack is verysevere for the security of scalar multiplication on Elliptic curve. This dissertation investi-gates the basic types of power analysis attack; concludes the construction of secure scalarmultiplication against power analysis attack; proposes some secure countermeasures withthe algebraic construction of the scalar multiplication algorithms. The author obtainsmain results as follows:(1) The scalar multiplication under the power analysis attack is discussed. The coun-termeasures are concluded, the security of the elliptic curve scalar multiplicationagainst power analysis is analyzed with the consideration of provable security.(2) The security against power analysis attack of regular algorithm from left to right isanalyzed. The algebraic equation is educed, the scalar multiplication using only xcoordinate is proposed with Weierstrass form, the method of recovering y coordinateis also introduced.(3) The regular algorithm from right to left is analyzed. The algebraic equation iseduced, a fast algorithm is proposed on elliptic curve in GF(2m), the scalar multi-plication using only x coordinate is proposed with Weierstrass form.(4) An SPA resistant scalar multiplication based on the recoding of the scalar is pro-posed. The e?ciency of the new algorithm is guaranteed by fast Shamir's method,the algorithm from right to left is also developed.(5) A countermeasure to DPA with random point is proposed. A new method to updatethe random point is introduced to resist the doubling attack, the e?ciency of thenew algorithm is the same as that of the traditional method, it is also secure againstRPA and ZPA.(6) The algorithm of highest weight binary form of scalar is proposed, a new SPAresistant scalar multiplication is proposed based on HBF algorithm and fast Shamir'smethod. A new DPA resistant scalar multiplication is propose with introductionof random point, the new countermeasure is secure against RPA,ZPA and thedoubling attack.(7) The methods of randomizing the scalar are summarized. Three random splittingscalar methods are proposed, and three countermeasures to DPA are obtained, these methods are secure under the present power analysis attacks, and the e?ciency issame as that of the traditional method.