# Can you identify the public key used to encrypt something?

If I encrypt a string with a public key, does the encrypted ciphertext reveal the public key I used to encrypt it? Basically, I don't want anyone to know who the ciphertext is addressed to.

I'm thinking about RSA, but also interested in DSA. The ciphertext is not known.

-
Note that implementations may intentionally make that easy. security.stackexchange.com/questions/25170/… – Ricky Demer Jun 11 '13 at 6:45
– Xeoncross Jun 11 '13 at 17:21

An RSA ciphertext won't reveal who it is encrypted to, but it might reveal some information about who it isn't.

We'll assume that everyone has an RSA key of the same length (e.g. 2048 bits). Now, a public key consists of a large modulus N (and an exponent, that's not important for this discussion); a ciphertext consists of a value C between 0 and N-1.

Suppose Alice has a public key $N_{alice}$ and Bob has a different public key $N_{bob}$. If we were to encrypt a message with Alice's public key, that generates a value $C < N_{alice}$. Now, if $N_{bob} < N_{alice}$, then it is possible that $C \ge N_{bob}$; if that happens, someone listening in can immediately deduce that $C$ was not encrypted with Bob's public key.

Now, this isn't an inherent problem with RSA; if Alice and Bob cooperated, they could generate keys $N_{alice} \approx N_{bob}$ (say, agree in the first 200 bits); this would make it quite improbable that an attacker would be able to rule out a particular public key, This doesn't reduce the security of RSA, but it is not generally done.

As for DSA, well, DSA doesn't encrypt messages. If we look at DL-based encryption systems (El Gamal, IES), we see that the ciphertext doesn't reveal the public key (assuming that the various public keys use similar parameters; for example, the same group).

-
The answer assume RSA with proper padding, or that the plaintext remains undisclosed and unguessable. With textbook RSA and a plaintext that gets fully disclosed or guessed, it is easy to find the matching private key, by recomputing the ciphertext with each public key, and finding which public key matches. – fgrieu Jun 11 '13 at 5:22
And: RSA ciphertexts for the user of a public modulus $N$ are uniformly distributed on $[0…N−1]$ (or $[0…⌊N/2⌋]$ in some variants). With enough messages known to be for the same user, this may allow identifying which key belongs to who (e.g. by assuming that in a group of users, order of mean of the ciphertexts for each user matches order of public modulus). – fgrieu Jun 11 '13 at 5:24
This sounds like more of a problem when you are only using 2 keys. However, if I had several hundred possible public keys that the message could be encrypted too - it seems like RSA would probably only reveal it wasn't to ~50% correct? In some cases (the highest public keys, it could single them out or reveal it wasn't to ~99% of the others right? – Xeoncross Jun 11 '13 at 14:59
Also, are there any other key-pair encryption schemes which don't reveal data like the modulus of the public key? – Xeoncross Jun 11 '13 at 15:54
@Xeoncross: Yes, there are public-key encryption systems whose ciphertexts need not reveal the target: El Gamal, IES. – poncho Jun 11 '13 at 16:05