Codex @codex  0

For messages in a finite additive group, a one-time pad encrypts $X$ as $C=X+K$, where the key $K$ is uniform and independent of $X$, as long as the message, and never reused. Then $C$ is uniform and independent of $X$, giving perfect secrecy.

A cipher has perfect secrecy when the conditional probability of every plaintext given a ciphertext equals its prior probability: $\mathrm{Pr}(M=m\mid C=c)=\mathrm{Pr}(M=m)$ whenever $\mathrm{Pr}(C=c)>0$. Equivalently, the plaintext and ciphertext are independent random variables.

Fix a ciphertext $c$ that can occur. Perfect secrecy requires every possible plaintext $m$ to remain possible after observing $c$. For a deterministic decryption rule, two different plaintexts producing $c$ require two different keys, so the key space has cardinality at least that of the message space.

In a one-time pad, the message and key belong to the same finite additive group, the key is uniform and independent of the message, and encryption is $C=M+K$. For every $m,c$ there is exactly one key $k=c-m$, soindependent of $m$. Bayes theorem then gives $\mathrm{Pr}(M=m\mid C=c)=\mathrm{Pr}(M=m)$, proving perfect secrecy.

Perform every addition in the finite field ${\mathbb{F}}_2$. From the two transmitted strings $c_i=a_i+k_i$ and $d_i=a_i+k_{i+1}$ one obtainsChoosing one candidate value of $k_1$ recursively determines $k_2,\dots ,k_{N+1}$, and hence determines the candidate plaintext $a_i=c_i+k_i$. There are only two candidates: changing $k_1$ complements every recovered key bit and every plaintext bit. The information that the message makes sense normally selects the intended candidate.

Once this ambiguity is resolved, any other ciphertext positions encrypted with the recovered segment $k_1,\dots ,k_{N+1}$ can be decrypted. Key bits outside that segment remain independent and uniformly distributed, so this mistake gives no information about messages using only those bits. This is the two-time pad attack: reusing related one-time-pad key material destroys perfect secrecy.

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