Cryptanalysis of RSA with private key \(d\) less than \(N^{0. 292}\) (Q4250748)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 1304060
Language Label Description Also known as
default for all languages
No label defined
    English
    Cryptanalysis of RSA with private key \(d\) less than \(N^{0. 292}\)
    scientific article; zbMATH DE number 1304060

      Statements

      Cryptanalysis of RSA with Private Key d Less than N 0.292 (English)
      0 references
      Cryptanalysis of RSA with private key \(d\) less than \(N^{0. 292}\) (English)
      0 references
      0 references
      0 references
      26 November 2000
      0 references
      cryptanalysis
      0 references
      RSA cryptosystem
      0 references
      public key
      0 references
      small inverse problem
      0 references
      Consider an RSA cryptosystem with public key \((N,e)\), where \(N= pq\) \((p,q\) primes) is the module and \(e\) the exponent for enciphering. Furthermore, let \(d\) be the corresponding private exponent for deciphering and suppose that \(d< N^\delta\). In 1990, \textit{M. J. Wiener} [IEEE Trans. Inf. Theory 36, No. 3, 553--558 (1990; Zbl 0703.94004)] showed that if \(\delta< 0,25\) then the RSA system can be broken. In the present paper, the first substantial improvement to Wiener's result is given: The authors show that as long as \(\delta< 0,292\) one can efficiently break the system. This is done by reducing the problem of breaking the RSA system to the so-called ``small inverse problem'' which can be stated as follows: For \(A= (N+1)/2\) and \(e\) as above find integers \(k\) and \(s\) satisfying \(k(A+s)\equiv 1\pmod e\) where \(|s|< e^{0,5}\) and \(|k|< e^\delta\). The small inverse problem is solved by the authors for \(\delta< 1- \frac 12 \sqrt{2}\approx 0,292\) and they conjecture that their approach can be used for \(\delta< 0,5\). For the entire collection see [Zbl 0912.00038].
      0 references

      Identifiers