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.

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?

share|improve this question
2  
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). –  CodesInChaos Mar 17 '12 at 19:08
add comment

1 Answer

up vote 6 down vote accepted

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.

share|improve this answer
    
Isn't this also an issue with PKCS#1 v1.5 padding for encryption? It seems some papers suggest as much. –  owlstead Sep 21 '13 at 14:02
add 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.