# Split encryption into two steps

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?

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.

• 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}$? Dec 8, 2016 at 12:10
• @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). Dec 8, 2016 at 14:21