On Mon, 26 Mar 2012, Thierry Moreau wrote:
Florian Weimer wrote:
* Thierry Moreau:
The unusual public RSA exponent may well be an indication that the
signature key pair was generated by a software implementation not
encompassing the commonly-agreed (among number-theoreticians having
surveyed the field) desirable strategies.
I don't think this conclusion is warranted. Most textbooks covering
RSA do not address key generation in much detail. Even the Menezes et
al. (1996) is a bit sketchy, but it mentions e=3 and e=2**16+1 as
"used in practice". Knuth (1981) fixes e=3. On the other side, two
popular cryptography textbooks, Schneier (1996) and Stinson (2002),
recommend to choose e randomly. None of these sources gives precise
guidance on how to generate the key material, although Menezes et al.
gives several examples of what you should not do.
The original RSA publication suggests generating the RSA modulus N, and then
the encryption and decryption exponents, resp. e and d, so that the first
selection of the public exponent e might be rejected.
The current recommendations fixes the decryption exponent, and then tries
random N until e mod phi(N) and d mod phi(N) are both >1. The current
"desirable strategies" encompass more provisions, of course.
That can't be correct, for several reasons:
- If you deterministically fix the decryption exponent in advance, then
everyone knows it. (Maybe you meant "choose d at random, and then find N
compatible with that choice of d." Still, I don't see why you would do
that, and if you did then there is no particular reason e would not come
out to be non-prime.)
- Maybe you meant to fix e in advance, and then find N compatible with
that value of e. But the check for compatibility is that gcd(e, phi(N))=1,
not that e mod \phi(N) > 1.
Going back to the original question, I see no reason why non-prime e
should be much less secure than prime e. In particular:
- The information leaked to the attacker is that gcd(e, \phi(N)) = 1. So
the attacker arguably learns a bit more information about the factors of N
if e is non-prime than if e is prime. But I don't see how this information
can be used to help speed up current factoring algorithms.
- Fix e = e1 * e2, where e1 ande2b are prime. Conditioned on the fact that
gcd(e, phi(N))=1, it is as secure to use public exponent e1 (or e2) as to
use public exponent e. In particular, if an attacker could invert RSA
with public exponent e, then it could also invert using public exponent
e1; the (easy) reduction is left to the reader. =)
For the record, in the Katz-Lindell book we say that choice of e is
arbitrary as far as security goes, but e=3 is prefered in practice for
efficiency.
_______________________________________________
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography
