Remarks to short RSA public exponents - Grošek, Otokar; Nemoga, Karol; Satko, Ladislav (Annales Mathematicae Silesianae, 1998)
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.