Ora

How to do an Affine Cipher?

Published in Cryptography Ciphers 6 mins read

The Affine Cipher is a type of monoalphabetic substitution cipher, meaning each letter in the plaintext is substituted with another letter to form the ciphertext. It uses a mathematical function to encrypt and decrypt messages, relying on two keys and modular arithmetic.

Understanding the Basics

At its core, the Affine Cipher operates on the numerical representation of letters. Typically, the English alphabet (A-Z) is mapped to numbers from 0 to 25.

Alphabet to Number Mapping:

Letter Value Letter Value Letter Value Letter Value
A 0 H 7 O 14 V 21
B 1 I 8 P 15 W 22
C 2 J 9 Q 16 X 23
D 3 K 10 R 17 Y 24
E 4 L 11 S 18 Z 25
F 5 M 12 T 19
G 6 N 13 U 20

The cipher uses two keys, 'a' and 'b', where:

  • 'a' must be an integer coprime to 26 (meaning their greatest common divisor is 1). Examples include 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25.
  • 'b' can be any integer from 0 to 25.

Affine Cipher Encryption

To encrypt a message using an Affine Cipher, you'll apply a specific mathematical formula to each letter's numerical value.

The Encryption Formula

The formula for encryption is:

C = (ax + b) mod m

Where:

  • C is the numerical value of the ciphertext letter.
  • x is the numerical value of the plaintext letter.
  • a is the first key (multiplicative key).
  • b is the second key (additive key).
  • m is the size of the alphabet, typically 26 for English letters.
  • mod (modulo) means taking the remainder after division.

Step-by-Step Encryption Process

Let's encrypt the message "HELLO" using the keys a = 5 and b = 8.

  1. Convert Plaintext to Numerical Values:
    The first step in encrypting the message is to write the numeric values of each letter.

    • H = 7
    • E = 4
    • L = 11
    • L = 11
    • O = 14

  2. Apply the Encryption Formula (ax + b):
    Now, take each value of x (plaintext numerical value), and solve the first part of the equation, (5x + 8).

    • H (x=7): (5 * 7 + 8) = 35 + 8 = 43
    • E (x=4): (5 * 4 + 8) = 20 + 8 = 28
    • L (x=11): (5 * 11 + 8) = 55 + 8 = 63
    • L (x=11): (5 * 11 + 8) = 55 + 8 = 63
    • O (x=14): (5 * 14 + 8) = 70 + 8 = 78

  3. Apply the Modulo (mod m):
    After finding the value of (5x + 8) for each character, take the remainder when dividing the result of (5x + 8) by 26.

    • H (43): 43 mod 26 = 17
    • E (28): 28 mod 26 = 2
    • L (63): 63 mod 26 = 11
    • L (63): 63 mod 26 = 11
    • O (78): 78 mod 26 = 0

  4. Convert Numerical Values Back to Letters:

    • 17 = R
    • 2 = C
    • 11 = L
    • 11 = L
    • 0 = A

    So, the ciphertext for "HELLO" encrypted with a=5 and b=8 is "RCCLA".

Affine Cipher Decryption

To decrypt an Affine Cipher message, you need to reverse the encryption process using the inverse of the keys.

The Decryption Formula

The formula for decryption is:

x = a^-1 (C - b) mod m

Where:

  • x is the numerical value of the plaintext letter.
  • C is the numerical value of the ciphertext letter.
  • a^-1 (a-inverse) is the multiplicative inverse of a modulo m. This means (a * a^-1) mod m = 1.
  • b is the second key (additive key).
  • m is the size of the alphabet (26).

Finding the Multiplicative Inverse (a^-1)

To find a^-1, you need a number that, when multiplied by a and then divided by m, leaves a remainder of 1. For m = 26, you can test values or use the extended Euclidean algorithm.

For a = 5, we need to find a^-1 such that (5 * a^-1) mod 26 = 1.
Let's test multiples of 26 plus 1:

  • 1 * 26 + 1 = 27 (not divisible by 5)
  • 2 * 26 + 1 = 53 (not divisible by 5)
  • 3 * 26 + 1 = 79 (not divisible by 5)
  • 4 26 + 1 = 105 (105 / 5 = 21). So, a^-1 = 21.
    Check: (5     21) mod 26 = 105 mod 26 = 1.

Step-by-Step Decryption Process

Let's decrypt "RCCLA" using a = 5, b = 8, and a^-1 = 21.

  1. Convert Ciphertext to Numerical Values:

    • R = 17
    • C = 2
    • C = 2
    • L = 11
    • A = 0

  2. Apply the Decryption Formula (a^-1 (C - b) mod m):

    • R (C=17):
      • (C - b) = (17 - 8) = 9
      • (a^-1 (C - b)) = (21 9) = 189
      • (189 mod 26) = 7 (Because 189 = 7 * 26 + 7)
    • C (C=2):
      • (C - b) = (2 - 8) = -6
      • To handle negative numbers in modulo, add m until positive: -6 + 26 = 20
      • (a^-1 (C - b)) = (21 20) = 420
      • (420 mod 26) = 4 (Because 420 = 16 * 26 + 4)
    • C (C=2): (Same as above) = 4
    • L (C=11):
      • (C - b) = (11 - 8) = 3
      • (a^-1 (C - b)) = (21 3) = 63
      • (63 mod 26) = 11 (Because 63 = 2 * 26 + 11)
    • A (C=0):
      • (C - b) = (0 - 8) = -8
      • To handle negative numbers in modulo: -8 + 26 = 18
      • (a^-1 (C - b)) = (21 18) = 378
      • (378 mod 26) = 14 (Because 378 = 14 * 26 + 14)

  3. Convert Numerical Values Back to Letters:

    • 7 = H
    • 4 = E
    • 4 = E
    • 11 = L
    • 14 = O

    Wait, the original plaintext was "HELLO", but decryption resulted in "HEELO". Let's recheck the calculation for C=2.
    R (C=17) -> 7 (H) - Correct
    C (C=2) -> (2-8) = -6. (-6 mod 26) = 20. (21 * 20) = 420. (420 mod 26) = 4. 4 is E. Correct.
    C (C=2) -> 4 (E). This is where the error occurred in my thought process. The second 'L' was encrypted to 'C' (2), so it decrypts back to 'E' (4).

    Let's re-verify the encryption example:
    H (7) -> (57+8) = 43 -> 43 mod 26 = 17 (R) - Correct
    E (4) -> (5    4+8) = 28 -> 28 mod 26 = 2 (C) - Correct
    L (11) -> (511+8) = 63 -> 63 mod 26 = 11 (L) - Correct
    L (11) -> (5    11+8) = 63 -> 63 mod 26 = 11 (L) - Correct
    O (14) -> (5*14+8) = 78 -> 78 mod 26 = 0 (A) - Correct

    The ciphertext "RCCLA" is correct for "HELLO" with (a=5, b=8).

    Now re-decrypt "RCCLA":
    R (17) -> x = 21 (17 - 8) mod 26 = 21 9 mod 26 = 189 mod 26 = 7 (H) - Correct
    C (2) -> x = 21 (2 - 8) mod 26 = 21 (-6) mod 26.
    -6 mod 26 = 20.
    x = 21 20 mod 26 = 420 mod 26 = 4 (E) - Correct
    C (2) -> x = 21     (2 - 8) mod 26 = 21 (-6) mod 26 = 21 20 mod 26 = 420 mod 26 = 4 (E) - This indicates my ciphertext 'RCCLA' was wrong. The second 'L' (11) was encrypted to 'L' (11), not 'C' (2).

    Let's re-check the encryption of "HELLO" carefully, letter by letter, using the provided (5x+8) and mod 26:

    • H (x=7): (5*7 + 8) = 43. 43 mod 26 = 17 (R).
    • E (x=4): (5*4 + 8) = 28. 28 mod 26 = 2 (C).
    • L (x=11): (5*11 + 8) = 63. 63 mod 26 = 11 (L).
    • L (x=11): (5*11 + 8) = 63. 63 mod 26 = 11 (L).
    • O (x=14): (5*14 + 8) = 78. 78 mod 26 = 0 (A).

    So, "HELLO" encrypts to "RCLLA" (not "RCCLA"). My initial example calculation for 'RCCLA' was slightly off for the third letter.

    Now, let's decrypt "RCLLA":

    • R (C=17): 21 (17 - 8) mod 26 = 21 9 mod 26 = 189 mod 26 = 7 (H)
    • C (C=2): 21 (2 - 8) mod 26 = 21 (-6) mod 26 = 21 * 20 mod 26 = 420 mod 26 = 4 (E)
    • L (C=11): 21 (11 - 8) mod 26 = 21 3 mod 26 = 63 mod 26 = 11 (L)
    • L (C=11): 21 (11 - 8) mod 26 = 21 3 mod 26 = 63 mod 26 = 11 (L)
    • A (C=0): 21 (0 - 8) mod 26 = 21 (-8) mod 26 = 21 * 18 mod 26 = 378 mod 26 = 14 (O)

    This results in "HELLO" again. The decryption process is robust when the correct ciphertext is used.

Key Selection and Security

  • Key 'a': Must be coprime to 26. This is crucial because if 'a' shares a factor with 26 (e.g., 2, 4, 6, 8, etc., or 13), then a^-1 will not exist, and decryption will be impossible. There are 12 possible values for 'a'.
  • Key 'b': Can be any integer from 0 to 25. There are 26 possible values for 'b'.
  • Total Keys: This gives 12 * 26 = 312 possible keys. This is a very small keyspace, making the Affine Cipher relatively easy to break using brute-force attacks or frequency analysis.

While simple to implement, the Affine Cipher is not considered secure for protecting sensitive information due to its limited key space and susceptibility to cryptanalysis.

← Previous Article
What Does the Beast Represent in Hotel California?
Next Article →
What is a G59 Application?