×

Remarks to short RSA public exponents. (English) Zbl 0938.94012

Summary: The authors discuss pertinent questions closely related to the well-known RSA cryptosystem. From the practical point of view it is reasonable to use as a public exponent an integer \(s=2^k+1\), i.e., so-called short exponent, with the lowest possible binary weight. The most common are for \(k=1\) and \(k=2^4\), the two Fermat primes. In this paper they prove two theorems which give a percentage of acceptable public exponents \(s=2^k+1\), \(1\leq k\leq 1023\) to two randomly selected primes of 512 bits each. In fact, the results are valid for arbitrary set of exponents \(s\).
The authors also present results of their experiments. In the 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 not to use short public exponents, by their observation to use the attack based on continued fractions is infeasible.

MSC:

94A60 Cryptography
68P25 Data encryption (aspects in computer science)
PDFBibTeX XMLCite