Encrypt data like Emperor: Caesar cipher

Whether we're concerned about privacy or not, we utilize cryptography every day. Thanks to HTTPS we can securely log in to online banks, use government services, share our location, chat with friends, and participate in other activities where leaks could result in financial loss, damage to our reputation, or even mental or physical harm.

Your communications with this website are also encrypted! That's not because you're transmitting or receiving confidential data while being here, but rather your browser wouldn't allow you to open this page otherwise. In the past, something like credit card details could be transferred in plain text, making it an easy target for hackers. Today, the risk is significantly reduced as browsers enforce site owners like me to secure the connection.

Long before the advent of the World Wide Web, the secrecy and confidentiality aspects of his role led Julius Caesar to contemplate how to safeguard his orders. A messenger carrying important information could be intercepted, and then it would be disclosed to the enemy. To counter this threat, he began encrypting his correspondence using a simple algorithm that was eventually named after him: a Caesar cipher.

How it works

  1. Let's assume the key is 3.
  2. Take the text you want to encrypt.
  3. Right shift each letter by 3, so that A becomes D, B becomes E, and so on.
  4. Congratulations, the insidious foe can no longer read your text!

Imagine Julius Caesar writing something like this:

I order you to not stab me 23 times. I repea~~aahh.

Which was then transformed with the key of 3:

L rughu brx wr qrw vwde ph 23 wlphv. L uhshd~~ddkk.

Perhaps the senators didn't know how to decrypt his message, or they didn't have the key. That'd explain why they proceeded to stab him. If we know the key, we can simply shift each letter in the opposite direction.

  1. Let's assume the key is 3.
  2. Take the text you want to decrypt.
  3. Left shift each letter by 3, so that D becomes A, E becomes B, and so on.
  4. Congratulations, now you can read the original text!

Luckily, we don't need to go through this tedious process manually, as we have something that Caesar didn't: computers.

Preparing

Before writing any code, let's consider what needs to be implemented. The mathematics behind both actions is as follows:

  • Encryption: L = (i + k) % 26
  • Decryption: L = (i - k) % 26

Where i is the position of a letter we're encrypting or decrypting, k is the key, and L is the position of the result letter. We count letters from 0, because that simplifies the arithmetic. We can use this table to track indexes:

index | letter
---------------
   0   |   A
   1   |   B
   2   |   C
   3   |   D
   4   |   E
   5   |   F
   6   |   G
   7   |   H
   8   |   I
   9   |   J
  10   |   K
  11   |   L
  12   |   M
  13   |   N
  14   |   O
  15   |   P
  16   |   Q
  17   |   R
  18   |   S
  19   |   T
  20   |   U
  21   |   V
  22   |   W
  23   |   X
  24   |   Y
  25   |   Z

For example:

  • Encryption: right shift A by 3 positions: 0 + 3 = 3; 3rd letter of the alphabet is D.
  • Decryption: left shift D by 3 positions: 3 - 3 = 0; 0th letter of the alphabet is A.

I omitted the modulo operation to keep it as simple as possible. After all, it doesn't have any effect on the result: (0 + 3) % 26 = 3 and (3 - 3) % 26 = 0 - it's the same output. However, it's necessary to perform this operation, since it allows us to cycle the alphabet.

Consider the word "zephyr" encrypted with the key of 1.

  • The first letter is z (index=25).
  • 25 + 1 = 26
  • We should replace z with the next letter in the table above.

The problem is that there are no letters after the z! Here's where the modulo operation comes in handy.

In computing, the modulo operation returns the remainder of a division, after one number is divided by another.

If we divide 26 by 26, we'll get 1 with the remainder of 0: 26 comes into 26 exactly one time.

    1
   --
26|26
  -26
   --
    0 -- the remainder

This remainder points to the letter that we should take instead of Z: A. If the key was 3, then the desired index would be 25 + 3 = 28: 26 comes into 28 one time, but 28 - 26 = 2, leaving a remainder of 2.

    1
   --
26|28
  -26
   --
    2 -- the remainder

The remainder points to the letter C, which is three steps ahread of Z if we treat the alphabet as a circular array.

index | letter
---------------
  25  |   Z
   0  |   A -- new value of `Z` with the key of `1`
   1  |   B -- new value of `Z` with the key of `2`
   2  |   C -- new value of `Z` with the key of `3`

The modulo operation drops the whole part and returns the remainder that we're interested in.

ASCII Table

We could define an array of letters just as we did above, all calculated indexes would match perfectly using the same formulae.

  1. Take a letter.
  2. Find its position in the array.
  3. Use the formula to calculate the new position.
  4. Take a letter by that position.
  5. Put it into the output string.
  6. Repeat.

There's one caveat with uppercase and lowercase letters, which might require two arrays or some additional logic if you want to maintain cases of the input data. However, in reality, we don't need any arrays to perform this task. Computers store letters and other symbols as separate characters. A is a character, Z is a character, 5 and $ too. In effect, strings are simply arrays of characters.

Digital computers operate with binary numbers, where 0 means that there's no voltage in the circuit, and 1 that there is voltage. Each letter is represented by a combination of 0s and 1s, and somewhere there's an electric circuit that holds this combination. To store texts in computers and then read them back, the ASCII table was designed. It maps binary values and particular characters.

For instance:

 binary  | decimal | character
-------------------------------
100 0001 |   65    |    A
100 0010 |   66    |    B
100 0011 |   67    |    C
<...>
101 1010 |   90    |    Z
<...>
110 0001 |   97    |    a
110 0010 |   98    |    b
110 0011 |   99    |    c
<...>
111 1010 |  122    |    z

How does it help us? To put it simply, it's the standard way to encode characters. Perhaps, today virtually all programming languages know how to translate between ASCII codes and characters. We can use this built-in knowledge to implement the algorithm.

To make it possible, these formulae need to be adjusted:

  • Encryption: L = (i + k) % 26
  • Decryption: L = (i - k) % 26

Let's try to shift the lowercase "a" with it:

  • ASCII code = 97.
  • Key = 1.
  • (97 + 1) % 26 = 20

Hold on a second. a should become b, but the code associated with the b is 98, not 20! This is caused by the fact indexes for lowercase letters in the ASCII table start from 97 and end at 122 (z). We must include this offset in the formulae:

  • Encryption: L = (i + k - offset) % 26 + offset
  • Decryption: L = (i - k - offset) % 26 + offset

First, we apply the offset to i + k. 97 + 1 = 98 becomes 97 + 1 - 97 = 1. 1 would point to b in a normal array that contains only letter of the English alphabet. Then, we apply the offset one more time to find the position of b in the ASCII table: 1 + 97 = 98 = b. It's the same with decryption.

Coding

The program itself is much simpler than the amount of text above might suggest.

  1. Take the input string.
  2. Split it into characters.
  3. Shift each character using the formulae above with the given key.
  4. Return the output string.

We defined that the encryption should shift to the right (i.e. A -> B), and the decryption should shift to the left (i.e. B -> A). It doesn't have to be this way, you can switch the formulae and operations.

It makes sense to use a single method for both operations, as the only difference between them is the operator used when applying the key: it's either a plus sign (i + k) or minus (i - k). Duplicating all other code isn't a good practice.

Let's define this method first: shift(int key, String data, boolean shiftRight). With this signature alone we can finish the implementation of the encrypt/decrypt methods:

public static String encrypt(int key, String data) {
    return shift(key, data, true);
}

public static String decrypt(int key, String data) {
    return shift(key, data, false);
}

The last flag tells the shift method whether it should shift to the right. The Caesar cipher can't go up or down. Hence, if it doesn't shift to the right, it shifts to the left. A simple boolean parameter is sufficient here.

In Java, String objects have a method that returns a stream of characters. We can use it to access each character independently of another.

private static String shift(int key, String data, boolean shiftRight) {
    return data.chars()
            .map(c -> {
                // do something
            })
            // collect data to a String
}

The core logic will be located inside the function that we pass to map method. Once the data is transformed, we'll convert it to a new String and return back to the caller.

It's possible that the input text would contain characters other than letters. There are different strategies for what to do with them. I want to keep all these symbols. For that, we can add the following condition at the beginning of of the function. It'll simply return any character that is not a letter back to the stream.

if (!Character.isLetter(c)) {
    return c;
}

Any character that passes this code block is a letter to shift. We need to calculate the offset first.

int offset = Character.isUpperCase(c) ? 65 : 97;

Uppercase and lowercase letters are different characters located at different locations in the ASCII table:

 binary  | decimal | character
-------------------
100 0001 |   65    |    A
100 0010 |   66    |    B
100 0011 |   67    |    C
<...>
101 1010 |   90    |    Z
<...>
110 0001 |   97    |    a
110 0010 |   98    |    b
110 0011 |   99    |    c
<...>
111 1010 |  122    |    z

Therefore, the offset is calculated dynamically: 65 for uppercase letters and 97 for lowercase letters.

Finally, we can shift the character either to the right or left:

if (shiftRight) {
    return Math.floorMod(c - offset + key, 26) + offset;
} else {
    return Math.floorMod(c - offset - key, 26) + offset;
}

It's the same formulae that we've established in the section dedicated to the ASCII table.

The calculated index of a character that should replace the current character is returned back to the stream. At the end, we'll have a stream filled with shifted characters instead of original letters. This stream of characters can't be returned as a String object yet. We need to collect all characters back into a single array of data. A StringBuilder can be used for that:

private static String shift(int key, String data, boolean shiftRight) {
    return data.chars()
            .map(c -> {
                if (!Character.isLetter(c)) {
                    return c;
                }

                int offset = Character.isUpperCase(c) ? 65 : 97;
                if (shiftRight) {
                    return Math.floorMod(c - offset + key, 26) + offset;
                } else {
                    return Math.floorMod(c - offset - key, 26) + offset;
                }
            })
            .collect(StringBuilder::new, StringBuilder::appendCodePoint, StringBuilder::append)
            .toString();
}

The collect method will create a new instance of StringBuilder and apply appendCodePoint to each bit of data in the stream, converting character codes to actual letters. The final append apparently isn't used in combination with appendCodePoint, at least my imperical experience tells me so. But we need to specify it in order to compile the program.

A regular for loop can do this just fine if you find them more familiar. In fact, the newly founded Wikifunctions suggests to use a for loop in their Python implementation. Their JavaScript code is close to mine, yet it's slightly different. Take a look.

Here are tests that I used to validate my code:

public class CaesarCipherTest {
    private final String plainText = "The quick brown fox jumps over the lazy dog.";

    // encrypt
    @Test
    public void encryptWithKey0() {
        String output = CaesarCipher.encrypt(0, plainText);

        assertEquals(plainText, output);
    }

    @Test
    public void encryptWithKey1() {
        String output = CaesarCipher.encrypt(1, plainText);
        String expected = "Uif rvjdl cspxo gpy kvnqt pwfs uif mbaz eph.";

        assertEquals(expected, output);
    }

    @Test
    public void encryptWithKey13() {
        String output = CaesarCipher.encrypt(13, plainText);
        String expected = "Gur dhvpx oebja sbk whzcf bire gur ynml qbt.";

        assertEquals(expected, output);
    }

    @Test
    public void encryptWithKey25() {
        String output = CaesarCipher.encrypt(25, plainText);
        String expected = "Sgd pthbj aqnvm enw itlor nudq sgd kzyx cnf.";

        assertEquals(expected, output);
    }

    @Test
    public void encryptWithKey26() {
        String output = CaesarCipher.encrypt(26, plainText);

        assertEquals(plainText, output);
    }

    // decrypt
    @Test
    public void decryptWithKey0() {
        String output = CaesarCipher.decrypt(0, plainText);

        assertEquals(plainText, output);
    }

    @Test
    public void decryptWithKey1() {
        String input = "Uif rvjdl cspxo gpy kvnqt pwfs uif mbaz eph.";
        String output = CaesarCipher.decrypt(1, input);

        assertEquals(plainText, output);
    }

    @Test
    public void decryptWithKey13() {
        String input = "Gur dhvpx oebja sbk whzcf bire gur ynml qbt.";
        String output = CaesarCipher.decrypt(13, input);

        assertEquals(plainText, output);
    }

    @Test
    public void decryptWithKey25() {
        String input = "Sgd pthbj aqnvm enw itlor nudq sgd kzyx cnf.";
        String output = CaesarCipher.decrypt(25, input);

        assertEquals(plainText, output);
    }

    @Test
    public void decryptWithKey26() {
        String output = CaesarCipher.decrypt(26, plainText);

        assertEquals(plainText, output);
    }
}

Security

The time has come to look at the elephant in the room. The Caesar cipher is extremely easy to break. With 26 letters, there are just 25 potential keys. The very first key of 0 or 26 doesn't count, as it wouldn't have any effect. The text encrypted with either of these values will be exactly the same!

  • 0 + 0 % 26 = 0
  • 0 + 26 % 26 = 0

So, a brute-force attack in the form of a for loop could apply all possible keys, leaving it to us to decide which output makes sense.

public static List<String> bruteForce(String data) {
    // iterate from 1 to 25 (the range is inclusive..excluvisve)
    return IntStream.range(1, 26)
            // decrypt with each `i` value
            .mapToObj(i -> decrypt(i, data))
            .toList();
}

Let's run it:

public static void main(String[] args) {
    String input = "Gur dhvpx oebja sbk whzcf bire gur ynml qbt.";

    CaesarCipher.bruteForce(input).forEach(System.out::println);
}

And look at the output:

Ftq cguow ndaiz raj vgybe ahqd ftq xmlk pas.
Esp bftnv mczhy qzi ufxad zgpc esp wlkj ozr.
Dro aesmu lbygx pyh tewzc yfob dro vkji nyq.
Cqn zdrlt kaxfw oxg sdvyb xena cqn ujih mxp.
Bpm ycqks jzwev nwf rcuxa wdmz bpm tihg lwo.
Aol xbpjr iyvdu mve qbtwz vcly aol shgf kvn.
Znk waoiq hxuct lud pasvy ubkx znk rgfe jum.
Ymj vznhp gwtbs ktc ozrux tajw ymj qfed itl.
Xli uymgo fvsar jsb nyqtw sziv xli pedc hsk.
Wkh txlfn eurzq ira mxpsv ryhu wkh odcb grj.
Vjg swkem dtqyp hqz lworu qxgt vjg ncba fqi.
Uif rvjdl cspxo gpy kvnqt pwfs uif mbaz eph.
The quick brown fox jumps over the lazy dog. <-- here it is!
Sgd pthbj aqnvm enw itlor nudq sgd kzyx cnf.
Rfc osgai zpmul dmv hsknq mtcp rfc jyxw bme.
Qeb nrfzh yoltk clu grjmp lsbo qeb ixwv ald.
Pda mqeyg xnksj bkt fqilo kran pda hwvu zkc.
Ocz lpdxf wmjri ajs ephkn jqzm ocz gvut yjb.
Nby kocwe vliqh zir dogjm ipyl nby futs xia.
Max jnbvd ukhpg yhq cnfil hoxk max etsr whz.
Lzw imauc tjgof xgp bmehk gnwj lzw dsrq vgy.
Kyv hlztb sifne wfo aldgj fmvi kyv crqp ufx.
Jxu gkysa rhemd ven zkcfi eluh jxu bqpo tew.
Iwt fjxrz qgdlc udm yjbeh dktg iwt apon sdv.
Hvs eiwqy pfckb tcl xiadg cjsf hvs zonm rcu.

In Russian, "brute" in "brute-force" sounds exactly as the name of one of the conspirators, who assassinated Julius Caesar, Brutus. I couldn't find confirmation if this is intentional. For now, I'll consider this a poetical coincidence.

Useful links

14.12.2023