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.

5 comments:

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

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

    ReplyDelete
  3. Nobody needs Jeffrey to talk about AMC problems XD

    ReplyDelete
  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?

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

    ReplyDelete