Affine cipher

The affine cipher turns letters from one alphabet into letters from the same alphabet.

There are three steps to enciphering/deciphering using the affine cipher.

1. Turn a letter into a number
2. Do math on that number
3. Turn that number into a letter

The second step is where the enciphering and deciphering are different.

Values and techniques used

Keys

The affine cipher uses 2 numerical keys.

These keys are often represented by the variables a and b.

Alphabet length

Letters map to a number and the other way around. For the English alphabet that means “a” is 0, “b” is 1, …, “z” is 25.

The length of that sequence is used during both enciphering and deciphering.

The alphabet length is often represented by the variable m. For English: m = 26.

Key a and alphabet length m have to be coprime. That means they’re integers with a greatest common divisor of 1.

This requirement exists because it is used while deciphering. A cipher that can’t ever be deciphered isn’t very useful now, is it?

Modulo

The modulus operation is used both in enciphering and deciphering.

While similar, modulus and remainder are NOT the same thing!

A modulo operation can be thought of as counting on a circle.
That circle has as many steps as the modulus you are applying.

Adding 1 to the number we take the modulo of means taking one step clockwise on the circle.

Starting at 0, and incrementing by one every step.
The result of a modulo calculation starts at 0 and increments by 1 until the maximum is reached.
Instead of incrementing that maximum, it reaches the top, and starts from 0 again.

In our example, we calculate numbers with a modulus of 26 (the length of the English alphabet). That means the maximum number is 25.

The same logic is applied for subtracting 1.
A subtraction by 1 results in 1 step counterclockwise.

Modular multiplicative inverse

The modular multiplicative inverse is used during deciphering.

In modular arithmetic, regular division isn’t allowed.
Instead we multiply by the modular inverse.

In regular arithmetic dividing by $7$ is equivalent to multiplying by ${1 \over 7}$.

In modular arithmetic that inverse is dependent on which modulus is used.

For example, a modular multiplicative inverse of $7$ in $\bmod 26$ is $15$.

We want to find a number (which we’ll call $v$) where multiplying by that number in $\bmod 26$ works out to $1$.

• $a$ is $7$
• $w$ is a random integer
• in $\bmod 26$

We want to find $v$ such that:

written differently:

What we just wrote, is a rearranged special case of Bézout’s identity. It says that a multiple of 7 plus a multiple of 26 is equal to the greatest common divisor of 7 and 26.

In the affine cipher, the greatest common divisor is always 1.

Remember, the number we’re interested in is $a^{-1}$.

The extended Euclidean algorithm calculates the greatest common divisor of 2 numbers along with both factors of Bézout’s identity.

$v$ is one of those factors!

By plugging $a$ and $26$ into the algorithm, we get 3 things back.

1. The greatest common divisor of $a$ and $26$, that’s $1$.
2. The first integer in Bézout’s identity, that’s $v$
3. The second integer in Bézout’s identity, which is irrelevant.

function egcd(a, b) {
  if (a == 0) {
    return [b, 0, 1];
  }
  if (b == 0) {
    return [a, 1, 0];
  }
  let quotient = Math.floor(b / a);
  let remainder = b % a;
  let [g, x, y] = egcd(remainder, a);
  return [g, y - quotient * x, x];
}

fn egcd(a: i32, b: i32) -> (i32, i32, i32) {
    match (a, b) {
        (0, _) => (b, 0, 1),
        (_, 0) => (a, 1, 0),
        _ => {
            let quotient = b / a;
            let remainder = b % a;
            let (g, x, y) = egcd(remainder, a);
            (g, y - quotient * x, x)
        }
    }
}

The function to calculate the modular multiplicative inverse checks if the greatest common divisor between key a, and alphabet length m is 1. If it is, it returns the first Bezout coefficient $\bmod m$, which is $a^{-1}$.

function mmi(a, m) {
  let [gcd, v] = egcd(a, m);
  if (gcd == 1) {
    return ((v % m) + m) % m;
  }
}

fn mmi(a: i32, m: i32) -> Option<i32> {
    let (g, v, _) = egcd(a, m);
    match g {
        1 => Some(v.rem_euclid(m)),
        _ => None,
    }
}

Enciphering

Plaintext letter to number

A plaintext character is mapped to a number.

Our example uses the English alphabet and zero indexes letters. It maps “a” to 0, “b” to 1, …, “z” to 25.

In code, we take advantage of the ASCII table.

In ASCII, a lowercase "a" is represented by the number 97.

As a result, a character maps to the ASCII value of that character minus 97.

let plaintextNum = plaintextChar.charCodeAt(0) - 97;

let plaintext_num = plaintext_char as u8 - 97;

Manipulate the number

• $a$ and $b$ are the key numbers.
• $m$ is the length of the used alphabet.
• $x$ is the number corresponding to the plaintext letter.
• $y$ is the number corresponding to the ciphertext letter before the modulo operation.

The formula for enciphering is $y = a * x + b$.

This is done in $mod \space m$, so in our example it’s in $mod \space 26$.

That means the final ciphertext number is $y \space mod \space 26$.

let y = a * x + b;
y = ((y % 26) + 26) % 26;

let mut y = a * x + b;
y = y.rem_euclid(26);

Number to enciphered letter

Where we turned a letter into a number previously, we reverse that process.

In code, we use the ASCII table again.

This time, we add 97 to the zero indexed number and look up the resulting letter in the ASCII table.

let ciphertextChar = String.fromCharCode(ciphertextNum + 97);

let ciphertext_char = (ciphertextNum + 97) as char;

Demo

Deciphering

Enciphered letter to number

This step is identical to the first one while enciphering.

We look up the ASCII code for a lowercase letter, then we subtract the code for a lowercase ASCII "a". This results in a number that is zero indexed.

let ciphertextNum = ciphertextChar.charCodeAt(0) - 97;

let ciphertext_num = ciphertext_char as u8 - 97;

Manipulate the number

• $a$ and $b$ are the key numbers.
• $m$ is the length of the used alphabet.
• $y$ is the number corresponding to the ciphertext letter.
• $x$ is the number corresponding to the plaintext letter before the modulo operation.

The formula for enciphering is $y = a * x + b$.

The formula for deciphering is derived by rewriting that equation. The goal is to isolate the plaintext letter in the equation.

Rewritten with the plaintext number on the left side: The formula for deiphering is $x = a^{-1} * (y - b)$.

It is important to remember these calculation are done in $\bmod m$.

That is why we are not allowed to divide by $a$. Instead, we multiply by the modular multiplicative inverse of $a \pmod m$.

const inverse = mmi(a, 26);
let x = inverse * (cipherCharNum - b);
x = ((x % 26) + 26) % 26;

let inverse = mmi(a, 26);
let mut x = inverse * (cipherchar_num - b);
x = x.rem_euclid(26);

Number to plaintext letter

This step is identical to the last one while enciphering.

We add the number for a lowercase ASCII "a" to our zero indexed number. Then we look up the letter for that number in the ASCII table.

let plaintextChar = String.fromCharCode(plaintextNum + 97);

let plaintext_char = (plaintext_num + 97) as char;

Demo

Final code and demo

The demo and code to encipher/decipher entire strings instead of single characters is below.

Demo

Code

const LOWERCASE_ASCII_A = 97;

function mod(a, b) {
  return ((a % b) + b) % b;
}

function egcd(a, b) {
  if (a == 0) {
    return [b, 0, 1];
  }
  if (b == 0) {
    return [a, 1, 0];
  }
  let quotient = Math.floor(b / a);
  let remainder = b % a;
  let [g, x, y] = egcd(remainder, a);
  return [g, y - quotient * x, x];
}

function mmi(a, b) {
  let [gcd, v] = egcd(a, b);
  if (gcd == 1) {
    return mod(v, b);
  } else {
    throw new Error(`Key a: ${a} and alphabet length m: ${b} are not coprime`);
  }
}

function encipherChar(plainchar, a, b, m) {
  let plaincharNum = plainchar.charCodeAt(0) - LOWERCASE_ASCII_A;
  let ciphercharNum = a * plaincharNum + b;
  ciphercharNum = mod(ciphercharNum, m);
  return String.fromCharCode(ciphercharNum + LOWERCASE_ASCII_A);
}

function decipherChar(cipherchar, inverse, b, m) {
  let ciphercharNum = cipherchar.charCodeAt(0) - LOWERCASE_ASCII_A;
  let plaincharNum = inverse * (ciphercharNum - b);
  plaincharNum = mod(plaincharNum, m);
  return String.fromCharCode(plaincharNum + LOWERCASE_ASCII_A);
}

function encipherString(plaintext, a, b, m) {
  // check if an inverse to a exists
  mmi(a, m);

  return plaintext
    .split("")
    .map((char) => encipherChar(char, a, b, m))
    .join("");
}

function decipherString(ciphertext, a, b, m) {
  const inverse = mmi(a, m);

  return ciphertext
    .split("")
    .map((char) => decipherChar(char, inverse, b, m))
    .join("");
}

const LOWERCASE_ASCII_A: u8 = 97;

#[derive(Debug)]
enum AffineCipherError {
    NotCoprime(i32, i32)
}

fn egcd(a: i32, b: i32) -> (i32, i32, i32) {
    match (a, b) {
        (0, _) => (b, 0, 1),
        (_, 0) => (a, 1, 0),
        _ => {
            let quotient = b / a;
            let remainder = b % a;
            let (g, x, y) = egcd(remainder, a);
            (g, y - quotient * x, x)
        }
    }
}

fn mmi(a: i32, m: i32) -> Option<i32> {
    let (g, x, _) = egcd(a, m);
    match g {
        1 => Some(x.rem_euclid(m)),
        _ => None,
    }
}

fn encipher_char(plainchar: char, a: i32, b: i32, m: i32) -> char {
  let plainchar_num = plainchar as u8 - LOWERCASE_ASCII_A;
  let mut cipherchar_num = a * plainchar_num as i32 + b;
  cipherchar_num = cipherchar_num.rem_euclid(m);
  (cipherchar_num as u8 + LOWERCASE_ASCII_A) as char
}

fn decipher_char(cipherchar: char, inverse: i32, b: i32, m: i32) -> char {
  let cipherchar_num = cipherchar as u8 - LOWERCASE_ASCII_A;
  let mut plainchar_num = inverse * (cipherchar_num as i32 - b);
  plainchar_num = plainchar_num.rem_euclid(m);
  (plainchar_num as u8 + LOWERCASE_ASCII_A) as char
}

fn encipher_string(plaintext: &str, a: i32, b: i32, m: i32) -> Result<String, AffineCipherError> {
  mmi(a, m).ok_or(AffineCipherError::NotCoprime(a, m))?;
  let enciphered = plaintext.chars().map(|c| encipher_char(c, a, b, m)).collect();
  Ok(enciphered)
}

fn decipher_string(ciphertext: &str, a: i32, b: i32, m: i32) -> Result<String, AffineCipherError> {
  let inverse = mmi(a, m).ok_or(AffineCipherError::NotCoprime(a, m))?;
  let deciphered = ciphertext.chars().map(|c| decipher_char(c, inverse, b, m)).collect();
  Ok(deciphered)
}