[cryptography] RSA Moduli (NetLock Minositett Kozjegyzoi Certificate)
Thierry Moreau
thierry.moreau at connotech.com
Mon Mar 26 11:17:39 EDT 2012
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
More information about the cryptography
mailing list