Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

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

2 Answers 2

up vote 5 down vote accepted

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.

share|improve this answer
    
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 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 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 at 13:35
add comment

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.

share|improve this answer
    
Well, as long as $e$ isn't truely stupid - eg $e\neq \pm 1$ –  figlesquidge Jan 28 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 at 9:53
    
Good spot - didn't notice the other question. –  figlesquidge Jan 28 at 10:15
1  
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 at 8:18
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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