2
$\begingroup$

If we have a message space M {0,1,2,3,4,5,6} and likewise keyspace is K = {0,1,2,3,4,5,6} (generator choosen uniform keys k)

We define our encryption to be the XOR of their bitwise rep on K and M using 4 bits {0000, 0001, 0010, 0011, 0100, 0101, 0110}

This is one time pad right? Because we are XORing and using the a key of same length.

However here the message and keyspace is represented using 4 bits; it is also limited to values within the inclusive range 0000 to 0110.

Does that violate the perfect secrecy in any way? Perfect secrecy says regardless of prior info known to the attacker the ciphertext wont leak any additional info.

$\endgroup$
21
$\begingroup$

Does that violate the perfect secrecy in any way?

Yes, obviously. Restricting the message space doesn't hurt in any way (the attacker can't get any additional information about the message, even if he knows quite a lot about it already); restricting the key does.

OTP uses a group operation to combine the message and the key; one thing that it needs to assume is that the group members that make up the key are chosen uniformly randomly from all possible group elements - with your example, this is not the case.

Specifically, if we see in the ciphertext the value 0111, we can deduce from that is that the corresponding plaintext value is not 0000; after all, for that to be the case, the key value would have been 0111, and we know that's not the case. That are values that the attacker can deduce are not the message, and this is a violation of perfect secrecy.

Now, if you did have the message and key consisting of values from 0 to 6, the obvious thing to do is change the group operation to 'addition modulo 7'; that is, to encrypt, you add the message to the key, and then if that value is 7 or more, subtract 7 - that gives you the ciphertext. And, to decrypt, you do 'subtraction modulo 7'; you subtract the key from the ciphertext, and if that value is negative, add 7. This is a perfectly valid group operation, and since all values of the key are possible (and presumably equiprobable), it can satisfy the requirements of perfect secrecy.

$\endgroup$
13
  • $\begingroup$ Hi, why is it that if the ciphertext value 0111 we know that the plaintext will not be 0000? Is it because the key and message cannot be the same? However if we do not restrict the key space tot he same set of values as the message space as mentioned above, would this be allowed? I am confused. $\endgroup$
    – Jack
    Sep 3 at 7:27
  • 3
    $\begingroup$ The ciphertext 0111 cannot have underlying plaintext 0000 because 0111 is not an allowed key under the system you presented; plaintext 0000 could only yield ciphertext 0111 if the key was 0111. $\endgroup$ Sep 3 at 11:34
  • $\begingroup$ I'd also note that a naive modulo operation using a conditional subtraction as described may lead to a side-channel leakage of data. The mathematical "perfect secrecy" isn't violated but the real-world secrecy can be! $\endgroup$ Sep 3 at 14:25
  • 1
    $\begingroup$ @SAIPeregrinus: yes; I wrote out the "obvious" method because I expected the OP to have relatively minimal mathematical background (and my apologies if I got that wrong) - a real implementation would want to use better (but harder to explain) methods $\endgroup$
    – poncho
    Sep 3 at 16:41
  • 3
    $\begingroup$ @JörgWMittag: that is correct; changing the distribution so that all key values possible but some have different probabilities would leak some probabilistic information about the plaintext. $\endgroup$
    – poncho
    Sep 4 at 13:58

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.