Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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)

share|improve this question
    
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
add comment

2 Answers 2

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.

share|improve this answer
    
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
2  
@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
add comment

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.

share|improve this answer
    
The question is whether Eve can find the public key and not the private key. –  Jalaj Jan 19 '12 at 4:09
    
@Jalaj Indeed. But if I understand ByteCoin's answer correctly, this would be a method to get the public key. –  yydl Jan 19 '12 at 4:32
    
@ByteCoin I was always under the assumption that messages encrypted with a 2048-bit key result in a 2048-bit ciphertext. Am I wrong? –  yydl Jan 19 '12 at 4:33
2  
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
    
@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. –  ByteCoin Jan 19 '12 at 14:14
show 1 more comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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