Is the following cryptosystem possible:

There is an encryption function:

encrypt (k1, k2, T1, T2) = M, where

T1, T2 - two plain texts, with the same number of characters, k1, k2 - encryption keys of the same length, M - cipher text, the length of which is equal to the length of the input text. The length of the key is generally much less than the length of the input text

and accordingly the decryption function:

decrypt (k1, M) = T1

decrypt (k2, M) = T2


1 Answer 1


Is the following cryptosystem possible: The length of the key is generally much less than the length of the input text

I will assume that the plaintexts are essentially incompressable; that is, they are allowed to be arbitrary bit patterns.

If so, then if you are allowed to select the keys based on what the plaintexts are, then it is possible, but only if the length of the keys are at least half the length of the plaintext. If the keys are selected independently of the plaintexts, then it is impossible.

Lets show the last statement first; suppose you had such a method; what you could do to encode two messages T1 and T2 is to select two arbitrary (and well known) keys K1 and K2, and encrypt them into a message M, and then send that message M to someone. What that someone (who knows K1, K2) can do to recover T1, T2 is to run the decrypt function on M (using both K1, K2); that gives him T1, T2. What that means that if the length of T1, T2, M is n bits is sent him 2n bits of information expressed in only n bits - as we assumed that T1, T2 are incompressible, that's impossible.

The first statement is similar; to send T1, T2, you would have the procedure select K1, K2, and then send K1, K2 and M - you would need to send K1, K2 because we can no longer assume that the receiver knows them. The receiver again uses to the decrypt function to recover T1, T2 - if T1, T2, M are n bits long and K1, K2 are k bits long, then we sent him 2n bits expressed as a total of n+2k bits - this is possible only if 2n $\le$ n+2k, or k $\ge$ n/2.

The last part is to show that the first statement is possible - one easy (albeit insecure) way to demonstrate it [1] is to divide $T1, T2$ into halves, $T1_a, T1_b, T2_a, T2_b$. Then, we set $K1 = T1_a$ and $K2 = T2_b$ and set $M = T2_a || T1_b$ - the "decryption" method is fairly obvious.

[1]: This does assume that it's OK that the two decryption methods for T1 and T2 are different - one can put together a unified method that works for both, however I can't think of such a method that's easy to explain.


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.