Given a toy cipher that picks a key, k, from the key space of {00,01,10} and a message,m, from the same set {00,01,10} and encrypts using E = m ⊕ k.

How can I change the encryption function E in order to make this cipher perfect(according to Shannon's perfect secrecy rule)?

NOTE: This cipher is not perfect because there's no way to get a ciphertext of 11 if the k or m are 00 thus the ciphertext reveals extra information about the plaintext which makes this cipher imperfect.

Any hints or suggestions as to how to approach the problem would be helpful.


1 Answer 1


Two ways to go about it:

  1. Enlarge the key space so that every possible ciphertext is equally likely.
  2. Change the operation from XOR to one that stays in the set of the three values you have.

Either would work, but since you asked for hints I will leave the specifics for you.

  • $\begingroup$ 1 is probably not possible here since the keyspace is specified, it probably cannot be modified. (The ciphertext-space, however, is not specified, so 2 is probably the expected answer.) $\endgroup$
    – fkraiem
    Commented Oct 13, 2015 at 6:13
  • $\begingroup$ Yes, we should use the second case. Could you please elaborate on 2 because there are many ways to have a ciphertext space of {00,01,10}. I only asked for hints because people are never willing to give you the answer here :) $\endgroup$ Commented Oct 13, 2015 at 14:35
  • $\begingroup$ @DimitarStratiev, ok, I thought you wanted hints. Any operation you can think of that is bijective both with constant key and with constant plaintext would work, but modular addition is the simplest one. $\endgroup$
    – otus
    Commented Oct 13, 2015 at 14:40
  • $\begingroup$ I'm assuming that's modular addition on top of the m XOR k that the algorithm already does $\endgroup$ Commented Oct 13, 2015 at 15:05
  • 1
    $\begingroup$ Ah.. I think I got it! My answer is (M+K)mod3 $\endgroup$ Commented Oct 13, 2015 at 15:31

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.