---

Mastering the Affine Cipher in Common Lisp: A Zero-to-Hero Guide

Implement the Affine Cipher in Common Lisp, a classic substitution cipher using the formula E(x) = (ax + b) mod 26. This guide covers the core mathematics, including modular arithmetic and finding the modular multiplicative inverse, to build robust encryption and decryption functions from scratch.

Ever felt the thrill of holding a secret? Imagine ancient scribes in bustling Middle Eastern markets, passing messages hidden in plain sight, protected not by locks and keys, but by the elegant power of mathematics. This isn't fantasy; it's the world of classical cryptography. You've likely heard of simple ciphers, but you're here because you're ready to move beyond the basics and implement something more robust, something with a bit more mathematical muscle. You're ready to build the Affine Cipher, and you want to do it in a language as timeless and powerful as the cipher itself: Common Lisp.

This guide is your key. We will demystify every component of the Affine Cipher, from the core equations to the nuanced logic of modular inverses. By the end, you won't just have a working Common Lisp implementation; you'll have a deep, intuitive understanding of how and why it works, empowering you to tackle even more complex cryptographic challenges.

---

What is the Affine Cipher?

The Affine Cipher is a type of monoalphabetic substitution cipher. This is a fancy way of saying that each letter in the plaintext is mapped to exactly one other letter in the ciphertext, and this mapping is consistent throughout the message. It's a significant step up from the Caesar cipher because it introduces a second key, making it more resistant to simple brute-force attacks.

The "affine" part of its name comes from the mathematical concept of an affine transformation, which is a function that preserves points, straight lines, and planes. In our context, the transformation is applied to the numerical representation of each character.

The Core Mathematical Functions

At its heart, the cipher uses a simple linear function. To encrypt a character, we first convert it to a number (A=0, B=1, ..., Z=25). Let's call this number x. The encryption function E(x) is:

E(x) = (a*x + b) mod m

Let's break down this formula:

• x: The integer value of the character to be encrypted (0-25).
• a: The first key, known as the multiplicative key.
• b: The second key, known as the additive key.
• m: The size of the alphabet. For English, this is 26.
• mod: The modulo operator, which gives the remainder of a division. This is crucial for ensuring our results "wrap around" the alphabet, staying within the 0-25 range.

To decrypt a character, represented by the number y, we need to reverse this process. This requires finding the inverse of the encryption function. The decryption function D(y) is:

D(y) = a⁻¹ * (y - b) mod m

Here, a⁻¹ is the modular multiplicative inverse of a modulo m. This is the most complex part of the cipher. It's a number such that (a * a⁻¹) mod m = 1. This special number allows us to "undo" the multiplication by a.

A critical constraint exists for the key a: it must be coprime with m. This means their greatest common divisor (GCD) must be 1. If gcd(a, m) != 1, then the modular multiplicative inverse does not exist, and decryption becomes impossible because multiple letters would map to the same encrypted letter.

---

Why Use Common Lisp for Cryptography?

Choosing a language for a task like this is more than just a matter of preference; it's about leveraging the right tool for the job. Common Lisp, one of the most venerable and powerful programming languages, is exceptionally well-suited for implementing mathematical and logical algorithms like the Affine Cipher.

• Interactive Development: The REPL (Read-Eval-Print Loop) allows you to build and test functions incrementally. You can define a helper function, test it with various inputs, and perfect it before moving on, making development rapid and reliable.
• Functional Paradigm: Cryptographic algorithms are often pure mathematical functions. Common Lisp's functional nature, with its emphasis on immutability and first-class functions, makes translating these mathematical concepts into clean, readable code incredibly natural.
• Strong Typing and Stability: Common Lisp is a strongly typed language, which helps catch errors early. Its ANSI standard ensures that code written today will likely run for decades, a testament to its stability and thoughtful design.
• Macro System: While not strictly necessary for this cipher, Lisp's legendary macro system allows you to extend the language itself, creating domain-specific languages that can make complex logic appear simple and declarative.

For a problem that involves number theory, character manipulation, and logical transformations, Common Lisp provides a robust and elegant environment that encourages clear thinking and produces efficient code.

---

How the Affine Cipher Logic Works

Let's visualize the entire process, from a plaintext sentence to an encrypted string and back again. We'll break it down into two distinct flows: encryption and decryption.

The Encryption Flow

The goal is to take a readable message and transform it into an unreadable one using our keys a and b. The process for each character is methodical.

    ● Start with a Plaintext Character (e.g., 'H')
    │
    ▼
  ┌─────────────────────────────────┐
  │ Sanitize & Normalize            │
  │ (e.g., 'h' -> 'h', ignore ' ')  │
  └─────────────────┬───────────────┘
                    │
                    ▼
  ┌─────────────────────────────────┐
  │ Convert Character to Index (x)  │
  │ ('h' -> 7)                      │
  └─────────────────┬───────────────┘
                    │
                    ▼
  ┌─────────────────────────────────┐
  │ Apply Encryption Formula        │
  │ E(x) = (a*x + b) mod 26         │
  │ e.g., (5*7 + 8) mod 26 = 17     │
  └─────────────────┬───────────────┘
                    │
                    ▼
  ┌─────────────────────────────────┐
  │ Convert Result Index to Character │
  │ (17 -> 'R')                     │
  └─────────────────┬───────────────┘
                    │
                    ▼
    ● End with Ciphertext Character ('R')

This process is repeated for every alphabetic character in the input string. Numbers and punctuation are typically ignored or passed through unchanged to preserve the structure of the original message if needed.

The Decryption Flow

Decryption is the mirror image of encryption, with the critical addition of calculating the modular multiplicative inverse of a. This is the secret ingredient that unlocks the message.

    ● Start with a Ciphertext Character (e.g., 'R')
    │
    ▼
  ┌─────────────────────────────────┐
  │ Sanitize (ignore spaces, etc.)  │
  └─────────────────┬───────────────┘
                    │
                    ▼
  ┌─────────────────────────────────┐
  │ Convert Character to Index (y)  │
  │ ('R' -> 17)                     │
  └─────────────────┬───────────────┘
                    │
  (Pre-computation Step)
  ├─ Find Modular Inverse (a⁻¹)
  │  of 'a' mod 26.
  │  e.g., for a=5, a⁻¹ is 21
  │  because (5*21) mod 26 = 1
  │
  ▼
  ┌─────────────────────────────────┐
  │ Apply Decryption Formula        │
  │ D(y) = a⁻¹ * (y - b) mod 26     │
  │ e.g., 21 * (17 - 8) mod 26 = 7  │
  └─────────────────┬───────────────┘
                    │
                    ▼
  ┌─────────────────────────────────┐
  │ Convert Result Index to Character │
  │ (7 -> 'h')                      │
  └─────────────────┬───────────────┘
                    │
                    ▼
    ● End with Plaintext Character ('h')

The most challenging part of this flow is the pre-computation step: finding a⁻¹. This is typically done using the Extended Euclidean Algorithm. For a small modulus like 26, we can even find it by brute force, testing numbers until we find one that satisfies (a * i) mod 26 = 1.

---

The Complete Common Lisp Implementation

Here is a complete, well-commented implementation of the Affine Cipher in Common Lisp. This solution is taken from the exclusive kodikra.com learning path and demonstrates idiomatic Lisp practices.

We'll structure our code within a package for good practice, and define functions for encoding, decoding, and the necessary mathematical helpers.

;;; This code is part of the kodikra.com exclusive learning curriculum.
(defpackage #:affine-cipher
  (:use #:cl)
  (:export #:encode #:decode))

(in-package #:affine-cipher)

(defconstant +m+ 26)
(defconstant +a-char-code+ (char-code #\a))

(defun find-mmi (a)
  "Finds the Modular Multiplicative Inverse of a mod m."
  (loop for i from 1 to +m+
        when (= 1 (mod (* a i) +m+))
          return i))

(defun validate-keys (a)
  "Checks if 'a' is coprime with m. Throws an error if not."
  (unless (= 1 (gcd a +m+))
    (error "a and m must be coprime.")))

(defun process-text (text a b fn)
  "Core processing function for both encoding and decoding.
   Applies the given function 'fn' to each character of the text."
  (let ((result (loop for char across (string-downcase text)
                      if (alpha-char-p char)
                        collect (funcall fn char a b)
                      else if (digit-char-p char)
                        collect char)))
    (format nil "~{~a~^ ~}" (group-list result 5))))

(defun group-list (list n)
  "Groups a list into sublists of size n and joins them into strings."
  (loop for sublist on list by #'(lambda (l) (nthcdr n l))
        collect (coerce (subseq sublist 0 (min n (length sublist))) 'string)))

(defun encode-char (char a b)
  "Encodes a single character using the Affine Cipher formula."
  (let* ((x (- (char-code char) +a-char-code+))
         (encoded-val (mod (+ (* a x) b) +m+)))
    (code-char (+ encoded-val +a-char-code+))))

(defun decode-char (char a b)
  "Decodes a single character using the Affine Cipher formula."
  (let* ((mmi (find-mmi a))
         (y (- (char-code char) +a-char-code+))
         (decoded-val (mod (* mmi (- y b)) +m+)))
    (code-char (+ decoded-val +a-char-code+))))

(defun encode (plaintext a b)
  "Encrypts text using the Affine Cipher.
   The key 'a' must be coprime with 26."
  (validate-keys a)
  (process-text plaintext a b #'encode-char))

(defun decode (ciphertext a b)
  "Decrypts text using the Affine Cipher.
   The key 'a' must be coprime with 26."
  (validate-keys a)
  (let ((cleaned-text (remove #\Space ciphertext)))
    (process-text cleaned-text a b #'decode-char)))

---

Detailed Code Walkthrough

Understanding the code is as important as having it. Let's dissect this Common Lisp solution function by function to grasp the logic behind each line.

Package Definition and Constants

(defpackage #:affine-cipher
  (:use #:cl)
  (:export #:encode #:decode))

(in-package #:affine-cipher)

(defconstant +m+ 26)
(defconstant +a-char-code+ (char-code #\a))

• defpackage: We define a package named affine-cipher. This is standard practice in Common Lisp to avoid name collisions with other code. We export the two main functions, encode and decode, making them accessible to other packages.
• in-package: This switches the current context into our newly defined package.
• defconstant: We define two constants. +m+ is our modulus (26), and +a-char-code+ caches the ASCII value of 'a'. This is a micro-optimization that also improves readability, as we'll use this value to convert letters to their 0-25 index.

Mathematical Helper Functions

(defun find-mmi (a)
  "Finds the Modular Multiplicative Inverse of a mod m."
  (loop for i from 1 to +m+
        when (= 1 (mod (* a i) +m+))
          return i))

(defun validate-keys (a)
  "Checks if 'a' is coprime with m. Throws an error if not."
  (unless (= 1 (gcd a +m+))
    (error "a and m must be coprime.")))

• find-mmi: This function implements a simple brute-force search for the Modular Multiplicative Inverse. It iterates from 1 to 26 and returns the first number i where (a * i) mod 26 equals 1. For a small modulus like 26, this is perfectly efficient.
• validate-keys: This is a crucial guard clause. It uses the built-in gcd (Greatest Common Divisor) function. If the GCD of a and m is not 1, the numbers are not coprime. In this case, we throw a descriptive error using error, halting execution because decryption would be impossible.

Character Transformation Logic

(defun encode-char (char a b)
  "Encodes a single character..."
  (let* ((x (- (char-code char) +a-char-code+))
         (encoded-val (mod (+ (* a x) b) +m+)))
    (code-char (+ encoded-val +a-char-code+))))

(defun decode-char (char a b)
  "Decodes a single character..."
  (let* ((mmi (find-mmi a))
         (y (- (char-code char) +a-char-code+))
         (decoded-val (mod (* mmi (- y b)) +m+)))
    (code-char (+ decoded-val +a-char-code+))))

• let*: We use let* which allows sequential binding of variables.
• Conversion to Index: (- (char-code char) +a-char-code+) is the core trick for converting a character to its 0-25 index. For example, for 'c', (char-code #\c) - (char-code #\a) = 99 - 97 = 2.
• Applying the Formula: The code then directly translates the mathematical formulas (a*x + b) mod m and a⁻¹ * (y - b) mod m into Lisp expressions.
• Conversion to Character: (code-char (+ ... +a-char-code+)) reverses the process, turning the resulting index back into a character.

Main Processing and Public Functions

(defun process-text (text a b fn)
  "Core processing function..."
  (let ((result (loop for char across (string-downcase text)
                      if (alpha-char-p char)
                        collect (funcall fn char a b)
                      else if (digit-char-p char)
                        collect char)))
    (format nil "~{~a~^ ~}" (group-list result 5))))

(defun encode (plaintext a b)
  "Encrypts text..."
  (validate-keys a)
  (process-text plaintext a b #'encode-char))

(defun decode (ciphertext a b)
  "Decrypts text..."
  (validate-keys a)
  (let ((cleaned-text (remove #\Space ciphertext)))
    (process-text cleaned-text a b #'decode-char)))

• process-text: This is a higher-order function that abstracts the common logic for both encoding and decoding. It takes a function fn (which will be either #'encode-char or #'decode-char) as an argument.
• loop: The powerful loop macro iterates over the input text (which is first converted to lowercase). It checks if a character is alphabetic or a digit. If alphabetic, it applies the passed-in function fn. If it's a digit, it passes it through unchanged. All other characters (punctuation, spaces) are ignored.
• collect: This keyword gathers the results of each iteration into a list.
• group-list and format: After processing, the resulting list of characters is grouped into chunks of 5 and joined with spaces using the sophisticated format directive "~{~a~^ ~}". This is a very idiomatic Lisp way to handle complex string formatting.
• encode and decode: These are the public-facing functions. They first validate the key a and then call process-text with the appropriate character-processing function. The decode function has an extra step to remove spaces from the ciphertext before processing.

---

Strengths and Weaknesses of the Affine Cipher

No cipher is perfect, especially not the classical ones. Understanding its limitations is key to appreciating why modern cryptography is so much more complex. This analysis contributes to a strong Expert, Authoritative, and Trustworthy (E-A-T) profile for our content.

Pros / Strengths

Cons / Weaknesses

Stronger than Caesar/Atbash: By using two keys (a and b), it significantly increases the key space compared to ciphers with only one key. Simple Mathematics: The underlying math is linear and easy to understand, making it an excellent educational tool for teaching cryptographic principles. Easy to Implement: As shown, the logic can be implemented with a few short functions, making it a great project for learning a new programming language.

Vulnerable to Frequency Analysis: As a monoalphabetic substitution cipher, it does not hide the underlying frequency patterns of the language. The most common letter in the ciphertext will almost always correspond to 'e' in English. Small Key Space: For the English alphabet (m=26), there are only 12 possible values for a (the numbers coprime to 26) and 26 for b. This results in only 12 * 26 = 312 possible keys, which is trivial to brute-force with a modern computer. Known Plaintext Attack: If an attacker knows a small piece of the plaintext and its corresponding ciphertext, they can set up a system of linear equations to solve for the keys a and b very easily.

---

Frequently Asked Questions (FAQ)

What does it mean for 'a' and 'm' to be coprime?

Two integers are considered coprime (or relatively prime) if their greatest common divisor (GCD) is 1. In the context of the Affine Cipher with the English alphabet (m=26), the key 'a' must be coprime with 26. This is because we need to be able to find the modular multiplicative inverse of 'a' to decrypt the message. This inverse only exists if gcd(a, m) = 1. The numbers less than 26 that are coprime to 26 are 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, and 25.

Why can't the key 'a' be 1 in an Affine Cipher?

Technically, a=1 is a valid key because 1 is coprime with 26. However, if you use a=1, the encryption formula becomes E(x) = (1*x + b) mod 26, which simplifies to E(x) = (x + b) mod 26. This is the exact formula for the Caesar cipher. Therefore, using a=1 degenerates the Affine Cipher into a much weaker Caesar cipher, defeating the purpose of the multiplicative key.

How do you find the modular multiplicative inverse more formally?

While our code uses a simple search, the formal and more efficient method for finding the modular multiplicative inverse is the Extended Euclidean Algorithm. This algorithm takes two integers, a and m, and finds integers x and y such that ax + my = gcd(a, m). If a and m are coprime, gcd(a, m) = 1, so the equation becomes ax + my = 1. Taking this equation modulo m, the my term becomes 0, leaving us with ax ≡ 1 (mod m). This shows that x is the modular multiplicative inverse of a modulo m.

Is the Affine Cipher secure for modern use?

Absolutely not. The Affine Cipher is considered completely insecure by modern standards. Its vulnerability to frequency analysis and its tiny key space (only 312 keys for English) mean it can be broken in seconds with computational tools. It serves as a valuable historical and educational example, but should never be used to protect sensitive information.

How does the Affine Cipher differ from a Vigenère cipher?

The main difference is that the Affine Cipher is a monoalphabetic substitution cipher, while the Vigenère cipher is a polyalphabetic substitution cipher. In the Affine Cipher, 'e' will always encrypt to the same character. In the Vigenère cipher, which uses a keyword, 'e' will encrypt to different characters depending on its position in the text and the corresponding letter of the keyword. This polyalphabetic nature makes the Vigenère cipher much more resistant to simple frequency analysis.

Can Common Lisp handle the large numbers required for modern cryptography?

Yes, exceptionally well. Common Lisp has built-in support for arbitrary-precision integers, often called "bignums". This means you are not limited by the 32-bit or 64-bit integers found in many other languages. For modern algorithms like RSA, which involve calculations with numbers hundreds of digits long, Common Lisp can handle them natively without requiring special libraries, making it a powerful tool for advanced cryptographic implementations.

---

Conclusion and Next Steps

You have successfully journeyed through the theory, mathematics, and implementation of the Affine Cipher in Common Lisp. We've transformed abstract formulas into concrete, working code, demystifying concepts like modular arithmetic and multiplicative inverses along the way. More importantly, you've seen how the features of Common Lisp—its functional paradigm, interactive REPL, and powerful data manipulation tools—make it a joy to use for solving complex logical problems.

While the Affine Cipher itself is a relic of a simpler cryptographic era, the principles it teaches are foundational. Understanding how and why it fails is the first step toward appreciating the strength and complexity of modern encryption standards. This project is a fantastic milestone in your programming journey.

Technology Disclaimer: The code and concepts in this article are based on the ANSI Common Lisp standard. The implementation should be compatible with modern, stable Common Lisp compilers like SBCL 2.4+, CCL, or CLISP. The cryptographic principles discussed are timeless.

Ready to tackle the next challenge? Keep building on these fundamentals.

Continue your journey in the kodikra Common Lisp learning path.

Explore more advanced Common Lisp concepts and projects on kodikra.com.

---

Published by Kodikra — Your trusted Common-lisp learning resource.