How badly does disclosing an M-bit prefix of an N-bit private key compromise security?

Question

I apologize profusely for knowing nothing about cryptography, please go easy on me!

I'm working on a project where I have a 2048-bit RSA private key and a public certificate generated from the private key. I encrypt secrets at one end-point using the certificate and decrypt them at another end-point using the private key.

On decryptor app startup, the code that parses the private key will throw an exception if the private key is unparseable. Right now the exception message discloses the first 21 bits of the key. My question is whether, and to what extent, this could compromise my secrets' security if the exception message got into a log file and was stolen by a malicious attacker.

Does disclosing the 21-bit prefix effectively reduce my 2048-bit private key to a 2027-bit private key? Or does it actually compromise things worse? Or does it not materially change the difficulty of guessing the full 2048-bit key?

EDIT: My private key is required to be DER-encoded in PKCS#8 format, so we are likely talking about the first 21 bits of a DER-encoded, PKCS#8-formatted, private key.

Answer 1

I further assume you mean a DER-encoded unencrypted PKCS#8 RSA key, since you wouldn't care about exposing an encrypted key, and it's a conventional two-prime key with equal-size factors (each 1024 bits) and the ubiquitous e=65537 using the standard PKCS#1 CRT-form representation.

I also note that 21 bits is a really odd amount to disclose: not 2 octets, not even 2 and half octets, but 2 and 5/8 octets? Anyway ...

It compromises ALMOST CERTAINLY NOTHING.

Unencrypted PKCS#8 is a SEQUENCE that contains a version INTEGER, an AlgorithmIdentifier and an OCTETSTRING containing the encoding of the key, which for PKCS#1 is a SEQUENCE containing another version INTEGER, then the modulus, then the public exponent, and only then the private exponent and other private values. For RSA the AlgorithmIdentifier is one of two fixed values depending on whether the inapplicable parameters are encoded as NULL or omitted.

Thus at least the first 20 octets of the PKCS#8 encoding are fixed values independent of your key, EXCEPT that the length field of the outer SEQUENCE reflects the length of the inner SEQUENCE, which in turn varies slightly (up to 4 octets) depending on whether the private exponent d happens to be >= 2^2047 and the three CRT values (dP, dQ, qInv) happen to be >= 2^1024, and thus need "extra" sign octets. If an adversary knows the PKCS#1 length (and thus the PKCS#8 length) is at its minimum or maximum, it gives less than 1 bit information about d. In between the min and max I don't think there are any usable relationships between dP dQ qInv and d but I can't rule it out, so worst case up to 1 bit there also. However the length ranges 0x04BC to 0x4C0 or 0x04BA to 0x04BE and is in the third and fourth octets, so IF your 21 bits are big-endian (that is, all of the first two octets and the top 5 bits of the third octet) then it includes no information about the part of the length that could be useful.

Answer 2

Let's assume that the leaked bits were from the "actual" private key, i.e. the primes $p$, $q$, the private exponent or its value modulo one of the primes.

A Coding-Theoretic Approach to Recovering Noisy RSA Keys gives a bound of 20% of the key material needing to be known for an attack. Given that you have a 2048-bit key, I don't think leaking 21 bits would be bad even if better attacks can be found.