CSci 4651 Lab 3: Practice with ruby.

Due Tuesday, April 5th at 11:59pm (by e-mail)

20 points: encoding and decoding with a Vigenere cipher

Vigenere cipher is an extension of a simple Caesar cipher. Caeser cipher works by shifting each letter of the alphabet by a fixed number (a shift), wrapping around the alphabet. For instance, if the shift is 3 then A is transformed into D, and Z is transfomed into C. One can view it as representing letters as numbers from 0 to 25, adding the shift value, and taking the result modulo 26:
A = 0, D = 3, so D is the encoding of A with the shift = 3 since (0 + 3) mod 26 = 3,
Z = 25, (25 + 3) mod 26 = 28 mod 26 = 2, and C = 2, so C is the encoding of Z.
The decoding is done by subtracting the shift value and then taking teh result modulo 26 (be careful with the negative numbers! Some programming languages incorrectly compute mod of negative numbers. However, Ruby % operator does not have this problem).

Vigenere ciphers generalizes the Caeser cipher idea. It is a polyalphabetic cipher, which means that a letter isn't always encoded with the same letter in the ciphertext. A key in Vigenere cipher is a word that is added (modulo 26) to each letter of the plaintexttext. The keyword is repeated as many times as needed to match the length of the plaintext. Here is a more detailed description: http://en.wikipedia.org/wiki/Vigen%C3%A8re_cipher.

For instance, if the keyword is "key" and the word we are encoding is "function":
we take the value of the first letter of the key, which is 10, add it to the value of "f" (5), and get a letter 15, which is p.
Adding u (= 20) to e (= 4) gives us y (= 24).
n = 13, y = 24, and combined (and taken mod 26) they give (13 + 24) mod 26 = 11, which is l.
The next letter in plaintext (c) is encoded with k again (since the key is repeated), resulting in m.
The result is "pylmxgyr".

Your goal for this task is to implement Vigenere encoding and decoding. While you can have yoru entire plaintext stored in a string, it may be more convenient to use Ruby file I/O

20 points: attempting to break Vigenere cipher

Your task is to write a Ruby program that attempts to break Vigenere encryption using frequency analysis.
Breaking Vigenere encryption is do-able, although somewhat challenging. Kasiski approach provides the basic idea: frequent letter combinations have a high probability of being encrypted by the same portion of the key words. Observing repeated patterns, one may guess the length of the keyword and even some of its letters.

Once the keyword length is known, frequency analysis may be applied to characters encrypted by the same letter of the keyword: http://en.wikipedia.org/wiki/Vigen%C3%A8re_cipher#Frequency_analysis.

Another potentially useful method is Key Elimination

Note that breaking a Vigenere cipher requires a careful examination of the encrypted text and good guessing. You may have to try multiple methods and combine them to break encryption. Keep a log of methods you tried and of ideas that you think are promising.

The following is English text encoded with the keyword that's between 3 and 8 characters long.


      coliwicojqkwbjplvwffjvapvjuikicomitxrxnemtbefickmpeitf
      oohesnojwxcgrddvkhitesnnafxjhhfhxxvxbmxvgpvjuikgcemifg
      sbapagoqympzgvmhggzzclgksdjqgthbytkgubbshlcnnspxufwxnr
      fbytkgusjtrbbhjxorqijqdxfexstmwtbsoxjjbmvhfjvyvmssnhvt
      dqrrithnhgjtacnvfhcsxrnrhirwcgroxxjbbhvstxoimmumwolxnr
      wsnqgfpfamvpotrrvascuicdrflioussjrfxodqwgiosjxgwmjwkgf
      pfaathihqxkmghqsumiqxrvasgusqksbpitemjfmuaseclgfcsasyo
      ojwpabvbmwqnuicxqucsasyyfpvqaucptwunfdneuxcgbstkcxbstk
      cxostmvfusumzfwstxtpaxjxfbaicgrsjhktbuvekwsoflqfhinepz
      smbrcfsmnrqksojqgestblgksgxvgossvstx
  

CSci 4651 course web site.

The views and opinions expressed in this page are strictly those of the page author. The contents of this page have not been reviewed or approved by the University of Minnesota.