Jonathan Katz wrote:
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.
My apologies to everyone. Indeed I had the basic RSA math wrong, but you
made the appropriate corrections. Thanks. (I indeed meant to fix e in
advance.)
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. =)
Yes.
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.
The number theoretic publications supporting e<log2(N) -- which is not
recommended by the original RSA article -- and e=2 -- the Rabin-Williams
cryptosystem -- are plenty and fascinating, but hard to summarize with
my above-demonstrated inability to write maths!
- Thierry Moreau
_______________________________________________
cryptography mailing list
[email protected]
http://lists.randombit.net/mailman/listinfo/cryptography
