When encrypting with RSA one calculates $ m^e \pmod n $ by doing the following:

m^e % n

Where $m$ is what we encrypt. Often $e$ is a very big number to make it more difficult to crack.

So how does one avoid overflow when encrypting?

  • 1
    $\begingroup$ What do you mean by overflow? The mod n ensures that the result will never be bigger than n $\endgroup$
    – mikeazo
    Commented Jan 27, 2014 at 22:42
  • $\begingroup$ But m^e will be a huge number though $\endgroup$
    – Gretty
    Commented Jan 27, 2014 at 22:43
  • $\begingroup$ I think he's not aware that you can do mod n after each intermediate multiply. $\endgroup$
    – poncho
    Commented Jan 27, 2014 at 22:44
  • $\begingroup$ How does that work? $\endgroup$
    – Gretty
    Commented Jan 27, 2014 at 23:07
  • 1
    $\begingroup$ You're not computing m^e and then reduce it modulo n. You do the mod n reduction after every multiplication. And you compute m^e mod n via something like a square and multiply algorithm where "mod n" is built into the squaring and multiplication. Note, however, that such a simple implementation will leak information on side-channels. So, if you really want to use RSA, you just take a well-known open source library to do that. :) $\endgroup$
    – sellibitze
    Commented Jan 28, 2014 at 11:32

2 Answers 2


Actually, the fundamental mathematical operation is not
$$ \begin{align} \mathbb{N} &\to \mathbb{N} \\ m &\mapsto (m^e) \bmod n & \text{(elevate to the power of \(e\), divide by \(n\) and take the remainder)} \\ \end{align} $$ but $$ \begin{align} \mathbb{Z}/n\mathbb{Z} &\to \mathbb{Z}/n\mathbb{Z} \\ m &\mapsto (m^e) \bmod n & \text{(elevate to the power of \(e\))}\hphantom{\text{, divide by \(n\) and take the remainder}} \\ \end{align} $$ It is an operation in modulo arithmetic.

In computations, the elements of $\mathbb{Z}/n\mathbb{Z}$ are almost always represented by the representative in the range $[0,n-1]$. Each elementary operation is performed in $\mathbb{N}$, then the result is truncated modulo $n$. For example, if $n$ fits in $k$ machine words, then a multiplication of two elements of $\mathbb{Z}/n\mathbb{Z}$ can be performed by computing the product, which fits in $2k$ machine words, then taking the remainder modulo $n$, yielding a representation of the element of $\mathbb{Z}/n\mathbb{Z}$ that is again in the range $[0,n-1]$ and in particular fits in $k$ words. Taking the exponential of a number involves a series of multiplication, each of which is truncated to $[0,n-1]$ in this way so as to obtain the smallest representative of the element of $\mathbb{Z}/n\mathbb{Z}$.

Even multiplication of two $k$-word numbers can be performed with intermediate values fitting in $k$ words. The naive method is wasteful both in the amount of memory and in that it builds a large number only to divide it afterwards. Methods such as Montgomery multiplication avoid computing a double-size number by reducing the size of the result after each intermediate step in the multiplication.

  • $\begingroup$ The technique in the last paragraph, with intermediate values fitting in $k$ words, is also usable for regular arithmetic (allowing a close match of the performance of Montgomery arithmetic, and even better performance for small $e$); see e.g. this paper of Dehm and Quisquater. $\endgroup$
    – fgrieu
    Commented Jan 28, 2014 at 10:15
  • $\begingroup$ I really don't understand this answer, what is $\mathbb{Z}/n\mathbb{Z}$, and what is meant by machine words? $\endgroup$
    – Gretty
    Commented Feb 2, 2014 at 17:48
  • $\begingroup$ @Gretty $\mathbb{Z}/n\mathbb{Z}$ is arithmetic modulo $n$. It's the basic math in which RSA works. A machine word is the basic unit that computers perform operations on, typically 32-bit or 64-bit numbers; operations on crypto-size numbers have to be decomposed in terms of these operations in order to perform them on a computer. $\endgroup$ Commented Feb 3, 2014 at 13:35

To clarify a misconception in your question:

It is not true that $e$ is chosen large to make RSA more difficult to crack. Often $e$ is chosen from $\{3,5,17,257,65537\}$. This has computational advances with regard to square and multiply algorithms as mentioned by Gilles. The choice of $e$ has no influence in the security of RSA primitive (as long as $\gcd(e,\lambda(n))=1$) - although there are flaws in the whole scheme for small exponents.

  • $\begingroup$ Well, as long as $e$ isn't truely stupid - eg $e\neq \pm 1$ $\endgroup$ Commented Jan 28, 2014 at 9:44
  • $\begingroup$ Well of course, also $\gcd(e, \lambda(n)) = 1$ should hold. Like mentioned in OP other question crypto.stackexchange.com/questions/13166/… $\endgroup$
    – gmoktop
    Commented Jan 28, 2014 at 9:53
  • $\begingroup$ Good spot - didn't notice the other question. $\endgroup$ Commented Jan 28, 2014 at 10:15
  • 1
    $\begingroup$ Also, just to clarify your last sentence above, the "flaws" for small $e$ (like Coppersmith's attack) only appear if one does not use a secure padding scheme (e.g. OAEP). With proper padding, RSA is secure even for $e=3$; without proper padding, it may not be secure for any $e$. $\endgroup$ Commented Jan 29, 2014 at 8:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.