Scripts to Solve Vigeneres via Dictionary Attacks

investigation.rb

ENGLISH_INDEX_OF_COINCIDENCE = 1.73

def kasiski_examination(text)
  segments = []
  (0..text.length-3).each do |starting_index|
    segments += text[starting_index..-1].chars.each_slice(3).map(&:join)
  end
  segments.uniq!
  # Only segments of length 3 should be kept (for the partial segments included)
  segments.keep_if{|segment| segment.length == 3}

  # Only segments that appear at least twice should be included
  segments.keep_if{|segment| text.scan(/#{segment}/).count > 1}

  segment_gcd_mapping = {}

  # Loop through segments and find the difference between each
  lowest_common_multiples = segments.each do |segment|
    locations = text.enum_for(:scan, /#{segment}/).map { Regexp.last_match.begin(0) }
    diffs = []
    current_location = locations.shift
    locations.each do |location|
      diffs << location - current_location
      current_location = location
    end
    segment_gcd_mapping[segment] = diffs.reduce(:gcd)
  end

  segment_gcd_mapping
end

kasiski_examination("EMUFPHZLRFAXYUSDJKZLDKRNSHGNFIVJYQTQUXQBQVYUVLLTREVJYQTMKYRDMFD")
 => {"VJY"=>20, "JYQ"=>20, "YQT"=>20} 
# Palimpsest - 10 letters
kasiski_examination("VFPJUDEEHZWETZYVGWHKKQETGFQJNCEGGWHKK?DQMCPFQZDQMMIAGPFXHQRLGTIMVMZJANQLVKQEDAGDVFRPJUNGEUNAQZGZLECGYUXUEENJTBJLBQCRTBJDFHRRYIZETKZEMVDUFKSJHKFWHKUWQLSZFTIHHDDDUVH?DWKBFUFPWNTDFIYCUQZEREEVLDKFEZMOQQJLTTUGSYQPFEUNLAVIDXFLGGTEZ?FKZBSFDQVGOGIPUFXHHDRKFFHQNTGPUAECNUVPDJMQCLQUMUNEDFQELZZVRRGKFFVOEEXBDMVPNFQXEZLGREDNQFMPNZGLFLPMRJQYALMGNUVPDXVKPDQUMEBEDMHDAFMJGZNUPLGESWJLLAETG".gsub("?","0"))
 => {"HKK"=>16, "WHK"=>2, "FXH"=>187, "TBJ"=>8, "HHD"=>88, "UVP"=>72, "QUM"=>72, "GWH"=>16, "ETG"=>348, "DQM"=>8, "KQE"=>53, "EUN"=>121, "KFF"=>40, "VPD"=>72, "PJU"=>81, "NUV"=>72} 
# Abscissa - 8 letters

def index_of_coincidence(text, maximum_keyword_length = 10, normalize = false, mask = [1])
  output = {}
  (1..maximum_keyword_length).each do |i|
    column_values = []
    texts = split_text_into_columns(text, i, mask)
    texts.select{|text| text.length > 0}.each do |test_text|
      column_value = 0
      ("A".."Z").each do |letter|
        column_value += test_text.count(letter).to_f * (test_text.count(letter) - 1)
      end
      column_values << column_value / (test_text.length * (test_text.length - 1))
    end
    puts "#{i} - #{column_values.inspect} - #{texts.inspect}"
    calculated_ioc = column_values.inject(0.0) { |sum, value| sum + value } / i
    calculated_ioc *= 26 if normalize
    output[i] = calculated_ioc
  end

  output.sort_by {|key, value| value}.reverse.to_h
end

def split_text_into_columns(text, number_of_columns, mask = [1])
  output = []
  resulting_text_after_masking = ""
  text.split("").each_with_index do |letter, index|
    output[index % number_of_columns] ||= []
    if mask[index % mask.length] == 1
      resulting_text_after_masking << letter
      output[index % number_of_columns] << letter
    end
  end

  output.map(&:join)
end

# Real keyword was 10 characters
index_of_coincidence("EMUFPHZLRFAXYUSDJKZLDKRNSHGNFIVJYQTQUXQBQVY")
 => {10=>0.06333333333333332, 5=>0.060317460317460304, 2=>0.03398268398268398, 4=>0.029292929292929294, 1=>0.028792912513842746, 6=>0.027777777777777776, 3=>0.020512820512820513, 7=>0.019047619047619046, 9=>0.0, 8=>0.0} 

# Real keyword was 8 characters
index_of_coincidence("VFPJUDEEHZWETZYVGWHKKQETGFQJNCEGGWHKK?DQMCPFQZDQMMIAGPFXHQRLGTIMVMZJANQLVKQEDAGDVFRPJUNGEUNAQZGZLECGYUXUEENJTBJLBQCRTBJDFHRRYIZETKZEMVDUFKSJHKFWHKUWQLSZFTIHHDDDUVH?DWKBFUFPWNTDFIYCUQZEREEVLDKFEZMOQQJLTTUGSYQPFEUNLAVIDXFLGGTEZ?FKZBSFDQVGOGIPUFXHHDRKFFHQNTGPUAECNUVPDJMQCLQUMUNEDFQELZZVRRGKFFVOEEXBDMVPNFQXEZLGREDNQFMPNZGLFLPMRJQYALMGNUVPDXVKPDQUMEBEDMHDAFMJGZNUPLGESWJLLAETG")
 => {8=>0.053887861034021996, 4=>0.046489709846518054, 2=>0.045726043449003606, 10=>0.04509246088193457, 9=>0.04482513872757775, 1=>0.04455302833751333, 7=>0.044328487724714136, 5=>0.04432629890164137, 6=>0.04383895869882121, 3=>0.04352653203951395} 

patterns.rb

ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

def find_pattern(pattern)
  longest_pattern = []

  expecting_pattern = []
  reversed_pattern = pattern.reverse
  reversed_pattern.each_with_index do |digit, index|
    revised_pattern = pattern[0..(-1 - index)]
    break if  revised_pattern.size <= expecting_pattern.size

    expecting_pattern.unshift digit

    if revised_pattern[0] == digit
      matches = true
      expecting_pattern.each_with_index do |digit_check, index_check|
        matches &&= revised_pattern[index_check] == digit_check
      end

      if matches
        longest_pattern = expecting_pattern
        break
      end
    end
  end

  return pattern[0..(-1 - longest_pattern.size)]
end

def find_diff_positive(left_text, right_text)
  diff = []

  left_text.split("").each_with_index do |letter, index|
    right_text_index = ALPHABET.index(right_text[index])
    left_text_index = ALPHABET.index(letter)
    change = (right_text_index >= left_text_index) ? right_text_index - left_text_index : (right_text_index + 26 - left_text_index)
    diff << change
  end

  return diff
end

# starting_position 64 as question marks are skipped during encryption/decryption
def pattern_shift_decipher(starting_position = 64, encrypted_text = "NYPVTTMZFPK", plain_text = "BERLINCLOCK", min_length = 7, max_length = 15)
  starting_position -= 1
  dictionary_array = File.readlines('dictionaries/standard.txt').map(&:chomp).keep_if{|word| word.length >= min_length && word.length <= max_length}

  patterns = {}
  keyword_array, abc_lookup_table = generate_table("KRYPTOS")

  dictionary_array.each do |word|
    keyword_starting_index = starting_position % word.size
    codex = generate_codex(abc_lookup_table, word)
    test_encryption_text = vigenere_encrypt(keyword_array, codex, plain_text, keyword_starting_index)
    diff = find_diff_positive(test_encryption_text, encrypted_text)
    patterns[word] = { diff: diff, pattern: find_pattern(diff), encrypted_text: test_encryption_text }
  end

  patterns
end

pattern_mapping = pattern_shift_decipher(64)
pattern_mapping.select{|k,v| v[:pattern].length < 9}
 => {"AUXILIARY"=>{:diff=>[5, 6, 16, 3, 1, 18, 3, 13, 5, 6, 16], :pattern=>[5, 6, 16, 3, 1, 18, 3, 13], :encrypted_text=>"ISZSSBJMAJU"}, "EARTHED"=>{:diff=>[0, 12, 17, 1, 4, 0, 25, 1, 0, 12, 17], :pattern=>[0, 12, 17, 1, 4, 0, 25, 1], :encrypted_text=>"NMYUPTNYFDT"}, "EARTHEN"=>{:diff=>[0, 12, 17, 1, 4, 0, 14, 1, 0, 12, 17], :pattern=>[0, 12, 17, 1, 4, 0, 14, 1], :encrypted_text=>"NMYUPTYYFDT"}, "EARTHLY"=>{:diff=>[0, 12, 17, 1, 4, 16, 8, 1, 0, 12, 17], :pattern=>[0, 12, 17, 1, 4, 16, 8, 1], :encrypted_text=>"NMYUPDEYFDT"}, "GALENICALS"=>{:diff=>[0, 5, 6, 11, 24, 16, 4, 6, 0, 5, 6], :pattern=>[0, 5, 6, 11, 24, 16, 4, 6], :encrypted_text=>"NTJKVDITFKE"}} 

vigenere.rb

### generate_table
### keyword: keyword used to generate initial table
### returns: array
### 1st value: keyword array
### 2nd value: hash with abc lookup for table
def generate_table(keyword)
  keyword_string = keyword.dup.split("").uniq.join

  ("A".."Z").each do |letter|
    keyword_string << letter unless keyword_string.include?(letter)
  end

  keyword_array = keyword_string.split("")

  abc_lookup_table = {}
  keyword_array.each_with_index do |letter, index|
    abc_lookup_table[letter] = keyword_array[index..-1] + keyword_array[0...index]
  end

  return keyword_array, abc_lookup_table
end

### generate_codex
### abc_lookup_table: table hash generated via generate_table
### keyword: keyword for creating keyed table
### returns: array composed of keyword letters from table
def generate_codex(abc_lookup_table, keyword)
  codex = []

  keyword.split("").each do |letter|
    codex << abc_lookup_table[letter]
  end

  codex
end

### vigenere_decrypt
### keyword_array: returned via generate_table
### codex: returned via generate_codex
### ciphertext: text to be decrypted
### codex_index: shift keyword, used for ending logic below, normally 0 to start fresh
### returns: decrypted text
def vigenere_decrypt(keyword_array, codex, ciphertext, codex_index = 0)
  codex_size = codex.size

  non_alphabetic_indexes = ciphertext.split("").each_index.select{|index| ciphertext[index].match(/[^A-Z]/i)}

  # Assumes encrypted text is in upcase with no spaces to speed up process
  decrypted_text = ciphertext.gsub(/[^A-Z]/i, '').split("").map do |letter|
    keyword_index = codex[codex_index].index(letter)
    decrypted_letter = keyword_array[keyword_index]

    # Reset back to 0 if we reach end of the codex
    codex_index = (codex_index + 1 == codex_size) ? 0 : codex_index + 1

    # Return encrypted letter
    decrypted_letter
  end

  # Set back to the value that can't be decrypted
  non_alphabetic_indexes.each do |index|
    decrypted_text.insert(index, ciphertext[index])
  end

  decrypted_text.join("")
end

### vigenere_encrypt
### keyword_array: returned via generate_table
### codex: returned via generate_codex
### plaintext: text to be encrypted
### codex_index: shift keyword, used for ending logic below, normally 0 to start fresh
### returns: encrypted text
def vigenere_encrypt(keyword_array, codex, unencrypted_text, codex_index = 0)
  codex_size = codex.size
  non_alphabetic_indexes = unencrypted_text.split("").each_index.select{|index| unencrypted_text[index].match(/[^A-Z]/i)}

  encrypted_text = unencrypted_text.upcase.gsub(/[^A-Z]/i, '').split("").map do |letter|
    keyword_index = keyword_array.index(letter)
    encrypted_letter = codex[codex_index][keyword_index]

    # Reset back to 0 if we reach end of the codex
    codex_index = (codex_index + 1 == codex_size) ? 0 : codex_index + 1

    # Return encrypted letter
    encrypted_letter
  end
  non_alphabetic_indexes.each do |index|
    encrypted_text.insert(index, unencrypted_text[index])
  end

  encrypted_text.join("")
end

def vigenere_kryptos_hardcode_encrypt(plain_text, word, starting_position = 1)
  starting_position -= 1
  keyword_starting_index = starting_position % word.size
  plain_text.upcase!
  keyword_array, abc_lookup_table = generate_table("KRYPTOS")

  codex = generate_codex(abc_lookup_table, word)
  vigenere_encrypt(keyword_array, codex, plain_text, keyword_starting_index)
end

# See https://en.wikipedia.org/wiki/Kryptos 
vigenere_kryptos_hardcode_encrypt("BETWEENSUBTLESHADINGANDTHEABSENCEOFLIGHTLIESTHENUANCEOFIQLUSION", "PALIMPSEST")
 => "EMUFPHZLRFAXYUSDJKZLDKRNSHGNFIVJYQTQUXQBQVYUVLLTREVJYQTMKYRDMFD" 
 
def vigenere_kryptos_hardcode_decryption(encrypted_text, known_plaintext, starting_position, min_length = 1, max_length = 200, dictionary = 'dictionaries/standard.txt')
  starting_position -= 1

  dictionary_array = File.readlines(dictionary).map(&:chomp).keep_if{|word| word.length >= min_length && word.length <= max_length}

  keyword_array, abc_lookup_table = generate_table("KRYPTOS")

  dictionary_array.each do |word|
    keyword_starting_index = starting_position % word.size
    codex = generate_codex(abc_lookup_table, word)
    decrypted_text = vigenere_decrypt(keyword_array, codex, encrypted_text, keyword_starting_index)
    if decrypted_text.include?(known_plaintext)
      puts "KRYPTOS, #{word}: #{decrypted_text}"
      return word
    elsif decrypted_text.include?(known_plaintext.reverse)
      puts "KRYPTOS, #{word} - R: #{decrypted_text.reverse}"
      return word
    end
  end

  nil
end
 
# You'll need a dictionary file with a word per line
# Only really useful if you have a needle

vigenere_kryptos_hardcode_decryption("EMUFPHZLRFAXYUSDJKZLDKRNSHGNFIVJYQTQUXQBQVYUVLLTREVJYQTMKYRDMFD", "SHADING", 1)
KRYPTOS, PALIMPSEST: BETWEENSUBTLESHADINGANDTHEABSENCEOFLIGHTLIESTHENUANCEOFIQLUSION
 => "PALIMPSEST" 

# If you're using a partial piece of the encrypted text you can specify a location for the text so that the correct starting point of the codex is used
vigenere_kryptos_hardcode_decryption("LRFAXYUSDJKZLDKRNSHGNFIVJYQTQUXQBQVYUVLLTREVJYQTMKYRDMFD", "SHADING", 8)
KRYPTOS, PALIMPSEST: SUBTLESHADINGANDTHEABSENCEOFLIGHTLIESTHENUANCEOFIQLUSION
 => "PALIMPSEST"