2
$\begingroup$

I am trying to figure out this quiz question on a course I am doing but keep getting it wrong.

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='aa'] = 0.4 and Pr[M='ab'] = 0.6. What is Pr[C='bb']? Express your answer to 4 decimal places with a leading 0, i.e., if your answer was 1/2 then you would enter 0.5000 (without a trailing period).

The way I reasoned was as follows: Probability P1 where m=aa and key is of size 1 = 1/26 * 0.4 Probability P2 where m=aa and key is of size 2 = 1/26*1/26*0.4 Probability P3 where m=ab and key is of size 1 = 0 Probability P4 where m=ab and key is of size 2 = 1/26*1/26*0.6

The answer (I thought) was P1 + P2 + P3 + P4 = 0.0169

This is apparently wrong. Can anyone guide me, please?

$\endgroup$
  • $\begingroup$ Shouldn't you multiply with 0.6 for P4? $\endgroup$ – Maarten Bodewes Sep 5 '18 at 22:21
  • $\begingroup$ Your answer seems correct, have you tried a truncated number instead of rounded? That would be 0.0168 $\endgroup$ – Baku Sep 5 '18 at 23:19
  • $\begingroup$ sorry copied it wrongly :) $\endgroup$ – Lilz Sep 6 '18 at 6:21
1
$\begingroup$

I'll assume the Vigenere cipher is defined to encrypt per $c_i\gets m_i\boxplus k_{(i\bmod l)}$ where $c_i$ is a ciphertext letter, $m_i$ is a plaintext letter, $k_i$ is a key letter, $l$ is the length of the key, $\boxplus$ is the Vigenere table of dimension 26×26. I'll note $\hat k_i=k_{(i\bmod l)}$.

It is assumed $$\begin{array}{rlcrl} \Pr[l=1]&=\frac1 2&\quad&\Pr[l=2]&=\frac1 2\\ \Pr[m_0=\mathtt a\;\wedge\;m_1=\mathtt a]&=\frac2 5&\quad&\Pr[m_0=\mathtt a\;\wedge\;m_1=\mathtt b]&=\frac3 5 \end{array}$$ It is asked $p=\Pr[c_0=\mathtt b\;\wedge\;c_1=\mathtt b]$. That is $$p=\frac2 5\Pr[\hat k_0=\mathtt b\;\wedge\;\hat k_1=\mathtt b]+\frac3 5\Pr[\hat k_0=\mathtt b\;\wedge\;\hat k_1=\mathtt a]$$

Unfortunately, the problem statement is unclear about the distribution of key. We can reasonably assume that each of the possible $k_0$ has probability $\frac1 {26}$, but what about $k_1$ when $l=2$? It is reasonable to assume one of

  1. Each of the possible $k_1$ has probability $\frac1{26}$. That yields $$p=\frac2 5\left(\frac1 2\frac1{26}+\frac1 2\frac1{26}\frac1{26}\right)+\frac3 5\left(0+\frac1 2\frac1{26}\frac1{26}\right)=\frac{57}{6760}\approx0.0084$$ (rounding to the nearest, that is down)
  2. Each of the possible $k_1\ne k_0$ has probability $\frac1{25}$. That yields $$p=\frac2 5\left(\frac1 2\frac1{26}+0\right)+\frac3 5\left(0+\frac1 2\frac1{26}\frac1{25}\right)=\frac{53}{6500}\approx0.0082$$ (rounding to the nearest, that is up)

Note: Bet on 1 to maximize the probability of scoring a correct answer, even though 2 is the less unsafe cryptographically.


The question's attempted resolution has reading 1, but each of the probability that it sums is missing the multiplication by the probability that $l$ has the value considered.

$\endgroup$
  • $\begingroup$ Thank you! You are currently my favourite person! I completely forgot the 1/2 probability of length 1 or length 2 $\endgroup$ – Lilz Sep 6 '18 at 20:28

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.