# Avoiding overflow when encrypting with RSA

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?

-
What do you mean by overflow? The mod n ensures that the result will never be bigger than n – mikeazo Jan 27 '14 at 22:42
But m^e will be a huge number though – Gretty Jan 27 '14 at 22:43
I think he's not aware that you can do mod n after each intermediate multiply. – poncho Jan 27 '14 at 22:44
How does that work? – Gretty Jan 27 '14 at 23:07
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. :) – sellibitze Jan 28 '14 at 11:32

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.

-
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. – fgrieu Jan 28 '14 at 10:15
I really don't understand this answer, what is $\mathbb{Z}/n\mathbb{Z}$, and what is meant by machine words? – Gretty Feb 2 '14 at 17:48
@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. – Gilles Feb 3 '14 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.

-
Well, as long as $e$ isn't truely stupid - eg $e\neq \pm 1$ – figlesquidge Jan 28 '14 at 9:44
Well of course, also $\gcd(e, \lambda(n)) = 1$ should hold. Like mentioned in OP other question crypto.stackexchange.com/questions/13166/… – gmoktop Jan 28 '14 at 9:53
Good spot - didn't notice the other question. – figlesquidge Jan 28 '14 at 10:15
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$. – Ilmari Karonen Jan 29 '14 at 8:18