Avatar of davearonson

davearonson's solution

to Simple Cipher in the Elixir Track

Published at Jul 13 2018 · 0 comments
Instructions
Test suite
Solution

Note:

This solution was written on an old version of Exercism. The tests below might not correspond to the solution code, and the exercise may have changed since this code was written.

Implement a simple shift cipher like Caesar and a more secure substitution cipher.

Step 1

"If he had anything confidential to say, he wrote it in cipher, that is, by so changing the order of the letters of the alphabet, that not a word could be made out. If anyone wishes to decipher these, and get at their meaning, he must substitute the fourth letter of the alphabet, namely D, for A, and so with the others." —Suetonius, Life of Julius Caesar

Ciphers are very straight-forward algorithms that allow us to render text less readable while still allowing easy deciphering. They are vulnerable to many forms of cryptoanalysis, but we are lucky that generally our little sisters are not cryptoanalysts.

The Caesar Cipher was used for some messages from Julius Caesar that were sent afield. Now Caesar knew that the cipher wasn't very good, but he had one ally in that respect: almost nobody could read well. So even being a couple letters off was sufficient so that people couldn't recognize the few words that they did know.

Your task is to create a simple shift cipher like the Caesar Cipher. This image is a great example of the Caesar Cipher:

Caesar Cipher

For example:

Giving "iamapandabear" as input to the encode function returns the cipher "ldpdsdqgdehdu". Obscure enough to keep our message secret in transit.

When "ldpdsdqgdehdu" is put into the decode function it would return the original "iamapandabear" letting your friend read your original message.

Step 2

Shift ciphers are no fun though when your kid sister figures it out. Try amending the code to allow us to specify a key and use that for the shift distance. This is called a substitution cipher.

Here's an example:

Given the key "aaaaaaaaaaaaaaaaaa", encoding the string "iamapandabear" would return the original "iamapandabear".

Given the key "ddddddddddddddddd", encoding our string "iamapandabear" would return the obscured "ldpdsdqgdehdu"

In the example above, we've set a = 0 for the key value. So when the plaintext is added to the key, we end up with the same message coming out. So "aaaa" is not an ideal key. But if we set the key to "dddd", we would get the same thing as the Caesar Cipher.

Step 3

The weakest link in any cipher is the human being. Let's make your substitution cipher a little more fault tolerant by providing a source of randomness and ensuring that the key contains only lowercase letters.

If someone doesn't submit a key at all, generate a truly random key of at least 100 characters in length.

If the key submitted is not composed only of lowercase letters, your solution should handle the error in a language-appropriate way.

Extensions

Shift ciphers work by making the text slightly odd, but are vulnerable to frequency analysis. Substitution ciphers help that, but are still very vulnerable when the key is short or if spaces are preserved. Later on you'll see one solution to this problem in the exercise "crypto-square".

If you want to go farther in this field, the questions begin to be about how we can exchange keys in a secure way. Take a look at Diffie-Hellman on Wikipedia for one of the first implementations of this scheme.

Running tests

Execute the tests with:

$ elixir simple_cipher_test.exs

Pending tests

In the test suites, all but the first test have been skipped.

Once you get a test passing, you can unskip the next one by commenting out the relevant @tag :pending with a # symbol.

For example:

# @tag :pending
test "shouting" do
  assert Bob.hey("WATCH OUT!") == "Whoa, chill out!"
end

Or, you can enable all the tests by commenting out the ExUnit.configure line in the test suite.

# ExUnit.configure exclude: :pending, trace: true

For more detailed information about the Elixir track, please see the help page.

Source

Substitution Cipher at Wikipedia http://en.wikipedia.org/wiki/Substitution_cipher

Submitting Incomplete Solutions

It's possible to submit an incomplete solution so you can see how others have completed the exercise.

simple_cipher_test.exs

if !System.get_env("EXERCISM_TEST_EXAMPLES") do
  Code.load_file("simple_cipher.exs", __DIR__)
end

ExUnit.start()
ExUnit.configure(trace: true, exclude: :pending)

defmodule SimpleCipherTest do
  use ExUnit.Case

  # @tag :pending
  test "encoding with 'a' returns the original text" do
    assert SimpleCipher.encode("a", "a") == "a"
    assert SimpleCipher.encode("b", "a") == "b"
    assert SimpleCipher.encode("c", "a") == "c"
  end

  @tag :pending
  test "encoding with another key returns shifted text" do
    assert SimpleCipher.encode("a", "d") == "d"
    assert SimpleCipher.encode("b", "d") == "e"
    assert SimpleCipher.encode("c", "d") == "f"
  end

  @tag :pending
  test "decoding with 'a' returns the original text" do
    assert SimpleCipher.decode("a", "a") == "a"
    assert SimpleCipher.decode("b", "a") == "b"
    assert SimpleCipher.decode("c", "a") == "c"
  end

  @tag :pending
  test "decoding with another key returns unshifted text" do
    assert SimpleCipher.decode("d", "d") == "a"
    assert SimpleCipher.decode("e", "d") == "b"
    assert SimpleCipher.decode("f", "d") == "c"
  end

  @tag :pending
  test "key uses per-letter translation for encoding" do
    key = "abc"

    assert SimpleCipher.encode("abc", key) == "ace"
    assert SimpleCipher.encode("bcd", key) == "bdf"
    assert SimpleCipher.encode("cde", key) == "ceg"
    assert SimpleCipher.encode("iamapandabear", "dddddddddddddd") == "ldpdsdqgdehdu"
  end

  @tag :pending
  test "key uses per-letter translation for decoding" do
    key = "abc"

    assert SimpleCipher.decode("ace", key) == "abc"
    assert SimpleCipher.decode("bdf", key) == "bcd"
    assert SimpleCipher.decode("ceg", key) == "cde"
    assert SimpleCipher.decode("ldpdsdqgdehdu", "dddddddddddddd") == "iamapandabear"
  end

  @tag :pending
  test "only lowercase a-z are translated, rest are passed through" do
    assert SimpleCipher.encode("this is a test!", "d") == "wklv lv d whvw!"
    assert SimpleCipher.decode("wklv lv d whvw!", "d") == "this is a test!"
  end

  @tag :pending
  test "if key is shorter than text, repeat key" do
    assert SimpleCipher.encode("abc", "a") == "abc"
    assert SimpleCipher.encode("abcdefghi", "abc") == "acedfhgik"
  end

  @tag :pending
  test "if key is longer than text, only use as much as needed" do
    key = "somewhatlongkey"

    assert SimpleCipher.encode("abc", key) == "spo"
    assert SimpleCipher.decode("abc", key) == "inq"
  end

  @tag :pending
  test "if you know both the encoded and decoded text, you can figure out the key" do
    key = "supersecretkey"

    plaintext = "attackxatxdawn"
    ciphertext = SimpleCipher.encode(plaintext, key)

    assert SimpleCipher.decode(ciphertext, plaintext) == key
  end
end
defmodule SimpleCipher do
  @doc """
  Given a `plaintext` and `key`, encode each character of the `plaintext` by
  shifting it by the corresponding letter in the alphabet shifted by the number
  of letters represented by the `key` character, repeating the `key` if it is
  shorter than the `plaintext`.

  For example, for the letter 'd', the alphabet is rotated to become:

  defghijklmnopqrstuvwxyzabc

  You would encode the `plaintext` by taking the current letter and mapping it
  to the letter in the same position in this rotated alphabet.

  abcdefghijklmnopqrstuvwxyz
  defghijklmnopqrstuvwxyzabc

  "a" becomes "d", "t" becomes "w", etc...

  Each letter in the `plaintext` will be encoded with the alphabet of the `key`
  character in the same position. If the `key` is shorter than the `plaintext`,
  repeat the `key`.

  Example:

  plaintext = "testing"
  key = "abc"

  The key should repeat to become the same length as the text, becoming
  "abcabca". If the key is longer than the text, only use as many letters of it
  as are necessary.
  """
  def encode(plaintext, key) do
    plaintext
    |> String.to_charlist
    |> Enum.zip(key |> String.to_charlist |> Stream.cycle)
    |> Enum.map(&encode_char/1)
    |> to_string
  end

  defp encode_char({pc, _kc}) when pc < ?a or pc > ?z, do: pc
  defp encode_char({pc,  kc}), do: ?a + rem(pc + kc - (?a * 2), 26)

  @doc """
  Given a `ciphertext` and `key`, decode each character of the `ciphertext` by
  finding the corresponding letter in the alphabet shifted by the number of
  letters represented by the `key` character, repeating the `key` if it is
  shorter than the `ciphertext`.

  The same rules for key length and shifted alphabets apply as in `encode/2`,
  but you will go the opposite way, so "d" becomes "a", "w" becomes "t",
  etc..., depending on how much you shift the alphabet.
  """
  def decode(ciphertext, key) do
    ciphertext
    |> String.to_charlist
    |> Enum.zip(key |> String.to_charlist |> Stream.cycle)
    |> Enum.map(&decode_char/1)
    |> to_string
  end

  defp decode_char({cc, _kc}) when cc < ?a or cc > ?z, do: cc
  defp decode_char({cc,  kc}), do: ?a + rem(26 + cc - kc, 26)

end

Community comments

Find this solution interesting? Ask the author a question to learn more.

What can you learn from this solution?

A huge amount can be learned from reading other people’s code. This is why we wanted to give exercism users the option of making their solutions public.

Here are some questions to help you reflect on this solution and learn the most from it.

  • What compromises have been made?
  • Are there new concepts here that you could read more about to improve your understanding?