1
$\begingroup$

I am not sure whether "linear decomposition" is appropriate to summary my question: We know that the traditional symmetric encryption/decryption algorithm (like AES, TDES) can be written as:

C = FUN_enc(key, P) P = FUN_dec(key, C)

Where FUN_enc is the encryption function/algorithm, FUN_dec is the decryption function, C is ciphertext, P is plaintext. For AES, FUN_enc and FUN_dec are AES encrypt and decrypt algorithms. Here we only consider the basic ECB mode.

OK, now comes my question: Does one encryption/decryption algorithm exists, that satisfy:

C1 = FUN_enc(key1, P) C2 = FUN_enc(key2, C1) and: C2 = FUN_enc(key3, P)

That is, one encryption can be splited into two individual encryption steps, and also give key1, key2, some algorithm can calculate key3.

One algorithm that can be decomposed to two:

FUN_enc(key, P) = FUN_enc(ke2, FUN_enc(key1, P)) and the algorithm FUN_enc SHALL also as secure as AES.

https://stackoverflow.com/questions/76967037/does-any-encryption-decryption-algorithm-supports-linear-decomposition

Improve this question
$\endgroup$
3
  • $\begingroup$ The question is ambiguous. Is it required that for any key1 and key2 we can find key3? That for any key3 we can find key1 and key2? That there is a decryption function? That keys are constant-size? What security properties are desired? The Pohlig-Hellman exponentiation cipher allows what you ask, except it has the property $E_k(XY\bmod P)=E_k(X)E_k(Y)\bmod P$ which often is undesirable. Independently: with keys any size multiple of 256 bit, it's easy to make something AES-256 based such that for any key1 and key2 we can find key3, merely as the concatenation of key1 and key2. $\endgroup$
    – fgrieu ♦
    Commented Aug 26, 2023 at 14:27
  • $\begingroup$ @fgrieu Oh, sorry. This question has these restrictions: 1. key3 is fixed and can't be changed. so it requires for fixed key3, we can find key1 and key2. 2. key1 and key2 are variables, and have constant-size. I have checked Pohlig-Hellman exponentiation cipher, it is based on prime number exponent, like RSA, but here I don't want to introduce big number operations, I just want some AES like symetric algorithms. And I have read kodlu's anser about does DES form a group, seems that there is no such algorithm. $\endgroup$
    – ZKM
    Commented Aug 28, 2023 at 4:05
  • $\begingroup$ This question comes from this application usage: There is a communication chan A --> B --> C, and A has the plaintext message M and encrypt it to M_enc, then send it to B. B encrypt the M_enc with another key and generate M_enc_enc, then send it to C. C has the fixed key3 and can decrypt M_enc_enc to M. $\endgroup$
    – ZKM
    Commented Aug 28, 2023 at 4:11

1 Answer 1

Reset to default
1
$\begingroup$

This would be a weakness and has been investigated under the name does DES form a group?

See question and answer here. A secure cipher should not have this property.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Yes, seems you are right. $\endgroup$
    – ZKM
    Commented Aug 28, 2023 at 4:12
  • $\begingroup$ Okay. You can accept the answer if it's satisfactory $\endgroup$
    – kodlu
    Commented Aug 28, 2023 at 4:24

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.