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 <[email protected]> writes:
On Mar 23, 2012, at 6:03 AM, Peter Gutmann wrote:
Jeffrey Walton <[email protected]> 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
[email protected]
http://lists.randombit.net/mailman/listinfo/cryptography
_______________________________________________
cryptography mailing list
[email protected]
http://lists.randombit.net/mailman/listinfo/cryptography
