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).

  • 4
    $\begingroup$ Nope, RSA is defined over an residue class ring. $\endgroup$ – DrLecter Dec 17 '14 at 17:49
  • 2
    $\begingroup$ @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". $\endgroup$ – yyyyyyy Dec 17 '14 at 19:36
  • $\begingroup$ @yyyyyy jup, thats correct! :) $\endgroup$ – DrLecter Dec 17 '14 at 19:40

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$).

  • $\begingroup$ 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. $\endgroup$ – tylo Dec 18 '14 at 22:29
  • $\begingroup$ @tylo $x^{ed} = x$ holds for all $x$ in RSA. $\endgroup$ – 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.

  • 1
    $\begingroup$ A ring where multiplication is an abelian group is a field. $\endgroup$ – cpast Jan 1 '15 at 17:09
  • $\begingroup$ @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. $\endgroup$ – fkraiem Jan 1 '15 at 17:55
  • $\begingroup$ In RSA $(\mathbb{Z}/n\mathbb{Z})^*$ is not a group. It's a semigroup, more specifically a monoid. $\endgroup$ – otus Sep 19 '15 at 15:59
  • 3
    $\begingroup$ 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...). $\endgroup$ – Calodeon Sep 19 '15 at 16:41
  • $\begingroup$ @Calodeon, that group does not form a ring, however. $\endgroup$ – 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

Source: http://williamstallings.com/Extras/Security-Notes/lectures/publickey.html

  • 3
    $\begingroup$ 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) $\endgroup$ – CodesInChaos Sep 19 '15 at 15:49

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.