Past exam of the mathematics course of the University of Cambridge / 2023 / ii / Paper 2 / 12I (Coding and Cryptography)

A one-time pad over the finite additive group ${\mathbb{Z}}_n$ uses a key $K$ that is uniform on ${\mathbb{Z}}_n$, independent of the plaintext $X$, as long as the plaintext, and never reused. Encryption and decryption are

For independent random variables $X,Y$, conditioning reduces entropy and translation by a known element of the finite additive group preserves entropy, soInterchanging $X$ and $Y$ gives $H(X+Y)\ge H(Y)$, henceThis is the entropy of a sum of independent finite-group variables.

The result explains why adding independent pad symbols cannot reduce uncertainty. For a uniform pad, $X+K$ is itself uniform and is independent of $X$, which is the perfect-secrecy property. Independence is necessary: if $X$ is nonconstant and $Y=-X(\mathrm{mod}n)$, then $X+Y=0$ is constant, so

Write the intercepted ciphertext, known plaintext, and desired plaintext without spaces:Because the pad is additive, Eve applies the malleability of an additive one-time pad and sendsLetter-by-letter, using $A=1,\dots ,Z=26$, this givesThus Eve should deliverIndeed, if $C=P+K$, then $C^{\prime }=C-P+P^{\prime }=P^{\prime }+K$, so Ollie decrypts the desired message.

Since $\alpha$ generates $K^{\times }$, it cannot lie in a proper subfield, so its minimal polynomial over ${\mathbb{F}}_2$ has degree $d$. Write it asThe identity $P(\alpha )=0$ and characteristic two giveMultiplying by ${\alpha }^n$ and applying the linear map $T$ yieldsThis is a binary linear recurrence of order at most $d$, so $(x_n)$ is the output of a linear-feedback shift register of length at most $d$.

Because ${\alpha }^{2^d-1}=1$,so the period divides $2^d-1$.

Conversely, suppose $r$ is an eventual period. Then for every sufficiently large $n$,Any block of $2^d-1$ consecutive powers of $\alpha$ runs through every element of $K^{\times }$. Hencefor every $y\in K$, including $y=0$. The assumed nondegenerate bilinear form forces ${\alpha }^r-1=0$. Since $\alpha$ generates the cyclic group $K^{\times }$ of order $2^d-1$, this means $2^d-1\mid r$. The least positive period is thereforeas in a trace-generated maximal-period linear-feedback sequence.