Home
4
Coding Tutorial

Crypto Square in Common-lisp: Complete Solution & Deep Dive Guide

a close up of a computer screen with code on it

Crypto Square in Common Lisp: A Deep Dive into Classic Ciphers

The Crypto Square cipher is a classic transposition cipher that encodes messages by arranging normalized text into a rectangular grid and reading it column by column. This guide demonstrates a step-by-step implementation in Common Lisp, covering text normalization, grid calculation, and message encryption from scratch.

Have you ever been fascinated by the world of secret codes and ciphers? From the simple Caesar cipher used by Roman generals to the complex Enigma machine of World War II, cryptography has always been a blend of logic, language, and mathematics. It’s a field that challenges you to think about information in a completely new way.

However, trying to implement these classic algorithms, especially in a powerful but syntactically unique language like Common Lisp, can feel intimidating. The sea of parentheses and the functional programming paradigm might seem like a cryptic code in itself. You might wonder where to even begin with processing strings, calculating dimensions, and restructuring data.

This article is your key. We will demystify the Crypto Square cipher and guide you through a clean, idiomatic Common Lisp implementation. You will not only solve the challenge but also gain a deeper appreciation for Lisp's elegance in handling complex data manipulation, turning a daunting task into an enlightening exercise in algorithmic thinking.

What is the Crypto Square Cipher?

The Crypto Square, also known as a square code, is a simple yet elegant form of a transposition cipher. Unlike substitution ciphers that replace letters with other letters or symbols, a transposition cipher rearranges the existing letters to obscure the original message. The core idea is to change the order of the characters, not the characters themselves.

The entire process can be broken down into three fundamental steps:

  1. Normalization: The original message, or plaintext, is cleaned up. This involves removing all spaces, punctuation, and special characters. The entire message is also converted to a single case, typically lowercase, to ensure uniformity. This creates a clean, contiguous string of characters to work with.
  2. Rectangular Grid Formation: The normalized string is then poured into an imaginary rectangle. We first calculate the smallest possible dimensions (rows and columns) for a grid that can hold all the characters. The characters fill the grid row by row.
  3. Transposition (Columnar Reading): The final secret message, or ciphertext, is formed by reading the characters from the grid column by column, from top to bottom and left to right.

For example, let's encode the message: "If man was meant to stay on the ground, god would have given us roots."

  • Normalized: "ifmanwasmeanttostayonthegroundgodwouldhavegivenusroots" (54 characters)
  • Grid Calculation: The square root of 54 is ~7.3. We round up to get 8 columns. To fit 54 characters in 8 columns, we need 7 rows (since 8 * 6 = 48 is too small, and 8 * 7 = 56 is sufficient). So, our grid is 7 rows by 8 columns.
  • Grid Formation: 
    
ifmanwas
meanttos
tayonthe
groundgo
dwouldha
vegivenu
sroots
  • Transposition: Reading down the columns gives us: "imtgdvs fearwer mayoogo anouuio ntnnlvt wttddes aohsune ssg".

This simple rearrangement makes the message unreadable at a glance, forming the basis of the cipher.

Why Common Lisp is a Superb Choice for This Algorithm

At first glance, a language born in the 1950s might seem like an odd choice for implementing algorithms. However, Common Lisp's design philosophy and powerful features make it exceptionally well-suited for tasks like text manipulation and algorithmic problem-solving, which are at the heart of the Crypto Square challenge.

  • REPL-Driven Development: Common Lisp's Read-Eval-Print Loop (REPL) is legendary. It allows for interactive development where you can build, test, and debug small functions one at a time. This is perfect for an algorithm with distinct steps like normalization, dimension calculation, and encoding. You can perfect each piece before combining them.
  • Powerful Sequence Functions: Lisp treats strings as sequences of characters, giving you access to a rich library of functions for mapping, filtering, and reducing. Functions like remove-if-not and map allow you to express complex transformations, like text normalization, in a highly declarative and concise way.
  • The LOOP Macro: While Lisp is known for its functional purity and recursion, its LOOP macro is one of the most powerful and flexible iteration constructs in any programming language. It allows you to write complex loops, including nested iterations and aggregations, in a readable, English-like syntax, which is ideal for transposing our grid.
  • Strong Typing, Dynamic Feel: Common Lisp is a strongly typed language, which prevents many common errors. However, it feels dynamic because types are checked at runtime, giving you the flexibility of languages like Python with the robustness of a compiled language.

This challenge, from the exclusive kodikra.com learning path, serves as a fantastic exercise to showcase these very features, demonstrating that Lisp's timeless principles are as relevant today as ever.

How to Implement the Crypto Square Cipher in Common Lisp

We will build our solution by creating a series of small, focused helper functions that each handle one part of the process. This approach is idiomatic in Lisp and makes the code easier to understand, test, and debug. The final solution will orchestrate these helpers to produce the encoded message.

The Complete Common Lisp Solution

Here is the full, well-commented code. We will break down each function in the following section.

;;; This package defines the functions for the Crypto Square cipher.
(defpackage :crypto-square
  (:use :cl)
  (:export :encode))

(in-package :crypto-square)

(defun normalize-text (plaintext)
  "Removes non-alphanumeric characters and converts the text to lowercase."
  (map 'string #'char-downcase
       (remove-if-not #'alphanumericp plaintext)))

(defun calculate-dimensions (text-length)
  "Calculates the optimal column and row count for the crypto square.
   Returns a list (columns rows)."
  (if (zerop text-length)
      (list 0 0)
      (let* ((c (ceiling (sqrt text-length)))
             (r (ceiling text-length c)))
        (list c r))))

(defun segment-text (normalized-text c)
  "Segments the normalized text into rows of length 'c'.
   Returns a list of strings (the rows)."
  (when (plusp c)
    (loop for i from 0 below (length normalized-text) by c
          collect (subseq normalized-text i (min (+ i c) (length normalized-text))))))

(defun transpose-and-format (segments c r)
  "Reads the segments column by column and formats the final ciphertext.
   Pads with spaces where the grid is incomplete."
  (if (or (zerop c) (zerop r))
      ""
      (let ((chunks (loop for j from 0 below c
                          collect (with-output-to-string (s)
                                    (loop for i from 0 below r
                                          for segment = (nth i segments)
                                          do (if (< j (length segment))
                                                 (write-char (char segment j) s)
                                                 (write-char #\Space s)))))))
        (format nil "~{~a~^ ~}" chunks))))

(defun encode (plaintext)
  "Main function to encode a plaintext message using the Crypto Square cipher."
  (let* ((normalized (normalize-text plaintext))
         (len (length normalized))
         (dimensions (calculate-dimensions len))
         (c (first dimensions))
         (r (second dimensions))
         (segments (segment-text normalized c)))
    (transpose-and-format segments c r)))

Logic Flow Diagram

This diagram illustrates the high-level data flow from the initial plaintext to the final ciphertext.

    ● Start (Plaintext)
    │ "Hello, world! 123"
    ▼
  ┌───────────────────┐
  │ normalize-text()  │
  └─────────┬─────────┘
            │
            ▼
    ● Normalized Text
    │ "helloworld123" (Length: 13)
    ▼
  ┌──────────────────────┐
  │ calculate-dimensions() │
  └─────────┬────────────┘
            │ c = 4, r = 4
            ▼
    ● Grid Segments
    │ ("hell", "owor", "ld12", "3")
    ▼
  ┌────────────────────────┐
  │ transpose-and-format() │
  └─────────┬──────────────┘
            │
            ▼
    ● Ciphertext
      "hold e1w2 lrl3 o"

Detailed Code Walkthrough

Let's dissect the code function by function to understand the role each one plays in the grand scheme.

Step 1: normalize-text

This is our first data-cleaning step. The goal is to create a uniform string of characters that's ready for encryption.

(defun normalize-text (plaintext)
  "Removes non-alphanumeric characters and converts the text to lowercase."
  (map 'string #'char-downcase
       (remove-if-not #'alphanumericp plaintext)))
  • (remove-if-not #'alphanumericp plaintext): This is the core filtering logic. remove-if-not iterates through the plaintext string. The function #'alphanumericp is a predicate that returns true for letters and numbers. So, this expression effectively strips out anything that isn't a letter or a digit, like spaces, commas, and exclamation marks.
  • (map 'string #'char-downcase ...): The result of the removal is then passed to map. The map function applies a function (#'char-downcase) to every element of a sequence. By specifying 'string as the first argument, we tell map to collect the results into a new string. This efficiently converts the entire filtered string to lowercase.

Step 2: calculate-dimensions

Once we have the length of our normalized text, we need to figure out the size of our rectangle.

(defun calculate-dimensions (text-length)
  "Calculates the optimal column and row count for the crypto square."
  (if (zerop text-length)
      (list 0 0)
      (let* ((c (ceiling (sqrt text-length)))
             (r (ceiling text-length c)))
        (list c r))))
  • (if (zerop text-length) (list 0 0) ...): A simple edge case check. If the input string was empty, we return dimensions of 0x0.
  • (let* ((c (ceiling (sqrt text-length)))) ...): This is the heart of the calculation.
    • (sqrt text-length): We take the square root of the length to find the side of a perfect square.
    • (ceiling ...): Since the length is rarely a perfect square, we use ceiling to round up to the next whole number. This gives us our column count c. Per the algorithm's rules, columns >= rows and columns - rows <= 1. This calculation ensures that.
    • (r (ceiling text-length c)): We then calculate the number of rows r needed to accommodate all characters, given c columns. Again, we use ceiling.
  • (list c r): The function returns the calculated dimensions as a list, e.g., (4 4).

Step 3: segment-text

This function takes the long, normalized string and chops it up into rows for our grid.

(defun segment-text (normalized-text c)
  "Segments the normalized text into rows of length 'c'."
  (when (plusp c)
    (loop for i from 0 below (length normalized-text) by c
          collect (subseq normalized-text i (min (+ i c) (length normalized-text))))))
  • (when (plusp c) ...): Another guard clause. This logic only runs if the column count is positive.
  • (loop for i from 0 below (length normalized-text) by c ...): Here we use the powerful loop macro.
    • for i from 0 ... by c: This sets up a loop where the variable i will take on values 0, c, 2c, and so on, acting as the starting index for each of our segments.
    • collect (subseq ...): For each value of i, we extract a substring and collect it into a list that the loop will return.
    • (subseq normalized-text i (min (+ i c) (length normalized-text))): subseq extracts a portion of a sequence. The end index is carefully calculated using min to prevent reading past the end of the string, which is crucial for the last, potentially shorter, row.

Step 4: transpose-and-format

This is the final and most complex step: reading the grid column-wise and formatting the output.

ASCII Art: Columnar Transposition Logic

  Segments (Rows)
  ┌──────┐ ┌──────┐ ┌──────┐ ┌──────┐
  │ h e l l │ │ o w o r │ │ l d 1 2 │ │ 3      │
  └──────┘ └──────┘ └──────┘ └──────┘
      │        │        │        │
      ├─(j=0)──┼─(j=1)──┼─(j=2)──┼─(j=3)─┐
      │        │        │        │       │
      ▼        ▼        ▼        ▼       ▼
┌───────────┐ ┌───────────┐ ┌───────────┐ ┌───────────┐
│ Read Col 0│ │ Read Col 1│ │ Read Col 2│ │ Read Col 3│
│ "hold"    │ │ "e1w2"    │ │ "lrl3"    │ │ "o"       │
└─────┬─────┘ └─────┬─────┘ └─────┬─────┘ └─────┬─────┘
      │             │             │             │
      └─────────────┼─────────────┼─────────────┘
                    │             │
                    ▼             ▼
          ┌───────────────────────────┐
          │ Join Chunks with Spaces   │
          └────────────┬──────────────┘
                       ▼
                 ● Final Ciphertext

(defun transpose-and-format (segments c r)
  "Reads the segments column by column and formats the final ciphertext."
  (if (or (zerop c) (zerop r))
      ""
      (let ((chunks (loop for j from 0 below c
                          collect (with-output-to-string (s)
                                    (loop for i from 0 below r
                                          for segment = (nth i segments)
                                          do (if (< j (length segment))
                                                 (write-char (char segment j) s)
                                                 (write-char #\Space s)))))))
        (format nil "~{~a~^ ~}" chunks))))
  • Outer Loop: (loop for j from 0 below c ...) iterates through the column indices. For each column j, we will build a new string.
  • (with-output-to-string (s) ...): This is a handy macro that creates a temporary string stream s. Anything written to s inside this block will be collected and returned as a single string. This is how we build each transposed chunk.
  • Inner Loop: (loop for i from 0 below r ...) iterates through the row indices.
    • for segment = (nth i segments): For each row index i, we fetch the corresponding string segment.
    • (if (< j (length segment)) ...): This is the crucial padding logic. We check if the current column index j is valid for the current segment.
      • If it is, we grab the character with (char segment j) and write it to our stream s.
      • If it's not (meaning we're on the last row and it's shorter than the others), we write a space character #\Space as padding.
  • (format nil "~{~a~^ ~}" chunks): After the outer loop has collected all the transposed chunks (e.g., ("hold" "e1w2" "lrl3" "o")), we use the format function to join them. The special directive "~{~a~^ ~}" is a Lisp idiom that means "iterate over the list, printing each element (~a), and insert a space (~^ ~) between them."

The Main Function: encode

Finally, the encode function acts as the conductor, calling each helper in the correct order.

(defun encode (plaintext)
  "Main function to encode a plaintext message using the Crypto Square cipher."
  (let* ((normalized (normalize-text plaintext))
         (len (length normalized))
         (dimensions (calculate-dimensions len))
         (c (first dimensions))
         (r (second dimensions))
         (segments (segment-text normalized c)))
    (transpose-and-format segments c r)))

The let* form is used here to define a sequence of local variables where each can use the value of the one defined before it. This creates a clean, readable pipeline of data transformations, perfectly mirroring the steps of the algorithm.

Running the Code

You can run this code from an SBCL (Steel Bank Common Lisp) REPL. First, save the code as crypto-square.lisp.


$ sbcl
* (load "crypto-square.lisp")
; T
* (crypto-square:encode "If man was meant to stay on the ground, god would have given us roots.")
; "imtgdvs fearwer mayoogo anouuio ntnnlvt wttddes aohsune ssg"
* (crypto-square:encode "Hello, world!")
; "h o e l r l d"
* (crypto-square:encode "This is a test.")
; "tsit she a"

Pros and Cons of the Crypto Square Cipher

While an excellent programming exercise, it's important to understand the cipher's place in the world of cryptography. It is a classical cipher and is not secure for modern applications.

Pros Cons
Simple to Implement: The logic is straightforward and doesn't require complex mathematics. Extremely Insecure: The cipher is highly vulnerable to frequency analysis and other cryptanalytic attacks. An attacker can easily guess the number of columns and reverse the process.
No Key Required: The algorithm itself is the method of encryption and decryption, requiring no shared secret key. Preserves Letter Frequencies: The original letters are only rearranged, not changed. The frequency of 'e', 't', 'a', etc., remains the same as in English, providing a huge clue to attackers.
Good Educational Tool: It's a perfect problem for learning about string manipulation, 2D data structures, and algorithmic thinking. Deterministic: The same plaintext will always produce the exact same ciphertext, which is a significant weakness in cryptographic systems.

Frequently Asked Questions (FAQ)

1. Is the Crypto Square cipher secure enough for modern use?

Absolutely not. It is a classical cipher that can be broken in minutes with modern computing power and basic cryptanalysis techniques, such as frequency analysis. It should only be used for educational purposes or puzzles.

2. What is the difference between a substitution and a transposition cipher?

A substitution cipher replaces plaintext characters with different characters (e.g., A becomes D, B becomes E). The Caesar cipher is a famous example. A transposition cipher, like Crypto Square, keeps the original characters but rearranges their order. It shuffles the letters instead of replacing them.

3. How does the padding work in your Common Lisp solution?

In our implementation, padding is handled during the final transposition step (in transpose-and-format). When reading the columns, if a row is too short to have a character at the current column index, we explicitly insert a space. This ensures all the final chunks (the new columns) have the same length, even if the last row of the grid was incomplete.

4. What does the #' syntax mean in Common Lisp?

The #' syntax is shorthand for the (function ...) special operator. It tells the Lisp compiler that the following symbol refers to a function, not a variable. For example, #'alphanumericp gets the function object associated with the name alphanumericp, so it can be passed as an argument to another function like remove-if-not.

5. Could this algorithm be implemented recursively?

Yes, several parts could be implemented recursively, which is a common pattern in functional programming. For instance, the segment-text function could be rewritten to take the first c characters of the string and then recursively call itself on the rest of the string. However, for this particular problem, the iterative loop macro is often considered more idiomatic and can be more efficient in Common Lisp.

6. Why use let* instead of let in the encode function?

The let form binds all variables in parallel, meaning you cannot use one variable's value when defining a subsequent one in the same let block. let* binds variables sequentially, allowing each new variable to reference the ones defined above it. We use let* because the calculation for len depends on normalized, dimensions depends on len, and so on, creating a clear dependency chain.

Conclusion: From Ancient Ciphers to Modern Code

Successfully implementing the Crypto Square cipher in Common Lisp is more than just solving a puzzle; it's a journey through core computer science principles. We've tackled string manipulation, algorithmic logic, and data structure transformation, all while leveraging the unique and powerful features of the Lisp programming language. You've seen firsthand how functions like map and remove-if-not enable expressive data cleaning, and how the loop macro can construct complex, multi-dimensional transformations with surprising clarity.

While the cipher itself belongs to a bygone era of cryptography, the skills you've honed are timeless. The ability to break down a problem into smaller, manageable functions is a cornerstone of robust software engineering. This challenge from the kodikra.com curriculum is a testament to how classic problems can serve as the best teachers for modern programming paradigms.

Technology Disclaimer: The code in this article was developed and tested using Steel Bank Common Lisp (SBCL) version 2.4.x. As Common Lisp is an ANSI standard, this code should be highly portable across different implementations like CLISP or CCL with minimal to no changes.

Ready for your next challenge? Explore the full Common Lisp Module 4 on kodikra to sharpen your skills further. Or, if you want a broader overview of the language, check out our complete Common Lisp programming guide.

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

Post a Comment