The basic ideas of cryptography

Secret communications have a long and fascinating history. You can read about it, for example, in ''The Code Book'' by Simon Singh or in David Kahn's ''The Codebreakers''. But only less than half a century ago, a dramatic change in this field has happened – it was the creation of public-key cryptography. Public-key cryptosystems play an enormous role in the modern computer world.

But what does ''public key'' mean? And what is the opposite: ''private key''?

Symmetric and asymmetric cryptosystems: a first acquaintance

First, let me introduce to you three characters traditionally appearing in cryptosystems' descriptions. Alice and Bob are two people wanting to communicate confidentially. But their adversary, Eve (a hint for the word ''eavesdropper''), intercepts their messages and tries to read them.

For thousands of years, all codes and ciphers were based on the assumption that Alice and Bob share a secret key that Eve does not possess. Alice uses her secret key to encrypt her message, Bob uses the same secret key to decrypt the message, and poor Eve, not knowing the secret key, is unable to perform the decryption. These were symmetric, or private key, cryptosystems. Their main disadvantage is that Alice and Bob need to exchange the secret key before they can get started.

In the 1970s, there appeared a revolutionary and seemingly counterintuitive idea of asymmetric (public key) cryptography. In a public-key cryptosystem, every person (for example, Bob) has two keys, a public encryption key e and a private (secret) decryption key d. Bob publishes his public key openly so that anybody can send him an encrypted message. But only Bob, knowing his private key, is able to decrypt these messages.

Of course, such construction would provide a lot of advantages. For example, Alice could send Bob an encrypted message even if they have never previously met. But how can we construct a public-key cryptosystem? It turns out that such systems can be based on hard computational problems. More precisely, one looks for a computational problem that is initially hard to solve, which becomes easy to solve if one knows some extra piece of information.

Nevertheless, symmetric cryptosystems have not disappeared. Indeed, they are more important than ever, since they tend to be significantly more efficient (i.e, fast) than asymmetric ones. Thus in practice, if Alice wants to send Bob a long message, she first uses an asymmetric cryptosystem to send the key for a symmetric cryptosystem, and then she uses the symmetric cryptosystem to encrypt her message.

What is modern cryptography based upon?

Modern public-key cryptography relies on many areas of mathematics, especially number theory, abstract algebra (groups, rings, fields), probability, statistics, and information theory. We will introduce to you just a small piece of all this math, mostly belonging to the elementary number theory.

The most efficient modern private key cryptosystems, such as AES, repeatedly apply to the message some mixing operations that are hard to unmix without the private key. But the connection with underlying mathematical ideas is somewhat less obvious here than it is with public-key cryptosystems.

A bit of formalization

In every technical area, especially the one with a strong mathematical background, some formal notation will be useful. So let's think about what the processes of encryption and decryption are from a mathematical point of view. Encryption transforms the message from some readable form (known also as plaintext) to some unreadable form (ciphertext). So it is, in fact, a function from the set of possible messages (for example, the set of binary strings – those consisting only of 0 and 1 – of certain length) to the set of possible ciphertexts and we may write $E(m) = c$, where $m$ stands for the message, $c$ for ciphertext, and $E$ for the encryption function.

What is decryption, then? This is another function $D$, which we apply to the ciphertext and obtain some readable message: $D(c) = m'$ .. Of course, we require that after decryption we have the original message, that $m' = m$. Imagine that Alice encrypted ''Number theory is useful for cryptography'' and Bob decrypted "I love you"! Or vice versa – decide yourself what is better. So, two functions $E$ and $D$ must be connected so that always $D(E(m)) = m$. In other words, $D$ must be an inverse function of $E$.

Conclusion

Now that we have introduced ourselves to the basics of cryptography we understand how some of the fundamental processes of encrypted message exchange work. Let's quickly go over the main points:

• Symmetric cryptosystems involve two people who both possess the same key to encrypt and decrypt their messages.
• Asymmetric cryptosystem implies that each person has two keys: a private key and a public key. The public key is available to everyone so that any person can encrypt a message using the public key of a receiver and send it to them, then only the recipient can decrypt it via the private key.
• $E(m)$ is a function that converts plaintext into the ciphertext and $D(c)$ is a function that converts the ciphertext back into the original plaintext, hence $D(c)$ is an inverse of $E(m)$.