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?

  • $\begingroup$ 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). $\endgroup$ – 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$.

  • $\begingroup$ "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. $\endgroup$ – Henning Makholm Nov 7 '15 at 17:35
  • $\begingroup$ 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. $\endgroup$ – Henning Makholm Nov 7 '15 at 17:38
  • $\begingroup$ @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. $\endgroup$ – Fixee Nov 7 '15 at 17:43
  • $\begingroup$ 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! $\endgroup$ – Henning Makholm Nov 7 '15 at 17:47
  • $\begingroup$ 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) $\endgroup$ – Bryan Nov 7 '15 at 19:32

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.