Does this RSA decryption scheme make sense?

Question

A custom file format has a header encrypted with a 2048-bit RSA public key. I need to decrypt it using a 2048-bit RSA private key. The header has 48 bytes, and according to the scheme I got for the task, after decryption I should get a 48 bytes of "plaintext" payload.

However, this scheme does not make any sense to me. It is my understanding that if we encrypt something using a 2048-bit RSA key, we will inevitably get a 256 ciphertext. Am I wrong in my assumption? Is there a way to RSA-decrypt a 48 byte ciphertext with a 2048-bit private key and get a 48 byte plaintext out of it?

I have tried using -raw mode with openssl like this, and it produces a 256-byte long plaintext message:

openssl rsautl -decrypt -in ./header.bin -out ./header-out.bin -inkey ./privkey.pem -raw

P. S. After discussion with the client and going through the encryption source code, we've figured out that the documentation had it wrong. In reality, header is not 48 bytes but variable length, and the first 2 bytes of the file contain the header length.

Answer 1

You're right, normal RSA does not (and cannot) work like that. Most likely, your client either:

1. is using RSA with an absurdly low (and insecure) key size,
2. is not actually using RSA at all, or
3. has provided you with incorrect documentation regarding the encrypted header size.

All of those seem plausible. I would suggest telling your client that the documentation they have provided appears inconsistent, and asking them to supply you with working code that can either read (and decrypt) or write (and encrypt) files in their format. That should hopefully be sufficient for you to figure out what the heck is actually going on.

(Note that it's quite possible that your client doesn't know either, if they didn't write the software themselves. It's quite possible that they believe the documentation to be correct, and lack the crypto expertise to know better.)

---

Ps. There is, technically, at least one more thing that they could be doing: they could be using (truncated) RSA decryption as a PRF. That is, they could be generating a random 48-byte header, feeding it (padded e.g. with zeroes) to 2048-bit RSA decryption as ciphertext, and truncating the resulting 2048-bit pseudorandom plaintext back to 48 bytes.

Is that secure? Maybe. It's definitely not a normal way of using RSA, but I can't immediately think of an obvious attack against it. And at least I can't think of any other halfway secure way to use 2048-bit RSA to map 48-byte strings to 48-byte strings.

Of course, the obvious problem is that, in order to do that, the encryption code would also need access to the private RSA key — which makes using RSA pointless, since any symmetric-key PRF would work just as well. But at least they could technically claim that they were "using RSA." And honestly it wouldn't be anywhere near the craziest thing ever found in do-it-yourself encryption schemes.

Answer 2

You can encrypt and decrypt arbitrary size of plaintext & ciphertext with RSA without using padding. This method is called as "Textbook RSA." However, it is definitely insecure. Different padding methods are used in current systems in order to make the output size equals to the size of the RSA modulus "$n$".

So in your case, 48-byte plaintext is padded according to some padding format and 2048-bit output is obtained inevitably. openssl may be use PKCS#1 as default format, I'm not sure. If you want to encrypt 48-byte plaintext and obtain it as 48-byte after decryption of corresponding ciphertext, you should use Textbook RSA.

Answer 3

if we encrypt something using a 2048-bit RSA key, we will inevitably get a 256 (bytes) ciphertext.

Yes, except it's possible to save a few bits, and there are commonly used tricks to save one bit (with the benefit of allowing subsequent textbook RSA signature with a second RSA modulus of the same size).

In this 1-bit-saving trick, a message to encipher $M$ is padded into an integer $m$ (adding randomness and redundancy) in such a way that $m<n/2$ (as in the EME-OAEP padding of RSAES-OAEP) and/or $m$ is even. Then textbook RSA is applied, giving $c\gets m\bmod n$. The actual ciphertext if $\tilde c\gets\min(c,n-c)$, which is one bit less than $n$. On decryption it's computed $\tilde m\gets\tilde c^d\bmod n$, then $m$ is either $\tilde m$ or $n-\tilde m$ whichever matches the $m<n/2$ and/or $m$ even criteria. Then $M$ is extracted from $m$ as usual.

It's possible to save more bits, but AFAIK all the techniques that do have expected computational cost that grows exponentially with the number of bits saved past the first one.

Is there a way to RSA-decrypt a 48 byte ciphertext with a 2048-bit private key.

No. It's not possible to save that much space in an RSA cryptogram.