Saturday, September 28, 2013

Notes - The Vigenere Cipher

The following are notes from Introduction to Cryptography with Coding Theory.
  • A variation of the shift cipher
    • key for the encryption is a vector of a chosen length
    • Example
      • key length 6
      • (21,4,2,19,14,17)
      • corresponds to word vector
      • To encrypt we shift by the word vector
  • A known plain text attack will succeed if enough characters are known
  • Cryptanalysis uses the fact that english letter frequency is not equal
    • a - 0.082
    • b - 0.015
    • c - 0.028
    • d - 0.043
    • e - 0.127
    • f - 0.022
    • g - 0.020
    • h - 0.061
    • i - 0.070
    • j - 0.002
    • k - 0.008
    • l - 0.040
    • m - 0.024
    • n - 0.067
    • o - 0.075
    • p - 0.019
    • q - 0.001
    • r - 0.060
    • s - 0.063
    • t - 0.091
    • u - 0.028
    • v - 0.010
    • w - 0.023
    • x - 0.001
    • y - 0.020
    • z - 0.001
  • Variations can occur but usually takes effort to produce, example the book Gadsby does not contain the letter e
  • However, when using a Vigenere Cipher the frequencies are distributed so that the above is not nearly as useful in decryption
  • Finding Key Length
    • We find the key length by matching the number of coincidences
    • write the ciphertext, then rewrite it with a displacement
    • Example
    •     VVHQ
    • VVHQW
    • Then we mark each time there is a match between the two rows, and after trying multiple displacements the largest number of coincidences will be closest to the key length
  • Finding the Key: First Method
    • take a look at the 1+5n letters and find the frequency of letters then repeat for 2+5n, 3+5n, 4+5n, 5+5n we then guess at the code by finding the difference between the most frequent letter and e to find the overall shift that is used as the key
    • After finding the key we then test it by decrypting to confirm if the key was correct
  • Soft Proof
    • place the frequencies of the english letters into a vector A0 and let Ai represent the frequencies shifted by i
    • When taking the dot product of these two vectors we arrive at 0.066 with a full match but significantly less than that for any other shift
    • We can also use this knowledge to approximate the number of coincidences we should find for a given match, which would be 0.066*the number of comparisons

No comments:

Post a Comment