Skip to content

Simple Cipher

Encode and decode text with a Vigenère cipher, moving each letter along the alphabet by the matching letter of a repeating key, and make a random key when none is given.

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

// FILE: simple_cipher.nomi
//# The Vigenère cipher over lowercase letters: each letter of the text moves
//# along the alphabet by the number of the key's letter at its position, `a`
//# moving it by 0, and the key repeats as often as the text needs.

import std::random.{Generator, Seed}

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

/// How long a random key is.
once random_key_length: NonNegativeInt = 100

/// A cipher with its key, a non-empty string of lowercase letters.
pub opaque struct Cipher
    key: String
end

impl Cipher
    /// The cipher with `key`, a non-empty string of lowercase letters.
    pub fn new(key: String) -> Cipher
        {key:}
    end

    /// A cipher with a random key of 100 lowercase letters drawn from
    /// `seed`, and the seed to draw from next.
    pub fn random(seed: Seed) -> (Cipher, Seed)
        (letters, next) =
            Generator.int(0..26)
            |> Generator.map(&Vector.get(alphabet, &1)!)
            |> Generator.list(random_key_length)
            |> Generator.step(seed)

        (Cipher{key: String.from_codepoints(letters)}, next)
    end

    /// The cipher's key.
    pub fn key(cipher: Cipher) -> String
        cipher.key
    end

    /// `plaintext`, lowercase letters, with each letter moved forward by its
    /// key letter.
    pub fn encode(cipher: Cipher, plaintext: String) -> String
        shift(cipher, plaintext, 1)
    end

    /// `ciphertext`, lowercase letters, with each letter moved back by its
    /// key letter: the inverse of `encode`.
    pub fn decode(cipher: Cipher, ciphertext: String) -> String
        shift(cipher, ciphertext, -1)
    end
end

/// `text` with each letter moved by its key letter's number, forward for a
/// `direction` of 1 and back for -1, wrapping around the alphabet.
fn shift(cipher: Cipher, text: String, direction: Int) -> String
    key =
        cipher.key
        |> String.to_codepoints()
        |> Iter.cycle()

    text
    |> String.to_codepoints()
    |> Iter.zip(key)
    |> Iter.map(fn (letter, by) ->
        moved = number(letter) + direction * number(by)
        Vector.get(alphabet, Int.modulo(moved, letter_count))!
    end)
    |> Iter.to_list()
    |> String.from_codepoints()
end

/// A lowercase letter's place in the alphabet, from 0 for `a`.
fn number(letter: Codepoint) -> Int
    Codepoint.to_int(letter) - Codepoint.to_int('a')
end

// FILE: simple_cipher_test.nomi
import
    std::random.Seed
    simple_cipher.Cipher
end

group "random key cipher"
    setup begin
        (cipher, _seed) = Seed.from_int(2026) |> Cipher.random()
        cipher
    end

    test "Can encode", cipher
        plaintext = "aaaaaaaaaa"
        key_start = Cipher.key(cipher) |> String.take(10)

        assert Cipher.encode(cipher, plaintext) == key_start
    end

    test "Can decode", cipher
        ciphertext = Cipher.key(cipher) |> String.take(10)

        assert Cipher.decode(cipher, ciphertext) == "aaaaaaaaaa"
    end

    test "Is reversible", cipher
        plaintext = "abcdefghij"

        assert Cipher.decode(cipher, Cipher.encode(cipher, plaintext)) == plaintext
    end

    test "Key is made only of lowercase letters", cipher
        letters = Cipher.key(cipher) |> String.to_codepoints()

        refute Iter.is_empty(letters)
        assert Iter.all_match(letters, &(&1 in 'a'..='z'))
    end
end

test "substitution cipher encodes"
    [
        ("Can encode", "abcdefghij", "aaaaaaaaaa", "abcdefghij"),
        ("Can double shift encode", "iamapandabear", "iamapandabear", "qayaeaagaciai"),
        ("Can wrap on encode", "abcdefghij", "zzzzzzzzzz", "zabcdefghi"),
        ("Can encode messages longer than the key", "abc", "iamapandabear", "iboaqcnecbfcr"),
    ]
    |> subtests (description, key, plaintext, expected), description
        assert Cipher.new(key) |> Cipher.encode(plaintext) == expected
    end
end

test "substitution cipher decodes"
    [
        ("Can decode",                              "abcdefghij", "abcdefghij",    "aaaaaaaaaa"),
        ("Can wrap on decode",                      "abcdefghij", "zabcdefghi",    "zzzzzzzzzz"),
        ("Can decode messages longer than the key", "abc",        "iboaqcnecbfcr", "iamapandabear"),
    ]
    |> subtests (description, key, ciphertext, expected), description
        assert Cipher.new(key) |> Cipher.decode(ciphertext) == expected
    end
end

test "substitution cipher is reversible"
    cipher = Cipher.new("abcdefghij")

    assert Cipher.decode(cipher, Cipher.encode(cipher, "abcdefghij")) == "abcdefghij"
end
  • Cipher is an opaque struct holding the key. Cipher.new(key) takes a given key, and Cipher.random(seed) draws one of 100 lowercase letters with std/random and answers the cipher and the next seed. Nomi has no hidden random state: randomness is a Seed threaded through Generator.step, so the random cipher is a pure function of its seed.
  • The key’s letters are drawn by one generator, Generator.int(0..26) mapped to the alphabet and repeated with Generator.list(100). Generator.uniform would also do, but it takes a NonEmptyList, and the alphabet built from a range is a Vector no literal proves non-empty.
  • encode and decode are one shift with a direction of 1 or -1. The text is zipped with the key cycled by Iter.cycle, so a key shorter than the text repeats with no index arithmetic, and Int.modulo wraps a letter past z or before a.
  • A letter’s number is its codepoint less a’s, and the moved letter is read back from the alphabet vector, so no Maybe from Int.to_codepoint needs unwrapping. The canonical data gives only lowercase letters, which the doc comments state as the promise.
  • The random-key cases run against a cipher made from a fixed seed, Seed.from_int(2026), in a group whose setup builds it, so the tests are deterministic and still check the canonical properties (the key encodes as to itself, decodes back, and is all lowercase letters) rather than a particular key.
  • The substitution cases are two subtests tables, encode and decode, and one test for reversibility, since it calls both.