[cryptography] RSA Moduli (NetLock Minositett Kozjegyzoi Certificate)

Adam Back adam at cypherspace.org
Fri Mar 23 11:13:23 EDT 2012


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



More information about the cryptography mailing list