29

What is RSA encryption output size when using 2048 bit key and pkcs1padding.

Is it always 256 bytes independent of input size?

How can i calculate it for other key sizes?

jww
  • 97,681
  • 90
  • 411
  • 885
hyda
  • 550
  • 1
  • 6
  • 15
  • 6
    Have you noticed that 256*8=2048? – Perseids Sep 06 '14 at 10:17
  • 2
    @Perseids. yes, but i am not sure that output is always 256 byte. is it? – hyda Sep 06 '14 at 10:25
  • 4
    From [`RSA_size`](https://www.openssl.org/docs/man1.1.0/crypto/RSA_size.html): *"RSA_size() returns the RSA modulus size in bytes. It can be used to determine how much memory must be allocated for an RSA encrypted value."* (The message size is dependent upon modulus size). – jww Jul 03 '17 at 04:00

3 Answers3

24

Yes, it is.

The output-size should always equals the size of the Modulus (part of the key), so:

2048 bit Modulus -> 2048 bit output
1024 bit Modulus -> 1024 bit output
...

If it is not, there exist numerous attacks on RSA, see here for basic information about that.

So to guarantee that the output is 2048 bit even when the input to encrypt is, let's say 7,
a padding must always be applied!

i_turo
  • 2,679
  • 1
  • 13
  • 15
  • 1
    The situation is a bit more complicated. Being somewhat pedantic I could argue that if the modulus is small for its bit size (say it begins with the bits 100) then you have a fair chance to get a ciphertext that is actually a bit shorter than the the modulus. But more to the point, not large input values, but a sound padding scheme make RSA secure. For example the [attack by John Hastad](http://www.nada.kth.se/~johanh/rsalowexponent.ps) works with any deterministic padding scheme if you use a small exponent (e.g. 3). – Perseids Sep 06 '14 at 10:47
  • 2
    The reason for the output being the same as the modulus is because **it is explicitly made to fit the size of the modulus**. Is it **not** because padding is applied. Even when padding is applied **moduluar** exponentiation will result in a random looking value between **zero** and the modulus, and this value could be encoded in **fewer bytes than the modulus**. See [my answer](https://stackoverflow.com/a/25701064/589259) why the result is still the same size as the modulus. This answer does not explain why the result is the same size as the modulus in bytes. – Maarten Bodewes Mar 12 '18 at 23:45
7

The output (as integer) of RSAEP (RSA encryption primitive) is always between 0 and n:

  1. If the message representative m is not between 0 and n-1, output message representative out of range and stop.

  2. Let c = m^e mod n.

  3. Output c.

Of course, c is a number. So you have to convert it to bytes for it to be usable. The only thing known about c is that it is smaller than n for a large value of m. It may be that c is a few bytes smaller even if m is large.

You've mentioned PKCS1Padding, which is part of the RSAES-PKCS1-V1_5-ENCRYPT encryption scheme. The padding will make sure that m is always large and randomized; requirements for RSA encryption to be secure.

You'll find that the encoding of c is specified in there:

...

Step 4: Convert the ciphertext representative c to a ciphertext C of length k octets: C = I2OSP (c, k)

...

where k is the size of the modulus in octets (bytes).

So yes, the answer is always k, the size of the modulus in bytes. Simply because the standard requires it that way. It is a value encoded as unsigned big endian number prefixed with as many zero bytes as required.

Notes:

  • the modulus size defines the key size. So the output of an RSA encryption is the same as the key size: ceil(keySize / 8.0) using floats or (keySize + 8 - 1) / 8 using integers.

  • RSA with OAEP padding uses the same technique, so the answer is correct for OAEP as well (and most other, less known schemes such as RSA-KEM).

  • Many library routines that perform "raw" RSA (just modular exponentiation of the message with the public exponent) still perform the I2OSP function - but better check to make sure.

Community
  • 1
  • 1
Maarten Bodewes
  • 90,524
  • 13
  • 150
  • 263
  • 3
    If unsure, read the standard! They are often much more readable than people expect. – Maarten Bodewes Sep 06 '14 at 14:06
  • To get the final buffer size using binary logic: `needed = (size + (keySize >> 3) - 1) & ~((keySize >> 3) - 1))` – Geoffrey Jun 16 '20 at 08:15
  • Why would you obscure that calculating by using shifts? Why not let the compiler figure it out? Readability is doubtlessly more important for this kind of calculation. – Maarten Bodewes Jun 16 '20 at 09:54
  • Why would you calculate it using floats, which are, by definition, imprecise? It's just to demonstrate another method, that's all :). – Geoffrey Jun 16 '20 at 10:02
3

The output size of plain RSA (using some padding scheme, but no hybrid encryption) is always the key size. The reason is that for some public key n the result is some integer c with 0<=c<n. There are lots of introductions for RSA, e.g. http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-045j-automata-computability-and-complexity-spring-2011/lecture-notes/MIT6_045JS11_rsa.pdf

Perseids
  • 12,584
  • 5
  • 40
  • 64