# Algebraic structures in RSA

1. Why do we need a field for RSA and what are the two operations in this field?

2. Why can't we have a ring or group for example? Because in a group you also have inverse elements.

• What is the "field" you are speaking of regarding RSA? Commented Mar 20, 2016 at 16:06
• The title says "Algebraic Structures" so I'm speaking of the field as an algebraic structure. -> en.wikipedia.org/wiki/Field_(mathematics) Commented Mar 20, 2016 at 17:00
• Yes, I know what a field is. :) But RSA does not involve any field, or at lease not directly. Commented Mar 20, 2016 at 17:02
• I suggest you get a new tutor. Commented Mar 20, 2016 at 17:09
• So what algebraic structure are we using in RSA? Commented Mar 20, 2016 at 17:11

RSA is not done over field. When using RSA, you rely on the fact that the adversary does not know the order of the multiplicative group, i.e. he does not known the value of Euler's totient function and he is unable to compute it.

Over field, computing it is trivial.

RSA encryption can be seen as an operation in a finite abelian group of order $\phi(n)$, with the the private exponent and public exponent being inverse elements of each other.

Then you see that $m*k*k^{-1} = m$. Of course the group operation is actually integer exponentiation with the result taken modulo some large (composite) number, $n$.

This is true, since there is an identity element $1$, for each $k$ such that $gcd(k, {\phi}(n)) = 1$ has an inverse element (each element in the group), and the group is closed because $gcd(k_0*k_1, \phi(n)) = 1$, for group elements $k_0, k_1$ (yielding another element in the group). The group is abelian simply because multiplication (of exponents) is commutative: $m^{ab} = m^{ba}$.

• The nature of $*$ in this answer is confusing (at least to me), and that muddies (my perception of) the whole answer. $*$ can't be an associative group law, e.g. in $m*k*k^{-1}=m$. And $k^{-1}$ is not the inverse of $k$ with respect to the law in the group $m$ belongs to. Further, messages that have no inverse modulo $n$ still are valid RSA, and I fail to reconcile that with "RSA encryption can be seen as an operation in a finite abelian group (..)".
– fgrieu
Commented Mar 21, 2016 at 11:16