Research On Side Channel Analysis Of Elliptic Curve Scalar Multiplication Algorithms

The elliptic curve cryptosystem(ECC)in public key cryptography had attracted much attention since it was put forward in 1985.The elliptic curve cryptography represented by the SM2 series algorithm had been widely used in our country.As the key operation process,the safety of elliptic curve scalar multiplication algorithm was based on the elliptic curve discrete logarithm problem,whose complexity was exponential order.The order of complexity to attack this problem was exponential.The side channel analysis meant that the attacker attacked the cryptographic algorithm by using the leaked side channel information from the operation of the cipher,and restored the sensitive information such as plaintext and private key.This effective attack method avoided the difficulties of mathematical problems,which were encountered during the attacking of cryptographic algorithms,and was often used to attack block cipher algorithms,RSA algorithms,and ECC algorithms.The common side channel analysis methods included timing analysis,cache(Cache)analysis,power consumption analysis and fault analysis,etc.The power consumption information in cryptographic operations usually needed to be acquired by special equipment,and the research of power consumption was abundant.The method of cache analysis needed to access the cryptographic hardware,which was hard to be simulated with software.The experimental results showed that the side channel analysis method was effective in attacking ECC scalar multiplication algorithms.The differential fault analysis method,the algebraic fault analysis method and the timing analysis method,presented in this thesis,can recover the private key of ECC scalar multiplication algorithm in finite time.The ideal experimental data was obtained through the three attacks of software simulation.Whereas,it is infeasible in computing to analyze the discrete logarithm problem of elliptic curve based on ECC algorithm by using mathematical theory.In this thesis,the study of attacks on ECC scalar multiplication algorithms further illustrated that the side channel analysis can analyze the power of cryptographic algorithm in practice,and then can get the sensitive information,such as the private key.Accordingly,attention should be paid to avoiding the leakage of the side channel information in the practical applications.In this thesis,the corresponding defensive measures for the different side channel analysis methods were given respectively.The main contents of this thesis were summarized as follows:Firstly,based on the elliptic curve scalar multiplication algorithm,an improved differential fault analysis scheme was proposed.Those problem of "fault detection" and "zero block failure" were solved,which were existed in the general differential fault analysis scheme.Through software simulation,ECC binary left to right scalar multiplication algorithm,binary non-adjacent form(NAF)scalar multiplication algorithm and Montgomery(Montgomery)scalar multiplication algorithm were successfully attacked.Effective attacks were implemented on an ordinary PC,and a 256 bit private key took 185 minutes to restore.Secondly,based on the elliptic curve scalar multiplication algorithm,an algebraic fault analysis scheme was proposed.The fault was injected in the process of elliptic scalar multiplication algorithm,the algebraic equations were established,then the key was restored by solving the equation group.Through software simulation,ECC Comb scalar multiplication algorithm and window NAF multiplication algorithm were successfully attacked.Effective attacks were implemented on an ordinary PC,and a 256 bit private key took 13 minutes to restore.Thirdly,based on the elliptic curve scalar multiplication algorithm,an timing analysis scheme was proposed.There were differences in the use of elliptic curve scalar multiplication in time,so the private key can be recovered.Through software simulation,ECC binary left to right scalar multiplication algorithm was successfully attacked.Effective attacks were implemented on an ordinary PC,and a 256 bit private key took 188 seconds to restore.