0

I've been reading about the algorithm, and I've seen that a number of attacks against textbook RSA are based on encrypting shorter messages and checking the result. If padding does what I think it does (expand out the message to be the same length as the key), is it safe to forego padding if the message is guaranteed to be length of the key already?

As far as I know some padding schemes introduce random characters, so my gut tells me that it is required anyway to prevent against plaintext attacks.

Should I go for a smaller message size and add padding? Or is it safe to use m==n and no padding.

7

When you encrypt a message using RSA, padding is needed to ensure several properties:

  1. Encrypting the same message twice must result in different outputs, to prevent a chosen plaintext attack. This is the reason why paddings are randomized.
  2. RSA preserves some structure, padding should eliminate that structure.
  3. When an attacker manipulates the ciphertext, you want to reject that forgery in a way that prevents the attacker from learning anything.

    Many older paddings, such as PKCS#1v1.5 fail to ensure this, and thus are broken for many applications. You should use OAEP padding.


Alternatively you can just encrypt a random number of the same size as the modulus with RSA and use its hash as key for symmetric encryption (e.g. AES-GCM). This is known as RSA-KEM and doesn't need any padding. It produces larger ciphertexts but is easier to implement.

0

As CodesInChaos mentioned padding does destroy the homomorphic property of RSA, that is given two (even very long) messages m1, m2 and their corresponding ciphertexts c1, c2 then you can forge a third valid ciphertext c' = c1 * c2.

Without padding or other precautions, the receiver can not tell whether you intended to send m1, m2 or m1*m2.

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.