Implementación del cifrado de Vigenère cipher usando TypeScript/JavaScript

Este problema me lo encontré haciendo una Kata de Codewars. Es algo simple, pero que hay que tener en cuenta unos pequeños puntos para resolverlo, así que decidí escribir un poco de cómo llegué a su solución.

Kata: Vigenère cipher helper

¿Qué es el cifrado de Vigenère cipher?

Este cifrado fue originalmente desarrollado por un criptógrafo italiano llamado Giovan Battista Bellaso en el año 1553. Pero recibe su nombre por obra de un criptógrafo francés llamado Blaise de Vigenère. Básicamente es un cifrado basado en una serie de caracteres o letras, formando estos una tabla llamada table de Vigenère que se usa como clave. En otras palabras, este cifrado es un cifrado por sustitución simple polialfabético, es decir, que cada caracter de una palabra a cifrar, será sustituida por otro caracter de su dominio, siendo este dominio, por ejemplo, el abecedario.

Pasemos a un mejor ejemplo:

Para crear el algoritmo, debes tener 3 cosas en cuenta:

  1. Un abecedario, que este sería el dominio en el que actuará la serie para crear la clave. Por ejemplo, el abecedario inglés.
  2. Una clave que puede ser cualquier palabra. Por ejemplo, test.
  3. La palabra o cadena que quieras encriptar. Por ejemplo, helloworld, esta palabra debe contener letras o caracteres que estén en el abecedario.

La clave lo que debe hacer es que debe ser igual en longitud, respecto a la cadena que queremos encriptar, si esta es menor o mayor, se repetirá o se limitará, respectivamente. Puede ver este comportamiento en la siguiente tabla:

abecedario:      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
                 --------------------------------------------------
palabra:         h e l l o w o r l d
                 --------------------------------------------------
clave:           t e s t t e s t t e
                 --------------------------------------------------
resultado:       a i d e h a g k e h

¿Cómo realmente se genera el resultado? Adelante en este artículo lo explicaré.

En este caso usaré TypeScript que de igual forma será totalmente compatible con Javascript a excepción de los tipos; claro.

El primer paso sería definir nuestro abecedario y la clave que usaremos. Usaremos el abecedario inglés y la clave test, así:

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

Definiremos una clase llamada VigenereCipher con la siguiente estructura:

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) {}
}

Esta clase recibirá al momento de instanciarse el abecedario y la clave, y exponiendo dos métodos: encode y decode, hay un método privado llamado generateKey, pero este sólo servirá como helper para crear la serie que genera la clave.

Generar la clave

Empecemos primero a crear la lógica de generateKey:

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

Este método se encarga de generar una cadena siguiendo una serie en base a nuestra clave hasta completar el mismo número de caracteres de la palabra a codificar o decodificar. Entonces, si nuestra clave es test y queremos codificar la palabra helloworld lo que retorna la función es: testtestte, como ves ambas tienen la misma cantidad de caracteres.

Codificar

Ahora estamos listos para crear la lógica de nuestro método encode. Pero antes, debemos comprender lo siguiente:

La forma matemática de la función de codificar la tomé de un artículo de Wikipedia sobre el Cifrado de Vigenère:

image.png Donde Xi es la letra en la posición i del texto a cifrar, Ki es el caracter de la clave correspondiente a Xi, pues se encuentran en la misma posición, y L es el tamaño del abecedario. En este caso L= 26 (porque lo tomamos del abecedario inglés).

   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;
    }

En cuanto a términos de solucionar la Kata de Codewars en su descripción especifican que si una letra de la palabra a codificar/decodificar no existe en nuestro abecedario la debemos retornar sin modificarla.

Este método toma como argumento la palabra que queremos codificar, creamos una variable abc que hace referencia al abecedario que le pasamos como argumento a la clase al momento de instanciarla, después, recorremos la cadena a codificar con un for, la variable indexInAbc contendrá el índice en el que se encuentra la actual letra en nuestro abecedario. El método indexOf es un método que nos retorna el índice en el que se encuentra un elemento dado, si no se encuentra retorna -1, tomando en cuenta eso, lo que hacemos es que si una letra no se encuentra en nuestro abecedario solo la unimos a la variable decodedStr sin modificarle. En la variable index lo que hacemos es sumar Xi y Ki (tomando como ejemplo lo que expliqué anteriormente), siendo Xi, el índice en nuestro abecedario de la letra actual y Ki, el índice en nuestro abecedario de nuestra clave. Y la letra que añadiremos a la variable decodedStr es el resultado de la operación de la suma Xi y Ki por el módulo del tamaño de nuestro abecedario, o sea L =26.
En JavaScript la operación módulo se representa con %

Decodificar

Ahora lo que haremos es decodificar una cadena, esto es el método inverso, tomado también del artículo de Wikipedia sobre el Cifrado de Vigenère:

image.png

Donde Ci es el caracter en la posición i del texto cifrado, Ki viene siendo el caracter de la clave correspondiente a Ci, y L el tamaño del abecedario.

Ahora podemos crear la lógica de nuestro método decode:

 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;
    }

Este método funciona casi de la misma forma que el método encode, de hecho, ambos se pueden simplificar mucho más. Lo único que cambia es que cuando la resta de los índices en este caso Ci - Ki es mayor o igual a 0, el índice de la letra que buscaremos en nuestro abecedario, será Ci - Ki por el módulo de L, y cuando Ci - Ki es menor a 0 el índice de la letra que buscaremos en el abecedario será (Ci - Ki + L) por el módulo de L. Siendo L el tamaño de nuestro abecedario.

Así que el resultado de nuestro ejemplo es:

const abc = "abcdefghijklmnopqrstuvwxyz";
const key = "test"
const c = new VigenereCipher(abc, key);

const encoded = c.encode("helloworld")
console.log(encoded) // aidehagkeh
console.log(c.decode(encoded))  // helloworld

Eso sería todo, no es un algoritmo muy complejo, pero realmente es muy interesante su implementación y darnos acercamiento a cómo puede funcionar algunos métodos de cifrado. ¡Muchas gracias por leer!

El código completo es este:

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

    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;
    }

    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;
    }

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


const abc = "abcdefghijklmnopqrstuvwxyz";
const key = "test"
const c = new VigenereCipher(abc, key);

const encoded = c.encode("helloworld")
console.log(encoded) // aidehagkeh
console.log(c.decode(encoded))  // helloworld