Affine Cipher in Crystal: Complete Solution & Deep Dive Guide

---

Affine Cipher in Crystal: A Complete Guide from Zero to Encryption Hero

The Affine Cipher is a classic monoalphabetic substitution cipher that uses a linear mathematical function to encrypt text. This complete guide breaks down the theory, mathematics (including the crucial modular multiplicative inverse), and provides a full, step-by-step implementation in the Crystal programming language.

---

Have you ever been fascinated by the world of secret codes and ciphers? It’s a world where simple text transforms into an unbreakable puzzle for the uninitiated, holding secrets only accessible to those with the right key. Many of us start this journey with simple ciphers, but quickly find ourselves wanting something more robust, something with a bit more mathematical elegance.

If you've moved past basic substitution ciphers and are looking for the next logical step, you've found it. The Affine Cipher introduces just enough mathematical complexity—specifically modular arithmetic—to be a fascinating challenge without being overwhelming. This guide will walk you through every concept, from the core theory to a fully functional Crystal implementation, turning you from a curious coder into a confident cipher creator.

What is the Affine Cipher?

The Affine Cipher is a type of monoalphabetic substitution cipher, meaning each letter in the alphabet is consistently mapped to another single letter. It's a significant step up from the Caesar cipher because instead of just shifting letters, it uses a linear function to perform the mapping. This makes it more resistant to simple brute-force attacks.

The "key" for an Affine Cipher consists of two integers, which we'll call a and b. The encryption is performed character by character using the following formula:

Encryption Formula: E(x) = (ax + b) mod m

• x is the numeric value of the plaintext character (e.g., a=0, b=1, ..., z=25).
• a and b are the keys.
• m is the size of the alphabet (typically 26 for English).
• mod is the modulo operator, which finds the remainder of a division.

For this system to work, there's a critical constraint on the key a: it must be coprime with the alphabet size m. This means their greatest common divisor (GCD) must be 1. We'll explore why this is so important in the next section.

---

How the Affine Cipher Works: The Core Mathematics

To truly master the Affine Cipher, you need to understand the "why" behind its mechanics. The magic lies in a specific branch of mathematics called modular arithmetic, particularly the concept of a modular multiplicative inverse.

The Key Pair: (a, b)

The strength of the cipher comes from its key. The key is a pair of integers (a, b) where:

• a is the "multiplicative" part of the key. It must be coprime with m (26). The valid values for a are {1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25}. If a were 1, the cipher would degenerate into a simple Caesar cipher.
• b is the "additive" or "shift" part of the key. It can be any integer from 0 to 25.

Why Must a be Coprime with m?

This is the most crucial rule. If a and m share a common factor other than 1, the encryption function becomes a "many-to-one" mapping. This means multiple different plaintext letters could encrypt to the same ciphertext letter. If this happens, decryption is impossible because you can't know which original letter was intended.

For example, if m=26 and you chose a=2 (which shares a factor of 2 with 26), both 'A' (0) and 'N' (13) would encrypt to the same letter (assuming b=0):

• E('A') = (2 * 0) mod 26 = 0 ('A')
• E('N') = (2 * 13) mod 26 = 26 mod 26 = 0 ('A')

You've lost information. By ensuring gcd(a, m) = 1, we guarantee that the function is a "one-to-one" mapping, and every plaintext letter has a unique ciphertext counterpart.

The Decryption Formula and the Modular Multiplicative Inverse

To reverse the process, we need to solve for x in the encryption equation. This requires some algebraic manipulation and the star of the show: the modular multiplicative inverse.

Decryption Formula: D(y) = a⁻¹(y - b) mod m

• y is the numeric value of the ciphertext character.
• a⁻¹ is the modular multiplicative inverse of a.

The term a⁻¹ is not 1/a. It's an integer such that (a * a⁻¹) mod m = 1. This inverse "undoes" the multiplication by a within the modular system. Finding this inverse is the key to decryption. For a small alphabet like m=26, we can find it with a simple search:

# Crystal code to find the modular multiplicative inverse
def modular_multiplicative_inverse(a, m)
  (1...m).find { |n| (a * n) % m == 1 }
end

# Example: Find the inverse of 5 mod 26
# We are looking for n where (5 * n) % 26 = 1
# (5 * 21) = 105
# 105 % 26 = 1 (since 105 = 4 * 26 + 1)
# So, the inverse of 5 is 21.
puts modular_multiplicative_inverse(5, 26) # => 21

With this inverse, the decryption formula successfully reverses the encryption, allowing us to recover the original message.

---

Where and When to Use This Cipher (For Learning)

Let's be clear: The Affine Cipher is not secure for modern communication. It is easily broken using frequency analysis, a technique where an attacker analyzes the frequency of letters in the ciphertext to guess the underlying plaintext. Common letters like 'E', 'T', and 'A' in English will still produce common ciphertext letters.

So, where does it fit?

• Educational Tool: It is an excellent project for learning programming and fundamental concepts in number theory and cryptography.
• Historical Context: It provides insight into the evolution of ciphers and the constant arms race between code makers and code breakers.
• Conceptual Stepping Stone: Understanding the Affine Cipher builds a solid foundation for tackling more complex, modern algorithms like RSA, which also rely heavily on modular arithmetic and multiplicative inverses.

This cipher is a perfect module in the kodikra learning path for anyone wanting to build their skills in algorithmic thinking and applied mathematics within programming.

---

Implementing the Affine Cipher in Crystal

Now, let's translate the theory into a working Crystal implementation. We'll build a module that can both encode and decode messages according to the Affine Cipher rules.

Project Setup

First, ensure you have Crystal installed. You can initialize a new project with the Crystal CLI:

$ crystal init app affine_cipher
$ cd affine_cipher

You can place the following code in the src/affine_cipher.cr file.

Encryption Logic Flow

The process of encrypting a message follows a clear, repeatable sequence for each character.

    ● Start with a Plaintext Character
    │
    ▼
  ┌───────────────────────┐
  │ Is it a letter?       │
  └───────────┬───────────┘
              │ Yes
              ▼
   ┌────────────────────┐
   │ Convert to lowercase │
   │ and get index (0-25) │
   │ e.g., 'c' ⟶ 2      │
   └──────────┬─────────┘
              │
              ▼
   ┌────────────────────┐
   │ Apply E(x)=(ax+b) mod 26 │
   └──────────┬─────────┘
              │
              ▼
   ┌────────────────────┐
   │ Convert new index    │
   │ back to a letter     │
   │ e.g., 15 ⟶ 'p'       │
   └──────────┬─────────┘
              │
              ▼
    ● Append to Ciphertext


  (If not a letter or digit, pass through unchanged)

The Complete Crystal Solution

Here is a robust, well-commented implementation. This code handles validation, encoding, and decoding while ignoring non-alphanumeric characters and grouping the output.

# src/affine_cipher.cr

module AffineCipher
  # The English alphabet as an array of characters.
  ALPHABET = ('a'..'z').to_a
  # The size of the alphabet, our modulus 'm'.
  M = ALPHABET.size

  # Encodes a given plaintext string using the Affine Cipher.
  #
  # The key `a` must be coprime to 26.
  # The output is grouped into 5-character words.
  def self.encode(plaintext : String, a : Int32, b : Int32) : String
    validate_key(a)

    processed_chars = plaintext.downcase.chars.filter_map do |char|
      if char.alphanumeric?
        transform(char, a, b)
      end
    end

    processed_chars.join.chars.each_slice(5).map(&.join).join(" ")
  end

  # Decodes a given ciphertext string using the Affine Cipher.
  #
  # The key `a` must be coprime to 26.
  def self.decode(ciphertext : String, a : Int32, b : Int32) : String
    validate_key(a)
    mmi = modular_multiplicative_inverse(a)

    ciphertext.chars.filter_map do |char|
      if char.alphanumeric?
        detransform(char, mmi, b)
      end
    end.join
  end

  # Private helper to perform the core transformation for both letters and digits.
  private def self.transform(char : Char, a : Int32, b : Int32) : Char | Nil
    if char.ascii_letter?
      x = char - 'a'
      new_index = (a * x + b) % M
      ALPHABET[new_index]
    elsif char.ascii_digit?
      char # Pass digits through unchanged
    end
  end

  # Private helper to perform the core de-transformation for decryption.
  private def self.detransform(char : Char, mmi : Int32, b : Int32) : Char | Nil
    if char.ascii_letter?
      y = char - 'a'
      # We use `(y - b + M)` to handle potential negative results gracefully in modular arithmetic.
      new_index = (mmi * (y - b + M)) % M
      ALPHABET[new_index]
    elsif char.ascii_digit?
      char # Pass digits through unchanged
    end
  end

  # Validates that the key 'a' is coprime to the alphabet size 'm'.
  # Raises an ArgumentError if the condition is not met.
  private def self.validate_key(a : Int32)
    # gcd is "Greatest Common Divisor"
    raise ArgumentError.new("a must be coprime to m") unless a.gcd(M) == 1
  end

  # Finds the modular multiplicative inverse of 'a' modulo 'm'.
  # This is a number 'n' such that (a * n) % m == 1.
  private def self.modular_multiplicative_inverse(a : Int32) : Int32
    # For a small m=26, a simple search is efficient enough.
    (1...M).find { |n| (a * n) % M == 1 }.not_nil!
  end
end

Code Walkthrough

1. Constants: We define ALPHABET and M (26) as constants for clarity and easy modification if we wanted to support a different alphabet.
2. validate_key(a): This is our safety check. Before any encoding or decoding, it uses the built-in Int32#gcd method to check if a and M are coprime. If not, it raises an ArgumentError, preventing invalid operations.
3. encode(plaintext, a, b):
   • It first calls validate_key.
   • It converts the plaintext to lowercase and processes it character by character.
   • filter_map is used to iterate: if a character is alphanumeric, it's passed to transform; otherwise, it's discarded (e.g., punctuation, spaces).
   • The resulting encrypted characters are joined together and then split into groups of 5, separated by spaces, for readability.
4. transform(char, a, b):
   • If the character is a letter, its 0-based index x is calculated (char - 'a').
   • The encryption formula (a * x + b) % M is applied.
   • The resulting index is used to look up the new character in our ALPHABET array.
   • Digits are passed through without modification.
5. decode(ciphertext, a, b):
   • It also validates the key a.
   • The first crucial step is to calculate the modular multiplicative inverse (mmi) of a.
   • It then iterates through the ciphertext, ignoring spaces, and passes each alphanumeric character to detransform.
   • The final result is a single, joined string of the decrypted characters.
6. modular_multiplicative_inverse(a): This private method implements the simple search described earlier. It iterates from 1 to 25, looking for the first number n that satisfies the condition (a * n) % M == 1. The .not_nil! at the end asserts that a value was found, which is guaranteed if our validate_key check has passed.

Decryption Logic Flow

Decryption is the mirror image of encryption, with the modular inverse as the key to unlocking the original message.

    ● Start with a Ciphertext Character
    │
    ▼
  ┌───────────────────────┐
  │ Is it a letter?       │
  └───────────┬───────────┘
              │ Yes
              ▼
   ┌────────────────────┐
   │ Convert to index (0-25) │
   │ e.g., 'p' ⟶ 15      │
   └──────────┬─────────┘
              │
              ▼
   ┌────────────────────┐
   │ Calculate MMI (a⁻¹)  │
   └──────────┬─────────┘
              │
              ▼
   ┌────────────────────────┐
   │ Apply D(y)=a⁻¹(y-b) mod 26 │
   └──────────┬─────────────┘
              │
              ▼
   ┌────────────────────┐
   │ Convert new index    │
   │ back to a letter     │
   │ e.g., 2 ⟶ 'c'        │
   └──────────┬─────────┘
              │
              ▼
    ● Append to Plaintext


  (If not a letter or digit, pass through unchanged)

---

Pros and Cons of the Affine Cipher

Like any technology, the Affine Cipher has its strengths and weaknesses, which are important to understand for context.

Pros (Advantages)

Cons (Disadvantages)

Simple to Implement: The logic is straightforward and requires only basic arithmetic operations. Introduces Key Concepts: It's an excellent vehicle for learning about modular arithmetic and multiplicative inverses. Stronger than Caesar/Atbash: With 312 possible keys (12 for 'a' * 26 for 'b'), it's much harder to brute-force than a Caesar cipher (25 keys). Parameterizable: The use of two keys (a, b) makes it more flexible than simpler substitution ciphers.

Insecure: It is highly vulnerable to frequency analysis and known-plaintext attacks. Small Key Space: While better than a Caesar cipher, 312 keys is trivially small for modern computers to brute-force. Limited to an Alphabet: The standard implementation only works on a fixed set of characters. Mathematical Constraint: The requirement for a to be coprime with m can be a point of confusion and error if not handled correctly.

---

Frequently Asked Questions (FAQ)

What happens if 'a' is not coprime with 26?

If 'a' is not coprime with 26 (i.e., their greatest common divisor is not 1), the encryption becomes irreversible. Multiple plaintext letters will map to the same ciphertext letter, and a modular multiplicative inverse for 'a' will not exist. Our implementation correctly raises an ArgumentError to prevent this.

How is the Affine Cipher different from the Caesar Cipher?

A Caesar Cipher is actually a special case of the Affine Cipher where the key a is fixed to 1. The Caesar Cipher only performs an additive shift (E(x) = (x + b) mod 26), whereas the Affine Cipher adds a multiplicative step (E(x) = (ax + b) mod 26), making it more complex.

Can the Affine Cipher be used for secure communication today?

Absolutely not. It is considered a classical, weak cipher. It can be broken in seconds with automated frequency analysis tools. It should only be used for educational purposes or as a fun puzzle.

How do you find the modular multiplicative inverse for larger numbers?

For a small modulus like 26, a simple search is fast enough. For much larger numbers, as used in modern cryptography like RSA, a more efficient algorithm is required. The standard method is the Extended Euclidean Algorithm, which can find the inverse very quickly.

What is 'm' in the Affine Cipher formula?

m is the size of the character set you are working with. For the standard English alphabet, m is 26. If you were to create an Affine Cipher for all ASCII characters, m might be 128 or 256 (though you would need to be careful about which characters are mappable).

Why are numbers and punctuation ignored in this implementation?

This is a common convention in classical ciphers to simplify the problem. The focus is on substituting alphabetic characters. In our code, digits are passed through unchanged, and punctuation is stripped out. A more advanced implementation could define a larger character set (a larger m) to include them in the encryption process.

How many possible keys are there for the English alphabet?

There are 12 possible values for a that are coprime to 26. There are 26 possible values for b (0 through 25). Therefore, the total number of unique keys is 12 * 26 = 312.

---

Conclusion

The Affine Cipher serves as a perfect bridge between trivial substitution ciphers and the complex, number-theory-heavy algorithms that power modern digital security. By implementing it in Crystal, you've not only written a functional encryption program but have also gained practical experience with crucial mathematical concepts like modular arithmetic, greatest common divisors, and the modular multiplicative inverse.

This project from the kodikra.com curriculum demonstrates how elegant mathematical principles can be transformed into powerful code. While you won't be using it to protect state secrets, the knowledge gained is a valuable asset in your journey as a developer and problem-solver.

Ready to continue your journey? Dive deeper into the world of algorithms and explore more with our complete Crystal learning path.

Disclaimer: The code and concepts in this article are based on Crystal 1.12+. Language features and syntax may evolve in future versions.

---

Published by Kodikra — Your trusted Crystal learning resource.