Max Euston

A basic introduction to Encryption

Simple (Substitution) Cipher

As a child, you may have used a secret decoder ring that you got in a cereal box. This is an example of a substitution cipher.

The key in this technique is a simple 1:1 (one to one) table. For example, let's use this one (our friend has a copy of it too):

(An even simpler example of this type of cipher is to say "add 2" (or any number), so that 'A' becomes 'C', 'B' becomes 'D', and so forth... "wrapping around the end", so that 'Y' becomes 'A', and 'Z' becomes 'B' - this way you don't need to know the whole table, you just need to know how to recreate it).

Say we want to send the message "Hello Friend" to our friend, using this key (the table above). We'd lookup each letter in the table, and write its corresponding code. Like this:

So, instead of "Hello Friend", we'd write "Tdnni Evfdyh". Our friend would get this message and simply do the reverse (lookup each letter in the code row and replace it with the letter).

This technique works well for young children, but with a non-trivial message (several sentences), even older children can crack it (figure out the key). This is done by using letter frequency analysis. If we know (or suspect) that the message is written in English, then we can use our knowledge of that language to make guesses. For example, the most common letter in English is 'e'. If we notice that the code 'd' shows up the most in an encrypted message, we can guess that it likely stands for 'e'. Similarly, in English, the letter 'q' is always followed by a 'u', and the most common 3-letter word is 'the'. As more of these guesses are made (correctly), the remaining portions of the encrypted message will become easier to crack.

Private Key (Shared Secret) Encryption

Instead of using the fixed (static) table above, let's use something a little more complex. Say we and our friend have a secret (key) phrase: "Test for Echo". We can convert the letters in this phrase (ignoring spaces) into a table of offsets ('A' -> 1 ... 'Z' -> 26) as follows:

Again, we want to send the message "Hello Friend" to our friend. This time, we'll use the varying offsets from the passphrase (repeated as many times as needed) from the table above like this:

While this technique works much better than the simple cipher shown above, it has its own set of issues. Even though the encrypted code for any one letter can be different (but not too different - there are only 8 distinct codes in our 11-character key), there are still patterns in the key and message. Because of this (and the fact that we are still using a very basic cipher), there are also patterns in the encrypted message, and "patterns are bad" in cryptography. In addition, if we use this key over and over for many messages, and our messages commonly start with the salutation "Hello Friend", there are more patterns which will aid someone in cracking our code.

Modern ciphers in use today utilize many techniques to hide these patterns, and are much more complex than those shown above.

One Time Pad ("Unbreakable") Encryption

We don't need to utilize complex ciphers to create a truly secure message (but there is a catch). Let's extend our examples above. Instead of looking at just the 26 letters of the (English) alphabet, we'll use the 256 values of any (8-bit) byte, and write our message as a stream of bytes. If we also have a long key that is truly random (not pseudorandom), then we can create an "unbreakable" code.

Let's use the following list of 16 random numbers for our key:

Using those numbers as offsets (like before), and wrapping at 256 (since, this time we are using bytes and not letters), we can encrypt our message "Hello Friend". For example, the first character in our message is 'H', which is 72 in ASCII. Adding the first number from our key (206), we get 278, but since we wrap at 256, the first byte of our encrypted message will be 22 (278-256). The process repeats for each byte of our message:

So, instead of "Hello Friend", we would write (in a string of 8-bit bytes) "22, 104, 142, 4, 110, 165, 133, 30, 224, 102, 1, 158". Our friend would use a copy of the same 16-number key to reverse the process.

Now, the catch. In order to utilize this technique, we need to have a key that is longer than the message, and never reuse it (since, like before, many of our messages start with the salutation "Hello Friend", and that creates a pattern over multiple messages). The problem with this technique is that if we have a way to get a long key to our friend securely, then we should just give them the message. There are uses for this technique though. If you don't know what you need to say in the future, or when you will need to say it (but can give your friend a very long list of numbers when you do see them), then this is a very secure method that is easy to implement.

Public Key Encryption

The above types of encryption are known as "symmetric". This means that the same key is used for encryption and decryption. This requires that the parties involved must have a prior relationship (for example, us and our friend) in order to have a "pre-shared key".

What if we need to communicate securely with someone whom we've never met before? Since we've never met, we don't have any secret in common (no key that is known to only the two of us). This is where "asymmetric" encryption is used. Here we use 2 different keys (one public key for encryption and one private key for decryption).

While it may seem strange at first to say "public key", it really does make sense in this case. The stranger we want to communicate with must publish some piece of information (public key) to allow us to encrypt our message to them. This allows anybody to send a secret message to the stranger. Using this type of encryption, having the public key does no good in trying to decrypt the message, it is only able to encrypt messages.

So, how does the stranger decrypt the message? They use the private key, which only they have (it is a closely guarded secret known only to them - it is never shared).

You may be saying to yourself, "That doesn't make sense. If I know how to do something (encrypt), then it must be simple to just undo (decrypt) it." Well, for things like addition/subtraction (like we used in the above examples), you are right, they are both similarly "hard" (or easy). Yet, there are mathematical functions that are easy to do, but hard to undo.

For example, while it's easy to calculate the following (explained below):

2⁶ mod 13

• 2⁶ means "2 multiplied by itself 6 times", or 2*2*2*2*2*2, which is 64
• 'mod' means "modulo", which is "remainder after integer division", so "64 mod 13 = 12" (64/13=4 with 12 "left over")
  it's very much like the "wrapping" we did above (which was "mod 26" for the alphabet or "mod 256" for bytes).

Techniques like this, using prime numbers (13 is prime) are the basis for public key cryptography. In our example, if you only knew that

2^N mod 13 = 12

One common technique for public key encryption utilizes numbers that are the product of 2 very large prime numbers. For example, if I told you that my 2 secret (prime) numbers multiplied together were 44718743, you'd have a tough time telling me what they were (using a calculator). While a modern computer can solve this quickly by trying many different numbers (5237 * 8539 = 44718743), if I gave you a number with hundreds of digits, you'd have a much harder time (even using many computers together, it would take you many years to solve).

It's also possible to have 2-way communications that use both parties' public keys to encrypt messages in both directions.

In addition, since even a computer has to work hard with numbers that contain hundreds of digits, public key encryption is commonly used just at the beginning of a conversation, to agree on a key ("shared secret") that both parties can use for the rest of the conversation.

Digital Signatures

One interesting aspect of public key encryption, is that it can be used to "sign" a message too. If a stranger wants to send out a signed message, they can do the following:

• Write a message.
• Calculate a hash code (or "fingerprint") of the message.
• Encrypt the hash code using their private key (yes - private key - the reverse of what is normally done).
• Send the unencrypted message and private-key-encrypted hash code out to the world.

When we get the message and the encrypted hash code, we can use the stranger's public key (which everybody has) to "decrypt" it. If we calculate the hash code on the message and it matches the (encrypted by the stranger, then decrypted by us) hash code that was sent with the message, then we can be assured that the stranger was the one who actually wrote the message.

If you combine Digital Signatures and Public Key Encryption, you can write/sign/encrypt/send messages securely in both directions.