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?

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ The probability that $k = \mathtt{c}$ is not $1/26$. $\endgroup$
    – fkraiem
    Jun 20, 2016 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, 2016 at 13:14
  • $\begingroup$ The probability that the length of the key is 1 is not 1. $\endgroup$
    – fkraiem
    Jun 20, 2016 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, 2016 at 13:25
  • 1
    $\begingroup$ Good, you can now answer your own question. :) $\endgroup$
    – fkraiem
    Jun 21, 2016 at 10:38

1 Answer 1

Reset to default
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
Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.