Cryptosystems and Encryption Algorithms

Key lengths and keyspaces

Before proceeding further, it’s important to understand various concepts relating to the number of possible different decryption keys in a cryptosystem, which we refer to as the size of the keyspace. This is important because one strategy for an attacker of a cryptosystem is to try to determine the decryption key. That’s why the size of the keyspace is something the attacker will be interested in. The majority of cryptosystems have a fixed size of the keyspace. However, it is worth noting the following:

• Some cryptosystems can provide a choice of size of the keyspace. For example, the encryption algorithm AES can be used in three different ‘settings,’ each of which has a different size of the keyspace. While a cryptosystem using AES may select just one of these ‘settings,’ it could also support more than one.

• For some cryptosystems, the size of the keyspace is highly flexible. For example, both the Vigenère cipher and one-time pad have keyspaces whose sizes can (at least in theory) be made arbitrarily large.

Since the size of the keyspace in modern cryptosystems can be enormous, we tend to focus attention on the length of a cryptographic key (often also referred to as the size or strength of the key), which is the number of bits it takes to represent the key. For example, the cryptographic key 10011010 has a length of eight. The length of a cryptographic key is referred to more commonly than the size of the keyspace.

Regarding the relationship between key length and the size of the keyspace, there is an important difference between symmetric and public-key cryptosystems.

Symmetric cryptosystems

Regarding the relationship between key length and the size of the keyspace, there’ is an important difference between symmetric and public-key cryptosystems. By and large, the length of the key can be used to determine the size of the keyspace. If the key length is $k$ bits (which we sometimes refer to by saying we have a $k$-bit key), then the size of the keyspace is $2^k$, since there are two choices (0 or 1) for each of the bits of the key. Therefore, the number of possible keys is:

$$2 \times 2 \times \cdots \times 2 = 2^{k}$$

We used the caveat ‘by and large’ because some symmetric cryptosystems specify that particular keys should not be used, which is why the keyspace is sometimes slightly smaller than $2^k$… Also, some symmetric cryptosystems use keys that contain redundant bits (for example, while DES keys are normally 64 bits long, 8 of these bits are redundant, and hence the effective key length is only 56 bits).