We consider the alphabet A= {0,1,2,3,4} and the space of messages consists of al

Question

We consider the alphabet A= {0,1,2,3,4} and the space of messages consists of all 1-symbol words, so it is M ={0,1,2,3,4}. The encryption is done using the shift cipher, so it is given by the equation X = x+k (mod 5) applied to each letter of the plaintext (as discussed in class, x is the letter that we encrypt, k is the secret key, and X is the encrypted letter).

Calculate Prob (M= 1 | C = 4) (according to Eve’s distribution). Recall that C= EK(M), that is the ciphertext is obtained by encrypting the message M (which is drawn according to Eve’s distribution which you found at point a.), and the key is equally likely to be any number in the set {0,1,2,3,4}. You’ll have to use the formula for conditional probability (see the notes, and the proof of Shannon’s theorem).

Explanation / Answer

Assume message distribution is given as below:

m

Pm

0

1/2

1

1/3

2

1/6

3

1/9

4

1/12

Shanon’s theorem:

If M = C = K then the system provides perfect secrecy if and only if:

(1) every key is used with equal probability 1/K, and

(2) for every x P and y C, there exists a unique key k Ksuch that ek(x) = y

Because the keys are chosen uniformly, each key has probability 1/5.

So, joint distribution is given as:

k

m

1/10

1/10

1/10

1/10

1/10

1/15

1/15

1/15

1/15

1/15

1/30

1/30

1/30

1/30

1/30

1/45

1/45

1/45

1/45

1/45

1/60

1/60

1/60

1/60

1/60

Next, we calculate the conditional probability distribution prob[m = 1 c = 4]. To do this, we consider the pairs (m,k) in our joint sample space and compute c = Ek(m) for each. The diagram below shows, the result, where each point is labeled by a triple (m,k,c), and those points for which c = 4 are shown bold as below:

(0,0,0,0,0)     (0,1,1,1,1) (0,2,2,2,2)    (0,3,3,3,3) (0,4,4,4,4)

(1,0,0,0,0)     (2,1,0,0,1) (1,2,0,0,2)    (1,4,0,0,4) (1,4,0,0,4)

(0,0,0,0,0)     (0,1,1,1,1) (1,2,4,2,4)    (0,3,3,3,3) (0,4,4,4,4)

(0,0,0,0,0)     (0,1,1,4,4) (0,2,2,2,2)    (0,3,3,3,3) (0,4,4,4,4)

(4,0,0,0,4)     (0,1,1,1,1) (0,2,2,2,2)    (0,3,3,3,3) (0,4,4,4,4)

Assume we find above distribution .

So prob[c = 4] = 1/10 + 1/15 + 1/30 + 1/45 + 1/60 = 40/60 = 2/3

Prob[m =1 and c = 4] = 1/15

Hence prob[m=1|c=4] = prob[m=1 and c= 4]/prob[c=2] = (1/15) / (2/3) = 2/5

m

Pm

0

1/2

1

1/3

2

1/6

3

1/9

4

1/12

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.