How to calculate the maximum output size for data encrypted with a RSA Private Key?

I have an an encryption algorithm I am working with that looks like this:

prv_key_enc(sha1_hash(data))

Where, the RSA parameters are:

• 1024 bit keysize

I have provided the RSA parameters as well as information on the data that will be encrypted (sha1 hashed value) because I do not know if those details will affect the size of the output (hence this question).

Question: Is it possible to calculate the maximum number of bytes that will be output by the RSA encryption?

NOTES:

The algorithm is fixed by a third party and can not be changed.

Encoding of the encrypted data

The output from the RSA encryption will be base64 encoded, so the above algorithm becomes this:

base64(prv_key_enc(sha1_hash(data)))

Therefore, the final output size will be:

ceil( num_bytes_from_enc / 3 ) * 4

prv_key_enc

I don't know how to express the algorithm for prv_key_enc except for providing an example implementation (including the base64 encoding) using Java:

c.init(Cipher.ENCRYPT_MODE, privateKey);
bytes outputData = org.apache.commons.codec.binary.Base64.encodeBase64(c.doFinal(data));
• RSA 1024 will give you an output of 128 bytes. Mar 6 '14 at 12:21
• @DrLecter - Many thanks. If you provide your response as an answer (rather than a comment), I can credit you :) Mar 6 '14 at 12:41
• Note that the input size will be smaller, since the padding will take some space. Mar 6 '14 at 12:55
• I also strongly recommend using OAEP padding over PBKS#1v1.5 padding for RSA encryption. The latter has weaknesses which can be exploited in many use cases and are annoying to work around. Mar 6 '14 at 12:56
• Please note that what you are doing here is not actually an "encryption" algorithm, because there is no way to decrypt it. It looks a bit similar to a signature algorithm, though. Mar 6 '14 at 13:03

The RSA encryption function $f(m)_{(e,n)}:=m^e \mod n$ is a function that maps inputs from ${\mathbb Z}_n$ to outputs of ${\mathbb Z}_n$, where ${\mathbb Z}_n=\{0,\ldots,n-1\}$. Consequently, your output is always an integer in ${\mathbb Z}_n$ and if you use RSA with a 1024 bit modulus $n$, then your output (ciphertext) will be 128 bytes.

Edit: After reading the comments and taking a second look at your question it seems that you are describing RSA signatures. Anyways, the output of the signing function, which is also defined from ${\mathbb Z}_n$ to ${\mathbb Z}_n$, using an 1024 bit RSA modulus $n$ will also be 128 bytes.

Nevertheless, in any case of use of RSA please make sure that you use a secure padding scheme.

• I have trouble with your notation $m^e\pmod n$. To me that's a class of integers, including $m^e+N$. The single non-negative integer less than $N$ belonging to this class is $m^e\bmod n$. Also: " output (ciphertext) will be 128 bytes " might be correct with odds $\epsilon$, $127/128<\epsilon<255/256$ (that's if the encoding used the minimum number of bytes than can represent the result; that's not unseen, and has caused mysterious apparently random failures), or many other possibilities (e.g. with ASN.1 encoding it will be correct only with very low odds).
– fgrieu
Mar 7 '14 at 12:56
• @fgrieu you are right, that is often ambiguous (also in my answers). I know that it would be sounder to use a separate operator such as $MOD$ to make it unambiguous. However, it should be clear from the context. Clearly, you are also right with the exact length and that it depends on the encoding used internally before returning the result. I will improve the answer if I find time to do so. Mar 7 '14 at 13:05
• @fgrieu I have fixed the first issue :) Mar 7 '14 at 13:13

We do initially did not have the specification of prv_key_enc, thus we can could not answer with some level of certainty anything more than: the maximum size of its output, in bytes, is at least 128. Looks like the answer now is: the output is always exactly 128 bytes before Base64 encoding, making it exactly 172 bytes.

One thing is sure: the term prv_key_enc is grossly non-standard. Problem is not that Googling it is circular. The main issue is that in RSA, encryption is always with the public key, thus at least one of the following does not hold: prv is for private key, enc is for encryption and correctly describes the overall intend.

Confusing public with private is an even worse sin than confusing encryption with signature, so the best guess we can could make is that the question is about a signature, or rather the signature of a hash (which is functionally equivalent) if we trust the notation (the first step of signature in most practical schemes is hashing, but is part of the signature process, including unambiguously in PKCS#1, so the notation suggests the signature of a the result of sha1_hash that will get re-hashed; such double-hashing is sometime used in practice, e.g. in Global Platform).

Update (AGAIN): Even given the Java code, I am uncertain about what is really done. It could be some signature that is NOT one prescribed by PKCS#1: using RSAES-PKCS1-V1_5 encryption overs the hash of the message, except with the private key instead of the public key; this would be a randomized signature scheme; its security uh, would be an other question, depending to some degree on the verifying code, and perhaps the public exponent.

In any case, a PKCS#1 RSA cryptogram (resulting from one encryption or signature) with a key of $n$ bits is defined to be an octet-string of exactly $\lceil n/8\rceil$ octets, which is always enough to code $x^y\bmod N$ when $2^{n-1}<N<2^n$, where $y$ is the public exponent $e$ for encryption, and a private exponent $d$ for signature; and $x$ is a prescribed padding of the message to encipher, or of some hash of the message to sign. Under PKCS#1, encryption of a 20-octet SHA-1 hash with a 1024-bit key, and signature of any data of any size up to at least $2^{61}-1$ octets with any key, both result in a single RSA cryptogram. Thus for $n=1024$ the single cryptogram is exactly 128 octets (or bytes, that's synonymous on modern computers), including when the leading octet(s) are zero, assuming PKCS#1 is followed to the letter.

However the association of ECB (initials of Electronic Code Book) with PKCS1Padding is very uncommon, except as part of some crypto APIs trying to unify things that should not. Update: We are now told this is Java We are left uncertain about what ECB means. Especially if prv_key_enc did encryption as we are told it does, prv could designate some private hybrid encryption mode using ECB at some point, and who knows what the size of the cryptogram would then be, except that if it uses RSA per PKCS#1 it is going to be at least 128 octets, or won't be decipherable.

Also importantly, practice differ widely!! And we do not have any initially had no clue about practice in the mysterious prv_key_enc (we now have); in particular it is not uncommon that a PKCS#1 signature

• is ASN.1 encoded, which always increases its maximum size by several bytes, but can make it of variable size (leading bytes in the encoding of the integer can be suppressed, this is allowed but not required by at least some ASN.1 implementations, there is a complication with sign, leading to several different ASN.1 signatures valid for the same message even for deterministic signature schemes); (update: given the Java source, I would say this is not the case here);
• or/and is expressed as a base-64 (or other base) character string of characters, which increases the size in bytes to some degree (update: given the Java source, base-64 is used here).
• I've seen RSA/ECB/PKCS1Padding used in java contexts pretty often. But I'm not sure what it actually does. It might be equivalent to none, or perhaps it splits the message if it's too long. Mar 7 '14 at 15:43
• @CodesInChaos: I've met this in Java Card; that's what I allude to with my " except as part of some crypto APIs trying to unify things that should not "; I think that when the message is too big for encryption, it is supposed to be proken in pieces and use ECB, which is bad, or cause some error; and I've been told something on the tune of "do not to use it, we did not test it".
– fgrieu
Mar 7 '14 at 15:52
• All cryptographic transformations in Java follow the format algorithm/mode/padding or simply algorithm. If you need to specify the padding you're using for RSA, you need to go with the former transformation. There aren't really any modes for RSA since it is not a block cipher so that parameter is ignored. It might as well read "None" instead of "ECB." An exception will be thrown if you exceed the valid input size (depends on your padding). Your data won't get broken up into blocks. Mar 8 '14 at 5:39
• It doesn't really mention in any documentation what version of PKCS1 they are using.. Could be platform dependent. However, the JVM is required to have at least these two PKCS1v2 transformations: RSA/ECB/OAEPWithSHA-1AndMGF1Padding and RSA/ECB/OAEPWithSHA-256AndMGF1Padding, so it's probably better to rely on those instead of the ambiguous PKCS1 padding parameter. Also, Cipher is only used for Encryption/Decryption, NOT signatures. There is a Signature class for that. Mar 8 '14 at 17:15
• The public and private keys can both be used without any errors to encrypt a message using the Cipher class. It will perform modular exponentiation using the private key in this case. So if privateKey actually represents the private key then yes, he is using a private key to encrypt a message. Mar 8 '14 at 17:24