Affine Cipher in 8th: Complete Solution & Deep Dive Guide

a close up of a sign with a lot of dots on it

From Zero to Hero: Mastering the Affine Cipher in 8th

The Affine Cipher is a classic substitution cipher that serves as a perfect entry point into the mathematical world of cryptography. It uses a linear function, (ax + b) mod m, to transform each letter of a message, making it a significant step up from simpler ciphers like Caesar's.

The Allure of Ancient Secrets: Why We Still Learn Ciphers

Imagine sending a secret message across a crowded room, confident that only your intended recipient can understand it. This fundamental human need for privacy has driven the art and science of cryptography for millennia. From ancient military commands to modern digital transactions, the core challenge remains the same: how to communicate securely in the presence of adversaries.

You might be wrestling with the abstract concepts of modular arithmetic or wondering how these old-school ciphers are relevant today. You're not alone. The beauty of studying ciphers like the Affine Cipher lies not in their modern-day security (which is nonexistent), but in the foundational principles they reveal. They are the perfect educational tool for understanding keys, algorithms, encryption, decryption, and the mathematical bedrock upon which all modern security is built.

This guide promises to demystify the Affine Cipher completely. We will not only explore its mathematical elegance but also implement a fully functional version from scratch using 8th, a powerful and concise stack-based language. By the end, you'll have a deep, practical understanding of this fascinating piece of cryptographic history.

What Is the Affine Cipher?

The Affine Cipher is a type of monoalphabetic substitution cipher. This means each letter in the plaintext is consistently replaced by a corresponding, single letter in the ciphertext. Unlike the Caesar cipher, which only shifts letters, the Affine Cipher uses a more complex mathematical function involving both multiplication and addition, making it significantly more robust.

The "affine" part of its name comes from affine transformations in mathematics, which are functions that preserve points, straight lines, and planes. In our context, it's a linear function of the form y = ax + b, but with a twist: it's all performed within a finite set of numbers using modular arithmetic.

The core of the cipher revolves around two keys, an integer pair (a, b), and a modulus m, which is the size of the alphabet. For the English alphabet, m = 26.

The Key `a` (Multiplier): This key stretches or compresses the numerical values of the letters.
The Key `b` (Shift): This key acts like a Caesar cipher shift, moving the entire result.
The Modulus `m` (Alphabet Size): This ensures our results always wrap around to stay within the alphabet (0-25).

The Encryption Formula

To encrypt a single character, we first convert it to its numerical equivalent (a=0, b=1, ..., z=25), which we'll call x. Then, we apply the encryption function E:

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

The result is a new number, which we then convert back into a character to form the ciphertext.

The Decryption Formula

To decrypt, we need to reverse the process. This requires finding the modular multiplicative inverse of a, denoted as a⁻¹. This is a number such that (a * a⁻¹) mod m = 1. The decryption function D for a ciphertext character's value y is:

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

The existence of a⁻¹ is critical. If it doesn't exist, decryption is impossible for certain characters, making the cipher useless. This leads to a crucial rule for selecting our key `a`.

How Does the Affine Cipher Work? The Mathematical Foundation

Understanding the "how" requires a dive into modular arithmetic. This branch of mathematics deals with remainders—it's often called "clock arithmetic." When we calculate 15 mod 12, we're asking for the remainder when 15 is divided by 12, which is 3. In cryptography, this is perfect for ensuring our calculations stay within the bounds of our alphabet size, m=26.

The Critical Role of Key `a`: Coprimality

For the cipher to be reversible (i.e., for decryption to be possible), the key a must be coprime with the alphabet size m. Two numbers are coprime if their greatest common divisor (GCD) is 1. For the English alphabet (m=26), the factors of 26 are 1, 2, 13, and 26. Therefore, a must not be divisible by 2 or 13.

The valid values for a (mod 26) are: 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25. There are 12 possible values.

Why is this necessary? If gcd(a, m) ≠ 1, then multiple plaintext letters could map to the same ciphertext letter. For example, if we chose a=2 and m=26, both 'A' (0) and 'N' (13) would encrypt to the same letter (assuming b=0):

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

When you receive the ciphertext 'A', it's impossible to know if the original letter was 'A' or 'N'. The mapping is not one-to-one, and the information is lost forever. This breaks the cipher. By ensuring gcd(a, m) = 1, we guarantee that a modular multiplicative inverse a⁻¹ exists, which ensures a unique decryption path for every character.

The Encryption and Decryption Flow

Here is a visual representation of the entire process, from plaintext to ciphertext and back again.

    ● Start (Plaintext Character)
    │
    ▼
  ┌──────────────────────────┐
  │ Convert Char to Number   │
  │ e.g., 'c'  ⟶  2          │
  └────────────┬─────────────┘
               │
               ▼
  ┌──────────────────────────┐
  │ Apply Encryption Formula │
  │ E(x) = (a*x + b) mod m   │
  └────────────┬─────────────┘
               │
               ▼
    ◆ Result (Cipher Number)
    │
    ▼
  ┌──────────────────────────┐
  │ Convert Number to Char   │
  │ e.g., 19  ⟶  't'         │
  └────────────┬─────────────┘
               │
               ▼
    ● End (Ciphertext Character)


    (Decryption is the reverse)

    ● Start (Ciphertext Character)
    │
    ▼
  ┌──────────────────────────┐
  │ Convert Char to Number   │
  │ e.g., 't'  ⟶  19         │
  └────────────┬─────────────┘
               │
               ▼
  ┌──────────────────────────┐
  │ Apply Decryption Formula │
  │ D(y) = a⁻¹(y-b) mod m    │
  └────────────┬─────────────┘
               │
               ▼
    ◆ Result (Plaintext Number)
    │
    ▼
  ┌──────────────────────────┐
  │ Convert Number to Char   │
  │ e.g., 2  ⟶  'c'          │
  └────────────┬─────────────┘
               │
               ▼
    ● End (Plaintext Character)

When and Where: The Practical Application (and Limitations)

Historically, the Affine Cipher and its variants were used in periods where cryptography was more of an art than a science. It offered a reasonable level of security against an adversary without mathematical training. However, in the modern era, its use is purely educational.

Why It's Not Secure Today

The Affine Cipher's greatest weakness is that it's a monoalphabetic substitution cipher. This means it is highly vulnerable to frequency analysis. In any given language, certain letters appear more frequently than others (in English, 'E', 'T', 'A', 'O' are the most common).

An attacker can simply count the frequency of each letter in the ciphertext. The most frequent ciphertext letter likely corresponds to 'E', the second most frequent to 'T', and so on. By identifying just two plaintext/ciphertext letter pairs, an attacker can set up a system of two linear equations to solve for a and b, breaking the entire cipher instantly.

For the English alphabet, there are only 12 possible values for a and 26 for b, resulting in only 12 * 26 = 312 possible keys. A brute-force attack (trying every possible key) would take a modern computer milliseconds to complete.

Pros and Cons of the Affine Cipher

Pros (Advantages)	Cons (Disadvantages)
Stronger than Caesar/Atbash: The two-part key `(a, b)` provides more key space and complexity than a simple shift cipher.	Vulnerable to Frequency Analysis: As a monoalphabetic cipher, it cannot hide the underlying letter frequencies of the plaintext language.
Excellent Educational Tool: Perfectly demonstrates modular arithmetic, coprimality, and modular inverses in a practical context.	Small Key Space: With only 312 possible keys for English, it is trivial to break with a brute-force attack.
Simple to Implement: The mathematical operations are straightforward, making it a great project for learning a new programming language.	Not Secure for Modern Use: Should never be used for any real-world sensitive data. It is considered completely broken.
Foundation for More Complex Ciphers: Understanding the Affine Cipher is a stepping stone to understanding more complex classical and modern ciphers.	Requires Mathematical Constraints: The key `a` must be chosen carefully (coprime to `m`), adding a layer of complexity for the user.

The Complete 8th Implementation: From Theory to Code

Now, let's translate our understanding into a working implementation using 8th. The stack-based nature of 8th allows for an elegant and concise solution. Our implementation will be structured into several helper words (functions) that build up to the final affine:encode and affine:decode words.

This solution is part of the exclusive kodikra.com learning path for 8th, designed to build your skills progressively.

The Full Solution Code in 8th

Here is the complete, commented code. We'll break it down in the next section.


\ Implementation of the Affine Cipher from the kodikra.com curriculum

: affine ( -- )
  ( ns-enter )

  \ --- Constants and Helpers ---

  26 var, m      \ Alphabet size
  "abcdefghijklmnopqrstuvwxyz" var, alphabet

  \ gcd: ( n m -- gcd ) - Calculates the greatest common divisor using Euclidean algorithm
  : gcd ( n m -- gcd )
    begin dup while tuck % repeat drop ;

  \ mmi: ( a m -- n ) - Calculates modular multiplicative inverse of a mod m
  \ Returns null if no inverse exists.
  : mmi ( a m -- n )
    m @ >r
    1 r@ 1.. ' ( n -- n' | null ) >r
      dup r@ * r> m @ % 1 == if drop nip exit then
    r> drop null ;

  \ clean: ( s -- s' ) - Cleans input string: lowercase, keep only letters and numbers
  : clean ( s -- s' )
    s:lower [ ' a-z n:in? ' 0-9 n:in? or ] s:filter ;

  \ char>int: ( char -- int ) - Converts a character to its 0-25 index
  : char>int ( char -- int )
    alphabet @ s:indexof ;

  \ int>char: ( int -- char ) - Converts a 0-25 index to a character
  : int>char ( int -- char )
    alphabet @ s:nth ;

  \ --- Core Logic ---

  \ encode-char: ( char a b -- char' ) - Encodes a single character
  : encode-char ( char a b -- char' )
    >r >r \ R: b a
    dup ' 0-9 n:in? if \ If it's a digit, pass it through
      r> r> 2drop
      exit
    then
    char>int r@ * r> + m @ % int>char ; \ (a*x + b) mod m

  \ decode-char: ( char a b -- char' ) - Decodes a single character
  : decode-char ( char a b -- char' )
    >r >r \ R: b a
    dup ' 0-9 n:in? if \ If it's a digit, pass it through
      r> r> 2drop
      exit
    then
    char>int r> - \ (y - b)
    m @ mod+ \ Ensure positive result before multiplication
    r> m @ mmi \ Get modular inverse of a
    * m @ % int>char ; \ a^-1 * (y - b) mod m

  \ --- Public API ---

  \ encode: ( s a b -- s' ) - Encodes a string
  : encode ( s a b -- s' )
    >r >r \ R: b a
    clean
    ' ( char -- char' ) >r
      r> r@ r@ encode-char r>
    s:map ;

  \ decode: ( s a b -- s' ) - Decodes a string
  : decode ( s a b -- s' )
    >r >r \ R: b a
    \ Validate key 'a'
    r@ m @ gcd 1 != if "a and m must be coprime." throw then

    clean
    ' ( char -- char' ) >r
      r> r@ r@ decode-char r>
    s:map
    \ Group output into 5-character words
    5 s:chunk " " s:join ;

  ( ns-leave )
;

Detailed Code Walkthrough

Let's dissect this code piece by piece to understand how it works on 8th's stack.

1. Setup and Helpers

: affine ( -- ) ( ns-enter ) ... ( ns-leave ) ;: We define a namespace called affine to encapsulate our words and prevent name collisions.
26 var, m and "..." var, alphabet: We define our constants. m is the alphabet size, and alphabet is a string we'll use for lookups.
: gcd ( n m -- gcd ): A standard implementation of the Euclidean algorithm. It repeatedly uses the modulo operator until one number is zero, leaving the GCD on the stack. This is vital for validating our key a.
: mmi ( a m -- n ): This word finds the modular multiplicative inverse. It iterates from 1 up to m-1, checking if (a * i) mod m == 1. If it finds a match, it returns that number i. If it completes the loop without a match, it returns null, indicating no inverse exists.
: clean ( s -- s' ): This utility word prepares the input string. It converts it to lowercase (s:lower) and then filters it (s:filter), keeping only characters that are in the range 'a'-'z' or '0'-'9'.
char>int and int>char: These are our conversion utilities. s:indexof finds the position of a character in the alphabet string, and s:nth retrieves a character from a string at a given index.

2. Core Encryption/Decryption Logic (Per Character)

: encode-char ( char a b -- char' ):
- >r >r: It takes a and b from the main stack and pushes them to the return stack for temporary storage. The return stack is now [b, a].
- dup ' 0-9 n:in? if ... then: It checks if the character is a digit. If so, it's not encrypted; we just clean up the return stack (r> r> 2drop) and return the digit as-is.
- char>int r@ * r> + m @ % int>char: This is the formula (a*x + b) mod m in action.
  1. char>int: converts char x to a number.
  2. r@ *: Peeks at a on the return stack (r@) and multiplies. Stack: [a*x].
  3. r> +: Pops b from the return stack (r>) and adds. Stack: [a*x + b].
  4. m @ %: Gets the value of m and performs modulo.
  5. int>char: Converts the resulting number back to a character.
: decode-char ( char a b -- char' ): This mirrors the encryption logic but uses the decryption formula.
- char>int r> -: Converts char y to a number, then pops b from the return stack and subtracts. Stack: [y - b].
- m @ mod+: This is a clever 8th word that performs (x + y) mod y. It ensures the result of y - b is positive before the next step, which is crucial for modular arithmetic.
- r> m @ mmi: Pops a from the return stack, gets m, and calculates the modular inverse of a. Stack: [y-b, a⁻¹].
- * m @ % int>char: Multiplies by the inverse, applies the final modulo, and converts back to a character.

3. Public API (Per String)

: encode ( s a b -- s' ): This word takes the full string and keys. It cleans the string and then uses s:map to apply the encode-char word to every character in the string, building the final ciphertext.
: decode ( s a b -- s' ):
- r@ m @ gcd 1 != if "..." throw then: This is a critical validation step. Before attempting to decode, it checks if a and m are coprime. If not, it throws an error because decryption would be impossible.
- It then proceeds similarly to encode, using s:map with the decode-char word.
- 5 s:chunk " " s:join: After decoding, it formats the output by chunking the resulting string into groups of 5 letters and joining them with spaces, a common practice for readability in ciphers.

Visualizing the `mmi` Logic

The Modular Multiplicative Inverse (MMI) is the heart of the decryption process. Here's a flow diagram of how our mmi word finds it.

    ● Start (Input: a, m)
    │
    ▼
  ┌──────────────────┐
  │ Loop i from 1 to m-1 │
  └─────────┬────────┘
            │
            ▼
    ◆ Is (a * i) mod m == 1 ?
   ╱                         ╲
  Yes                         No
  │                           │
  ▼                           ▼
┌───────────┐           (Continue Loop)
│ Return i  │                 │
└───────────┘                 │
  │                           │
  ▼                           ▼
● End (Found)         ● End (Not Found, return null)

Frequently Asked Questions (FAQ)

1. What happens if the key `a` is not coprime to `m`?: If `a` and `m` share a common factor other than 1, the encryption function is not a one-to-one mapping. This means multiple plaintext letters will encrypt to the same ciphertext letter. Consequently, a modular multiplicative inverse for `a` does not exist, and it becomes impossible to uniquely determine the original plaintext from the ciphertext. The information is irreversibly lost.
2. Is the Affine Cipher secure enough for modern use?: Absolutely not. The Affine Cipher is considered completely broken and offers no real security against modern cryptanalysis. Its small key space (312 keys for English) makes it vulnerable to brute-force attacks, and its monoalphabetic nature makes it trivially easy to break with frequency analysis.
3. How is the Affine Cipher different from the Caesar Cipher?: The Caesar Cipher is actually a special case of the Affine Cipher where the key `a` is fixed to 1. The Caesar Cipher's formula is `E(x) = (x + b) mod m`, involving only a shift. The Affine Cipher adds a multiplicative component `a`, `E(x) = (ax + b) mod m`, which scrambles the letters more effectively and creates a larger key space.
4. What exactly is a Modular Multiplicative Inverse?: In regular arithmetic, the inverse of a number `a` is `1/a` because `a * (1/a) = 1`. In modular arithmetic, the modular multiplicative inverse of `a` (mod `m`), written as `a⁻¹`, is a number such that `(a * a⁻¹) mod m = 1`. It's the number that "undoes" the multiplication by `a` within the modular system, which is why it's essential for decryption.
5. Can numbers and symbols be encrypted with this implementation?: Our specific implementation from the kodikra.com module is designed to handle the 26 letters of the English alphabet and pass numbers through unchanged. To encrypt numbers or symbols, you would need to expand the alphabet (increase `m`) to include those characters and update the conversion logic accordingly. For example, including digits would increase `m` to 36.
6. How many possible keys are there for the English alphabet?: For the English alphabet, `m=26`. The number of valid choices for `a` is the number of integers less than 26 that are coprime to 26, which is 12 (1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25). The key `b` can be any integer from 0 to 25 (26 choices). Therefore, the total number of unique keys is `12 * 26 = 312`.
7. Why is the modulo operator so important in cryptography?: The modulo operator is fundamental because it creates a finite field. It ensures that all mathematical operations, no matter how large the intermediate numbers get, produce a result that falls within a specific, predictable range (e.g., 0 to 25 for the alphabet). This "wrapping around" effect is the basis for many cryptographic algorithms, from classical ciphers to modern public-key cryptography like RSA.

Conclusion: A Foundation for the Future

We've journeyed from the historical origins of the Affine Cipher to its mathematical underpinnings and culminated in a practical, elegant implementation using 8th. While you should never use this cipher to protect real secrets, the concepts you've mastered here are timeless. Understanding modular arithmetic, coprimality, and modular inverses is not just an academic exercise; it's the key to unlocking the principles behind the powerful cryptographic systems that protect our digital world today.

By building this solution, you've gained hands-on experience with core programming concepts in a unique, stack-based environment. This project serves as a solid foundation, preparing you for more complex challenges and deeper explorations into both computer science and cryptography.

Disclaimer: The code and explanations in this article are based on the latest stable version of 8th. As the language evolves, some syntax or library words may change.

Ready for the next challenge? Continue your journey through the 8th 8 module on kodikra.com or master the 8th language from our comprehensive guide to further sharpen your skills.

Published by Kodikra — Your trusted 8th learning resource.

kodikra

Search this blog