Introduction to cryptography

Cryptography is "the art of writing in secret characters". Encrypting is the act of translating a 'normal message' to a message written with 'secret characters' (also known as the encrypted message). Decrypting is the act of translating a message written with 'secret characters' into a readable message (the unencrypted message). It is, by far, one of the most important areas in computer security, since modern encryption algorithms can ensure all three pillars of a secure conversation: privacy, integrity, and authentication.

Key-based algorithms

In the previous page we saw a rather simple encryption algorithm which simply substituted each letter in a message by the next one in the alphabet. The decryption algorithm was, of course, substituting each letter in the encrypted message by the previous letter in the alphabet. These kind of algorithms, based on the substitution of letters, are easily cracked. Most modern algorithms are key-based.

A key-based algorithm uses an encryption key to encrypt the message. This means that the encrypted message is generated using not only the message, but also using a 'key':

The receiver can then use a decryption key to decrypt the message. Again, this means that the decryption algorithm doesn't rely only on the encrypted message. It also needs a 'key':

Some algorithms use the same key to encrypt and decrypt, and some do not. However, we'll look into this in more detail in the next page.

Let's take a look at a simple example. To make things simpler, let's suppose we're not transmitting alphanumerical characters, only numerical characters. For example, we might me interested in transmitting the following message:

1 2 3 4 5 6 5 4 3 2 1

We will now choose a key which will be used to encrypt the message. Let's suppose the key is "4232". To encrypt the message, we'll repeat the key as many times as necessary to 'cover' the whole message:

1 2 3 4 5 6 5 4 3 2 1

4 2 3 2 4 2 3 2 4 2 3

Now, we arrive at the encrypted message by adding both numbers:

  1 2 3 4 5 6 5 4 3 2 1

+ 4 2 3 2 4 2 3 2 4 2 3
  5 4 6 6 9 8 8 6 7 4 4

The resulting message (54669886744) is the encrypted message. We can decrypt following the inverse process: Repeating the key as many time as necessary to cover the message, and then subtract the key character by character:

  5 4 6 6 9 8 8 6 7 4 4

- 4 2 3 2 4 2 3 2 4 2 3
  1 2 3 4 5 6 5 4 3 2 1

Voilà! We're back at the unencrypted message! Notice how it is absolutely necessary to have the decryption key (in this case, the same as the encryption key) to be able to decrypt the message. This means that a malicious user would need both the message and the key to eavesdrop on our conversation.

Please note that this is a very trivial example. Current key-based algorithms are much more sophisticated (for starters, keys are at least 128 bits long, and the encryption process is not as simple as 'adding the message and the key'). However, these complex algorithms are based on the same basic principle shown in our example: a key is needed to encrypt/decrypt message.

Symmetric and asymmetric key-based algorithms

The example algorithm we've just seen falls into the category of symmetric algorithms. These type of algorithm uses the same key for encryption and decryption:

Although this type of algorithms are generally very fast and simple to implement, they also have several drawbacks. The main drawback is that they only guarantee privacy (integrity and authentication would have the be done some other way). Another drawback is that both the sender and the receiver need to agree on the key they will use throughout the secure conversation (this is not a trivial problem).

Secure systems nowadays tend to use asymmetric algorithms, where a different key is used to encrypt and decrypt the message. Public-key algorithms, which are introduced in the next page, are the most commonly used type of asymmetric algorithms.