# Equation for largest text-block size mod n in RSA encryption

I am working on a small program in sage that encodes messages using RSA encryption in an attempt to show the process step by step, along with mathematical justifications for each step, for a presentation. This question deals with the mathematics behind it, so i figured it would be better to post here than at the crypto stack exchange forum.

In RSA, you have a large modulus, n. When a message gets encoded, it is broken up into blocks of k letters each, and we must be sre that these blocks are less than n (the modulus). What is, then, the largest block size k that can be used? I believe it is

$$k = \left\lceil \frac{ln(n+1)}{ln(256)} \right\rceil -1$$

But can not figure out how to prove/show this?

• If you chop your message into RSA-sized blocks, do not just encrypt each block separately with the RSA primitive! Doing so corresponds to using RSA as a block cipher in ECB mode, which is considered not to be secure for general use -- an eavesdropper would be able to tell if two messages you send start or end with the same several bytes, which can be a significant information leak. If you must use RSA as your only primitive, you should still use it in a mode that prevents this, such as CBC with a random separately encrypted IV (and modular addition/subtraction in place of the XORs). – Henning Makholm Nov 7 '15 at 18:05

RSA allows the encryption of any message $M$ between 0 and $n-1$. Technically $M$ should be coprime to $p$ and $q$ ($pq=n$), but realistically we do not need to worry about this because finding an $M=kp$ is equivalent to factoring $n$. Moreover, RSA still works with such an $M$ (although the standard proof does not show this).

So any $M$ between 0 and $n-1$ has the property that $M^{ed}=M \bmod n$. You ask how to encode a longer message? The obvious way is to break the longer message into a base-$n$ number and encode each "digit." In other words, treat your longer message $M^*$ as a very large integer and let $M^*=jn+k$ where $k<n$ and use $k$ as an input to RSA. Repeat.

Your question seems to want to do this in base-256 instead. The expression you gave is computing

$$\lceil \log_{256} (n+1) \rceil$$

which gives the number of bytes required to accommodate a "chunk" of $M^*$. Is this what you're after?

Finally, I should say that no one really breaks a message down and encrypts each chunk like this using RSA. First it's insecure, and second it's inefficient (since RSA is slow compared to symmetric algorithms). Instead you would pick a symmetric key $K$ and encrypt $K$ with RSA, then append (say) the AES-CBC encryption of $M^*$ under $K$.

• "Technically $M$ should be coprime to $p$ and $q$": No, this is not necessary. For a message that happens to be a multiple of $p$, it will still be the cases that $M^{k(p-1)(q-1)+1}\equiv 0 \equiv M\bmod p$ (obviously), and $M^{k(p-1)(q-1)+1}\equiv M \bmod q$ (due to Fermat's little theorem for $q$), so by the Chinese Remainder Theorem the only possible value of $M^{k(p-1)(q-1)+1}$ modulo $pq$ is $M$ itself. – Henning Makholm Nov 7 '15 at 17:35
• The general fact is that $a^{k\varphi(m)+1}\equiv a\pmod m$ if either $a$ is coprime to $m$ (Euler's theorem), or $m$ is square-free (by the above reasoning). So RSA works for any messages as long as the original two primes are different. – Henning Makholm Nov 7 '15 at 17:38
• @HenningMakholm "should be" is different to "must be." I said "should be" because otherwise the standard proof fails and you have to use a more involved argument (as you have done in your comment). I noted in my answer that RSA still works even without this condition. You seem to be agreeing. – Fixee Nov 7 '15 at 17:43
• x @Fixee: I seem to draw a different conclusion though, namely that what you call the "standard proof" does not work to prove that RSA produces a pair of inverse permutations. Therefore, I don't think calling that proof "standard" is warranted, when it doesn't actually prove what we need to have proved. It's a lot better to use a proof that works than to claim that the message "should" satisfy a condition that the sender doesn't even know what is! – Henning Makholm Nov 7 '15 at 17:47
• Fixee. Yes! I must have misrepresented what i was after. I am looking for the reason that k is equal to that logarithm you mentioned (i.e. The reasoning why k must equal that to ensure the process still works modulo n) – Bryan Nov 7 '15 at 19:32