Research On The Effiency And Security Of Elliptic Curve Scalar Multiplication Algorithm

Elliptic curve scalar multiplication is the core operation and security foundation of theelliptic curve cryptosystem, the efficiency and security of the scalar multiplication algorithm isgetting more and more attention of the researchers. Traditional efficient elliptic curve scalarmultiplication algorithm has some weaknesses, making it is vulnerable to Side-Channel Attacks（SCA） and Fault Analysis Attacks （FAA）. Then a lot of countermeasures with expense ofefficiency to these attacks have been proposed. Among them, some algorithm-levelcountermeasures can resist all of the SCAs and FAAs so far. However, these secure elliptic curvescalar multiplication algorithms don’t have any advantages in efficiency. This thesis focuses onhow to improve the algorithms’ operational efficiency as much as possible while guarantee thealgorithms’ security, also proposes a new method called Bug Attack to attack cryptosystemswhich use secure elliptic curve scalar multiplication algorithms. The main results are as follows:Firstly, we propose using higher radix positional numeral system to express the scalar in thesecure elliptic curve scalar multiplication algorithms. A new secure elliptic curve scalarmultiplication algorithm based on ternary representation is presented. This thesis analyzes thecorrectness and the complexity of the new algorithm, and also compares the efficiency betweenthe new algorithm based on ternary and traditional algorithm based on binary. The result showsthat the efficiency of the algorithm based on ternary is improved by approximately21.7%inprojection Jacobian coordinates.Secondly, the general base-m positional numeral system is used to represent the scalar ofsecure elliptic curve scalar multiplication algorithm. After discuss the correctness of thisalgorithm, we analyze the relationship between the running time of the algorithm and the base mand give a function g（m, n） to represent the running time of the algorithm, in this function, m isthe radix and n is the order of the elliptic curve points group. It reveals that the time complexityof the algorithm is O（mlog2m）. Based on the function g（m, n）, the thesis discusses the relation-ship between g（m, n） and m in different security parameters n. It proves that, for any securityparameter n, there is always an optimal radix m_optso that the secure algorithm has the shortestrunning time. At the same time, we analyze the characteristics of m_optand find that m_optis afunction h（l） where l is the binary length of the security parameter n. The result shows that withthe increase of security parameter n, the m_optalso tends to be greater. Then this thesis analyzesthe m_optof the NIST standard elliptic curves, and compares the efficiency between the algorithmbased on m_optand the algorithm based on binary, the result shows that the efficiency is improvedby at least25.64%.Thirdly, for considering the application of the secure elliptic curve scalar multiplicationalgorithm, we propose a method called Bug Attack to attack the IEEE P1363a standard ECIESencryption scheme. The analysis shows that this attack is feasible for the standard ECIESencryption scheme which use the secure elliptic curve scalar multiplication algorithm, especiallyfor the devices which are resource-constrained such as smart card. Then we propose somecountermeasures to the Bug Attack in hardware and software, and analyse the advantages and disadvantages of them.