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).
$\begingroup$
$\endgroup$
-
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
$\begingroup$
$\endgroup$
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$
$\endgroup$
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
$\begingroup$
$\endgroup$
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
