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 Jan 27 '14 at 22:42
  • $\begingroup$ But m^e will be a huge number though $\endgroup$ – Gretty Jan 27 '14 at 22:43
  • $\begingroup$ I think he's not aware that you can do mod n after each intermediate multiply. $\endgroup$ – poncho Jan 27 '14 at 22:44
  • $\begingroup$ How does that work? $\endgroup$ – Gretty Jan 27 '14 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 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.

| improve this answer | |
  • $\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 Jan 28 '14 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 Feb 2 '14 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$ – Gilles 'SO- stop being evil' 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.

| improve this answer | |
  • $\begingroup$ Well, as long as $e$ isn't truely stupid - eg $e\neq \pm 1$ $\endgroup$ – Cryptographeur Jan 28 '14 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 Jan 28 '14 at 9:53
  • $\begingroup$ Good spot - didn't notice the other question. $\endgroup$ – Cryptographeur Jan 28 '14 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$ – Ilmari Karonen Jan 29 '14 at 8:18

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.