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.

The question pertains not in terms of security but computing operational functionality, as it how the computation is done.

Is it true that for RSA with no padding, the length of data must be equal to the length of key?

If so, why is that so? What is the reasoning why the data needs should have the same number of bits as the modulus? What is the mathematical implication?

Examples: Limitations to input size corresponding to key size in bits:

keysize: 512 bits  (64 bytes),  number of input bytes: multiples of 64
keysize: 768 bits  (96 bytes),  number of input bytes: multiples of 96
keysize: 1024 bits (128 bytes), number of input bytes: multiples of 128
keysize: 2048 bits (256 bytes), number of input bytes: multiples of 256
keysize: 4096 bits (512 bytes), number of input bytes: multiples of 512
share|improve this question
    
Because, among other things, there is a simple meet-in-the-middle attack on (unpadded) RSA which becomes more practical the smaller the message is. See Section 5 of link.springer.com/chapter/10.1007%2F3-540-44448-3_3 –  fkraiem Mar 23 at 6:08
    
So, is the length of data must be equal to the length of key? –  Babbit Mar 23 at 9:52
1  
Can anyone show me a pseudo code how this may be coded if the length of data must be equal to the length of key? –  Babbit Mar 23 at 12:54
    
Your data needs (should have) the same number of bits as the modulus, but it must also be numerically less than the modulus. You should use padding even if your data ends up having the same number of bits as the modulus. –  user3100783 Mar 23 at 17:14
    
Thank you, user3100783. What is the reasoning why the data needs (should have) the same number of bits as the modulus? What is the mathematical implication? –  Babbit Mar 23 at 18:26
show 4 more comments

1 Answer 1

The short answer is NO. Generally, it is not true that for RSA with no padding, the length of data must be equal to the key length. When and if that applies, that's a restriction of a particular cryptographic library, and either that's not the only restriction about the data, or the library does not allow reliable decryption of what's encrypted.

RSA (encryption) with no padding is a well defined algorithm when enciphering integers. It uses a public key $(N,e)$. The key length is given as the bit size $n$ of $N$; that is $n$ is the integer such that $2^{n-1}\le N<2^n$. This form of RSA encryption with no padding takes as input some integer $m$ with $0\le m<N$ called the plaintext (or message), and outputs the integer $c$ with $0\le c<N$ called the ciphertext, such that $c\equiv m^e\pmod N$ (or in other words such that $m^e-c$ is a multiple of $N$). That transformation is reversible for decryption. Notice that if we remove the restriction that $m$ is less than $N$, we create the problem that $m$ and $m+N$ yield the same $c$, therefore decryption of the ciphertext can not reliably recover the plaintext; for example, $m=2^n-N-1$ and $m=2^n-1$ both encipher to the same $c$.

RSA with no padding is not universally defined when we move to data rather than integers, for many reasons including:

  • There's no agreement on the stuff data is made of. Is that bits? Octets of 8 bits? Characters for various definitions of that?
  • Endianness in the conversion to integer and back.
  • Dealing with the aforementioned $m<N$ requirement; a fine option would be defining a fixed data size insuring that. For example, message data of exactly $\lfloor (n-1)/8\rfloor$ octets (and some usual conversion to integer) would insure $0\le m<2^{n-1}\le N$; but then that fixed data size is less than the key length (in octets).

The library in the question does not do the later. Its requirement seems to be that the input data length in bytes (octets) must be a multiple of $n/8$, where $n$ is the key size in bits (an a multiple of 8 in all the examples). We can guess that the input is split into data blocks of exactly $n/8$ octets, each individually converted to a number $m$ (probably using straight big-endian convention, which is the most common), then RSA-enciphered as above, with each result converted back to exactly to $n/8$ bytes using the same convention, and the results concatenated in the same order as the original to form the ciphertext. We have no way to guess what happens when one of the $m$ does not meet the $m<N$ requirement.

It seems the library in the question unify symmetric and asymmetric cryptography into a one-size-fits-all API, even if that's at the price of drawbacks:

  • Making it easy to unwillingly implement an unsafe cryptosystem; in particular, if some data belonging to a small set (like a dice throw, or candidates to an election) is enciphered in this way, it is trivial to break the encryption (just encipher each possible plaintext and see which match the ciphertext).
  • Allowing large data and subdividing that into blocks before enciphering each with RSA, which makes decryption grossly inefficient; and is insecure when used with no padding: in particular repeated plaintext blocks are visible in the ciphertext.
  • Either ignoring the $m<N$ requirement (with the consequence that for some data, encryption followed by decryption does not give back the original data); or rejecting some data at encryption time (which might escape testing). Most likely, one of this occurs when enciphering a block of data consisting of $n/8$ octets all 0xFF.

Except in very specific cases (such as enciphering a random bit string of $n-1$ bits):

  • Do not use RSA with no padding (also called textbook RSA or naked RSA), but rather use some secure RSA scheme built on top of that; see e.g. RSAES-OAEP of PKCS#1. Among the reasons not to use RSA encryption with no padding
    • Like any deterministic public encryption, it is unsafe when the plaintext has low entropy.
    • Short plaintext is vulnerable. In particular, even uniformly random plaintext of $\lfloor n/e\rfloor$ bits can be found by $e^{\text{th}}$ root extraction, and there are extensions to that.
    • Dan Boneh's Twenty Years of Attacks on the RSA Cryptosystem has more excellent reasons; and there are even more.
  • Do not use RSA to directly encipher application data that could be larger than what makes the RSA scheme used safe (for example, RSAES-OAEP with 2048-bit key and SHA-256 hash allows to safely encipher data of 0 to 190 octets and still have enough randomness added by the scheme); rather, use hybrid encryption.
share|improve this answer
    
As a note, even when you're enciphering a random bit string of n - 1 bits, that data can still be changed in predictable ways because of unpadded RSA's malleability (which would only be ok in some very specific cases as stated). The nice thing if you use padding is that the padding will fail if the enciphered data has been modified. –  user3100783 Mar 24 at 15:28
    
@user3100783: The padding check will fail if the enciphered data has been accidentally modified (with overwhelming odds for RSAES-OAEP, still quite likely for RSAES-PKCS1-v1_5). But that's NOT a security feature! One who wants to alter the enciphered data without being detected can do it trivially (just encipher whatever you want the deciphered thing to be); remember the adversary knows anything public, thus including the public key! –  fgrieu Mar 24 at 16:34
    
True, what I meant is that you can't modify the original plaintext if it's padded. So in the situation you said, they would replace all the plaintext with their own plaintext, and pad that. That becomes a valid message. I'm talking about the situation where they want to modify your plaintext and send that (can't be done with padding). –  user3100783 Mar 24 at 17:53
    
The ciphertext can be edited (when there is no padding) to make predictable changes to the decrypted plaintext. –  user3100783 Mar 24 at 18:00
    
@user3100783: I only partially agree: even without padding, when enciphering a random bit string of $n-1$ bits, the plaintext can be changed in predictable ways because of unpadded RSA's malleability only in very specific ways, related to the multiplicative properties of RSA; it is not like the adversary can change a bit here or there by messing with the ciphertext. We can build use cases where it is better for the adversary to take advantage of the genuine RSA ciphertext, than it is to craft another one from scratch (with fully chosen plaintext), but they tend to be artificial. –  fgrieu Mar 24 at 18:18
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.