Understanding Problem with rsa min key length 1024

[Daniel Kahn Gillmor]

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>