# Is it possible to figure out the public key from encrypted text?

Suppose Alice sends messages to Bob by encrypting the messages with Bob's public key.

Eve knows that the data is encrypted using RSA, but does not know the public key. Can Eve figure out the public key just by observing the encrypted messages?

And if so, approximately how much data would it take for Eve to discover the public key?

(assume that the public key used is the same throughout, and that Eve can potentially grab as many encrypted messages as she desires)

-
Why would I Want to determine the public key when I can just ask for it and get it as part of the standard? The private key is the unknown. –  Chad Jan 20 '12 at 16:18
@Chad You can always ask for it, but not always will they give it to you... The public key can also be an unknown... –  yydl Jan 20 '12 at 19:31
Are you talking about plain RSA, or RSA used with a correct padding scheme? –  CodesInChaos Jan 31 '12 at 18:53
@CodeInChaos I guess that would be part of the answer if that matters. For me, personally, I'm interested in the with-padding case. –  yydl Feb 1 '12 at 1:19

Actually, if Eve does have access to Alice's plaintext messages (and Alice doesn't do random padding as she should), then yes, Eve does have a chance, even with only two messages.

Suppose she guesses $e$ (the public exponent), and that it's not a not huge value (say, the common value 65537).

Then, for every plaintext/ciphertext pair $P_i$, $C_i$, she knows that (if $N$ is the unknown modulus):

$P_i ^ e = C_i \mod N$

or, in other words:

$P_i ^ e - C_i = k_iN$

for some integer $k_i$.

So, if she takes two plaintext/ciphertext pairs, and computes the value:

$gcd( P_1 ^ e - C_1, P_2 ^ e - C_2 )$

that is extremely likely to be the value $N$, possibly multiplied by a small integer. Now, this gcd operation might be on operands of possibly a few hundreds of millions of bits long; not something you want to do every day, but it certainly in the realm of possibility if you're a bit patient.

Now, if Alice does do random padding before doing her RSA encryption, well, Eve doesn't have access to the values $P_i$, so this observation doesn't help her.

-
Your reduction seems to be on the following line: If she can guess $e$, then she can compute $N$ and hence the factorization of $N$. Since the latter problem is assumed to be hard, we see that we have a contradiction and hence it should not be possible for Eve to find out the public key by looking at the plaintext and the corresponding ciphertext. So, I think you proved that it is not possible to guess the value of $e$. Correct me if I am wrong. –  Jalaj Jan 19 '12 at 4:08
@Jalaj: no, that's not at all what I'm saying. Of course it may be possible to guess $e$; it's quite common for systems to restrict it to, say, 65537. I just showed how it might be possible for someone (assuming known plaintexts and determanistic padding; unlikely for public key encryption, but plausible if signatures are involved) to reconstruct $N$. I never mentioned computing the factorization of $N$ (the gcd operation was used to recover $N$, not factor it). –  poncho Jan 19 '12 at 4:17
Ohh yes! Sorry, I misunderstood it. Thanks for the clarification. –  Jalaj Jan 19 '12 at 4:21
That does not work with RSA encryption as defined by PKCS#1 or any reasonable standard, which uses random padding. –  fgrieu May 8 '12 at 13:03
The number of messages required depends on how confident Eve wants to be that she knows Bob's private key and hasn't been unlucky. For instance, if Eve sees a few 1024-bit messages go by then she can just wait until she's seen roughly $2^{1024}$ ciphertexts and look for a hard-to-factor number that numerically slightly larger than any ciphertext she's seen. However Eve could be unlucky in that Bob's modulus is actually 2048 bits and it just so happens that all the ciphertexts happen to be numbers with 1024 bits.
That method is hopelessly inefficient. After $2^k$ ciphertext are intercepted, it gets only about the top $k$ bits of the public key. –  fgrieu Jan 19 '12 at 9:37