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
26 November 2000
0 references
cryptanalysis
0 references
RSA cryptosystem
0 references
public key
0 references
small inverse problem
0 references
0.9406976699829102
0 references
0.887945830821991
0 references
0.872898280620575
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