Partial Key Exposure Attack On CRT-RSA By Lattice-based Coppersmith's Method

In 1978,Rivest,Shamir and Adleman proposed the famous public key cryptosystem,RSA.Due to the wide applications of RSA,the security analysis of RSA has gradually become one of the hot spots in the cryptographic world.In 1990,Wiener proposed a small secret exponent attacks based on continuous scores.After the attack,considering the perspective of the small secret exponent attack against the RSA,CRT-RSA is proposed as a variant of the RSA.In 1996,Coppersmith proposed a lattice-based method for cryptanalysis of RSA.With the continuous efforts of other scholars,this method gradually formed a mature and complete research method.This paper systematically summarizes the Coppersmith's method for finding small solutions of multivariate modular polynomials,and introduces the strategies of construction of lattice,which include "Basic Strategy" and "Extended Strategy" proposed by Jochemsz and May.According to the Coppersmith's method,this dissertation studies partial key exposure attacks on CRT-RSA.The main results of the dissertation are as follow:1 For the case when the bit information of the private key is exposed in different places,it can also be understood that the exposed bit information can be divided into n blocks.At this point,the problem can be converted into finding small solutions of polynomial equations modulo p which has n+1 variables.By using concept of continuous helpful polynomials,we can reduce the dimension of lattice and shorten the running time,and when certain conditions are satisfied,the new attack result needs fewer exposed bits.Thus we can improve the known results.2 For the case when least significant bits of the private key are exposed,we can con-vert LSBs exposure problem into finding small solutions of polynomial equations modulo p or modulo eM which has double variables.Using a concept of helpful polynomials,we can reduce the dimension of lattice and shorten the running time,and when certain conditions are satisfied,the new attack result needs fewer exposed bits.