In this article we will see how to implement Caesar’s cipher in Elm, a new functional language for front-end web development. While the Caesar cipher is not one you should ever use for messages that really have to be secret, it is easy to understand, fun to play with, and is a good place to exercise some ideas in functional programming — especially the notion of function pipelines. You can find the full code at on GitHub, or you can use Ellie.
The idea behind Caesar’s code is simple: Take a message like HELLO and shift the characters forward by k units in the alphabet — or, better, in the characters as laid out in the ASCII code. Thus, if k = 1, then the encrypted message is IFMMP. If k = 2, then the encrypted message is JGNNQ. Etc. Decryption is simple: shift by -k. Decryption is just encryption with a different key.
To decrypt a message, you need to know the key, which is a number between 1 and 25. But there are so few keys that we can simply try them all. Consider, for example, the message O^^ZS.^WS . We try k = -1 and get N]]YR-]VR — nonsense. We try k = -2 and get M\\XQ,\UQ — more nonsense. Finally, k = -14 yields APPLE PIE. We have decrypted our message.
This is the brute force method for breaking a an encrypted message. It will work if the key space is small relative to the available computing power. For a variation of the Caesar code that is theoretically unbreakable, use a key that as long as your message, and use its letters to shift the corresponding letters of the message. For example, if the message to be encrypted is APPLE PIE, which is 9 characters long, we may use the 9-character key ABCDEFGHI. Encryption goes as follows:
- The first letter of the key is A, so shift the A of APPLE zero places to A.
- The second letter of the key is B, so shift the P of APPLE one place to Q.
- The third letter of the key is C, so shift the next P of APPLE two places to R.
The encrypted message is AQROI%VPM.
For more on this topic, Google “One time pad.” Note that the number of possible number of keys is 26 to the power 9, which works out to be 5,429,503,678,976 — more than 5 trillion. You could, in theory, use brute force. If decryptions can be carried out in a nanosecond, then all keys could be tried in an hour and a half. But in the process, all possible nine-letter messages would be generated: lots of nonsense, like AWJEPUXMO, which discard using some algorithm, and then the rest, e.g., SWORDFISH, KOALABEAR, COCA COLA, and JOE’S BAR. Then the problem is: which is the correct decryption? The problem has no solution. Question: how many sensible nine-letter messages are there?
The code for the one-time-pad upgrade of the Caesar code is also on GitHub.
Here we discuss only the simple Caesar method, with the one-time pad version left as an exercise. The full Elm code is displayed in module Encrypt below. It has just five function definitions. Let’s go through them one at a time. First is a function which converts strings into lists of integers.
string2ascii message =
|> List.map Char.toCode
If we import
Encrypt into the
import Encrypt exposing(..), we can try it out:
> string2ascii "HELLO"
[72,69,76,76,79] : List Char.KeyCode
The call to
String.toList transforms the message into a list of characters, namely
List.map applies the function
Char.toCode to each character in the list to compute its numerical code.
Notice that we are using the “forward pipe operator” to make function composition easier to read. As an example, consider the function
double x = 2*x. To double the number 1 three times, we could write
(double (double (double 1)))
But it is easier to read and understand the equivalent form
1 |> double |> double |> double
It works as expected:
> double x = 2*x
<function> : number -> number
> 1 |> double |> double |> double
8 : number
This way of writing function composition conforms to our mental picture of a function as a gizmo with an input and output. To compose functions is therefore to connect the input of one function to the output of another, thus forming a pipeline, as in the figure below.
We should think of data as flowing into the pipeline at the left, being transformed in turn by each gizmo through which it passes, and flowing out on the right as the composed function value. One can build whole hierarchies of pipelines like this. See Scott Wlaschin’s Functional Design Patterns.
Continuing with the code
Back to the
Encryptmodule. The function
ascii2string is the inverse of
> ascii2string [72,69,76,76,79]
"HELLO" : String
This function is defined using the function pipeline
nums |> List.map Char.fromCode |> String.fromList
A list of numbers “goes in” on the left, is transformed into a list of characters, and then into a string.
Next, we define the function
add x y = x + y, which does the obvious thing. Thus
add 1 2 yields the value
3. A little less obvious is the value of an expression like
add 2. Does it even make sense? There seems to be an argument missing. (Yikes!) The answer is: yes it does make sense —
add 2 is the function which adds
2 to its argument. Thus
(add 2) 3 is
The reason this works is that in Elm, as in any good functional language, functions can be values (and also parameters). If functions could not be values, then
add 2 would indeed be nonsense.
The reason why this is useful in our context is that it makes it easy to add a number to a list of numbers:
> List.map (add 2) [1,2,3,4]
[3,4,5,6] : List number
And this makes it easy to define an encryption function with yet another pipeline:
encrypt k str =
|> List.map (add k)
String.toUpper transforms a string into all caps: The value of the function call
string.toUpper “hello" is
"HELLO". As noted above, the decryption function operates by encrypting with -k:
decrypt k str = encrypt -k str
It is fun to play around with these functions in
elm-repl. To see them at work in an actual web app, take a look at this Ellie.
module Encrypt exposing (..)import Charstring2ascii message =
|> List.map Char.toCodeascii2string nums =
|> List.map Char.fromCode
|> String.fromListadd x y =
x + yencrypt k str =
str |> String.toUpper |> string2ascii |> List.map (add k) |> ascii2stringdecrypt k str =
encrypt -k str