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