Prove a plain text belongs to encrypted data

Question

Given an encrypted (RSA) message and it's original plain text, is there a way to prove that the plain text belongs to the encrypted message ?

Answer 1

If you have the private key, then sure, you can decrypt the ciphertext and compare the plaintexts.

If you only have the public key, then no, this is impossible, assuming that by “encrypted (RSA)” you mean “encrypted with an asymmetric encryption primitive based on RSA” (of which there are two standard ones, both describes in PKCS#1). Any encryption primitive where someone can decrypt a ciphertext by guessing possible plaintexts and then checking guesses would be badly broken. This is formalized as indistinguishability properties. For an asymmetric encryption mechanism, even if an adversary can submit arbitrary plaintexts and get corresponding ciphertexts, the adversary must not be able to find out the decryption of a ciphertext that they were not given that way (indistinguishability against chosen-plaintext attacks).

With textbook RSA (i.e. just doing the exponentiation), you can of course apply the public key operation to the plaintext. This is one of the reasons why textbook RSA is not an encryption (or signature) mechanism by itself.

Message encryption schemes based on RSA get around this problem by incorporating a random string into the plaintext before applying the public-key operation. This is known as padding, because the simplest way is to concatenate the plaintext with a random string to pad it to the RSA key length. (It takes more than just this to do padding correctly!) If you have a ciphertext, the possibly corresponding plaintext and the public key, you still can't tell whether the ciphertext matches the plaintext because you'd have to guess the random string, and it's long enough to make guessing infeasible.

Incidentally, this structure makes it possible to prove what a ciphertext decrypts to without revealing the private key, or any information about other ciphertexts. If you reveal the plaintext and the random string used during encryption, anyone can calculate the corresponding ciphertext. Both the entity that produced the ciphertext, and the holder of the private key, can do this.

Answer 2

RSA "encrypted message" is "plain text" encrypted by some public key. If you know said public key, you can encrypt "plain text" again and see, that both encrypted massages are the same.

That means you can prove that given plaintext belongs to encrypted message, if you know public key used for encryption.