# RSA - source and image - all are possible?

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

• Question not clear for me. Are you asking; does every ciphertext has a unique plaintext? Dec 18 '18 at 13:46
• @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 ? Dec 18 '18 at 15:12
• 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 ? 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.$$)
• Actually, the condition $1 < a < \phi(n)$ is not actually required; it is injective iff $\gcd(a,\phi(n)) = 1$ Dec 18 '18 at 15:50
• 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^*$.