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

Answer 2

I hope my idea works.

Let us assume that (e,d,n) is a tuple of the RSA public exponent. The RSA private exponent and the RSA modulus n :

Select a prime number, say p, between 1 and a 256 bit integer.

To encrypt a message m, compute the new public exponent as e*p and the ciphertext as:

c= m^{e*p} mod n.

To decrypt, the receiver should know the prime p, so you send this p later to him, with this he computes

(1) P = p^{-1} mod phi(n)

and

(2) m^e=c^{P} mod n

and

finally m=(m^e)^d mod n. This works as the receiver knows phi(n).

By the way, where can we use this? Is there any application you have in mind for this?

Answer 3

As silky implies in his answer, the way in which RSA is usually used to encrypt a document is in combination with a symmetric algorithm, like AES. A secure random key is generated for the AES algorithm, the documented is encrypted with that AES key, and the AES key is encrypted with the recipient's public key. Both parts are supplied to the recipient.

You can adapt this to your situation simply by sending only the document encrypted with the AES key in the first step, and withholding the AES key encrypted with the recipient's public key until the second step. The first part will be on the order of the original file size, and the second part will be a small, constant size (on the order of the RSA key size).

Answer 4

Hmm, interesting.

You're referring to RSA, I assume?

FYI, RSA isn't actually used to encrypt documents. It's used to exchange keys (keys for a symmetric algorithm, like AES).

So what you're really talking about is an approach that changes the keys.

Technically (mathmatically) if you put a different number in, you'll get a different number out. So that's not an issue; changing the public key in some fashion will (assuming you convince your RSA implementation to use it, or prepare an appropriately different number) result in a different symmetric key, thus an undecryptable document by Bob (because he'll expect a different key).

Really, though, I'm not so sure you care about this. It's a fairly useless thing to do. Perhaps, however, you're actually interested in Key Splitting (or "Secret Sharing" as wikipedia seems to call it).

HTH. I'm by no means an expert.