# Is it possible to prove which public key was used to encrypt a message?

Pretty much the title: If Alice sends a message to Bob that she encrypts with Bob's public key, is it possible for Eve to prove that the ciphertext was encrypted with Bob's public key, that the encrypted message is intended for Bob?

Update

Suppose the algorithm is RSA.

-
I have a feeling this is going to depend somewhat on the precise protocol chosen; don't some of them basically say, "hey, I was encrypted with Bob's public key #1!"? – Clockwork-Muse Jul 9 '13 at 17:13
@Clockwork-Muse If Alice signed her message with her key before encrypting the message with Bob's key, then yes... But I'm not sure otherwise, hence the question. Please see my update. – John Jul 9 '13 at 17:18
Check the following paper out: slideshare.net/jmoquendo/wasntmefinal – munkeyoto Jul 9 '13 at 17:29

"Proving" depends on whether the recipient (Bob) cooperates (i.e. accepts to reveal his private key to the verifier), and also on the type of cryptographic algorithms and details of the key.

If Bob cooperates, then he may decrypt the message; this may show that the message "makes sense" when decrypted with Bob's private key, which is a rather strong hint that Bob was intended as the recipient, or at least as a recipient. This depends on what qualifies as "making sense", of course. Most asymmetric encryption systems are hybrid: an asymmetric key exchange yields a message-specific key shared between sender and receiver, and the key is then used to encrypt the actual message data. If the encryption uses (as it should) a MAC to detect alterations, then this can be turned into a convincing proof that the sender really worked with Bob's public key in mind (but it depends on the exact algorithms employed).

Note that, depending on the used algorithms, it can be possible for Bob to take an existing message, and compute his own key pair so that the message (as a sequence of bytes), when decrypted with his brand new private key, decrypts to a message of his choosing. Thus, asymmetric encryption cannot, in general, be considered equivalent to an ownership claim.

If Bob does not cooperate, things can be tricky. We are now in the model of traffic analysis, where an attacker tries to see through anonymous communications. In that model, Bob is not a potential attacker, but a potential victim. Hiding the recipient identity is not a primary property of asymmetric encryption and key exchange systems. If we consider asymmetric encryption with RSA, then the key size is leaked, since it matches the encrypted message size; this can reduce the number of possible recipients.

As a more extreme case, consider Diffie-Hellman. DH is computed in a given group, consisting of a prime modulus p, a subgroup size q (q divides p-1 and is normally prime) and a subgroup generator g (g has order q, which means that gq = 1 mod p). These values (the "group parameters") are part of Bob's public key. The message will first begin by a value B = gb mod p, with a randomly chosen exponent b: that value is a subgroup element. For a given asymmetrically encrypted message, it is easy to look at the header, see the B value, and check whether it matches a given (p,q,g) DH group specification: simply compute Bq mod p; for the right group, it will yield 1, but (with overwhelming probability) not for a distinct group.

So if potential recipients use Diffie-Hellman and each one generated his own group, then this simple test will pinpoint the actual recipient. On the other hand, if several recipients decided to generate their respective key pairs within the same group (which is allowed in DH and does not incur any security weakness), then outsiders will not be able to determine which recipient is the right one: doing so would entail solving the Decisional Diffie-Hellman problem, which is hard (we don't know of any way to solve DDH, in a normal DH group, except through Discrete Logarithm, which is thwarted by large enough p and q).

Also, pinpointing is not proving. Anybody can take a copy of Bob's DH group parameters (they are part of Bob's public key, thus public themselves) and generate his own key pair within the same group. Therefore, being able to recognize Bob's group in a given message does not demonstrate that only Bob could read the message; the message could be meant for somebody else whose key works in the same group.

(Having many keys in the same group is a very common occurrence when using the elliptic curve version of DH, because generating your own curve is hard work and severely limits interoperability.)

-

I'm going to take a different approach in my answer here. You state: "prove that the ciphertext was encrypted with Bob's public key" I say, how are you sure its Bob's key. Because of the structure of Public Key Servers (http://pgp.mit.edu/) there is nothing to stop me from making a key pretending to be "Bob." There is also NO MECHANISM to validate that Bob is the ultimate recipient period. E.g. See here: http://pgp.mit.edu:11371/pks/lookup?search=topsecretgov.gov&op=vindex

What is the ultimate endgame with this question? Is it that of repudiation? While I enjoyed Tom Leek's answer, my answer is one of a "threat" where the purpose is to illustrate that you CANNOT ultimately rely on encryption. There is no mechanism to validate who put the key on that server. You can subpoena MIT in hopes they're logging, but you get what? An IP. This is meaningless.

To get further into this, private keys can become compromised with a keystroke logger, malware, etc. This is how malware authors that have targeted "distros" (Debian, FreeBSD, etc) have managed to sneak in bits of garbage throughout the years. Horrible key management.

-
I understand the difference. So to you my question might be, can you prove, mathematically that ciphertext C must have been encrypted by RSA public key K? Or if not prove, suggest with a high probability? – John Jul 9 '13 at 19:37
I don't believe this is possible (theoretical). Hence the "web of trust" en.wikipedia.org/wiki/Web_of_trust and PGP Key Signing parties. – munkeyoto Jul 9 '13 at 19:57

Using only RSA as currently implemented, no, this is not possible. The only way for Eve to prove the message was encrypted with Bob's public key is to decrypt it using Bob's private key, and that defeats the entire purpose of public-key cryptography (to keep whichever key of the pair that proves you're you, the "private key", private).

There are mechanisms available that allow someone to learn something about the message without fully decrypting the whole thing. Consider a scheme in which Alice encrypts the actual message using Bob's public key, then takes that message, adds in some non-confidential "header" information including the source and intended recipient, then signs that entire package with the Digital Signature Algorithm using Alice's own private key. Anyone who knows Alice's public key (and that is public information) can verify the digital signature, and thus can know that Alice sent this message exactly as they currently have it, including the information about the intended recipient. They still can't see the message, nor can they prove that message really was encrypted with Bob's public key, but that's really none of their business anyway; if Bob can't decrypt it then he can tell Alice that she screwed up.

With an added tweak to encrypt the actual message symmetrically, and then encrypt the key for that message asymmetrically with the recipient's public key, this is the basic idea behind PGP. There is information inherent in e-mail transit that simply must be plainly visible in order to get the e-mail to the recipient. But, it's valuable to be able to prove who sent it, what their intentions were, and that nobody tampered with it, before trying to read the actual contents.

Another layer of complexity behind the whole thing is how to prove that anybody's public key really is theirs; this is accomplished with key signing, where a trustworthy entity vouches for the validity of the information by appending information that only someone who knows that entity's private key could produce (either a DSA signature, or a crypto hash that's then encrypted with the entity's private key). In SSL/TLS the signing forms a hierarchical "trust chain", with a CA vouching for an end user's certificate, another CA vouching for that CA's certificate, and so on, leading back to one of the "trusted root" certificates distributed with your web browser or OS, which you must trust if you're to use the system at all. In PGP it's a flatter "web of trust" structure, where peers who know and trust each other sign each other's keys in a secure environment, then distribute them to other people who know and trust the signer and so can trust the certificate.

-