---
title: Functional Ciphers in Ruby
teaser: Work with ciphers in Ruby using a functional approach.
tags: news,ruby,haskell
author: Joël Quenneville
published_on: 2015-04-02
---

Ciphers are an algorithm for encrypting or decrypting text. They have been used
since ancient times. Julius Caesar [famously encrypted military messages] via a
cipher that shifted all letters by a constant value. Today, this algorithm is
known as the ROT family of ciphers.

[famously encrypted military messages]: https://en.wikipedia.org/wiki/Caesar_cipher#History_and_usage

We want to write some code that will show us multiple passes of ROT encryption
on some input text, using some of Ruby's functional constructs.

## ROT5

The ROT5 algorithm rotates the alphabet by 5 characters. We could implement it
as follows:

```ruby
rot5 = ->(text) do
  alphabet = ("a".."z").to_a
  key = Hash[alphabet.zip(alphabet.rotate(5))]
  text.each_char.inject("") { |encrypted, char| encrypted + key[char] }
end
```

The key is a hash that maps inputs from the standard alphabet to the rotated
one. It looks like: `{ "a" => "f", "b" => "g", ... }`. We use this key to
convert each character of the input string to its rotated value.

This works as expected:

```ruby
rot5.call("password")
# => "ufxxbtwi"
rot5.call("supersecret")
# => "xzujwxjhwjy"
```

We can easily extend this to allow us to shift by any value by adding another
argument:

```ruby
rot = ->(rotation, text) do
  alphabet = ("a".."z").to_a
  key = Hash[alphabet.zip(alphabet.rotate(rotation))]
  text.each_char.inject("") { |encrypted, char| encrypted + key[char] }
end

rot.call(5, "password")
# => "ufxxbtwi"
rot.call(10, "password")
# => "zkccgybn"
```

## Multiple applications

We want to see what happens when you apply a ROT function multiple times to a
value. We could manually write `rot5(rot5(rot5("password")))`, however that is
not very flexible and doesn't even show the intermediate steps. Instead, we are
going to take inspiration from `iterate` in Haskell.

Haskell's [`iterate` function] takes a function and starting value and returns an
infinite lazy list of recursive applications of the function to the value. In
other words:

```haskell
iterate f x == [x, f(x), f(f(x)), f(f(f(x))), ...]
```

To implement this in Ruby, we are going to need [`Enumerator`].

[`iterate` function]:
http://hackage.haskell.org/package/base-4.7.0.2/docs/Prelude.html#v:iterate
[`Enumerator`]: http://ruby-doc.org/core-2.2.0/Enumerator.html

## Ruby's `Enumerator`

One of the lesser-known core classes in Ruby, `Enumerator` implements the
[internal and external iteration patterns]. `Enumerator#new` take a block with a
yielder parameter and adds all values sent to the yielder to its list.

```ruby
numbers = Enumerator.new do |yielder|
  yielder << 1
  yielder << 2
  yielder << 3
end

numbers.first(3)
# => [1, 2, 3]
```

`Enumerator` is lazy-*ish*. Take the following infinite iterator:

```ruby
infinite = Enumerator.new do |yielder|
  x = 1
  loop do
    yielder << x
    x +=1
  end
end
```

We can ask for the first 10 values without having to calculate the entire
series.

```ruby
infinite.first(10)
# => [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
```

However, using a method such as `map` that acts on every item will never return
because this is an infinite series. We will need true laziness to get this one
to work.

```ruby
infinite.lazy.map { |n| n * 2 }
# => #<Enumerator::Lazy: ...>

infinite.lazy.map { |n| n * 2 }.first(10)
# => [2, 4, 6, 8, 10, 12, 14, 16, 18, 20]
```

Calling `map` on a lazy enumerator won't actually execute until you ask for some
items in the series, and even then it will only execute for those items. We've
written previously about [how to take advantage of this laziness to refactor
code].

[internal and external iteration patterns]:
https://chickenriceplatter.github.io/blog/2013/04/07/internal-vs-external-iterators/
[how to take advantage of this laziness to refactor code]:
https://thoughtbot.com/blog/lazy-refactoring

## Building `iterate`

The Haskell implementation is deceptively simple:

```haskell
iterate :: (a -> a) -> a -> [a]
iterate f x =  x : iterate f (f x)
```

It just keeps recurring and appending to the list (lazily of course).

The Ruby implementation is a bit more verbose, and uses iteration rather than
recursion.

```ruby
iterate = -> (x, &block) do
  Enumerator.new do |yielder|
    loop do
      yielder << x
      x = block.call(x)
    end
  end.lazy
end
```

This method accepts a starting value and a block. On each iteration of the loop,
it calls the block with the value of the previous iteration. The result is an
infinite, lazy enumerator.

```ruby
iterate.call("x") { |x| "f(#{x})" }.first(5)
# => ["x", "f(x)", "f(f(x))", "f(f(f(x)))", "f(f(f(f(x))))"]

iterate.call(1) { |x| x * 2 }.first(10)
# => [1, 2, 4, 8, 16, 32, 64, 128, 256, 512]
```

## Multiple applications of ROT5

Now that we have `iterate`, we can finally try multiple applications of ROT5.
Instead of passing a block (which is just an anonymous function), we can
directly pass the named function `rot5`:

```ruby
iterate.call("password", &rot5).first(5)
# => ["password", "ufxxbtwi", "zkccgybn", "ephhldgs", "jummqilx"]

iterate.call("supersecret", &rot5).first(5)
# => ["supersecret", "xzujwxjhwjy", "cezobcombod", "hjetghtrgti", "mojylmywlyn"]
```

This is exactly what we want. However, we run into a problem if we try to use
our more generic function `rot`.

```ruby
iterate.call("password", &rot).first(5)
# => ArgumentError: wrong number of arguments (1 for 2)
```

`rot` expects two arguments, but `iterate` only passes it one. To get around
this, we need to use currying.

## Currying

Currying allows us to call a function with only part of its arguments and it
will return another function that requires the remainder.

```ruby
two_text = ->(text1, text2) { "#{text1} #{text2}" }.curry
# => #<Proc: (lambda)>
hello = two_text.call("hello")
# => #<Proc: (lambda)>

hello.call("world")
# => "hello world"

two_text.call("currying").call("works!")
# => "currying works!"
```

If we curry `rot`, we can partially apply it and then pass it into `iterate`:

```ruby
rot = ->(rotation, text) do
  alphabet = ("a".."z").to_a
  key = Hash[alphabet.zip(alphabet.rotate(rotation))]
  text.each_char.inject("") { |encrypted, char| encrypted + key[char] }
end.curry

iterate("password", &rot.call(3)).first(5)
# => ["password", "sdvvzrug", "vgyycuxj", "yjbbfxam", "bmeeiadp"]

iterate("password", &rot.call(7)).first(5)
# => ["password", "whzzdvyk", "doggkcfr", "kvnnrjmy", "rcuuyqtf"]
```

Great! Now we can encrypt any text with any number of passes through any ROT
algorithm and see all the intermediate values.

## Deconstructing ROT

Calling a ROT algorithm multiple times on itself does not make it any harder to
decrypt. ROTX of ROTY is the same as ROT X + Y

```ruby
rot.call(10, rot.call(5, "password"))
# => "ephhldgs"

rot.call(15, "password")
# => "ephhldgs"
```

Also, every multiple of 26 is just plain text:

```ruby
rot.call(26, "password")
# => "password"

rot.call(52, "password")
# => "password"

rot.call(10, rot.call(10, rot.call(6, "password")))
# => "password"
```

This can easily be seen when using `iterate`:

```ruby
iterate.call("password", &rot.call(13)).first(5)
# =>
[
  "password", # ROT0
  "cnffjbeq", # ROT13
  "password", # ROT26
  "cnffjbeq", # ROT39
  "password"  # ROT52
]
```

Building on the two facts above, we can use `iterate` to brute-force any
ROT-encrypted text:

```ruby
rot.call(17, "thisisasupersecretmessage")
# => "kyzjzjrjlgvijvtivkdx"

iterate("kyzjzjrjlgvijvtivkdx", &rot.call(1)).first(26)
# The decrypted message will be one of the 26 messages below:
# =>
[
  "kyzjzjrjlgvijvtivkdvjjrxv",
  "lzakakskmhwjkwujwlewkksyw",
  "mablbltlnixklxvkxmfxlltzx",
  "nbcmcmumojylmywlyngymmuay",
  "ocdndnvnpkzmnzxmzohznnvbz",
  "pdeoeowoqlanoaynapiaoowca",
  "qefpfpxprmbopbzobqjbppxdb",
  "rfgqgqyqsncpqcapcrkcqqyec",
  "sghrhrzrtodqrdbqdsldrrzfd",
  "thisisasupersecretmessage", # Gotcha!
  "uijtjtbtvqfstfdsfunfttbhf",
  "vjkukucuwrgtugetgvoguucig",
  "wklvlvdvxshuvhfuhwphvvdjh",
  "xlmwmwewytivwigvixqiwweki",
  "ymnxnxfxzujwxjhwjyrjxxflj",
  "znoyoygyavkxykixkzskyygmk",
  "aopzpzhzbwlyzljylatlzzhnl",
  "bpqaqaiacxmzamkzmbumaaiom",
  "cqrbrbjbdynabnlancvnbbjpn",
  "drscsckcezobcombodwocckqo",
  "estdtdldfapcdpncpexpddlrp",
  "ftueuemegbqdeqodqfyqeemsq",
  "guvfvfnfhcrefrpergzrffntr",
  "hvwgwgogidsfgsqfshasggous",
  "iwxhxhphjetghtrgtibthhpvt",
  "jxyiyiqikfuhiushujcuiiqwu"
]
```