1. Let $m = 6$, and let $\mathbb{Z}_m$ denote the set $\{0,…,m-1\}$. Let $X \mod m$ denote the remainder obtained when dividing $X$ by $m$.

    (a) Consider the symmetric encryption scheme in which the encryption of message $M \in \mathbb{Z}_m$ under key $K \in \mathbb{Z}_m$ is $M+K \mod m$. Is this encryption scheme perfectly secure? Why or Why not?

I'm having a lot of trouble understanding why the "X mod m" and all of the other modulo operations are relevant. I know it says let it denote the remainder obtained when dividing $X$ by $m$, but… the remainder of what? Why would the remainder be relevant?

  • 3
    $\begingroup$ Please consider writing the text by hand, not just dumping a picture, because it makes search easier (and someone else is more likely to benefit from your question). Cheers $\endgroup$ – rath Nov 29 '13 at 22:48
  • 2
    $\begingroup$ @rath [+1] Nice idea, so I quoted the text of that image. (Sometimes I wonder how I spend my friday nights…) $\endgroup$ – e-sushi Nov 29 '13 at 23:12

The modulo operator keeps the result of the addition of $M$ and $K$ within the set $Z$.

For example, if $m$ is 10, $M$ is 6 and $K$ is 5, $M + K$ would be 11 which is no longer in the set $Z$. Taking 11 mod 10 results in 1 which is in the set $Z$.

The definition of perfect security is:

An interesting special case is perfect security: an encryption algorithm is perfectly secure if a ciphertext produced using it provides no information about the plaintext without knowledge of the key. If E is a perfectly secure encryption function, for any fixed message m there must exist for each ciphertext c at least one key k such that $c = E_{k}(m)$. It has been proved that any cipher with the perfect secrecy property must use keys with effectively the same requirements as one-time pad keys.

| improve this answer | |
  • 1
    $\begingroup$ It's not really "the Caesar cipher", sure the Caesar cipher uses this primitive internally but is certainly not perfectly secure, so this is somewhat misleading. Otherwise good answer +1 $\endgroup$ – Thomas Nov 30 '13 at 3:48
  • 1
    $\begingroup$ Perfect secrecy and perfect security are not the same thing. OTP provides perfect secrecy. $\endgroup$ – daniel Dec 2 '13 at 11:04

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.