5
$\begingroup$

Both Pohlig-Hellman and RSA perform encryption and decryption by exponentiation modulo some integer ($p$ prime for PH, $n$ composite for RSA). They both use a key $e$ as the exponent to encrypt a message. They both use the inverse element of key $e$ to decrypt. In both, the encryption key $e$ can be a randomly chosen integer coprime with $p-1=\phi(p)$ (for PH) or $\phi(n)$ (for RSA).

So what's the main difference between Pohlig-Hellman and RSA?

Note: The question has been edited for accuracy and more standard notations.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
13
$\begingroup$

The main difference is that Pohlig-Hellman is a symmetric cypher, while RSA is a public key system. This is because, with Pohlig-Hellman, anyone who knows the encryption key $e$ can compute the inverse operation (because the 'decryption' key $e^{-1} \bmod p-1$ is easy to compute), while the RSA, someone who knows the encryption key $e$ (but not the factorization of the RSA modulus) cannot compute the decryption operation.

Improve this answer
$\endgroup$
5
  • $\begingroup$ @markroxor: Pohlig-Hellman and RSA are more different than that; PH uses, one might say, q=1; and because computing $\phi N$ is easy, it is a symmetric system, based on the difficultly of discrete logs. In contrast, RSA is based on, well, the RSA problem, which assumes the difficulty of factoring (note: computing discrete logs in a composite modulus allows you to factor, hence we don't need to note the discrete log problem separately) $\endgroup$
    – poncho
    Commented Jul 28, 2022 at 12:01
  • $\begingroup$ I agree with you @poncho, I cannot edit my comment but I mistakingly commented that q=2 whereas it is q=1. $\endgroup$
    – markroxor
    Commented Jul 28, 2022 at 22:00
  • 1
    $\begingroup$ @markroxor: trick I've found to 'edit' a comment that is over 5 minutes old; copy it, delete it, and then re-add it (with corrections, of course...) $\endgroup$
    – poncho
    Commented Jul 29, 2022 at 12:26
  • $\begingroup$ breaks the continuity of the conversation but ok :) $\endgroup$
    – markroxor
    Commented Jul 29, 2022 at 13:16
  • $\begingroup$ To extend a bit upon your answer, in case of RSA we choose a number N s.t. N=pq (p and q being prime), hence 𝜙N = (p-1)(q-1). Pohlig-Hellman is RSA with q=1, hence, 𝜙N = 𝜙p = (p-1). What makes RSA strong is our inability to calculate 𝜙 N easily even if you know N, which isnt the case in Pohlig-Hellman. $\endgroup$
    – markroxor
    Commented Jul 29, 2022 at 13:16

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.