## 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.

1. this is hard... how come there's only one question in the AMC level?

2. There are actually 12, but AMC problems are no fun; that's why.

3. Nobody needs Jeffrey to talk about AMC problems XD

4. AMC.. no fun?? wut's fun of it when i cant even understand them??
and QC, aren't you forgettin someone??.. i donno, maybe the FRESHMENZ?

5. I'll try to make one of those codes :)