Given a Polig-Hellman (is that really the name for that?) system with

$$C = M^k \bmod p$$

where $M$ is the message, $C$ is the ciphertext, $k$ is a (secret) key (any integer relatively prime to $p-1$), and $p$ is a large public prime.

Encrypting twice like this

$$(M^{k_{A}})^{k_{AB}} \bmod p = (M^{k_{B}})^{k_{BA}} \bmod p$$

where the second pair of keys is generated according to https://crypto.stackexchange.com/a/42140/41839, by selecting a random $k_B$ (relatively prime to $p-1$), and then computing

$$k_{BA} = k_{A} k_{AB} k_{B}^{-1} \bmod p-1$$

If the second encryption step with $k_{AB}$ and $k_{BA}$) is done by an untrusted server, so it knows these keys, what are the security aspects of such a system (besides not offering ciphertext indistinguishability as wanted)?

Given more key pairs matching the first one, can you calculate the secret key $k_{A}$ by solving the following equations if you know $k_{AB}$, $k_{AC}$, $k_{BA}$ and $k_{CA}$?

$$k_{BA} = k_{A} k_{AB} k_{B}^{-1} \bmod p-1$$ $$k_{CA} = k_{A} k_{AC} k_{C}^{-1} \bmod p-1$$

  • 1
    $\begingroup$ If the server knows one key, say $k_A$, then he can calculate the others $k_B$ and $k_C$. $\endgroup$
    – user27950
    Commented Dec 20, 2016 at 13:46
  • $\begingroup$ Named as Pohlig-Hellman Exponentiation Cipher. $\endgroup$
    – kelalaka
    Commented Mar 7, 2020 at 7:50


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.