Remarks to short RSA public exponents
Abstract
In this paper we discuss pertinent questions closely related to well known RSA cryptosystem [5]. From practical point of view it is reasonable to use as a public exponent an integer s = 2k+1, i.e., so called short exponent, with the lowest possible binary weight. The most common are for k = 1 and k = 24, the two Fermat primes. In this paper we prove two theorems which give a percentage of acceptable public exponents s = 2k+1, 1 ≤ k ≤ 1023 to two randomly selected primes of 512 bits each. In fact, our results are valid for arbitrary set of exponents s. We also present results of our experiments. In our simulation, for all such acceptable public exponents, the corresponding secret exponent t had a weight within the range of 451-567. Thus, although it is recommended in [8] not to use short public exponents, by our observation to use the attack based on continuos fractions is infeasible.
Keywords
RSA modulus; RSA exponents; short exponents
References
2. __________ „ Update 2.9 by S.S. Wagstaff, Jr., Sept. (1995).
3. J. Hastad, On using RSA with low exponent in a public key network, Lecture Notes in Computer Science, Vol. 218, Springer-Verlag, Berlin, (1986), 403-408.
4. J.J. Quisquater, C. Couvreur, Fast decipherment algorithm for RSA public-key cryptosystem, Electron. Lett., 18 (1982), 905-907.
5. R.L. Rivest, A. Shamir, L. Adleman, A method for obtaining digital signatures and public key cryptosystems, Commun. ACM., 21 (1978), 158-164.
6. S.A. Vanstone, R.J. Zuccherato, Short RSA keys and their Generation, J. of Cryptology, 8 (1995), 101-114.
7. G.J. Simmons, M.J. Norris, Preliminary comments on the M.l.T. Public-Key Cryptosystem, Cryptologia, 1 (1977), 406-414.
8. M.J. Wiener, Cryptanalysis of short RSA secret exponents, IEEE Trans. Information Theory. Vol. IT 36, (1990), 553-558.
Department of Mathematics, Slovak University of Technology Slovakia
Institute of Mathematics, Slovak Academy of Sciences Slovakia
Department of Mathematics, Slovak University of Technology Slovakia
The Copyright Holders of the submitted text are the Author and the Journal. The Reader is granted the right to use the pdf documents under the provisions of the Creative Commons 4.0 International License: Attribution (CC BY). The user can copy and redistribute the material in any medium or format and remix, transform, and build upon the material for any purpose.
- License
This journal provides immediate open access to its content under the Creative Commons BY 4.0 license (http://creativecommons.org/licenses/by/4.0/). Authors who publish with this journal retain all copyrights and agree to the terms of the above-mentioned CC BY 4.0 license. - Author’s Warranties
The author warrants that the article is original, written by stated author/s, has not been published before, contains no unlawful statements, does not infringe the rights of others, is subject to copyright that is vested exclusively in the author and free of any third party rights, and that any necessary written permissions to quote from other sources have been obtained by the author/s. - User Rights
Under the Creative Commons Attribution license, the users are free to share (copy, distribute and transmit the contribution) and adapt (remix, transform, and build upon the material) the article for any purpose, provided they attribute the contribution in the manner specified by the author or licensor. - Co-Authorship
If the article was prepared jointly with other authors, the signatory of this form warrants that he/she has been authorized by all co-authors to sign this agreement on their behalf, and agrees to inform his/her co-authors of the terms of this agreement.
