Functional Ciphers in Ruby

Joël Quenneville

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.

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:

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:

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:

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:

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

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

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.

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:

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.

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.

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.

Building iterate

The Haskell implementation is deceptively simple:

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.

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.

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:

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.

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.

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:

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

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

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

Also, every multiple of 26 is just plain text:

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:

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:

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"
]