1
$\begingroup$

I couldn't find any articles that addressed to how to decrypt c after it was encrypted using the Pohlig-Hellman cipher if $e$ and $n-1$ aren't relatively.

Can someone please tell me how to do it?

I couldn't find an questions about this on StackExchange.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

It is essentially the same as the answer I gave in How to compute $m$ value from RSA if $phi(n)$ is not relative prime with the $e$?, with the same restrictions ($e$ assumed prime, $e^2$ assumed not to be a divisor of $p-1$), with the sole change being that $\lambda = p - 1$.

It's easy enough to cover the composite $e$ case (factor $e$ into primes $e = r_1 r_2 … r_n$, and then find solutions for $c = m^{r_1 r_2 … r_n}$ by inverting each $r_i$ individually.

The other case $e^2$ is a divisor of $p-1$ is a lot tougher, and probably needs a different approach...

Improve this answer
$\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.