[cryptography] RSA Moduli (NetLock Minositett Kozjegyzoi Certificate)

Thierry Moreau thierry.moreau at connotech.com
Fri Mar 23 11:37:20 EDT 2012


Please let me try to summarize.

I guess it is OK to infer from Adam explanations and Peter observation 
about homegrown CA software implementations used by some CAs that ...

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.

At a modulus size of 2048 bits, I wouldn't lose sleep on this hypothesis.

- Thierry

Adam Back wrote:
> As to why conventionally e is a small low hamming weight prime, even though
> it doesnt have to be, I suspect it arose because some RSA code used to
> generate not strong primes, but random primes.
> 
> If you generate a random prime, then the factors of P=(p-1)/2, Q=(q-1)/2
> will be random.  But quite likely to contain 3, somewhat likely to 
> contain 5
> etc with decreasing probability for larger potential prime factors.  (And
> crucially for strength, it is unlikely a random prime will be B-smooth for
> dangerously small B.) Anyway so consider you choose a random pair of primes
> p & q, and a random or fixed non-prime small low hamming weight e..  say
> 2^15-1, it has factors 3x3x11x331, so then you very often will have to 
> abort
> and try again a new e or a new p and/or q because P or Q will factorize by
> some of these small factors, and then d will not be computable.
> 
> Consequently it'll be simpler and faster to pick a prime e, for a given 
> size
> e a prime has the lowest probability of having a co-factor with
> carmichael(n).
> 
> If you have strong primes which I think is more common at this point, e
> could be any random odd (non-even) number, presumably with low hamming
> weight.
> 
> Low hamming weight is a performance trick for modexp which involves more
> multiply operations for higher hamming weight.
> 
> Adam
> 
> On Fri, Mar 23, 2012 at 03:05:48PM +0100, Adam Back wrote:
>> I presume its implied (too much tongue in cheek stuff for my literal 
>> brain
>> to interpret) but a self-signed CA cert is a serious thing - thats a 
>> sub-CA
>> cert typically.  How that came to be signed with a bizarre though legal e
>> parameter is scary - what library or who wrote the code etc.
>>
>> Usual reason to use primes of form 2^n+1 and co-prime to carmichael(n) is
>> low hamming weight.
>>
>> Other than that typically p, q are strong primes P=(p-1)/2, Q=(q-1)/2 
>> also
>> prime, so any odd (non-even) e is pretty much guaranteed to work as 
>> carm(n)
>> = 2*P*Q where P = (p-1)/2, Q = (q-1)/2.  Or if using Lim-Lee primes, at
>> least B-smooth, meaning P=P1*P2*...Pn where |Pi|>B for all Pi.  And e 
>> would
>> typically be smaller than B-bits anyway for performance.
>>
>> (If e is not-coprime to carm(n) then d doesnt exist, as modinv(a,x) 
>> requires
>> gcd(a,x)==1, so its not like it will be insecure, it just wont work!)
>>
>> e should also not be too small or other attacks kick in.
>>
>> Dan Boneh has a good summary of RSA limitations:
>>
>> http://www.ams.org/notices/199902/boneh.pdf
>>
>> Adam
>>
>> ps carm(n) = phi(n)/2 = (p-1)*(q-1)/2.
>>
>> On Fri, Mar 23, 2012 at 06:51:51AM -0700, Jon Callas wrote:
>>> -----BEGIN PGP SIGNED MESSAGE-----
>>> Hash: SHA1
>>>
>>>
>>> On Mar 23, 2012, at 6:39 AM, Peter Gutmann wrote:
>>>
>>>> Jon Callas <jon at callas.org> writes:
>>>>> On Mar 23, 2012, at 6:03 AM, Peter Gutmann wrote:
>>>>>> Jeffrey Walton <noloader at gmail.com> writes:
>>>>>>> Is there any benefit to using an exponent that factors? I always 
>>>>>>> thought low
>>>>>>> hamming weights and primality were the desired attributes for public
>>>>>>> exponents. And I'm not sure about primality.
>>>>>>
>>>>>> Seeing a CA put a key like this in a cert is a bit like walking 
>>>>>> down the
>>>>>> street and noticing someone coming towards you wearing their 
>>>>>> underpants on
>>>>>> their head, there's nothing inherently bad about this but you do 
>>>>>> tend to want
>>>>>> to cross the street to make sure that you avoid them.
>>>>>
>>>>> But Peter, CAs don't *precisely* put keys into certs. CAs certify a 
>>>>> key that
>>>>> the key creator wants to have in their cert.
>>>>
>>>> This is a self-signed cert from the CA, so the key creator was the CA.
>>>
>>> So it's like issuing yourself an Artistic License card with a color 
>>> printer and laminator. :-) Good for lots of laughs.
>>>
>>>     Jon
>>>
>>>
>>> -----BEGIN PGP SIGNATURE-----
>>> Version: PGP Universal 3.2.0 (Build 1672)
>>> Charset: us-ascii
>>>
>>> wj8DBQFPbIAAsTedWZOD3gYRAo4KAKDuG0OgEg81mxGUJDGlYp5OzLMI/gCgkRRq
>>> /G3T3NLS/8k1L4njuxMJMd0=
>>> =tHSy
>>> -----END PGP SIGNATURE-----
>>> _______________________________________________
>>> cryptography mailing list
>>> cryptography at randombit.net
>>> http://lists.randombit.net/mailman/listinfo/cryptography
> _______________________________________________
> cryptography mailing list
> cryptography at randombit.net
> http://lists.randombit.net/mailman/listinfo/cryptography
> 




More information about the cryptography mailing list