8
$\begingroup$

Is it possible that if a plaintext is encrypted first with a key, $n_1$, and then this ciphertext is again encrypted using the same algorithm but a different key, $n_2$ that the resulting ciphertext could be converted back to the original plaintext with a single key?

For example: keys $n_1$, $n_2$, and $n_3$

$p_1$ = "plaintext"

$p_2 = C(n_1, p_1)$

$p_3 = C(n_2, p_2)$

Is this possible: $Dec(n_3, p_3) = p_1$? (where $C$ is an encryption algorithm taking the key and plaintext)

An example I can think of is the Caesar Cipher (the key can be seen as the shift). Where first a shift of 4 is used, and then a shift of 6. A shift of 16 would reveal the plaintext in a single operation (a single key).

Obviously this is a trivial example. Are there any cases where this could happen with a stronger algorithm, such as AES?

$\endgroup$
5
  • 1
    $\begingroup$ Hi, Joseph. The title of your question asks about decrypting with a third key, but then you wrote $C(n_3, p_3) = p_1$. Do you want the encryption algorithm to work as a decryption when used with the third key $n_3$ or that equation should be something like $Dec(c_3, p_3) = p_1$? $\endgroup$ Jul 31, 2019 at 12:59
  • $\begingroup$ Hilder Vítor Lima Pereira You're right, I'll change that. Thanks. $\endgroup$
    – Joseph
    Jul 31, 2019 at 13:03
  • 2
    $\begingroup$ The expression describing this is commutative encryption, see this question. It does not work for today's symmetric ciphers. $\endgroup$
    – tylo
    Jul 31, 2019 at 15:38
  • 1
    $\begingroup$ @tylo a cipher is commutative if $Enc_{k_1}(Enc_{k_2}(m)) = Enc_{k_2}(Enc_{k_1}(m))$? If yes, then this is not what the question is asking... The searched property here is $Dec_{k_3}(Enc_{k_2}(Enc_{k_1}(m))) = m$, which implies only $Enc_{k_2}(Enc_{k_1}(m)) = Enc_{k_3}(m)$ $\endgroup$ Jul 31, 2019 at 17:40
  • 4
    $\begingroup$ @tylo, no, this is asking if encryption under some cipher forms a group, and commutativity is neither necessary nor sufficient for something to be a group. $\endgroup$
    – Mark
    Jul 31, 2019 at 22:48

2 Answers 2

11
$\begingroup$

It is possible with the old Pohlig-Hellman cipher.

Here's how it works:

  • The global parameter is a prime $p$

  • A secret key is a value $k$ which is relatively prime to $p-1$

  • To encrypt a message $M$, you compute $C = M^k \bmod p$, and that's you

  • To decrypt a ciphertext $C$, you compute $k^{-1} \bmod p-1$, and then compute $M = C^{k^{-1}} \bmod p-1$

With this system, if you encrypt with $k_1$, and then with $k_2$, the resulting ciphertext is $C = (M^{k_1} \bmod p)^{k_2} \bmod p = M^{k_1k_2} \bmod p$; hence, this is identical to encrypting with the key $k_1k_2 \bmod p-1$, and so can be decrypted by that key.

$\endgroup$
3
$\begingroup$
  1. You cannot understand encryption as a Caesar Cipher. Caesar cipher is just a simple kind of linear transformation. Two linear operations (e.g., + - * / shift bits, etc) can be combined into one single operation easily.

  2. AES definitely cannot. AES consists of 10 rounds of calculations. Each round consists of both linear & non-linear steps. There is no relations between different keys, in your case they are n1, n2, n3.

$\endgroup$

Your Answer

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

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