Table of Contents
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 ofa
anda
isa
. Otherwise, go to step 2. - If
a > b
, replacea
witha-b
and go to step 1. - If
b > a
, replaceb
withb-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!
Top comments (0)