Part 2: Classic Encryption Algorithms - Mono-alphabetic Substitution Ciphers
Tags: computerscience, security, beginners
Published: 2019-10-03 14:28:30

## Table of Contents

<!-- TOC -->

- [Table of Contents](#table-of-contents)
- [Mathematical Background](#mathematical-background)
  - [Greatest common divisor](#greatest-common-divisor)
  - [Coprime Numbers](#coprime-numbers)
  - [Modular Multiplicative Inverse](#modular-multiplicative-inverse)
- [Monoalphabetic Substitution Ciphers](#monoalphabetic-substitution-ciphers)
  - [Caesar Cipher](#caesar-cipher)
  - [Decimation Cipher](#decimation-cipher)
  - [Affine Cipher](#affine-cipher)

<!-- /TOC -->

## Mathematical Background

Before discussing some of the most known classical substitution algorithms, we need to set some mathematical foundations, that are used by these algorithms.

### Greatest common divisor

The **Greatest Common Divisor** (or `GCD`) of two numbers, is the largest number that divides them both. For example, the greatest common divisor of `8` and `36` is `4`, since `4` divides both `8` and `36` and no larger number exists that has this property.

The **Euclidean Algorithm** is a technique for quickly finding the **GCD** of two integers. The algorithm is based on the following observation: if *d* divides both *a* and *b*, then *d* also divides *a - b*. This means that the GCD of *a* and *b*, is the same as the GCD of *a - b* and *b*. As a result, we can use the following process to make an algorithm:

- If `a=b` stop. The GCD of `a` and `a` is `a`. Otherwise, go to step 2.
- If `a > b`, replace `a` with `a-b` and go to step 1.
- If `b > a`, replace `b` with `b-a` and go to step 1.

The Khan Academy has a great [article](https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/the-euclidean-algorithm) explaining the algorithm much better. 

The implementation of the above could be the following:

```js
/**
 * Calculate the greatest common divisor of two or more numbers.
 * @param  {...Number} arr The array of numbers to calculate the gcd of.
 * @return {Number}        The greatest common divisor of the provided numbers.
 */
const gcd = (...arr) => {

    // Recursion function that calculates the gcd of two numbers.
    const inner = (x, y) => (!y ? x : gcd(y, x % y));

    // Return the gdc of all the elements in the array.
    return [...arr].reduce((a, b) => inner(a, b));
};
```

### Coprime Numbers

Two integers, lets say `a` and `b` are said to be **coprime**, if the only positive integer that divides both of them is 1.

In other words, two numbers are **coprime** when their greatest common divisor is `1`.

Given the above, we can create a utility function to calculate a number of coprimes for a given integer:

```js
/**
 * Calculate a list of coprimes for the given `number`. Note that this function can generate only 
 * positive coprime numbers.
 * 
 * @param {Number} number       The number of which to calculate the coprimes.
 * @param {Number} [results=5]  The number of coprimes to calculate.
 * @returns {[Number]}          The `results` first coprimes of the given `number`.
 */
const findCoprimesFor = (number, results = 5) => {
    let coprimes = [1];  // A list to store all of our coprime numbers.
    let idx = 2;        // The current number.

    // The only coprime of 0 is 1, so there is no need to fire the loop.
    if (number === 0) {
        return coprimes;
    }

    // While there are more results to be calculated.
    while (coprimes.length !== results) {

        // If the gcd of the number and the idx is 1, then these two numbers are coprime.
        if (gcd(number, idx) === 1) {
            // So add them to the list.
            coprimes.push(idx);
        }

        // Increase to the next natural number.
        idx++;
    }

    return coprimes;
}
```

### Modular Multiplicative Inverse

A multiplicative inverse is something you can multiply to a number by to get 1. So, if for example we have the number `3`, its multiplicative inverse is `1/3`. But for our purposes, we want an *integer* that when multiplied by `3` gives something that is congruent to `1 (mod 26)`. In our case `9` is such a number, since `3 * 9 = 27 = 1 (mod 26)`.

Again Khan Academy explains this greatly in their [article](https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/modular-inverses).

In order to calculate the inverse we can use a naive algorithm, as shown below:

```js
const mmi = (a, b) => {
    a %= b;
    for(let i = 1; i < b; i++){
        if((a * i) % b === 1){
            return i;
        }
    }
}
```


## Monoalphabetic Substitution Ciphers

In monoalphabetic ciphers, each character of the plaintext is replaced with a corresponding character of ciphertext. A single one-to-one mapping function (*f*) from plaintext to ciphertext character is used to encrypt the entire message using the same key (*k*).

### Caesar Cipher

More than 2000 years ago, the military secrets of the Roman empire were kept secret with the help of cryptography. The 'Caesar cipher' as it is now called, was used by Julius Caesar to encrypt messages by shifting letters alphabetically.

The first step is to assign a number to each letter. So we have the following:

|            |       |       |       |       |       |       |       |       |       |       |       |       |       |       |       |       |       |       |       |       |       |       |       |       |       |       |
| :--------: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: |
| **Letter** |   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   |
| **Index**  |   0   |   1   |   2   |   3   |   4   |   5   |   6   |   7   |   8   |   9   |  10   |  11   |  12   |  13   |  14   |  15   |  16   |  17   |  18   |  19   |  20   |  21   |  22   |  23   |  24   |  25   |

#### Encryption

In order to encrypt a message, we convert its letters to numbers, as we did above, add the key to them, and then convert them back to letters.

In the following example, we are going to set our key `k` as 3, and encrypt the message `MEET AT TEN`. 

|                          |   M   |   E   |   E   |   T   |       |   A   |   T   |       |   T   |   E   |   N   |
| :----------------------: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: |
|    **Original Index**    |  12   |   4   |   4   |  19   |       |   0   |  19   |       |  19   |   4   |  13   |
| **Original Index + key** |  15   |   7   |   7   |  22   |       |   3   |  22   |       |  22   |   7   |  16   |
|     **Cipher Text**      |   P   |   H   |   H   |   W   |       |   D   |   W   |       |   W   |   H   |   Q   |

So our ciphertext will be `PHHW DW WHQ`.

When Caesar used the cipher, he always shifted by 3, buth there's no reason for us to stick with this convention. For example, we could have encrypted the message `MEET ME AT TEN` by shifting the letters by 5 instead of 3:

|                          |   M   |   E   |   E   |   T   |       |   A   |   T   |       |   T   |   E   |   N   |
| :----------------------: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: |
|    **Original Index**    |  12   |   4   |   4   |  19   |       |   0   |  19   |       |  19   |   4   |  13   |
| **Original Index + key** |  17   |   9   |   9   |  24   |       |   5   |  24   |       |  24   |   9   |  18   |
|     **Cipher Text**      |   R   |   J   |   J   |   Y   |       |   F   |   Y   |       |   Y   |   J   |   S   |

So our ciphertext will be `RJJY FY YJS`.

There's a sublety to the Caesar cipher that hasn't come up yet. Imagine that we want to encrypt the message `MEET AT TWO` (note the change) with `5` as a key.

|                          |   M   |   E   |   E   |   T   |       |   A   |   T   |       |   T   |   W   |   O   |
| :----------------------: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: |
|    **Original Index**    |  12   |   4   |   4   |  19   |       |   0   |  19   |       |  19   |  22   |  14   |
| **Original Index + key** |  17   |   9   |   9   |  24   |       |   5   |  24   |       |  24   |  27   |  19   |
|     **Cipher Text**      |   R   |   J   |   J   |   Y   |       |   F   |   Y   |       |   Y   |  (?)  |   T   |

Note the question mark. It doesn't seem like there is a letter corresponding to the number 27. Such a letter would be two places past the letter `Z`. Whenever we are looking for a letter past the letter `Z`, we simply wrap around, and start back at the beginning of the alphabet again. In this way, the letter two past `Z` is `B`; so the encrypted message would be `RJJY FY YBT`.

The implementation of the above algorithm could be as follows:

```js
/**
 * Encrypt the provided `plaintext` to a ciphertext using the Caesar's cipher.
 * 
 * @param {String} plaintext  The plaintext to be encrypted.
 * @param {Number} key        The key to be used by the algorithm.
 * @return {String}           The encrypted message.
 */
const encrypt = (plaintext, key) => {
  /**
   * Convert the plaintext by removing all non-letter characters and convert it to upper-case.
   * This will remove all special characters, numbers and whitespace characters from the original
   * string.
   */
  plaintext = plaintext.replace(/[^a-zA-Z]/g, "").toUpperCase();

  // The alphabet used by the algorithm.
  let 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"];

  // Create an empty string to store the ciphertext.
  let ciphertext = "";

  /**
   * For each letter in the plaintext, calculate the index of the corresponding ciphertext letter
   * and append it to the ciphertext string.
   */
  for (let i = 0; i < plaintext.length; i++) {
    let cipherIdx = (alphabet.indexOf(plaintext[i]) + key) % 26;
    ciphertext += alphabet[cipherIdx];
  }

  return ciphertext;
};
```

#### Decryption

In order to decrypt the message, we just need to shift the letters **back** by the key. This corresponds to subtracting the key when we convert to numbers.

Again, using the `PHHW DW WZR` example:

|                          |   P   |   H   |   H   |   W   |       |   D   |   W   |       |   W   |   Z   |   R   |
| :----------------------: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: |
|    **Original Index**    |  15   |   7   |   7   |  22   |       |   3   |  22   |       |  22   |   7   |  16   |
| **Original Index - key** |  12   |   4   |   4   |  19   |       |   0   |  19   |       |  19   |   4   |  13   |
|     **Cipher Text**      |   M   |   E   |   E   |   T   |       |   A   |   T   |       |   T   |   E   |   N   |

The implementation of the above algorithm could be as follows:

```js
/* Decrypt the provided `plaintext` to a ciphertext using the Caesar's cipher.
 *
 * @param {Number} key        The key to be used by the algorithm.
 * @param {String} plaintext  The ciphertext to be decrypted.
 * @return {String}           The decrypted message.
 */
const decrypt = (plaintext, key) => {
  let 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"];

  // Create an empty string to store the plaintext.
  let plaintext = "";

  /**
   * For each letter in the ciphertext, calculate the index of the corresponding plaintext letter
   * and append it to the plaintext string.
   */
  for (let i = 0; i < plaintext.length; i++) {
    let plainIdx = mod(alphabet.indexOf(plaintext[i]) + key, 26);
    plaintext += alphabet[plainIdx];
  }
};

const mod = (m, n) => {
  return ((n % m) + m) % m;
};
```
### Decimation Cipher

The decimation cipher is another monoalphabetic substitution cipher. As in the Caesar cipher we are shifting the letters forward, but instead of adding the key to the index, we do a multiplication.

#### Encryption

In order to encrypt a message, we once again convert its letters to numbers, multiply the key with them, and then convert them back to letters. 

In the following example, we are going to set our key `k` as 63 and encrypt the message `MEET AT TEN`.

|                                 |   M   |   E   |   E   |   T   |       |   A   |   T   |       |   T   |   E   |   N   |
| :-----------------------------: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: |
|       **Original Index**        |  12   |   4   |   4   |  19   |       |   0   |  19   |       |  19   |   4   |  13   |
|    **Original Index * key**     |  756  |  252  |  252  | 1197  |       |   0   | 1197  |       | 1197  |  252  |  757  |
| **Original Index * key MOD 26** |   2   |  18   |  18   |   1   |       |   o   |   1   |       |   1   |  18   |   3   |
|         **Cipher Text**         |   C   |   S   |   S   |   B   |       |   A   |   B   |       |   B   |   S   |   N   |

So our ciphertext will be `CSSN AB BSN`.

Once again, there is a sublety to the Decimation cipher that hasn't come up. We can't use just **any** number. Some keys may cause the cipher alphabet to map several plaintext letters to the same ciphertext letters. 

For example, the `key` 10 using the standard Latin alphabet, we get the following:

|                         |   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   |
| :---------------------: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: |
|   **Original Index**    |   0   |   1   |   2   |   3   |   4   |   5   |   6   |   7   |   8   |   9   |  10   |  11   |  12   |  13   |  14   |  15   |  16   |  17   |  18   |  19   |  20   |  21   |  22   |  23   |  24   |  25   |
|  **Ciphertext Index**   |   0   |  10   |  20   |   4   |  14   |  24   |   8   |  18   |   2   |  12   |  22   |   6   |  16   |   0   |  10   |  20   |   4   |  14   |  24   |   8   |  18   |   2   |  12   |  22   |   6   |  16   |
| **Ciphertext Alphabet** |   A   |   K   |   U   |   E   |   O   |   Y   |   I   |   S   |   C   |   M   |   W   |   G   |   Q   |   A   |   K   |   U   |   E   |   O   |   Y   |   I   |   S   |   C   |   M   |   W   |   G   |   Q   |

As you can notice, some letters appear two times, and some letters never appear. To be more precise, the letters `ACEGIKMOQSUWY` appear twice, and the letters `BDFHJLNPRTVXZ` never appear. In order to bypass this issue, we must select a key that is a [**coprime**](#coprime-numbers) of the length of the alphabet.

The implementation of the above algorithm could be as follows:

```js
/*
 * Encrypt the provided `plaintext` to a ciphertext using the Decimation cipher.
 *
 * @param {String} plaintext  The plaintext to be encrypted.
 * @param {Number} key        The key to be used by the algorithm.
 * @return {String}           The encrypted message.
 */
const encrypt = (plaintext, key) => {
  /**
   * Convert the plaintext by removing all non-letter characters and convert it to upper-case.
   * This will remove all special characters, numbers and whitespace characters from the original
   * string.
   */
  plaintext = plaintext.replace(/[^a-zA-Z]/g, "").toUpperCase();

  // The alphabet used by the algorithm.
  // prettier-ignore
  let 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"];

  // Create an empty string to store the ciphertext.
  let ciphertext = "";

  /**
   * For each letter in the plaintext, calculate the index of the corresponding ciphertext letter
   * and append it to the ciphertext string.
   */
  for (let i = 0; i < plaintext.length; i++) {
    let cipherIdx = (alphabet.indexOf(plaintext[i]) * key) % 26;
    ciphertext += alphabet[cipherIdx];
  }

  return ciphertext;
};
```

#### Decryption

Just like we decrypted Caesar cipher messages by subtracting the encryption key, we can decrypt a message encrypted using the Decimation cipher by multiplying the message by multiplying by the multiplicative inverse of the key. This in essence "reverses" the multiplication operation.

Using our `CSSN AB BSN` message, and since our key was `63` we need the modular multiplicative inverse of that key. This number is `19`. So, we will multiply our message with that number in order to decrypt it.

|                              |   C   |   S   |   S   |   B   |       |   A   |   B   |       |   B   |   S   |   N   |
| :--------------------------: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: |
|      **Original Index**      |   2   |  18   |  18   |   1   |       |   o   |   1   |       |   1   |  18   |   3   |
| **Original Index * inverse** |  12   |   4   |   4   |  19   |       |   0   |  19   |       |  19   |   4   |  13   |
|       **Cipher Text**        |   M   |   E   |   E   |   T   |       |   A   |   T   |       |   T   |   E   |   N   |

The implementation of the above, could be as follows:

```js
/*
 * Decrypt the provided `ciphertext` to a ciphertext using the Decimation cipher.
 *
 * @param {String} ciphertext  The ciphertext to be decrypted.
 * @param {Number} key        The key to be used by the algorithm.
 * @return {String}           The decrypted message.
 */
const decrypt = (ciphertext, key) => {
  // The alphabet used by the algorithm.
  let 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"];

  // Create an empty string to store the plaintext.
  let plaintext = "";

  let inverse = mmi(key, 26);
  /**
   * For each letter in the ciphertext, calculate the index of the corresponding plaintext letter
   * and append it to the plaintext string.
   */
  for (let i = 0; i < ciphertext.length; i++) {
    let plainIdx = (alphabet.indexOf(ciphertext[i]) * inverse) % 26;
    plaintext += alphabet[plainIdx];
  }

  return plaintext;
};
```

### Affine Cipher

The Affine cipher works through a combination of modular multiplication and modular addition. In other words, the affine cipher is a combination of a Caesar's cipher and a multiplication cipher.

#### Encryption

In order to encrypt a plaintext with the affine cipher, we need two keys, `a` and `b`. Once again, we convert the letters to a number, then multiply it by `a`, and then add `b` to the result, and finally get the `result modulo 26`.  

Let's encrypt the message `MEET AT TEN` with the affine cipher, using the keys `3` and `10`:

|                             |   M   |   E   |   E   |   T   |       |   A   |   T   |       |   T   |   E   |   N   |
| :-------------------------: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: |
|          **Index**          |  12   |   4   |   4   |  19   |       |   0   |  19   |       |  19   |   4   |  13   |
| `y = (3*index + 10) mod 26` |  20   |  22   |  22   |  15   |       |  10   |  15   |       |  15   |  22   |  23   |
|       **Ciphertext**        |   U   |   W   |   W   |   P   |       |   K   |   P   |       |   P   |   W   |   X   |

The implementation of the above algorithm could be as follows:

```js
/*
 * Encrypt the provided `plaintext` to a ciphertext using the Decimation cipher.
 *
 * @param {String} plaintext   The plaintext to be encrypted.
 * @param {Number} keyA        The first key to be used by the algorithm.
 * @param {Number} keyB        The second key to be used by the algorithm.
 * @return {String}            The encrypted message.
 */
const encrypt = (plaintext, keyA, keyB) => {
  /**
   * Convert the plaintext by removing all non-letter characters and convert it to upper-case.
   * This will remove all special characters, numbers and whitespace characters from the original
   * string.
   */
  plaintext = plaintext.replace(/[^a-zA-Z]/g, "").toUpperCase();

  // The alphabet used by the algorithm.
  // prettier-ignore
  let 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"];

  // Create an empty string to store the ciphertext.
  let ciphertext = "";

  /**
   * For each letter in the plaintext, calculate the index of the corresponding ciphertext letter
   * and append it to the ciphertext string.
   */
  for (let i = 0; i < plaintext.length; i++) {
    let cipherIdx = ((alphabet.indexOf(plaintext[i]) * keyA) + keyB) % 26;
    ciphertext += alphabet[cipherIdx];
  }

  return ciphertext;
};
```

#### Decryption

As we discussed above, the affine cipher is a combination of the Caesar cipher and the Decimation cipher. Thus, the encryption process is a Caesar cipher merged with a multiplication cipher. In order to decrypt the message we need a combination of a Caesar and a multiplication cipher decryption.

First we need to calculate the modular multiplicative inverse of `keyA`. Then we perform the reverse operations performed by the encryption algorithm. So, we are going to multiply the index with the inverse of `keyA` and then subtract the `keyB` and calculate the modulo of the result.

|                             |   U   |   W   |   W   |   P   |       |   K   |   P   |       |   P   |   W   |   X   |
| :-------------------------: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: |
|          **Index**          |  20   |  22   |  22   |  15   |       |  10   |  15   |       |  15   |  22   |  23   |
| `y = (3*index + 10) mod 26` |  12   |   4   |   4   |  19   |       |   0   |  19   |       |  19   |   4   |  13   |
|       **Ciphertext**        |   M   |   E   |   E   |   T   |       |   A   |   T   |       |   T   |   E   |   N   |

The implementation of the above, could be like the following:

```js
/*
 * Decrypt the provided `ciphertext` to a plaintext using the Affine cipher.
 *
 * @param {String} plaintext  The encrypted to be decrypted.
 * @param {Number} keyA        The first key to be used by the algorithm.
 * @param {Number} keyB        The second key to be used by the algorithm.
 * @return {String}           The decrypted message.
 */
const decrypt = (ciphertext, keyA, keyB) => {
  // The alphabet used by the algorithm.
  // prettier-ignore
  let 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"];

  // Create an empty string to store the plaintext.
  let plaintext = "";

  let inverse = mmi(keyA, 26);
  /**
   * For each letter in the ciphertext, calculate the index of the corresponding plaintext letter
   * and append it to the plaintext string.
   */
  for (let i = 0; i < ciphertext.length; i++) {
    let plainIdx = (alphabet.indexOf(ciphertext[i]) * inverse - keyB) % 26;
    plaintext += alphabet[plainIdx];
  }

  return plaintext;
}
```

On the next part we are going to discuss the evolution of monoalphabetic substitution ciphers, the polyalphabetic substitution ciphers.

Do you have something to add? Leave a comment below, and thanks for reading!