Asymmetric and Symmetric Encryption

Five Essays on Cryptography (3/5)

Cryptography is one of the core disciplines that we use to protect digital information today. It is part of the larger area of Information Security which has become recently one of the most discussed topics across industries. This series of five articles is aimed at those who would like to have an overview of the domain of cryptography, a bit of its history, and a grasp on important concepts and recent developments.

All articles in this series

• 1 Cryptography is Interwoven in our Daily Life
• 2 A Tool for Information Warfare Becomes a Field of Science
• 3 Asymmetric and Symmetric Encryption
• 4 Cryptographic Hashes and Credentials Management
• 5 The Use of Cryptography in our Economy (to appear)

Special thanks to my friend Philipp Jovanovic (Twitter @Daeinar) for sharing his expert opinion on this series of articles.

Comments, Feedback: Laurent Balmelli (Twitter Laurent Balmelli)

Modern Encryption

In this article I explore the modern usages of encryption in more details. In particular in the previous article I introduced one of the core issues when using encryption for confidentiality: the need to agree on a shared secret, i.e., in practice a key, in order to be able for two parties to encrypt and decrypt a secret communication.

When I reviewed the example of the Vigenere cipher in the previous article, I explained that keys were words chosen by the parties wanting to communicate. In modern cryptography, a key is typically represented by a series of hexadecimal values. In practice when people choose a key to encrypt their data, they do it by picking a passphrase that is then transformed into a key through a derivation function.

In a symmetric encryption scheme, once a key has been decided by the parties, the encryption of the plain text can now begin.

The process can be really complicated, but it remarkably makes use of only simple mathematical operations. In the case of the Advanced Encryption Standard (AES) algorithm that I mentioned in article 2, the key is applied to blocks of information (for example of size 128 bits, i.e., 16 bytes). In this case, the key will also be of size 128 bits. Hence any encryption operation will combine a block of information with a key and the mathematical operations used are typically Boolean operations acting directly on the bit representation of the information.

There are many different types of schemes that are in use today with different properties. Many of the schemes are implemented and used jointly depending on the applications (a good book to understand the differences is Serious Cryptography: A Practical Introduction to Modern Encryption, Jean-Philippe Aumasson). Combination of the schemes are often referred to as cipher suites and your typical internet browser (more precisely the components that implement secure communication) supports many of them.

The Key Exchange Problem

We know now that using encryption to secure data required both parties to agree on the key, i.e. a shared secret. This step has been a nagging issue in the world of cryptography until a discovery in 1976 by two Stanford students Whitfield Diffie and Martin Hellman. They invented a mathematical method to agree on a shared secret over an unprotected communication channel.

Using their approach, by only exchanging public values (i.e. values that can be published) and choosing independently random ones, two parties can compute separately values leading to the same key. The key is then used to secure their communications. They invented what they termed themselves as a public key distribution scheme.

Note that it was revealed later that a similar discovery was made by researchers at GCHQ (in particular James H. Ellis, see here), i.e., the national security agency in the United Kingdom, but it was kept classified. Diffie and Hellman received the Turing award in 2015 for their invention. They also recognized Ralph Merkle as a contributor: Merkle introduced the idea of public-key cryptography in 1974 to what is known now as Merkle puzzles.

Let’s see now how this is done with a small example: The first party, named Alice, picks to public values p and g and a private one, a. Remember that public values can be revealed but the private one should be kept secret.

She computes the value of A=g^a mod p, where ^ denotes the exponentiation and mod the modulo operator. She sends p, g and A to Bob, the second party and recipient.

Bob picks a private value b, and calculates B=g^b mod p and sends B to Alice. Again here the value B is not private. Now Bob and Alice have enough information to derive the same encryption key.

Alice will calculate the key as K=B^a mod p and Bob will derive the same key as K=A^b mod p.

Note that in order to find the same key, the above calculation will not work with any numbers p and g. The number p has to be a particular prime number and g is referred to as the base number. For the above process, working examples are p=23, g=5, a=6 and b=15. In this case, the resulting K value is 2. Obviously to make this process impossible to brute-force (i.e. by trying all possible values), we need to work with much larger numbers. More on that below.

This invention was expectedly received as a breakthrough by the scientific community, but this is not the only reaction that it spurred. The students also received a letter from the US government (more precisely the NSA) stating that publishing the results will be deemed legally equivalent to exporting controlled arms to a hostile foreign power. But Hellman defied the threat of prosecution by presenting its students’ paper anyway (and did not end up in prison). A short historical recollection of these events is in recounted in Chapter 24 of the excellent book of Tim Hartford, “50 Inventions that Shaped the Modern Economy”. Check also the related article “Keeping Secrets”, published online by Stanford magazine in Medium.

It is however another team of researchers that made their scientific results practical: Three researchers at MIT (Rivest, Shamir and Adleman) turned Diffie-Hellman discovery into a practical technique referred to as RSA Cryptosystem. It became the first public key encryption scheme.

The RSA Algorithm and Notions of Security

As I wrote above, the breakthrough discovery by Diffie and Hellman was made practical a year later by Rivest, Shamir and Adleman from MIT. Their work led to the first practical asymmetric encryption scheme.

So far in this series of articles, I only discussed symmetric encryption schemes (such as Caesar, Virgenere, AES), i.e., ones that use the same key for encryption and decryption. In the case of asymmetric encryption schemes, two keys are needed: a public and a private one.

The private key is, as the name indicates, to be kept secret in the same manner Alice and Bob choose a and b in the example that we discussed above. In that respect the private key is similar to a password. In contrast the public key can be shared with anybody and is used by anyone who would like to communicate secretly with the owner of the corresponding private key. Hence private and public keys are generated in pairs, i.e., they are linked to each other by the mathematics that underlie the RSA algorithm.

There are two main scenarios around how to use a public-private key pair.

The first one goes as follows: If you would like to communicate confidentially, i.e., using encryption with somebody, you must get hold of his public key (which is available to anybody). You would use then this key to encrypt your message. The particularity of this type of algorithm (i.e. asymmetric) is that the resulting message can only be decrypted using the private key. This is where the asymmetry is coming from. Hence the holder of the private key is the only person who will be able to access to the message.

In the second scenario, it is a private key that is used first. Using her private key, the owner can sign a message (or any type of information), i.e. produce a digital signature, in order to prove that she is the issuer of that message, i.e., to prove its authenticity. Then anybody who wants to verify authenticity can do it by verifying the signature using the public key of the owner. This signature verification process can be used today in a court of law to demonstrate that the private key of the holder was used to sign the message, i.e., that fact cannot be legally repudiated (because the key is private).

The security of the RSA algorithm relies on the so-called factoring problem. In this case the problem at stake is to find two (large) primes numbers that result in the product of a (larger) number. This is the brute-force search activity that I was referring to at the beginning of this article. As I noted before: to make this problem impossibly difficult with today’s computer, we need to pick up numbers that are large enough. Today large enough numbers should be over 1024 bits in size and are typically chosen to be 2048 to 4096 bits. Note that such key sizes are intended for an asymmetric scheme such as RSA. In contrast, due their difference in functioning, symmetric schemes use keys that are typically much smaller, e.g., 128 bits for AES are sufficiently secure today. But we should refrain to compare key sizes between schemes since properties derived from them and usage are different.

The RSA algorithm is used in many practical applications today that I will discuss in the remainder of this series of articles. For example, RSA keys are used to connect to computers, i.e., there are used to replace passwords. More generally, RSA keys are also used all over the web, for example in some versions of the https protocol and to authenticate owners of websites (more about this in the next articles.) In brief, it is an essential component that helps us to secure data today.

The Limitations of Asymmetric Cryptography

We have seen so far that asymmetric and symmetric cryptography are two distinct approaches to encryption (and signing). Their security guarantees are also based on different principles: In the case of symmetric encryption, encrypted information should be indistinguishable from random bits. Hence, in this case such a property provides a measure of security. In contrast, guarantee of security in asymmetric encryption (in the RSA approach) is rather based on the difficulty of factoring large numbers. Note that, since there are other ways to implement asymmetric schemes, others might have different constraints when assessing the level of security. Hence to be sufficiently secure, the numbers used for encryption (i.e., the keys) should be sufficiently large to provide enough security (see also the explanation of key sizes above), but size varies based on the approach.

However an important differentiation of these two encryption schemes is their computational efficiency. This is what differentiates them the most in their usage.

The complexity of mathematical operations used in asymmetric encryption makes it inadequate to use for anything else than the communication of short messages. In contrast, it can be used to exchange symmetric keys securely. For example, a transmission protocol can perform the exchange of a symmetric key during an handshake session between two parties. Then, because symmetric encryption is much more efficient computationally (as noted at the beginning of this article), the rest of the communication can be done in computationally efficient manner using the exchanged symmetric key.

This is all for this article! In the next article, I will introduce cryptographic hashes as well their usage for credentials management and in block chains. Hash functions are an essential part of the cryptographer toolbox and used in particular for the signing operation that I introduced here. Thanks again for following this series.

Check my other articles about security, technology and societal aspects.