Lattice-Based Cryptanalysis Of RSA And Its Variants

The RSA algorithm is a widely used public-key cryptosystem,which has far-reaching influence in the field of public-key cryptography.With the development of lattice theory and the introduction of the LLL algorithm,lattice-based cryptanalysis has gradually become an important mathematical tool for studying the security of public-key cryptographic algorithms.By considering the algebraic relationship contained in the public and private keys,the lattice-based cryptanalysis of RSA transforms its security analysis into extracting small roots of modular or integer equations in polynomial-time.In this dissertation,we apply the lattice-based technique and its optimized analytic techniques to investigate the security analysis of RSA and its variants.We extend,improve and optimize the previous analytic results.We summarize a new problem and present our research results at the same time.The main achievements and innovations of this dissertation are described as fol-lows:1.For the standard RSA with small encryption exponent,we apply the linearization technique to solve a trivariate modular equation and obtain new extended analytic results of small exponent attack.Our method overcomes the drawback of previ-ous works and makes small decryption exponent attack applicable to arbitrary small encryption exponents.2.For the PP-RSA variant with multiple pairs of encryption and decryption expo-nents,we obtain new extended analytic results of small exponent attack by solving specific simultaneous modular equations and applying the exponent optimization technique.Our method considers more pairs of encryption and decryption expo-nents,therefore we further improve the previous results.3.For the MEQ-RSA variant with modified Euler quotient,we give the precise range of the applicable encryption exponent.Moreover,we analyze the case when using multiple pairs of encryption and decryption exponents and obtain new ex-tended analytic results of small exponent attack by applying the Minkowski-sum technique to solve simultaneous modular equations.4.For the MP-RSA variant with the small prime difference,we point out that the factoring attack is more effective than small decryption exponent attack when the number of prime factors increases.Then we apply the integer method and the linearization technique to obtain the optimized analytic results,which improve the previous insecure bound of the prime difference.5.For the factoring general RSA moduli with known bits problem,we present a unifying solution by solving two specific bivariate integer equations.This solu-tion covers all previously known results and further gives the optimized analytic results of the insecure bounds.6.We propose a new problem on RSA called the implicit related-key factorization problem.It can be seen as a combination of the implicit factorization problem and the partial key exposure attack.By applying the splitting technique and the linearization technique,we transform the private key into a linear combination of several smaller unknown variables.Then we solve the modular equation to obtain the insecure bound of the implicit information.Our results can provide theoretical security requirements for the usage of implicit related-keys.