Given a key $e = 3$ (the public exponent for RSA) and a group of numbers, say $Z_n^*$ (the multiplicative group of $n = pq$, where $p$ and $q$ are primes as requested by RSA).

I can find the decryption key: $d = e^{-1}$

Is it correct to say than any member $a$ in $Z_n^*$ has a source such that: $source = a ^ d$?

Edit: suppose we have gcd(3,phi(n)) = 1 as requested by RSA

  • $\begingroup$ Question not clear for me. Are you asking; does every ciphertext has a unique plaintext? $\endgroup$ – kelalaka Dec 18 '18 at 13:46
  • $\begingroup$ @kelalaka What i mean is given a member of some group in Zn, and a key e, if i am free to choose my plaintext p, then no matter what member x in Zn i am given i can always generate the source of x, right ? I just need to perform x ^ (e^-1) and i get the source ? $\endgroup$ – caffein Dec 18 '18 at 15:12
  • $\begingroup$ So that basically means than given a specific key i can cover all of Zn: i just take a member in Zn, create the decryption key, decrypt and get the source and therefore i can generate a source for any member in Zn given a specific key, right ? $\endgroup$ – caffein Dec 18 '18 at 15:13

If you're asking whether the power map $x\mapsto x^a \pmod n$ is injective, it suffices to take $a$ with $1 < a < \phi(n)$ and $\gcd(a,\phi(n)) = 1$.

Edit: I couldn't complete the answer earlier. As mentioned in the comments $gcd(a,n)$ is enough, but for computational efficiency one might as well take $a \pmod n$ as the exponent. In the RSA setup, $n$ is square free thus the function is bijective.

To see this, note that after all $e,d$ have similar roles and if one of them, say $e$, satisfies $\gcd(e,n)=1,$ then there is an integer $f$ such that $ed+fn=1$ (by the fact that they are inverses) thus demonstrating $gcd(d,n)=1.$)

  • 2
    $\begingroup$ Actually, the condition $1 < a < \phi(n)$ is not actually required; it is injective iff $\gcd(a,\phi(n)) = 1$ $\endgroup$ – poncho Dec 18 '18 at 15:50
  • $\begingroup$ Further, if in addition to $\gcd(a,\phi(n)) = 1$ it holds that $n$ is square-free [that is the product of distinct prime(s)], then $x\mapsto x^a \bmod n$ is a bijection over $\Bbb Z_n$, in addition to being a bijection over $\Bbb Z_n^*$. $\endgroup$ – fgrieu Dec 18 '18 at 17:17

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.