Solving the Vigenère Cipher Helper Kata in TypeScript: A Step-by-Step Guide

I encountered this problem while working on a Kata from Codewars. It's a simple problem, but there are a few points to keep in mind to solve it, so I decided to write a bit about how I arrived at the solution.

Kata: Vigenère cipher helper

What is the Vigenère cipher?

This cipher was originally developed by an Italian cryptographer named Giovan Battista Bellaso in 1553. However, it is named after a French cryptographer named Blaise de Vigenère. Essentially, it is a cipher based on a series of characters or letters, forming a table called the Vigenère table that is used as the key. In other words, this cipher is a polyalphabetic substitution cipher, meaning that each character in a word to be encrypted will be substituted by another character within its domain, such as the alphabet.

Let's move on to a clearer example:

To create the algorithm, you need to keep 3 things in mind:

An alphabet, which would be the domain in which the series operates to create the key. For example, the English alphabet.
A key that can be any word. For example, test.
The word or string you want to encrypt. For example, helloworld. This word must contain letters or characters that are in the alphabet.

The key must be of equal length to the string we want to encrypt. If it is shorter or longer, it will be repeated or limited, respectively. You can see this behavior in the following table:

alphabet:       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
                --------------------------------------------------
word:           h e l l o w o r l d
                --------------------------------------------------
key:            t e s t t e s t t e
                --------------------------------------------------
result:         a i d e h a g k e h

How exactly is the result generated? I'll explain it further in this article.

In this case, I'll use TypeScript, which will be fully compatible with JavaScript, except for the types.

The first step is to define our alphabet and the key that we will use. We will use the English alphabet and the key test, like this:

const abc = "abcdefghijklmnopqrstuvwxyz";
const key = "test"

We'll define a class called VigenereCipher with the following structure:

class VigenereCipher {
    private abc: string;
    private key: string;
    constructor(abc: string, key: string) {
        this.abc = abc;
        this.key = key;
    }

    decode(word: string) { }

    encode(word: string) { }

    private generateKey(key: string) {}
}

This class will receive the alphabet and the key when instantiated, and will expose two methods: encode and decode. There's also a private method called generateKey, but this will only serve as a helper to create the series that generates the key.

Generating the key

Let's start by creating the logic for generateKey:

 private generateKey(word: string) {
       let generatedKey = "";
       while (generatedKey.length < word.length) {
           generatedKey += this.key;
       }
       return generatedKey.slice(0, word.length);
   }

This method generates a string by following a series based on our key until it matches the length of the word to be encoded or decoded. So, if our key is test and we want to encode the word helloworld, the function returns: testtestte, as you can see, both have the same number of characters.

Encoding

Now we're ready to create the logic for our encode method. But first, we need to understand the following:

The mathematical form of the encoding function was taken from a Wikipedia article on the Vigenère cipher:

Where X_i is the letter at position i of the text to be encrypted, K_i is the corresponding key character for X_i, as they are in the same position, and L is the size of the alphabet. In this case, L*= 26 (because we are using the English alphabet).*

   encode(word: string) {
        let completeKey = this.generateKey(word);

        let encodedStr = "";

        const abc = this.abc;

        for (let i = 0; i < word.length; i++) {
            const indexInAbc = abc.indexOf(word[i]);

            if (indexInAbc < 0) {
                encodedStr += word[i]
                continue;
            }
            let index = indexInAbc + abc.indexOf(completeKey[i]);
            encodedStr += abc[index % abc.length];
        }
        return encodedStr;
    }

_{In terms of solving the Codewars Kata, its description specifies that if a letter in the word to be encoded/decoded
does not exist in our alphabet, we should return it unchanged.}

This method takes as an argument the word we want to encode. We create a variable abc that references the alphabet we passed to the class when it was instantiated. Then, we iterate over the string to be encoded with a for loop. The variable indexInAbc will contain the index where the current letter is found in our alphabet. The indexOf method returns the index where a given element is located, or -1 if it is not found. Considering that, if a letter is not in our alphabet, we simply append it to the encodedStr variable without modifying it. In the index variable, we sum X_i and K_i (taking the example I explained earlier), where X_i is the index of the current letter in our alphabet and K_i is the index of our key in the alphabet. The letter that we add to the encodedStr variable is the result of the operation of the sum X_i and K_i modulo the length of our alphabet, or L = 26. _{In JavaScript, the modulo operation is represented by} <sub>%</sub>

Decoding

Now let's decode a string. This is the inverse method, also taken from the Wikipedia article on the Vigenère cipher:

Where C_i is the character at position i of the encrypted text, K_i is the corresponding key character for C_i, and L is the size of the alphabet.

Now we can create the logic for our decode method:

 decode(word: string) {
        const key = this.generateKey(word);

        let decodedStr = "";
        const abc = this.abc;

        for (let i = 0; i < word.length; i++) {

            const indexInAbc = abc.indexOf(word[i]);

            if (indexInAbc < 0) {
                decodedStr += word[i]
                continue;
            }
            let index = indexInAbc - abc.indexOf(key[i]);

            if (index >= 0) {
                decodedStr += abc[index % abc.length];
                continue;
            }

            if (index < 0) {
                decodedStr += abc[index + abc.length];
            }

        }
        return decodedStr;
    }

This method works almost the same way as the encode method. In fact, both can be simplified much further. The only difference is that when the subtraction of the indices in this case C_i - K_i is greater than or equal to 0, the index of the letter we will look for in our alphabet will be C_i - K_i modulo L, and when C_i - K_i is less than 0, the index of the letter we will look for in the alphabet will be (C_i - K_i + L) modulo L. L is the size of our alphabet.

So the result of our example is:

const abc = "abcdefghijklmnopqrstuvwxyz";
const key = "test"
const c = new

 VigenereCipher(abc, key);

console.log(c.encode("helloworld"));

aidiahagke

I hope this has been useful for someone! :D

Conclusion

When solving a problem related to ciphers or encryption, it is important to first understand the theory behind it. By understanding the core principles, you can develop algorithms that are efficient and accurate. In the case of the Vigenère cipher, knowing the role of the alphabet, key, and the modular arithmetic involved helps in crafting a correct implementation. I encourage you to try implementing this algorithm and experiment with different keys and alphabets to deepen your understanding.