Is there a way to alter a public key in a way that the decryption can still be done with the private key after some alteration?

Question

In an asymetric encryption scheme, I was wondering if it's possible to achieve the following:

1. Bob sends to Alice his public key
2. Alice alters Bob's public key and encrypt some document with it
3. Alice sends the encrypted document to Bob
4. Bob retrieve the document but can't decrypt it with his private key
5. Later, Alice sends some additional information (probably related to the method she used to alter Bob's public key) to Bob
6. Bob uses this additional information to modify his private key and successfully decrypt the document

Anyone?

I am assuming RSA for the keys generation, encryption and decryption but if it's easier to do with another scheme feel free to comment.

Answer 1

(I assume you talk about RSA.)

Yes it is possible, but not 100%.

The public key is a part of the private key. It contains the modulus and the exponent of the key.

You can completely forget changing the modulus, because you would have to generate a new rsa keypair, which is the same problem as the one we are trying to solve.

But it is possible to change the exponent. You can select any (prime) number between 1 and your exponent as the new exponent and hope that it is coprime with the totient. Without knowing the totient it's impossible to select always a correct exponent. To find out the totient you would have to know the prime factors of the key, which means that you would have to break the key (have fun!).

So, it's actually impossible to have a 100% percent working method to do that, at least not while knowing only the public key.

If you need more information about the theory check here