7
$\begingroup$

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

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

2 Answers 2

Reset to default
11
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • 1
    $\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, 2014 at 22:29
  • $\begingroup$ @tylo $x^{ed} = x$ holds for all $x$ in RSA. $\endgroup$
    – fkraiem
    Jan 1, 2015 at 17:59
-3
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • 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, 2015 at 15:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.