RSA Lattice Attack Method for Discrete Private Key Bit Leakage
Liu Xiang-hu · Jisuanji gongcheng · 2014
RSA algorithm is one of the most widely used public key cryptosystems at present and lattice attacks play an important role for the analysis of RSA system.The problem of partial discrete private key bit leakage is transformed into the solution of multivariate linear congruence equations and a special lattice is constructed.And then by the lattice reduction algorithms such as LLL algorithm,the small roots of multivariate linear congruence equations can be obtained with a high probability.Based on the above technology,this paper proposes a lattice attack method on RSA for discrete private key bit leakage.With this method,if the public parameter satisfies e=N~β≤N~(1/2) and the unknown part of private key d satisfies N~α N~(1/2-β),it can recover the private key d with a high probability.The experiment on1 024 bit number is given with NTL package and the results verify the availability of the attack method.