# RSA function over $Z_t^{*}$ where $t$ is prime

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?:)

• Looks good, assuming you know how to compute the inverse of $e$ modulo $t-1$. (Do you?) – yyyyyyy Jun 29 '15 at 18:53
• I hope ;) extended euclidean algortihm? – cryptohater 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.