3
$\begingroup$

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?

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\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, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.