# Does RSA operate over a Finite Field (Galois Field)?

Is it correct to say that RSA operates over a Finite Field (Galois Field)? In this case GF(p)? I do understant that the modulo in RSA is not itself a prime number, but all the operations (multiplication, inversion) occur as if it is a GF(p).

• Nope, RSA is defined over an residue class ring. – DrLecter Dec 17 '14 at 17:49
• @DrLecter: Technically, your comment does not contradict the statement in question: a residue class ring may be (isomorphic to) a finite field. You want to append "that is not a field". – yyyyyyy Dec 17 '14 at 19:36
• @yyyyyy jup, thats correct! :) – DrLecter Dec 17 '14 at 19:40

## 3 Answers

No, RSA encryption and signature is performed in (the multiplicative semigroup of) the factor ring $\mathbb Z/n\mathbb Z$ which is not a field since the non-zero elements $kp+n\mathbb Z$ (for $0<k<q$) and $kq+n\mathbb Z$ (for $0<k<p$) do not have multiplicative inverses. (However, one easily observes that all other non-zero elements are invertible, as their representants are coprime to $n=pq$).

• While the correct answer to the question is "no", the RSA definitions also can work for those elements, which are not coprime to $n$. Since they are zero divisors, they dont have inverse elements, but it can still be true that $x^{ed} = x$, with $x$ not coprime to $n$. I cant recall the exact requirement there, but there are topics on this on crypto-SE. – tylo Dec 18 '14 at 22:29
• @tylo $x^{ed} = x$ holds for all $x$ in RSA. – fkraiem Jan 1 '15 at 17:59

RSA operates over a multiplicative group $(\mathbb{Z}/n\mathbb{Z})^*$, not over a field. You can say that it's a ring, but since addition is not used in RSA it's redundant.

• A ring where multiplication is an abelian group is a field. – cpast Jan 1 '15 at 17:09
• @cpast No, the fact that the group of units of a ring is abelian does not imply anything about the ring, not even that it is commutative. – fkraiem Jan 1 '15 at 17:55
• In RSA $(\mathbb{Z}/n\mathbb{Z})^*$ is not a group. It's a semigroup, more specifically a monoid. – otus Sep 19 '15 at 15:59
• Well, no. What is called the multiplicative group, and written $(\mathbf Z/n\mathbf Z)^*$, or sometimes $(\mathbf Z/n\mathbf Z)^\times$, is the group consisting of all invertible elements modulo $n$. It is a group, and it is not to be confused with $\mathbf Z/n\mathbf Z \setminus \{0\}$ (sometimes also written $(\mathbf Z/n\mathbf Z)^*$, thats unfortunate...). – Calodeon Sep 19 '15 at 16:41
• @Calodeon, that group does not form a ring, however. – otus Sep 19 '15 at 16:51

William Stalling says

RSA is based on exponentiation in a finite (Galois) field over integers modulo a prime

• The RSA modulus is not prime, so arithmetic modulo n is no finite field. So that statement is either wrong, or at least very misleading. (Using a sufficiently loose interpretation of "based on" you could say that private key arithmetic using the Chinese-Remainder-Theorem works in several finite fields, one per factor of the modulus, but I don't think that's a useful interpretation) – CodesInChaos Sep 19 '15 at 15:49