The DOI matches its Crossref record; 7 of the 7 references it cites were found in a registry or an index.
Cryptanalysis of short RSA secret exponents
Abstract
A cryptanalytic attack on the use of short RSA secret exponents is described. The attack makes use of an algorithm based on continued fractions that finds the numerator and denominator of a fraction in polynomial time when a close enough estimate of the fraction is known. The public exponent e and the modulus pq can be used to create an estimate of a fraction that involves the secret exponent d. The algorithm based on continued fractions uses this estimate to discover sufficiently short secret exponents. For a typical case where e>pq, GCD(p-1, q-1) is small, and p and q have approximately the same number of bits, this attack will discover secret exponents with up to approximately one-quarter as may bits as the modulus. Ways to combat this attack, ways to improve it, and two open problems are described. This attack poses no threat to the normal case of RSA where the secret exponent is approximately the same size as the modulus. This is because the attack uses information provided by the public exponent and, in the normal case, the public exponent can be chosen almost independently of the modulus.>
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
The Art of Computer Programming
Knuth, D. E. (1968) · Cited by 15,999
A method for obtaining digital signatures and public-key cryptosystems
Rivest, R. L., Shamir, A., & Adleman, L. (1978) · Communications of the ACM · doi:10.1145/359340.359342 · Cited by 13,462
A method for obtaining digital signatures and public-key cryptosystems
Rivest, R. L., Shamir, A., & Adleman, L. (1983) · Communications of the ACM · doi:10.1145/357980.358017 · Cited by 13,012
The Art of Computer Programming. Volume 2: Seminumerical Algorithms.
Taussky, O., & Knuth, D. E. (1970) · The American Mathematical Monthly · doi:10.2307/2317055 · Cited by 3,822
The Art of Computer Programming
Worlton, W. J. (1968) · Nuclear Science and Engineering · doi:10.13182/nse68-a19548 · Cited by 2,251
Theorems on factorization and primality testing
Pollard, J. M. (1974) · Mathematical Proceedings of the Cambridge Philosophical Society · doi:10.1017/s0305004100049252 · Cited by 402
N Using RSA with Low Exponent in a Public Key Network
Håstad, J. (2007) · Springer eBooks · doi:10.1007/3-540-39799-x_29 · Cited by 115
Cited by
Handbook of applied cryptography
(1997) · Choice Reviews Online · doi:10.5860/choice.34-4512 · Cited by 10,357
Collision-Free Accumulators and Fail-Stop Signature Schemes Without Trees
Barić, N., & Pfitzmann, B. (1997) · Lecture Notes in Computer Science · doi:10.1007/3-540-69053-0_33 · Cited by 557
Cryptanalysis of RSA with private key d less than N/sup 0.292/
Boneh, D., & Durfee, G. (2000) · IEEE Transactions on Information Theory · doi:10.1109/18.850673 · Cited by 391
The Two Faces of Lattices in Cryptology
Nguyen, P. Q., & Stern, J. (2001) · Lecture Notes in Computer Science · doi:10.1007/3-540-44670-2_12 · Cited by 252
Metadata
- Authors
- Wiener, M. J.
- Venue
- IEEE Transactions on Information Theory
- Published
- 1990-05
- Volume
- 36
- Issue
- 3
- Pages
- 553-558
- ISSN
- 0018-9448 (ISSN-L)
- OpenAlex
- W2166780626
- Cited by
- 698
- References
- 7
- FWCI
- 4.77
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.