Past exam of the mathematics course of the University of Cambridge / 2024 / ii / Paper 4 / 3K (Coding and Cryptography)

Table of contents
- a 3K
  - i a
    - Solution i
  - ii a
    - Solution ii
- b 3K
  - Solution b

a

i

Solution

Because decryption determines

M

from

(C, K)

,

H (M ∣ C, K) = 0.

The chain rule and monotonicity give

H (M ∣ C) \leq H (M, K ∣ C) = H (K ∣ C) + H (M ∣ C, K) = H (K ∣ C) .

ii

Solution

The unicity distance is the least ciphertext length for which the key is determined, or in the usual approximation the length at which the expected number of spurious keys falls to about zero. Assume equiprobable keys, a stationary plaintext source of information entropy rate

H_{E}

, and ciphertext symbols that are approximately uniform on

A

. The language redundancy per symbol is

D = lo g_{2} ∣ A ∣ - H_{E} .

The key equivocation is then approximated by

H (K ∣ C_{1}, l d o t s, C_{n}) ≃ lo g_{2} ∣ K ∣ - n D .

Hence the classical closed-form estimate is

n_{0} ≃ \frac{lo g _{2} ∣ K ∣}{lo g _{2} ∣ A ∣ - H _{E}} .

b

Solution

Entropy is nonnegative. Gibbs' inequality also gives

H (X_{1}, l d o t s, X_{n}) \leq lo g_{2} ∣ A^{n} ∣ = n lo g_{2} 27.

Divide by

n

and pass to the assumed limit to obtain

0 \leq H_{E} \leq lo g_{2} 27.

 Ancestors (9)

 View article source

 Discussion (0)

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.

  See all articles in the same topic Create my own version