Are there two step encryption systems that - given the same plain text - support choosing two keys ($k_{A_1}, k_{A_2}$) for a first encryption so, that you can calculate another pair of keys ($k_{B_1}, k_{B_2}$) resulting in equal cipher texts?

$E(k_{B_1}, E(k_{A_1}, m)) = E(k_{B_2}, E(k_{A_2}, m))$ with $k_{A_1} \neq k_{A_2}$

A one-time-pad encryption is one of these systems, if you choose the keys like this $k = k_{A_1} \oplus k_{B_1} = k_{A_2} \oplus k_{B_2}$. Are there other systems that don't suffer from key re-usage?


1 Answer 1


There's always the old Polig-Hellman 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.

Decryption can be done as:

$$M = C^{k^{-1} \bmod p-1} \bmod p$$

To address your requirement, given $k_{A_1}, k_{A_2}$, you can select a random $k_{B_1}$ (relatively prime to $p-1$), and then compute $k_{B_2} = k_{A_1} k_{B_1} k_{A_2}^{-1} \bmod p-1$, and Bob's your uncle.

  • $\begingroup$ If one knows $k_{B_1}$ and $k_{B_2}$ ($p$ and $p-1$ are public), how hard is it, to find out the other keys $k_{A_i}$? $\endgroup$
    – ChaosCoder
    Dec 8, 2016 at 12:10
  • $\begingroup$ @ChaosCoder: just from the information $k_{B_1}, k_{B_2}$, and you're looking for a specific pair $k_{A_1}, k_{A_2}$ (other than just any pair that works), impossible (there are $p-1$ pairs of possible $k_{A_1}, k_{A_2}$ pairs that are compatible, and each pair has $E(k_{B_1}, E(k_{A_1}, m))$ acting as a different transform (assuming $E$ doesn't have equivalent keys). $\endgroup$
    – poncho
    Dec 8, 2016 at 14:21

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.