1
$\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?

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.

Improve this question
$\endgroup$
3
  • $\begingroup$ One can't even apply padding to 16 bit RSA. So do you want to use textbook RSA? $\endgroup$
    – CodesInChaos
    Commented May 9, 2012 at 9:55
  • 1
    $\begingroup$ 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. $\endgroup$
    – CodesInChaos
    Commented May 9, 2012 at 9:58
  • $\begingroup$ 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. $\endgroup$
    – yrk
    Commented May 11, 2012 at 18:50

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ 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. $\endgroup$
    – poncho
    Commented May 9, 2012 at 2:58
  • $\begingroup$ Also, for a 16-bit message there is not much of "recognizing". But the key point is: don't use 16-bit RSA. $\endgroup$
    – Paŭlo Ebermann
    Commented May 9, 2012 at 7:20

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.