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

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

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

| improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ 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 (..)". $\endgroup$ – fgrieu Mar 21 '16 at 11:16
1
$\begingroup$

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.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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