Is it possible to alter the plaintext message without altering the ciphertext?

Question

Is it possible to alter the contents of a plaintext message without altering the ciphertext? Altering the private key is allowed to accomplish this. If the answer is yes, how would I go about in doing this? Encryption strength is not particularly important.

Answer 1

Yes, but typically not in any controlled way.

Essentially you're asking whether two different encryption parameterisations map to the same ciphertext space and that is precisely what most cryptosystems do.

Let's take AES-ECB as an example. Suppose that I have a key $k_0$ and a plaintext $P_0$ and a ciphertext $C=\mathrm{AES}_{\mathrm Enc}(k_0,P_0)$. Now I can pick any other key $k_1$ and compute $P_1\mathrm{AES}_{\mathrm Dec}(k_1,C)$ and lo and behold $C=\mathrm{AES}_{\mathrm Enc}(k_1,P_1)$. However $P_1$ is almost certainly gibberish. To try and control $P_1$ is to say I have a matched plain and cipher and want to find the corresponding key. This is intended to be hard.

To take a public key example, let's consider El Gamal on an arbitrary additive group $\langle G\rangle$. Pick a private key $a$ and public key $A=aG$ and off we go. For a plaintext message $M_0$ some one chooses a random $r$ and sends $(R,C)=(rG,rA+M_0)$. Now choose any other private key $b$ which would have corresponding public key $B=bG$ and we decrypt $(R,C)$ using this key to get $C-rB$ which we call $M_1$. Note that $M_1=M_0+r(B-A)$ so to select $M_1$ I need to know $r$ which would involve solving a discrete logarithm.

There is one cryptosystem where the alternative plaintext can be pretty much completely specified and that is the one-time pad. It's a straightforward exercise to show that any OTP cryptogram can be written as any plaintext message of the same length enciphered with a different OTP which differs from the original OTP by the difference of the messages.