Understanding Problem with rsa min key length 1024
Daniel Kahn Gillmor
dkg at fifthhorseman.net
Fri Apr 12 22:39:49 AEST 2019
On Fri 2019-04-12 16:11:48 +0930, David Newall wrote:
> When picking random prime 512-bit numbers, the number 2 is a valid
> choice. If you disallow that choice then you're not picking from the
> full 512-bit space.
that's correct. However, most people and most attack machinery already
know about 2 being a prime number and have very cheap ways of testing
for whether 2 is one of your supposedly secret primes. If you use 2 as
one of your factors in an RSA key, it will be immediately cracked,
despite it being a valid "4096-bit prime" according to the definition
you're using here.
Ensuring that the MSB is set is a way of ensuring that the most
commonly-known primes are not used in the generation of RSA keys.
> In RSA keys, the key is the product of two 512-bit prime numbers. If
> those numbers are selected on the basis that both have their MSB set,
> then the key space is only 1022 bits.
It's even worse than that, because primes are sparse! so the actual
space being searched (all primes of a given length) is *much* smaller
than 1022 bits once we weed out all the composite numbers ;)
But even taking the labeling of the "key space" as you've given it, if
your concern is that 1022 bits is too small of a key space (and it is,
given how sparse primes are!), then the right approach in 2019 is to use
3072-bit keys (which you rightly point out are "only" choosing from a
3070-bit "key space"), not to quibble about whether it ought to be OK to
select 2 as one of the factors.
All the best,
--dkg
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 227 bytes
Desc: not available
URL: <http://lists.mindrot.org/pipermail/openssh-unix-dev/attachments/20190412/29737d61/attachment.asc>
More information about the openssh-unix-dev
mailing list