# [cryptography] RSA Moduli (NetLock Minositett Kozjegyzoi Certificate)

Jonathan Katz jkatz at cs.umd.edu
Mon Mar 26 10:38:09 EDT 2012

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
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.