0
$\begingroup$

Given a public key $(e,n)$, if we are free to choose the plaintext does that mean we are able to generate any possible ciphertext in $Z_n$ ?

Because if we were given $e$ we can say that the decryption key is $e^{-1} = k \mod n$ and then choose the ciphertext we wish to generate, say $c$, perform $c^k$ and that shows that any ciphertext is "reachable" via encryption given a specific key and some plaintext?

Is that correct?

Edit: The question is theoretical so we assume we know both the public and the private key.

$\endgroup$
4
  • 2
    $\begingroup$ Possible duplicate of Does RSA work for any message M? $\endgroup$
    – kelalaka
    Dec 18, 2018 at 19:37
  • $\begingroup$ @kelalaka Not exaclty, what i mean is to use the key as exponent and not the phi(n) function. $\endgroup$
    – caffein
    Dec 18, 2018 at 19:40
  • $\begingroup$ In my case the message does not have to be relatively prime to anything, it is just a message so it's not so related. $\endgroup$
    – caffein
    Dec 18, 2018 at 19:47
  • 2
    $\begingroup$ A decryption key is $e^{-1} \pmod {\varphi(n)}$ and not $e^{-1} \pmod n$ $\endgroup$ Dec 18, 2018 at 19:52

1 Answer 1

3
$\begingroup$

Given a public key $(e,n)$, if we are free to choose the plaintext does that mean we are able to generate any possible ciphertext in $Z_n$ ?

Yes

Because if we were given $e$ we can say that the decryption key is $e^{-1} = k \mod n$

Not quite; the decryption key (which is traditionally named $d$; I'll leave it $k$ using your terminology) is related to the encryption key as $e \cdot k \equiv 1 \pmod{ \text{lcm}(p-1, q-1) }$, where $p, q$ are the prime factors of $n$, or in other words $e^{-1} = k \mod \text{lcm}(p-1, q-1)$. Other than that detail, you're correct.

and then choose the ciphertext we wish to generate, say $c$, perform $c^k \bmod n$ and that shows that any ciphertext is "reachable" via encryption given a specific key and some plaintext?

That is correct...

$\endgroup$

Your Answer

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

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