I am trying to understand the notion of RSA security.

Choosing a public exponent where $e = 3$ facilitates the calculations, considering that it is secure if the plaintext or message is long.

If the message is short, it affects security but why?

Does that relates to the $2^n$ possibilities, if the message is short the probability of knowing the message is high?

  • 2
    $\begingroup$ Typical RSA messages consist of a random symmetric key, so this concept doesn't really apply in practice. We also use special padding modes instead of plain RSA, which prevents many attacks (AFAIK including yours). $\endgroup$ – CodesInChaos Mar 17 '12 at 19:08

This only applies to "text book" RSA, i.e. plain modular exponentiation with the public or secret exponent.

If you have a $n$-bit modulus, and use a message $x$ shorter than $n/3$ bits, the modular part of modular exponentiation doesn't come to play when calculating the ciphertext as $c = x^3 \bmod n$. The effect is that you can simply calculate the (integer) cubic root of the ciphertext $c$ to extract the plaintext, and don't have to deal with the key at all.

I think similar attacks are possible if the message is only slightly longer than $n/3$ bits.

This is one of the reasons that you normally don't use textbook RSA, but standard RSA, which uses non-zero padding to fill up the message to the size of the modulus, so the modular reduction actually comes into effect. Another reason is that you need some randomness in the padding, to avoid that the same message encrypted twice with the same public key gives always the same result.

Also, in practice you are not encrypting the message directly, but encrypt a key for a symmetric algorithm, which then is used to encrypt the actual message, in a hybrid scheme.

  • $\begingroup$ Isn't this also an issue with PKCS#1 v1.5 padding for encryption? It seems some papers suggest as much. $\endgroup$ – Maarten Bodewes Sep 21 '13 at 14:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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