Skip to content

Affine Cipher

Encode and decode text with the affine cipher, which maps letter number i to (a * i + b) mod 26.

Adapted from Exercism’s problem specification (MIT). Listed under Encoding & Ciphers.

// FILE: affine_cipher.nomi
//# The affine cipher: letter number `i` becomes letter `(a * i + b) mod 26`.
//# Digits pass through unchanged, and everything else is dropped.

once alphabet     = Iter.to_vector('a'..='z')
once letter_count = PositiveInt.try_from(Vector.length(alphabet))!

/// Each lowercase letter's number, from 0 for `a`.
once letter_numbers =
    Iter.zip(alphabet, 0..letter_count)
    |> Iter.to_map()

/// An encryption key. `a` must be coprime with 26, or no key decrypts it.
pub struct Key
    a: Int
    b: Int
end

/// Why a phrase cannot be encrypted or decrypted.
pub enum Error
    NotCoprime
end

/// The ciphertext of `phrase` under `key`, in lowercase groups of five.
pub fn encode(phrase: String, key: Key) -> Result<String, Error>
    _ = inverse(key.a)?

    phrase
    |> translate(fn i -> key.a * i + key.b)
    |> Iter.chunks(5)
    |> Iter.map(String.join)
    |> String.join(" ")
    |> Ok()
end

/// The plaintext of `phrase` under `key`, with no spaces.
pub fn decode(phrase: String, key: Key) -> Result<String, Error>
    a_inverse = inverse(key.a)?

    phrase
    |> translate(fn y -> a_inverse * (y - key.b))
    |> String.join()
    |> Ok()
end

/// The `x` with `a * x` one more than a multiple of 26, which exists only
/// when `a` and 26 are coprime.
fn inverse(a: Int) -> Result<Int, Error>
    0..letter_count
    |> Iter.find(fn x -> Int.modulo(a * x, letter_count) == 1)
    |> Maybe.to_result(.NotCoprime)
end

/// Each letter and digit of `text`, a letter moved to the letter `step`
/// gives for its number, and a digit kept.
fn translate(text: String, step: (Int) -> Int) -> List<String>
    text
    |> String.lowercase()
    |> String.to_codepoints()
    |> Iter.flat_map(&shift(&1, step))
    |> Iter.map(Codepoint.to_string)
    |> Iter.to_list()
end

fn shift(cp: Codepoint, step: (Int) -> Int) -> Maybe<Codepoint>
    if Codepoint.is_digit(cp) then return Some(cp)

    Map.get(letter_numbers, cp)
    |> Maybe.map(fn i -> Vector.get(alphabet, Int.modulo(step(i), letter_count))!)
end

// FILE: affine_cipher_test.nomi
import
    affine_cipher
    affine_cipher.Key
end

group "encode"
    test "encodes"
        [
            ("encode yes", "yes", Key{a: 5, b: 7}, "xbt"),
            ("encode no", "no", {a: 15, b: 18}, "fu"),
            ("encode OMG", "OMG", {a: 21, b: 3}, "lvz"),
            ("encode O M G", "O M G", {a: 25, b: 47}, "hjp"),
            ("encode mindblowingly", "mindblowingly", {a: 11, b: 15}, "rzcwa gnxzc dgt"),
            ("encode numbers", "Testing,1 2 3, testing.", {a: 3, b: 4}, "jqgjc rw123 jqgjc rw"),
            ("encode deep thought", "Truth is fiction.", {a: 5, b: 17}, "iynia fdqfb ifje"),
            (
                "encode all the letters",
                "The quick brown fox jumps over the lazy dog.",
                {a: 17, b: 33},
                "swxtj npvyk lruol iejdc blaxk swxmh qzglf",
            ),
        ]
        |> subtests (description, phrase, key, expected), description
            assert affine_cipher.encode(phrase, key) == Ok(expected)
        end
    end

    test "encode with a not coprime to m"
        assert affine_cipher.encode("This is a test.", {a: 6, b: 17}) == Err(.NotCoprime)
    end
end

group "decode"
    test "decodes"
        [
            ("decode exercism", "tytgn fjr", Key{a: 3, b: 7}, "exercism"),
            (
                "decode a sentence",
                "qdwju nqcro muwhn odqun oppmd aunwd o",
                {a: 19, b: 16},
                "anobstacleisoftenasteppingstone",
            ),
            ("decode numbers", "odpoz ub123 odpoz ub", {a: 25, b: 7}, "testing123testing"),
            (
                "decode all the letters",
                "swxtj npvyk lruol iejdc blaxk swxmh qzglf",
                {a: 17, b: 33},
                "thequickbrownfoxjumpsoverthelazydog",
            ),
            (
                "decode with no spaces in input",
                "swxtjnpvyklruoliejdcblaxkswxmhqzglf",
                {a: 17, b: 33},
                "thequickbrownfoxjumpsoverthelazydog",
            ),
            (
                "decode with too many spaces",
                "vszzm    cly   yd cg    qdp",
                {a: 15, b: 16},
                "jollygreengiant",
            ),
        ]
        |> subtests (description, phrase, key, expected), description
            assert affine_cipher.decode(phrase, key) == Ok(expected)
        end
    end

    test "decode with a not coprime to m"
        assert affine_cipher.decode("Test", {a: 13, b: 5}) == Err(.NotCoprime)
    end
end
  • The key is a pub struct Key { a, b }, and the one error, an a that shares a factor with 26, is Error.NotCoprime.
  • The modular inverse is found by search, Iter.find over 0..26 for the x with a * x mod 26 == 1. The search fails exactly when a is not coprime with 26, so one function both checks the key and gives the inverse; the extended Euclidean algorithm is not worth it for 26 candidates.
  • encode checks the key with _ = inverse(key.a)? before it starts, since it does not need the inverse.
  • translate takes the step as a function, fn i -> key.a * i + key.b or fn y -> a_inverse * (y - key.b), so encoding and decoding share it. Int.modulo brings a negative result back into 0..26, where % would leave it negative.
  • Letters go to numbers through a map, a once that pipes Iter.zip(alphabet, 0..letter_count) into Iter.to_map(), written stacked to start from the pairs, and back with Vector.get(...)!, which cannot miss because the index is reduced mod 26.
  • Each table names Key in its first row only (Key{a: 5, b: 7}); the rows after it write {a: 15, b: 18}, which the first row makes a Key, so the table needs no annotation.