I am preparing for the final exam in my Data Security class so I am trying to read and understand the textbook's exercise questions. Any hint would be great.

Question (Exercise 9.14 of textbook): enter image description here

enter image description here

Observation: Similar to $RSA$ decryption that $e.d = 1$, we to find some number $r$ such that $E*r = 1$ so that $(m^E)^r \ (mod \ N) = m$. But what should that $r$ be? Any hint would be great.


I will assume that Alice uses $D' = E^{-1}(\varphi(N) - 1)$ with $E^{-1}$ the inverse of $E$ modulo $\lambda(N)$. The question uses a very specific definition of $D'$, which requires the assumption that $E$ divides $\varphi(N) - 1$. But since such an $E$ is necessarily coprime to $\varphi(N)$, it is a special case of the more general definition of $D'$ provided above.

So we must find some number $E'$ such that $$E' E^{-1}(\varphi(N) - 1) \equiv 1 \pmod {\lambda(N)}$$ Now note that $E' = -E$ is a solution because $\varphi(N) \equiv 0 \pmod{\lambda(N)}$, so we have

$$m^{-ED'} \equiv 1 \pmod N$$.

So given $c = m^{E}$, compute $c^{-D'}$ to obtain $m$ again. Either you first take the inverse, or you just use $\lambda(N) - D'$ as the exponent.

| improve this answer | |

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.