Research On Power Analysis Attack On Some Typical Public-Key Cryptosystems Implementations With Its Countermeasures

In practical applications,cryptographic algorithms are mostly implemented on chips and other hardware devices,such as smart cards,cryptographic keys,etc.These devices will produce time,power,electromagnetic radiation and other information when running the cryptographic algorithms.It is found that these information are closely related to the key and key operation in the cryptographic implementations.We refer to these information as side-channel information.Power or electromagnetic information is used to recover key or seek flaws,which is called power analysis attack.Aiming at cryptographic algorithm implementations,this type of attack is more threatening than traditional cryptanalysis,which is the focus of this thesis.In this thesis,we study the power analysis methods and countermeasures of public-key cryptosystems.In terms of power analysis methods,we propose a new combination attack method to break a specific RSACRT(Chinese Remainder Theorem,CRT)implementation by restoring a prime.Aiming at Elliptic curve signature algorithm,a method of recovering the base of a constant time modular inversion is proposed.This method can reveal the private key of the signature algorithm combined with the lattice attack.In terms of countermeasures,we propose a new fast scalar multiplication algorithm based on the affine coordinate system over binary fields.The algorithm resists the simple power analysis and collision attack,and reduces the modular multiplications of 12%.A new efficient and constant time modular inversion is proposed over prime fields.This method can reduce modular multiplications in nearly 90%.Meanwhile,we construct a multi side-channel attack platforms.Based on these platforms,effectiveness of proposed methods is verified by analyzing the implementations of certain cryptographic algorithms.Contributions are as follows:1.In terms of attack of RSA-CRT,we study a new combination attack.We propose a similar operation template attack(SOTA)inside the RSA-CRT algorithm and a new prime recovery procedure.Through the constructing templates on the power traces of known data,SOTA avoids the requirement of a profiling device.We find that the security of RSA-CRT implementation can be reduced to a hidden number problem over prime fields.Based on the problem and results of SOTA,we propose a new method to recover a prime involved in RSA-CRT.The research proves that this method is also suitable for the bit-flipping and multiplication blinding countermeasures.It can also quickly recover one secret prime even if 50% input data are noisy.Countermeasures to combination attack are also given in this thesis.2.In terms of combination attack on Elliptic curve based on signature algorithm,we study the lattice attack method of SM2(Shang Mi 2)signature algorithm and the security of constant time modular inversion.The lattice attacks on ECDSA(Elliptic Curve Digital Signature Algorithm)and SM2 signature algorithm are carried out by various experiments.It is verified that attacking SM2 requires more conditions than attacking ECDSA.We study the security of constant time modular inversion based on Fermat's little theorem.It is pointed out that under the Hamming weight leakage model,we can recover the base of the inversion which is considered as a resistance to side-channel attack.The study shows that,for ECDSA,we successfully restore the least significant byte of random number on which based we reveal the private key by combining lattice attack.For the SM2 signature algorithm,we obtain the whole private key through our base recovery method.3.In the implementation of Elliptic curve based cryptography,we propose an efficient and secure scalar multiplication and constant modulus inversion algorithm.We investigates the drawbacks of the existing efficient scalar multiplication algorithm against simple power analysis attacks over binary fields,and proposes a faster scalar multiplication implementation,which can reduce the modular multiplication by 12%.In this thesis,the characteristics of standard prime are studied,and an efficient constant time modular inversion algorithm over prime field is proposed.It is suitable for NIST and SM2 standard prime.The new algorithm saves nearly 90% modular multiplication and improves the computational efficiency nearly 2 times.4.In the practice of power analysis attack,we independently developed the software and hardware platform of power analysis,and based on this platform to evaluate the security of commercial products.The hardware platform supports the collection of power/electromagnetic emission of ISO7816,USBKey and smart phones.Typical power analysis methods are implemented on the software platform,which covers the mainstream cryptographic algorithms and Chinese SM series of algorithms.In this thesis,we presents a SOTA based CPA(Correlation Power Analysis)attack on the authentication protocol of 3/4G USIM(Universal Subscriber Identity Module).We collect electromagnetic emission on smart phone,and successfully implements the lattice attack of the SM2 signature algorithm.The above two practical security evaluations verify the effectiveness of the attack methods proposed in the thesis.