Understanding Problem with rsa min key length 1024

David Newall openssh at davidnewall.com
Fri Apr 12 16:41:48 AEST 2019

On 11/4/19 11:26 pm, schlifka at geekpit.org wrote:
> However Due nature of RSA-algorithm in case of 1024bit this might 
> result in a key length of 1023 or 1024 bit. 

I've been confused by this and am astounded by the information I've 
found.  For example,

    Q: I am receiving warning messages regarding key lengths.  What do
    these messages mean, and how can I prevent them?

    A: The key-length warning messages you are seeing are sent by
    OpenSSH when it encounters certain defective RSA or DSA keys that
    are sometimes generated by a bug in the ssh-keygen program (in
    commercial SSH).  These defective keys are Pubkey Authentication
    keys whose Most Significant Bit (MSB) is not set.  Thus, these keys
    ar efrequently half as long as advertised (they advertise as full
    length.) ...

    Next Generation SSH2 Implementation: Securing Data in Moption,
    Chapter 6, Dale Liu

The problem with this answer is that a random key can have MSB zero or 
one.  If MSB is known to be one, then the key is 1023-bits prefixed with 
a constant one.

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.

Tragically, as I understand, the logic that Dale espouses is entrenched 
and we have only half the key space that's advertised. (The key space is 
the upper-half of the 1024-bit range.)

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.

More information about the openssh-unix-dev mailing list