# Montgomery and Galois fields

I'm a little bit confused about the design of a RSA module in VHDL. My question isn't directly related to hardware design. I've read a lot of publications and I bought also a book. In one publications I've found 2 different Montgomery algorithms. The first works in $GF(\hspace{.04 in}p)$, where $p$ is the modulus (so the inputs have to be smaller than $p$). The second algorithm works in $GF(2^m)$, where $m$ is the width of the multiplier. Now, what is the best choice for a RSA modulus? Is RSA encrypt/decrypt a standard operation?
It basically is a modular exponetiation, right?

I've already replied to the question posted some days before. Montgomery multiplication is another way to perform modular multiplication in the residue system representation. The operation induced is in fact a group morphism. In $GF(p)$, $p$ prime, or in the multiplicative group $\mathbb{Z}/n\mathbb{Z}$, the transformation allows to perform modular multiplication without division. But beforehand, you have to convert the operands in the new representation.

How are two operands $a$ and $b$ multiplied in the residue representation in $\mathbb{Z}/n\mathbb{Z}$?

First: you select a radix $R$ relatively prime, with the modulus $n$. $R$ is generally a power of $2$, for which division is obvious.

• Operands $a$ and $b$ are converted into $A=a\cdot R \bmod n$, and $B=b\cdot R \bmod n$.
• Use Montgomery algorithm to compute $$C=\operatorname{Montgo}_{\rm Mul}(A,B, n)= A * B \bmod n = a\cdot b\cdot R^{-1}$$
• Convert back to regular representation: $$c=\operatorname{Montgo}_{\rm Mul}(C,R^{2} \bmod n, n)=C*R^2 \bmod n = C \cdot R^2\cdot R^{-1} \bmod n \\ = C\cdot R \bmod n= a\cdot b\cdot R^{-1}R \bmod n= a\cdot b \bmod n$$

Here the Montgomery multiplication is denoted by $*$, and as a group morphism, it can be used to perform modular exponentiation in the residue system. Operand to be exponentiated is converted once at the beginning of the process, and after the result is converted back to regular representation. If $C=A^{*e}$ is the exponentiation of $A=a \cdot R \bmod n$, then $c=a^e= C*R^2 \bmod n$.

Hence Montgomery Multiplication is preferred in case of multiple reductions with the same modulus is required as in the case of modular exponentiation.

For binary representation $GF(2^m)$ an analogous application can also be adapted. Search over the Web.

• Ok, I already know how to use a Montgomery multiplier ( conversion operands in montgomery representation and reverse ). My question is a little bit different. I asked what is the best choice for a RSA module. Because in $GF(p)$ my inputs have to be smaller than modulus $p$, in $GF(2^m)$ don't. Now I don't know if the base of the exponential function ( plain text for encrypt or cypher text for decrypt ) has restriction deriving from modulus. Jan 20 '15 at 12:06
• P.s. Of course the inputs of my multiplier are the base of modular exponentiation. Jan 20 '15 at 12:11
• Your question is a little bit confused. $GF(2^m)$ is generated by a polynial of degre m, and all its elements are represented by a polynomial of degre at most m-1. Knowing that, you can use exactly the same procedure as in $Z/nZ$ to implement Montgomery arithmetic in $GF(2^m)$. As it's explained above this operation is a morphism of multiplicative groupe. From implementation the only difference is the reduction is obtained by right-shift if the lsb is 1 (otherwise you can't divide by $\alpha$ generating root). Try it on a small example and show it us. RSA can't be implemented on $GF(2^m)$. Jan 20 '15 at 13:33