[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