RSA function is defined over $Z_N^{*}$ where $N=pq$ with $p,q$ primes. A public key is a pair $(N,e)$ and a private key is $(N,d)$ where $d=e^{-1} \mod \phi(N)$.

Assume that RSA function is defined over $Z_t^{*}$ where $t$ is prime (instead of $t$ being composite). Show how one can compute $d$ from a public key $(t,e)$.

Could you check my solution? It looks a really easy assignment... if $t$ is prime, then $\phi(t)=t-1$, so $d$ can be calculate from formula: $d = e^{-1} \mod \phi(t)=e^{-1} \mod (t-1)$? And that's it?:)

  • $\begingroup$ Looks good, assuming you know how to compute the inverse of $e$ modulo $t-1$. (Do you?) $\endgroup$
    – yyyyyyy
    Jun 29 '15 at 18:53
  • 2
    $\begingroup$ I hope ;) extended euclidean algortihm? $\endgroup$ Jun 29 '15 at 18:55

In RSA, $\phi(N)$ is hidden and this is why nobody could calculate private key. For a prime modulus, order of multiplicative group is not a secret. Well, this question looks like encouraging your own thinking of RSA and related arithmetic, so please keep digging in.


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.