I have this question that I'm trying to answer:

Consider a monoalphabetic substitution cipher applied to plaintexts consisting of just a single letter. That is, $$M = \{0, 1, . . . , 25\}$$ The keyspace $K$ is the set of all permutations of $M$. (As usual, we identify the letter $A, . . . , Z$ with this set of integers.) Show that this is perfectly secret.

I understand that to show perfect secrecy it suffices to show that $|K|\ge |M|$. I'm just not understanding how to answer this question. Would it make sense to say $K = \{0, 1, ..., 25\}\Rightarrow |K|\ge |M|$?

  • 2
    $\begingroup$ The key space being at least as big as the message space is only a necessary condition for perfect secrecy, but not a sufficient one. For example, AES128 will not offer perfect secrecy when encrypting a single block. $\endgroup$ Feb 9 '17 at 8:16
  • $\begingroup$ @CodesInChaos so then what do I have to show in order to perform this task? $\endgroup$
    – R. Kelly
    Feb 9 '17 at 8:19

IF $K$ is randomly chosen (and well distributed over the key space with size 26! - the total number of possible permutations) then each $C$ (ciphertext letter) is also equally likely. An attacker may choose any $K$ but it is impossible to gain any advantage by that; each message $M$ is still as likely as before.

Basically this scheme is a one-time-pad using a per-character permutation rather than XOR as often used.

As indicated by the first IF, what's missing is the requirement that the choice of $K$ is perfectly random. Generally we try and proof ciphers correct by looking at the set $\operatorname{Gen}, \operatorname{E}, \operatorname{D}$. The $\operatorname{Gen}$ is missing from the question.

  • $\begingroup$ I'm not sure if you already used $Pr$ (probability) notations for this question, so I tried to refrain from using those. $\endgroup$
    – Maarten Bodewes
    Feb 9 '17 at 12:39
  • 1
    $\begingroup$ The keyspace is defined as the set of all permutations, so it's $26!$ possible keys. It's not just modular addition instead of XOR. In this case, it should be included that for all messages $m$ and ciphertexts $c$, $25!$ of those permutations map $m$ to $c$, and for a random permutation this has the probability $25! / 26! = 1/26$. For any fixed $c$, each $m$ can be the preimage exactly with probability $1/26$. $\endgroup$
    – tylo
    Feb 9 '17 at 13:14
  • $\begingroup$ Ok, I'll try and adjust he answer accordingly (traveling right now). The fact remains of course that the key must be chosen at random from the possibe keys though. $\endgroup$
    – Maarten Bodewes
    Feb 9 '17 at 13:56
  • $\begingroup$ Changed answer, a more formal answer is probably asked for though; if somebody can post that I'd happily vote up. $\endgroup$
    – Maarten Bodewes
    Feb 10 '17 at 11:49

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.