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$
3
-
4$\begingroup$ Nope, RSA is defined over an residue class ring. $\endgroup$– DrLecterDec 17, 2014 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$– yyyyyyyDec 17, 2014 at 19:36
-
$\begingroup$ @yyyyyy jup, thats correct! :) $\endgroup$– DrLecterDec 17, 2014 at 19:40
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
2
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$– tyloDec 18, 2014 at 22:29
-
$\begingroup$ @tylo $x^{ed} = x$ holds for all $x$ in RSA. $\endgroup$– fkraiemJan 1, 2015 at 17:59
$\begingroup$
$\endgroup$
1
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$ Sep 19, 2015 at 15:49