Kostas Kalafatis

Posted on Oct 3, 2019

Part 2: Classic Encryption Algorithms - Mono-alphabetic Substitution Ciphers

#computerscience #security #beginners

Table of Contents
Mathematical Background
Monoalphabetic Substitution Ciphers

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 explaining the algorithm much better.

The implementation of the above could be the following:

/**
 * 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:

/**
 * 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.

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

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:

/**
 * 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:

/* 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 of the length of the alphabet.

The implementation of the above algorithm could be as follows:

/*
 * 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:

/*
 * 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:

/*
 * 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:

/*
 * 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!

DEV Community

Part 2: Classic Encryption Algorithms - Mono-alphabetic Substitution Ciphers

Table of Contents

Mathematical Background

Greatest common divisor

Coprime Numbers

Modular Multiplicative Inverse

Monoalphabetic Substitution Ciphers

Caesar Cipher

Encryption

Decryption

Decimation Cipher

Encryption

Decryption

Affine Cipher

Encryption

Decryption

Top comments (0)

Read next

Learning Java Together: A Fun Journey into Coding Basics 👩🏼‍💻📚!

Day 36: Monitoring Kubernetes with Prometheus and Grafana

Azure Cloud Computing Platform: Unlocking Endless Possibilities 🌍

Understanding Kubernetes Security: Common Vulnerabilities and Modern Solutions