# How can we find Public key have only 8 or 16bits? How many messages does Eve need to know the Public key in RSA?

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.

-
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

## 1 Answer

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.

-
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