Cryptanalysis of RSA Using Algebraic And Lattice Methods

Author : Glenn Durfee, Computer and Network Security Researcher, Palo Alto Research Center
Publication Date : June 2002

Excerpts from the Preface:

We study the security of public key cryptosystems. In particular we study the RSA public key cryptosystem and several variants. We obtain our results using tools from the theory of integer lattices.

We begin with an introduction to the theory of integer lattices and describe the main results to be used throughout the rest of the work. We then review the concept of a public key cryptosystem and in particular the RSA public key cryptosystem. Next we introduce a novel algorithm for the factorization of class of integers closely related to those used by RSA and other public key cryptosystems in the literature, showing that a new class of integers can be efficiently factored. We go on to introduce new attacks on the RSA public key cryptosystem which use partial knowledge of a user's secret key, showing that leaking one quarter of the bits of the secret key is sufficient to compromise RSA. Next we describe new attacks on the RSA public key cryptosystem when a short secret exponent is used. Lastly, we describe the three Sun-Yang-Laih key generation schemes for RSA, and introduce attacks to break two of these schemes.

View/Download Cryptanalysis of RSA Using Algebraic And Lattice Methods