2
$\begingroup$

A message coded with RSA is broken up into blocks, then padded/transformed prior to encryption via modular exponentiation with the public key. However, the encryption result for each block is not necessarily a fixed length of bits, octets or characters. What are the accepted protocols for delimiting these encrypted blocks so that they can be decrypted with the private key?

$\endgroup$
  • 2
    $\begingroup$ Are you sure you're not mixing up RSA and block ciphers (such as AES)? $\endgroup$ – Daffy Jan 31 '16 at 1:14
  • 4
    $\begingroup$ In the real world RSA is not used for bulk data and there is never a need to separate encrypted values from each other. Usually RSA encrypts a working symmetric key (DEK, CEK, MEK) which is always small, and the need is to separate the RSA encrypted key from other data. There are many standard protocols/formats for this including SSL/TLS SSH PKCS#7/CMS/S-MIME PGP XMLenc, and many more that are accepted without being standard. Generally they use the same techniques to delimit RSA-encrypted values that they use for other data, and these techniques are different. $\endgroup$ – dave_thompson_085 Jan 31 '16 at 1:34
4
$\begingroup$

Nobody (at least, nobody who does crypto seriously) splits up data into blocks to be independently encrypted with RSA. Not only is this inefficient, in CPU and in network bandwidth (because asymmetric encryption necessarily implies data enlargement), but we do not really know how "safe" it is. This is a little-studied question, so there is no accepted protocol for that.

Real-life protocols that use asymmetric encryption (e.g. CMS or OpenPGP) use hybrid encryption: the asymmetric algorithm is used to convey a symmetric key, which is then used with a symmetric encryption algorithm to process the bulk of the data. This has the extra advantage of also working with key exchange algorithms (like Diffie-Hellman) which are not asymmetric encryption algorithms (in a way, DH can be seen as an asymmetric encryption algorithm where you do not choose what you encrypt).

RSA-encrypting data "directly" is encountered mostly in protocols that must live under strict bandwidth constraints (e.g. in smart cards), where every single byte counts; but in that case, messages are very short, and there is no question of splitting messages into blocks.

$\endgroup$
  • $\begingroup$ I've seen signatures with message recovery being used, but most of the time smart cards just provide raw RSA or padded RSA operation. What is encrypted depends on the application or middleware. But in that case you might as well use a hybrid cryptosystem where an AES key is generated off-card and used for speedy encryption on the host CPU. So I haven't seen any data being encrypted directly yet (but OK, YMMV). $\endgroup$ – Maarten Bodewes Mar 31 '16 at 18:01
3
$\begingroup$

Textbook RSA encryption (which just consists of modular exponentiation) is not secure. Furthermore, it operates on integers (numbers) rather than bytes. So you need some scheme of converting bytes to these integers. Furthermore, to provide the necessary security, you need some kind of padding scheme.


Various RSA schemes are present in PKCS#1. Currently OAEP is most secure with regards to direct encryption. It has a specific overhead, and specifies the maximum message size as:

b. If mLen > k - 2hLen - 2, output "message too long" and stop.

So the maximum input block size is $k - 2 \cdot {hLen} - 2$ where $k$ is the key size in octets and ${hLen}$ is the length of the hash function used within OAEP. So e.g. for SHA-1 (the default) and a key size of 2048 bit you'd get a block size of $2048 / 8 - 2 \cdot 20 - 2 = 214$ octets.

If the Bleichenbacher attack is not possible you might also use PKCS#1 v1.5 padding which has just a padding overhead of 11 bytes.


So that takes care of the input block size. The output block size is much simpler:

c. Convert the ciphertext representative c to a ciphertext C of length k octets (see Section 4.1):

       C = I2OSP (c, k).

The I2OSP function changes the integer output of the RSA modular exponentiation and converts it into an octet stream using the Integer 2 (to) Octet Stream Primitive. So the length is the same as the key size (or modulus size) in octets.

So the output of a 2048 bit RSA calculation is just $2048 / 8 = 256$ bytes.


So in principle you can encrypt blocks of 214 bytes and output 256 bytes with a 2048 bit key. This is very inefficient, especially during decryption with the private key. Furthermore, you'd have the 42 bytes of overhead to deal with.

You'd have to access the private key continuously during decryption. This is not a good idea, in general you need to authenticate before using an asymmetric key used for decryption.

An attacker could also swap the blocks of encrypted data around, but such attacks are possible for any data that isn't authenticated.


So, as already indicated, everybody tries to use a hybrid cryptosystem instead of streaming data into RSA for encryption.

When using textbook RSA for practicing cryptography you could encrypt each letter of plaintext separately and then determine the block size as the modulus size in bytes. But please do not forget that such a scheme should not be used for any real-life protocols.

$\endgroup$
  • $\begingroup$ Although I agree whole-heartily with the information provided by Thomas I did want to provide a direct answer to the question. $\endgroup$ – Maarten Bodewes Mar 31 '16 at 18:16
  • $\begingroup$ Practically, the output does not need to be the size of the modulus, because small enough numerical ciphertexts might produce 0x00 at the most significant bytes and may therefore be dropped. Depending on the size of the modulus roughly 1 in 128 to 1 in 256 ciphertexts will be shorter than the modulus (in bytes). That's at least how pyCrypto behaves. $\endgroup$ – Artjom B. Mar 31 '16 at 21:43
  • $\begingroup$ @ArtjomB. Yeah, Bouncy Castle too I'm afraid - at least when the padding mode is not supplied. I just found some huge bugs in there trying to implement KEM. However, let's keep to the RSA standard for practical purposes, where I2OSP has to be performed. $\endgroup$ – Maarten Bodewes Mar 31 '16 at 22:44

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.