vigenere.rb

#!/usr/bin/env ruby

##
# A pure ruby version of a Vigenere cipher engine. Encodes, decodes and guesses
# keys.
#
class Vigenere
  ##
  # Encodes a plaintext string into a enciphered code. Strips all
  # nonalphanumeric characters from input. Takes the following keys:
  # 
  #   :message => the string to either encode or decode
  #   :key => the key, can be any number of characters. the key is guessed
  #     on decode if it is empty.
  #
  def self.encode(options = {})
    opts = {
      :message => '',
      :key => ''
    }.merge(options)
    opts[:message] = opts[:message].downcase.gsub(/[^a-z]/, '').chars.to_a
    opts[:key] = opts[:key].downcase.gsub(/[^a-z]/, '').chars.to_a
    res = []
    base, top = Vigenere.base_integers
    opts[:message].each_with_index do |c, idx|
      x = c[0] + opts[:key][idx % opts[:key].size][0] - base
      x -= 26 if x > top
      res << x.chr
    end
    res.join
  end
  
  ##
  # Decodes a vigenere enciphered string. Takes the same options as encode.
  # Will try to guess the key if empty or nil.
  #
  def self.decode(options = {})
    opts = {
      :message => '',
      :key => nil
    }.merge(options)
    opts[:message] = opts[:message].downcase.gsub(/[^a-z]/, '').chars.to_a
    opts[:key] = opts[:key].downcase.gsub(/[^a-z]/, '').chars.to_a
    res = []
    base, top = Vigenere.base_integers
    opts[:message].each_with_index do |c, idx|
      x = c[0] - opts[:key][idx % opts[:key].size][0] + base
      x += 26 if x < base
      res << x.chr
    end
    res.join
  end
  
  ##
  # Returns the Ruby integer codes for 'a' and 'z'.
  #
  def self.base_integers
    [ 'a'[0], 'z'[0] ]
  end
  
  ##
  # Character frequencies of English.
  #
  def self.frequencies
    [
      0.080, 0.015, 0.030, 0.040, 0.130, 0.020, 0.015, 0.060, 0.065, 0.005,
      0.005, 0.035, 0.030, 0.070, 0.080, 0.020, 0.002, 0.065, 0.060, 0.090,
      0.030, 0.010, 0.015, 0.005, 0.020, 0.002
    ]
  end
  
  ##
  # Uses correlation of frequencies to guess the key of a Caeser cipher. It
  # returns an array of frequencies with each index being the corresponding
  # English letter.
  #
  def self.correlation_of_frequency(str)
    counts = {}
    chars = str.downcase.gsub(/[^a-z]/, '').chars.to_a
    chars.each_with_index do |c, idx|
      counts[c] ||= 0
      counts[c] += 1
    end
    freq = {}
    counts.each { |key, value| freq[key] = value.to_f / chars.size.to_f }
    base, top = Vigenere.base_integers
    uchars = chars.sort.uniq
    freqs = (0..25).collect do |i|
      uchars.inject(0.0) do |sum, c|
        sum += freq[c] * Vigenere.frequencies[(c[0] - base - i) % 26]
      end
    end
    freqs
  end
  
  ##
  # Finds the index of coincidence for a Vigenere cipher. Well, really it just
  # guesses and lets you decide on the length.
  #
  def self.index_of_coincidence(str)
    chars = str.downcase.gsub(/[^a-z]/, '').chars.to_a
    base, top = Vigenere.base_integers
    c = (0..25).inject(0.0) do |sum, i|
      c2 = (base + i).chr
      len = chars.select { |c| c == c2 }.size
      sum += len * (len - 1)
    end * ((chars.size * (chars.size - 1)) ** -1)
    if c >= 0.066
      1
    elsif c >= 0.052
      2
    elsif c >= 0.047
      3
    elsif c >= 0.045
      4
    elsif c >= 0.044
      5
    elsif c >= 0.0434
      6
    elsif c >= 0.0428
      7
    elsif c >= 0.0422
      8
    elsif c >= 0.0416
      9
    elsif c >= 0.041
      10
    elsif c >= 0.0408
      11
    elsif c >= 0.0406
      12
    elsif c >= 0.0404
      13
    elsif c >= 0.0402
      14
    elsif c >= 0.04
      15
    elsif c >= 0.0398
      16
    elsif c >= 0.0396
      17
    elsif c >= 0.0394
      18
    elsif c >= 0.0392
      19
    elsif c >= 0.039
      20
    elsif c >= 0.0388
      21
    elsif c >= 0.0386
      22
    elsif c >= 0.0384
      23
    elsif c >= 0.0382
      24
    elsif c >= 0.038
      25
    else
      raise "You have a very large (over 25) index of coincidence #{c}"
    end
  end
  
  ##
  # Splits a string into Caesarian solvable alphabets based on a given period.
  #
  def self.split_string_into_alphabets(str, period = nil)
    period ||= Vigenere.index_of_coincidence(str)
    res = []
    str.downcase.gsub(/[^a-z]/, '').chars.each_with_index do |c, idx|
      i = idx % period
      res[i] ||= []
      res[i] << c
    end
    res.collect { |r| r.join }
  end
  
  ##
  # Reassembles a split alphabet string into one big string. Can directly
  # take the output from split_string_into_alphabets.
  #
  def self.reassemble_alphabets(ary)
    res = []
    (0..(ary.first.size - 1)).each do |idx|
      (0..(ary.size - 1)).each do |alphabet|
        res << ary[alphabet][idx].chr if ary[alphabet][idx]
      end
    end
    res.join
  end
  
  ##
  # Counts the number of frequencies for each character in a given alphabet.
  #
  def self.frequency_examination(alphabets)
    base, top = Vigenere.base_integers
    alphabets.collect do |a|
      r = []
      chars = a.chars.to_a
      (0..25).each do |c|
        r[c] = chars.select { |c2| c2 == (base + c).chr }.size
      end
      r
    end
  end
  
  ##
  # An interactive solver for a Vigenere cipher. It will let you choose a
  # different key for each alphabet found. Returns the 'solved' string.
  #
  def self.interactive_solver(str)
    period = Vigenere.index_of_coincidence(vig)
    puts "Probably has a period of #{period}"
    
    alphabets = Vigenere.split_string_into_alphabets(vig, period)
    assembled = []
    frequencies = alphabets.collect { |a| Vigenere.correlation_of_frequency(a) }
    sorted_frequencies = frequencies.collect { |f| f.sort.reverse[0, 10] }
    frequency_examination = Vigenere.frequency_examination(alphabets)
    
    keys = []
    alphabets.each_with_index do |r, idx|
      keys[idx] = frequencies[idx].index(sorted_frequencies[idx][0])
    end
    
    inp = nil
    while inp.to_i >= 0
      assembled.clear
      if inp and inp < alphabets.size
        puts "Top 10 choices: (currently '#{(base + keys[inp]).chr}')"
        sorted_frequencies[inp][0,10].each do |c|
          key = (base + frequencies[inp].index(c)).chr
          decoded = Vigenere.decode :message => alphabets[inp], :key => key
          puts "key '#{key}' ic #{"%.8f" % c}: #{decoded}"
        end
        puts "Frequency examination:"
        frequency_examination[inp].each do |f|
          print f
        end
        puts
        (0..25).each do |c|
          print (base + c).chr
        end
        puts
        print "Enter key: "
        $stdout.flush
        k = $stdin.readline.chomp
        keys[inp] = k[0] - base
      end
      alphabets.each_with_index do |r, idx|
        char = (base + keys[idx]).chr
        assembled << Vigenere.decode(:message => r, :key => char)
        puts "#{"%2d" % idx}: encrypted: #{r} key: #{char} decrypted: #{assembled.last}"
      end
      print "Change alphabet key (-1 to quit): "
      $stdout.flush
      inp = $stdin.readline.chomp.to_i
    end
  end
  return Vigenere.reassemble_alphabets(assembled)
end