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 <[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
_______________________________________________
cryptography mailing list
[email protected]
http://lists.randombit.net/mailman/listinfo/cryptography
