The ability to communicate privately, such that only the intended parties have access to the confidential information, is the most well-known capability of cryptography. Our products use encryption to preserve the confidentiality of sensitive data both in-transit across communication interfaces as well as while stored in memory. This blog series will introduce the most commonly used encryption algorithms, explains their differences, and discusses the applications for which each is best suited.
Preventing other people from eavesdropping on our private conversations is not a simple task. Many different methods have been proposed for transforming unprotected information (known as plaintext) into some unintelligible form (known as ciphertext), but few are able to stand up to scrutiny and attacks.
One such approach for transforming a plaintext message into ciphertext is to map each letter of the underlying alphabet to some other letter – a technique known as a monoalphabetic substitution cipher:
|
A |
B |
C |
D |
E |
F |
G |
H |
I |
J |
K |
L |
M |
N |
O |
P |
Q |
R |
S |
T |
U |
V |
W |
X |
Y |
Z |
|
↓ |
↓ |
↓ |
↓ |
↓ |
↓ |
↓ |
↓ |
↓ |
↓ |
↓ |
↓ |
↓ |
↓ |
↓ |
↓ |
↓ |
↓ |
↓ |
↓ |
↓ |
↓ |
↓ |
↓ |
↓ |
↓ |
|
G |
Q |
J |
V |
E |
O |
Y |
A |
S |
C |
U |
K |
M |
F |
N |
Z |
B |
X |
L |
W |
H |
R |
T |
I |
P |
D |
Encrypting the plaintext message “security” using this mapping results in the ciphertext “lejhxswp”, which certainly seems unintelligible. If Alice wished to communicate privately with Bob, she might share this secret mapping with him in person. They could then mail encrypted letters to each other, and easily decrypt them using their shared key (the mapping from plaintext to ciphertext alphabet).
Unbeknownst to Alice and Bob, Eve has been intercepting their encrypted messages and trying to decrypt them, although she doesn’t know the secret mapping. As a first attempt at breaking the cipher, Eve considers trying all possible mappings – a brute force attack. Unfortunately, there are 26! ≅ 288 possibilities, which is far too many for Eve to search through even with the help of a computer. However, brute force attacks are rarely the most efficient ways to break encryption. Eve decides to abandon the brute force attack approach, and instead use her knowledge of the English language to try and break one of Bob’s messages - can you break it? Try picking a mapping for one character at a time[1], perhaps starting by guessing that the stand-alone ciphertext character “I” might be used to encrypt the plaintext character “A”:
ITT VAHR IQG QA WTID UIRKM EISR I GNTT ZAD
Despite the monoalphabetic substitution cipher’s large number of possible keys (a key space of 288), it’s possible for people to decrypt these ciphertexts using nothing but their knowledge of the English language and some trial-and-error on their subway ride to work. Having a large number of possible keys is certainly a necessary, but clearly an insufficient, condition for building a secure encryption algorithm.
A large key space alone does not imply that an encryption algorithm is secure, because brute force attacks (trying all possible keys) are rarely the most efficient way to break an encryption scheme. In the case of the monoalphabetic substitution cipher, knowledge of the underlying language allows an attacker to both reduce the set of possible mappings (e.g., due to a small number of valid words with repeated letters), and also quickly check whether a candidate mapping results in a valid and coherent statement (e.g., does it result in words that don’t exist?).
Ideally, we would eliminate these shortcut attacks so that breaking the encryption scheme without knowing the key is basically impossible. That is, the encryption algorithm should rely on some problem that is hard to solve if you don’t know the key, but that is easy to solve if you do.
The illustration shows a function f(x) that is easy to compute over input x when the evaluator has access to the red key (top arrow), and easy to invert to recover x (middle arrow). However, the function is hard to invert when the red key is not known (bottom arrow).
With access to some function f(x) with this property, Alice and Bob can start to design an algorithm to communicate privately. Their general approach will be to compute f(x) over a plaintext message x using a key that they both know, so that the other can easily invert f(x) to recover the plaintext message x. As Eve doesn’t know their shared key, she won’t be able to recover the plaintext message from the ciphertext.
Since both Alice and Bob share the same key, their information in this design is symmetric, so algorithms that follow this design principle are called symmetric encryption algorithms.
In the next blog, we'll share the solution to the algorithm above and take a look at two of the most common algorithms in this class.
