## Friday, May 5, 2006

### Vernam Cipher. Topic: Cryptography.

Definition: (Vernam Cipher) Given a plaintext $A$ (message you want to encode, represented by the numbers $0$ through $26$) of length $N$ characters and a suitably random key $K$ of $N$ characters, the ciphertext $B$ (encoded message, also represented by the numbers $0$ through $26$) is generated by

$B(i) = A(i)+K(i) \pmod{26}$,

where $X(i)$ denotes the value of the $i$th character of a string $X$.

--------------------

Definition: Let $P(a)$ be the probability of event $a$. Let $P(a;b)$ be the probability that both $a$ and $b$ occur and $P(a|b)$ be the probability that $a$ occurs given that $b$ does.

--------------------

Problem: Prove that the Vernam Cipher is secure - that is, the probability of $A(i)$ being a certain character given $B(i)$ is the same as the probability of $A(i)$ being that character not given $B(i)$.

Solution: Let $m, n$ be an arbitrary characters. We establish that $P(A(i) = m)$ and $P(B(i) = n)$ are independent events because $K$ is arbitrarily generated (here the suitable randomness comes into play). So $P(A(i) = m; B(i) = n) = P(A(i) = m) \cdot P(B(i) = n)$.

But then

$P(A(i) = m) | B(i) = n) = \frac{P(A(i) = m; B(i) = n)}{P(B(i) = n)} = \frac{P(A(i) = m) \cdot P(B(i) = n)}{P(B(i) = n)} = P(A(i) = m)$

as desired. So knowing the key will not help at all in determining the plaintext, resulting in a secure cipher. QED.

--------------------

Comment: Problems with this cipher lie in the suitable randomness. Creating such keys (and distributing them) proves to be a more difficult task than it sounds.