7
$\begingroup$

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)

Improve this question
$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – Chad
    Commented Jan 20, 2012 at 16:18
  • $\begingroup$ @Chad You can always ask for it, but not always will they give it to you... The public key can also be an unknown... $\endgroup$
    – yydl
    Commented Jan 20, 2012 at 19:31
  • $\begingroup$ Are you talking about plain RSA, or RSA used with a correct padding scheme? $\endgroup$
    – CodesInChaos
    Commented Jan 31, 2012 at 18:53
  • $\begingroup$ @CodeInChaos I guess that would be part of the answer if that matters. For me, personally, I'm interested in the with-padding case. $\endgroup$
    – yydl
    Commented Feb 1, 2012 at 1:19

2 Answers 2

Reset to default
6
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – Jalaj
    Commented Jan 19, 2012 at 4:08
  • 2
    $\begingroup$ @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). $\endgroup$
    – poncho
    Commented Jan 19, 2012 at 4:17
  • $\begingroup$ Ohh yes! Sorry, I misunderstood it. Thanks for the clarification. $\endgroup$
    – Jalaj
    Commented Jan 19, 2012 at 4:21
  • $\begingroup$ That does not work with RSA encryption as defined by PKCS#1 or any reasonable standard, which uses random padding. $\endgroup$
    – fgrieu ♦
    Commented May 8, 2012 at 13:03
1
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ The question is whether Eve can find the public key and not the private key. $\endgroup$
    – Jalaj
    Commented Jan 19, 2012 at 4:09
  • $\begingroup$ @Jalaj Indeed. But if I understand ByteCoin's answer correctly, this would be a method to get the public key. $\endgroup$
    – yydl
    Commented Jan 19, 2012 at 4:32
  • $\begingroup$ @ByteCoin I was always under the assumption that messages encrypted with a 2048-bit key result in a 2048-bit ciphertext. Am I wrong? $\endgroup$
    – yydl
    Commented Jan 19, 2012 at 4:33
  • 3
    $\begingroup$ That method is hopelessly inefficient. After $2^k$ ciphertext are intercepted, it gets only about the top $k$ bits of the public key. $\endgroup$
    – fgrieu ♦
    Commented Jan 19, 2012 at 9:37
  • $\begingroup$ @yydl Let's take the concrete example of RSA where n=221 and e=11 so that's a 8-bit modulus. If the plaintexts only come from the set 54, 59, 61, 63, 70, 82, 92, 125, 166, 175, 181, 185, 208 then Eve, who just sees the ciphertexts might reasonably assume that the 4-bit modulus 15 is being used. Of course as fgrieu says it's inefficient but it's the best that can be done under the constraints of the original question. $\endgroup$
    – ByteCoin
    Commented Jan 19, 2012 at 14:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.