1
$\begingroup$

Apologies if this should be in the Mathematics stack exchange, I just ask it here because the context is cryptography. Here is the question that I seemingly cannot get correct:

Consider the Vigenere cipher over the lowercase English alphabet, where the key can have length 1 or length 2, each with 50% probability. Say the distribution over plaintexts is Pr[M='dd'] = 0.2 and Pr[M='de'] = 0.8. What is Pr[C='ff']?

My starting assumptions are therefore that:

Pr[M=dd]    = 0.2
Pr[M=de]    = 0.8

I believe I can calculate Pr[C=ff] in the following manner:

Pr[C=ff]    = (Pr[C=ff | M=dd] x Pr[M=dd]) + (Pr[C=ff | M=de] x Pr[M=de])

From a notation point of view:

M = message
C = ciphertext
K = key
Pr[M=dd] = Probability that the message is 'dd'
Pr[C=ff | M=dd] = Probability the ciphertext is 'ff' conditioned on the message being 'dd'.

The convention for key notation is that:

K=a means 'shift by 0'
K=ab means 'shift first character by 0, shift second character by 1'
etc.

So:

  • For key length 1, M=dd: There is only one key that can produce C=ff (that is K=c).
  • For key length 2, M=dd: There is only one key that can produce C=ff (that is K=cc)
  • For key length 1, M=de: There is no key that can produce C=ff.
  • For key length 2, M=de: There is only one key that can produce C=ff (that is K=cb)

Therefore:

  • Pr[C=ff | M=dd] x Pr[M=dd] = [1/26 + 1/(26^2)] x 0.2
  • Pr[C=ff | M=de] x Pr[M=de] = [0 + 1/(26^2)] x 0.8

Ergo:

  • Pr[C=ff] = [1/26 + 1/(26^2)] x 0.2 + [0 + 1/(26^2)] x 0.8
  • Pr[C=ff] = 0.009171598

Apparently this is incorrect, but I'm not sure where I'm going wrong, can anyone help explain what I'm doing incorrectly?

$\endgroup$
  • 1
    $\begingroup$ The probability that $k = \mathtt{c}$ is not $1/26$. $\endgroup$ – fkraiem Jun 20 '16 at 12:53
  • $\begingroup$ Sorry I don't follow you there, when you can only pick one character randomly from the lowercase English alphabet, how are the odds not 1 in 26? $\endgroup$ – Chris Jun 20 '16 at 13:14
  • $\begingroup$ The probability that the length of the key is 1 is not 1. $\endgroup$ – fkraiem Jun 20 '16 at 13:21
  • $\begingroup$ I see what you are getting at with respect to the 0.5 for each key. My thinking was that it would all get wrapped up due to the law of total probability in this particular problem since the key can only be either 1 or 2. I'll visit it again tomorrow with a fresher set of eyes, thanks for the pointer. $\endgroup$ – Chris Jun 20 '16 at 13:25
  • 1
    $\begingroup$ Good, you can now answer your own question. :) $\endgroup$ – fkraiem Jun 21 '16 at 10:38
2
$\begingroup$

The answer to this (thanks to help from fkraiem) was literally included in the first sentence of the question.

I went wrong by assuming that the probability of the occurrence of a 1 or 2 character key didn't weigh into the calculation. My (rather questionable) reasoning was that since the key did in fact have to be either 1 character or 2 characters (i.e. it couldn't be 0 or 3 or more characters), that the 50% probability didn't weigh into it. Yes, that reasoning is in fact both as silly and as incorrect as it sounds.

So, the corrected components of the calculations above are:

Therefore:

  • Pr[C=ff | M=dd] x Pr[M=dd] = [1/26 x 0.5 + 1/(26^2) x 0.5] x 0.2
  • Pr[C=ff | M=de] x Pr[M=de] = [0 x 0.5 + 1/(26^2) x 0.5] x 0.8

Ergo:

  • Pr[C=ff] = [1/26 + 1/(26^2)] x 0.5 x 0.2 + [0 + 1/(26^2)] x 0.5 x 0.8
  • Pr[C=ff] = 0.004585799
$\endgroup$

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.