# 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? – fkraiem Mar 20 '16 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) – CryptoBoy Mar 20 '16 at 17:00
• Yes, I know what a field is. :) But RSA does not involve any field, or at lease not directly. – fkraiem Mar 20 '16 at 17:02
• I suggest you get a new tutor. – fkraiem Mar 20 '16 at 17:09
• So what algebraic structure are we using in RSA? – CryptoBoy Mar 20 '16 at 17:11

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 Mar 21 '16 at 11:16