Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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.
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).
