Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

If we know that the public key has only 16bits.

It's have over 6500 primes smaller than 2^16. How long we can find the public key ?? speed : 1.000.000 cal/s.

share|improve this question
One can't even apply padding to 16 bit RSA. So do you want to use textbook RSA? – CodesInChaos May 9 '12 at 9:55
RSA below 512 bits is ridiculously broken, and RSA below 1024 bits is still pretty weak. If you want small keys/blocks, go with elliptic curves, but even they become weak below 160 bits. – CodesInChaos May 9 '12 at 9:58
a public key is actually two numbers: $(e, N)$. While small $e$ is o.k., small $N$ implies small $d$, the private key. This is very weak. – yarek May 11 '12 at 18:50

If the plaintext is easily recognizable, one message is sufficient. Simply brute force all 16 bit RSA keys, decrypt the ciphertext. If the result "looks" like plaintext, you have found the key. A 16 bit RSA keyspace should be easy to brute force.

share|improve this answer
To be technical, one probably isn't enough. After all, the public key consists of a modulus and a public exponent; even if you're given both P and C, for a candidate modulus M, there is a significant probability that there will be a value e such that $P^e \equiv C \mod M$, and this value $e$ has a good chance to be relatively prime to $\phi(M)$. Hence, there are likely to be multiple $(M, e)$ pairs, and so you'll need a second encrypted message to have a chance to figure out which one it might be. – poncho May 9 '12 at 2:58
Also, for a 16-bit message there is not much of "recognizing". But the key point is: don't use 16-bit RSA. – Paŭlo Ebermann May 9 '12 at 7:20

Your Answer


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.