Mathematical Food for Thought

  
 
google
yahoo
bing
 

  • 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 »
Google

 

  
 
free web counters
Etronics