How can a decryption program tell me that a private key is incorrect for RSA and ECC?

Question

I have a program which will encrypt the symmetric key with RSA public key with keysize 2048. I am able to decrypt the message with the corresponding private key. My question is, is it possible to decrypt a message with the different private key with same key length successfully? if it is possible then decrypted data can be junk data? In this case, how can I know, decryption is / was successful?

I have the same program for ECC keys (256,384) and will decryption return junk data in ecc using a different private key?

Answer 1

The answer is different for the schemes that are used. So there is no one answer for the simple reason that the different modes have different properties.

In general modes such as PKCS#1 v1.5 or OAEP encryption is used for RSA. These modes contain a specific padding that is performed before the modular exponentiation that is the backbone of RSA. Performing the modular exponentiation with the private key - possibly sped up using the Chinese Remainder Theorem or multi-prime calculations - will result in the padded message. Now the padding is checked before the message is returned. This means that using an invalid private key / ciphertext pair will result in a padding error. Note that padding errors may actually lead to attacks on the key.

---

It is not possible to perform encryption directly using ECC. Instead ECIES can be used to perform it indirectly. This is basically key agreement followed by encryption using a symmetric key. In this case the asymmetric key agreement may fail without error resulting in an incorrect symmetric key. Then the subsequent decryption may not cause an error either. This can be fixed by using an authenticated cipher such as GCM, which generates an error for any invalid secret key / ciphertext pair.

The same goes for RSA-KEM as for ECIES. So again: it depends on the scheme.

---

So the conclusion: use an authenticated encryption scheme for the symmetric cipher. And don't forget to protect against padding oracle attacks for RSA. PKCS#1 v1.5 padding should not be used anymore because of a specific padding oracle attacks called the Bleichenbacher attack. OAEP should be secure (if the implementation is secure, of course).

If you do that you can be sure that some kind of error is returned if you use an invalid private key / ciphertext pair.

---

Another option is to sign the plaintext message. In that case you can verify the authenticity of the message after decryption. This has the additional advantage that an adversary cannot simply encrypt a different message using the public key. In general this should be combined with the authenticated encryption option mentioned in the previous section.

Answer 2

In RSA it is mathematically/theoretically but not practically possible (the cornerstone of cryptography) when you take into consideration padding like Maarten described.

Suppose you have a max length message encrypted under RSA without padding. Decrypting with another RSA key of the same length will give you junk data. Ignoring the RSA key size or how you derive a symmetric key from the secret (important implementation questions though), you wouldn't immediately know otherwise unless your secret contained some type of indication that ensures you've decrypted the message successfully. For example a header saying "Here is your secret:...." But don't do this, use padding for RSA.

EC encryption is harder to comment on given the lack of implementation description. Gut feeling though is a similar scenario.