Receive New Tutorials

Two Algorithms for Solving Vigenere Cipher in Ruby

– {{showDate(postTime)}}

The Vigenère cipher is named for Blaise de Vigenère (pictured).

This piece is reposted from Hannah Squier’s blog with permission.

In this tutorial, we’ll cover two different algorithms to encrypt text with Vigenere Cipher. One is a more naive, but concise, solution; and the second is more computationally efficient. We’ll discuss the time and space complexity of each and conclude with how to design your code so it is as efficient as it can be.

Background

Vigenere Cipher is a variation on the more well known Caesar’s cipher. Before diving into Vigenere it’s important to understand how Caesar’s cipher works.

Caesar’s cipher takes a single integer key, and offsets each character in the target string by that many letters in the alphabet. So with a key of 2, the following letters would map like so: a → c, r → t, z → b, etc. Encrypting “iloveruby” with a key of 2, yields “knqxgtwda.” Every letter is shifted in the alphabet by the key and letters wrap around the alphabet.

Instead of one key, Vigenere takes in a key sequence as an array ([1, 2, 3]). Every letter is shifted by the corresponding key in the key sequence. The key sequence repeats itself once the end of the pattern is reached. See below how Vigenere Cipher encrypts “iloveruby” with key sequence [1, 2, 3].

Word    "iloveruby"
Keys:   [1, 2, 3]
Word:   i l o v e r u b y
Keys:   1 2 3 1 2 3 1 2 3
Cipher: j n r w g u v d b

The Problem

Write a method that takes a string and a key-sequence and returns the encrypted word using Vigenere Cipher. For now, assume all characters are lowercase a-z characters.

Method #1: Concise But Inefficient

In this method we begin by initializing an empty string that will be the encrypted version of our word. We also initialize a constant ALPHABET, which is an array of strings from ‘a’ to ‘z.’ Then, we iterate through each character in the word being encrypted. We simultaneously index through the keys by using the modulus. On each iteration, we create a shifted alphabet by adjusting ALPHABET by the key amount. We then map the current character to the correct character in the shifted alphabet and append it to the encrypted string. See the pseudocode and solution below.

# The method vigenere_cipher takes two arguments: word (string) and keys (array).
  # First, initialize an empty encrypted word string.
   # Iterate through each character in word keeping track of index.
    # Set new variable key to the (index % keys.length) element of keys.
    # On each iteration, save the ALPHABET array shifted by key amount to shifted_alphabet.
    # Find the index of the current character in the ALPHABET array.
    # Use the index to map that character from ALPHABET to the shifted_alphabet.
    # Append the mapped character to encrypted word string.
  # Return the encrypted word string.

def vigenere_cipher(string, keys)

  encrypted_word = ""

  string.each_char.with_index do |char, i|
    key = keys[i % keys.length]
    shifted_alpha = ALPHABET[key..-1] + ALPHABET[0...key]
    encrypted_word << shifted_alpha[ALPHABET.index(char)]
  end
  encrypted_word
end

ALPHABET = %w(a b c d e f g h i j k l m n o p q r s t u v w x y z)

This method is concise, but has a few drawbacks. First of all, the shifted alphabet is re-created in memory on each iteration. If the encrypted word were 20 letters long, the shifted_alphabets would be re-created 20 times. With this approach we don’t have to handle the case where the mapped letter wraps around the alphabet (z → a).

The second drawback of this method is related to the way we store the ALPHABET constant. ALPHABET is an array, so every time we search through it for the current character to find the corresponding index, it is an O(n) operation. As you will see in the next method, if we had used a hash instead of an array, this would only be an O(1) operation.

Space Complexity: O(m), where m is the length of the alphabet. The only additional thing being created in memory is the shifted_alphabet which is m elements long.
Time Complexity: O(m*n), where m is the length of the alphabet and n is the length of the word. Indexing through the array ALPHABET (line 8) is an O(m) operation. We do this n times because we have to do it on each iteration. Therefore, the time complexity is the product of the length of word and the length of ALPHABET.
Conciseness & Readability: 8/10

Method #2: Trickier But More Efficient

Instead of creating a shifted alphabet, in this method, we use indexing and hashes. One hash maps each letter of the alphabet to an index and the other maps an index to each letter. The indexing makes mapping each letter to its encrypted version a bit trickier because we have to handle the wrap around case, but it saves memory. Follow along with the pseudocode and real code below to see how it’s done.

# Initialize two hash constants.
  # INDEX_TO_LETTER has indexes for keys and letters for values.
  # LETTER_TO_IDNEX has letters for keys and indexes for values.

# Method vigenere_cipher2 takes a word (string) and keys (array).
  # Initialize encrypted word to an empty string.
  # Iterate through each character in word keeping track of its index.
    # Set new variable key to the (index % keys.length) element of keys.
    # Find index of current character using LETTER_TO_INDEX.
      # If (index + key) < 26 append INDEX_TO_LETTER[index + key] to encrypted word.
      # Otherwise append INDEX_TO_LETTER[index + key - 26] to encrypted word.
  # Return encrypted word.

def vigenere_cipher2(string, keys)

encrypted_word = ""

string.each_char.with_index do |char, i|
  key = keys[i % keys.length]
  index = LETTER_TO_INDEX[char]

  if (index + key) < 26
    encrypted_word << INDEX_TO_LETTER[index + key]
  else
    encrypted_word << INDEX_TO_LETTER[index + key - 26] end end encrypted_word end INDEX_TO_LETTER = {0=>"a", 1=>"b", 2=>"c", 3=>"d", 4=>"e", 5=>"f", 6=>"g", 7=>"h", 8=>"i", 9=>"j", 10=>"k", 11=>"l", 12=>"m", 13=>"n", 14=>"o", 15=>"p", 16=>"q", 17=>"r", 18=>"s", 19=>"t", 20=>"u", 21=>"v", 22=>"w", 23=>"x", 24=>"y", 25=>"z"}

LETTER_TO_INDEX = {"a"=>0,"b"=> 1,"c"=> 2,"d"=> 3,"e"=> 4,"f"=> 5,"g"=> 6,"h"=> 7,
"i"=> 8,"j"=> 9, "k"=>10, "l"=>11, "m"=>12, "n"=>13, "o"=>14, "p"=>15, "q"=>16, "r"=>17, "s"=>18, "t"=>19, "u"=>20, "v"=>21, "w"=>22, "x"=>23, "y"=>24, "z"=>25}

Instead of recreating a shifted alphabet, this method maps each character to its shifted character by using indexing and hashes. While rewriting the alphabet has a space complexity of O(m), we do not need any extra memory when we use indexing into a hash.

Space Complexity: O(1) There are no new variables being stored in memory in this method, so it has constant space complexity.
Time Complexity: O(n). Where n is the length of the string. We iterate through each character in word, so this method has an O(n) time complexity. We do not have to include the complexity of indexing through the alphabet because we used two hashes instead of an array to represent the alphabet. Finding a value in a hash by its key is only an O(1) operation.
Conciseness & Readability: 6/10

Conclusion

Method 1 is a more concise but less efficient solution. This solution could be the best option if readability is most important. However, Method 2 has a better time and space complexity, so as the length of the word grows, this becomes the better solution.

Both of these methods could be augmented to handle cases where not all the characters are lowercase alpha characters. This makes the problem a bit more challenging, but does not change the general logic of the problem. Also, this cipher could be adjusted to handle different alphabets. (Fun fact: the Khmer alphabet has 74 characters! How would this affect Vigenere Cipher efficiency?)

There are many different ways to solve every algorithmic challenge, but each way has its tradeoffs. The important part is knowing what is best for your specific use case and how design decisions affect efficiency.

Bonus

Icqrz Epfjph*!

*Decode the secret message with Vigenere Cipher and a [1,2] key sequence.

Author’s Bio

vigenere cypher Hannah Squier is a self-taught software developer, with a background in GIS and civil engineering. As a UC Berkeley Engineering graduate and early startup employee, she has navigated many complex challenges with her technical know-how and perseverance. While preparing for her next adventure to become a full time software engineer, she writes tutorials to give back to the developer community. When she’s not coding, Hannah plays frisbee and thinks about how to make cities better places to live in. Get in touch at hannahsquier@gmail.com.