Mathematical Food for Thought

  
 
 

  • About

    Serves a Daily Special and an All-You-Can-Eat Course in Problem Solving. Courtesy of me, Jeffrey Wang.
  
Vernam Cipher. Topic: Cryptography. May 5th, 2006

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.

Posted in Cryptography || 5 Comments »

5 Responses to “Vernam Cipher. Topic: Cryptography.”

  1. freshmenz=] Says:
    May 6th, 2006 at 6:06 pm

    this is hard… how come there’s only one question in the AMC level?

  2. paladin8 Says:
    May 6th, 2006 at 7:54 pm

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

  3. QC Says:
    May 6th, 2006 at 9:44 pm

    Nobody needs Jeffrey to talk about AMC problems XD

  4. freshmenz=] Says:
    May 6th, 2006 at 10:00 pm

    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. #H34N1 Says:
    March 8th, 2007 at 5:48 am

    I’ll try to make one of those codes :)

Leave a Reply

You must be logged in to post a comment.
Google

 

  
 
free web counters
Etronics