3.3 Key space

The security of an encryption algorithm is subtly related to the notion of key space. Simply put, a key space refers to encryption/decryption key pairs. The size of a key space determines how many of these pairs are available in a cryptographic algorithm (recall that in a symmetric algorithm, the encryption and decryption keys are the same, but in asymmetric cryptography they are different).

Clearly, the key space must be sufficiently large to prevent brute-force attacks (by means of an exhaustive search). But it would be very dangerous to assume an encryption algorithm is secure based on its key space size only.

A case in point: consider a simple type of cipher, the so-called polyalphabetic substitution ciphers, where the plaintext letters are substituted by ciphertext letters using multiple substitution alphabets. If the plaintext letters from the Roman alphabet are always substituted by a letter coming from the same alphabet, there are 26! possibilities for doing this (the number of possible permutations of the 26 letters). Consequently, a polyalphabetic substitution cipher that uses three distinct alphabets has a key space size of (26!)3. This is approximately 7 × 1079 possible keys.

Assume someone comes up with an algorithm (a program) for a brute-force attack on a polyalphabetic substitution cipher where testing a single key hypothesis is computationally equivalent to a single floating-point operation. Then, searching half of the preceding key space would require 3.5 × 1079 operations (a typical assumption in cryptography is that an attacker doing an exhaustive key search will – on average – need to search half of the key space before they discover the right key).

As of June 2022, the TOP500 project, which ranks and details the 500 most powerful non-distributed computer systems in the world, lists Frontier as the currently fastest supercomputer in the world. Frontier, which was built by the Cray corporation for the US Department of Energy’s Oak Ridge National Laboratory, performs 1.102 × 1018 floating-point operations per second.

Testing half of our key space on Frontier would take approximately 3.1 × 1061 seconds. This equals to roughly 0.86 × 1059 hours, or 0.35 × 1058 days, or 0.1 × 1056 years, that is, 1046 billion years. To set this into perspective, today’s astronomers estimate the age of the universe (the time elapsed since the Big Bang) to be about 14 billion years.

Clearly, the key space size of a polyalphabetic substitution cipher is too big to break using brute force. Such ciphers, however, can be easily broken using statistical analysis techniques.