Thursday 3 June 2010

Introduction to Ciphers

As some of my readers may already know, I am hard at work refreshing my cryptology skills for a job interview (tomorrow! Wish me luck!) at one of the big banks in my area. While reading, I noticed that one of the most basic building blocks of cryptology, namely ciphers, are always explained in an overly complex manner. The textbooks, evidently written by skilled mathematicians, focus entirely on the math-y stuff like bit shifting and modular arithmetic, instead of explaining what ciphers are. Thus, I've decided to write a short primer to help other aspiring cryptologers:

Definition

Ciphers are the science of writing hidden messages in such a way that no one, apart from the sender and intended recipient, suspects the existence of the message.

In practice, this is usually done by encrypting a key onto a message, yielding a ciphertext. Since the ciphertext never looks anything like the original message, nobody can suspect its existence unless you tell them and give them the key.

Let's give an example to illuminate things.

The RotThirteen cipher

The RotThirteen algorithm is the simplest there is; increase each letter thirteen times, and roll over to 'a' if you pass 'z'. Since the alphabet contains twice thirteen characters, this means that 'XYZ' is encrypted to 'KLM', and 'KLM' encrypted again becomes 'XYZ'! This property means we don't need a separate decryption step, saving time and effort. In fact, the entire algorithm can be wrapped in just one single function (and a helper function).

class Ciphers {
    public static string RotThirteen(string input) {
        char[] chars = input.ToCharArray();
        for (int i = 0; i < input.Length; i++) {
            int lowerRotation = Rotate(chars[i] - 'a', 13, 26);
            int upperRotation = Rotate(chars[i] - 'A', 13, 26);
            if (chars[i] > 'a') chars[i] = (char)('a' + lowerRotation);
            else if (chars[i] > 'A') chars[i] = (char)('A' + upperRotation);
        }
        return new string(chars);
    }

    private static int Rotate(int c, int delta, int max) {
        c += delta;
        while (c > max) c -= max;
        return c;
    }
}

Quickly creating a simple host application and testing this:



Click "RotThirteen":



Click "RotThirteen" again:



Working as expected!

Usages

In contrast to most ciphers, RotThirteen doesn't use secret keys. Instead, all messages are encoded with the public key 13. While RotThirteen is not very secure, its simplicity and elegance makes it popular where only simple encryption is needed. For instance:
  • As an anti-spam measure.
  • A convenient way to write both a puzzle and vgf nafjre in the same place, without giving away the answer prematurely.