0
$\begingroup$

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

Improve this question
$\endgroup$
3
  • $\begingroup$ Question not clear for me. Are you asking; does every ciphertext has a unique plaintext? $\endgroup$
    – kelalaka
    Dec 18, 2018 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, 2018 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, 2018 at 15:13

1 Answer 1

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • 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, 2018 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, 2018 at 17:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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