The art of cryptography has been around since the human race first communicated in written form. In its earliest form, cryptography, or encryption, involved taking written notes and applying a mathematical process to it to make the message unreadable. Then the recipient could use the same method, known only to them and the sender, to recover the message.
When using cryptography, the original text that you want to encrypt is referred to as plaintext. It is called plaintext because, in its original form, it is just text. Once plaintext has been encrypted, it is referred to as ciphertext. The terms plaintext and ciphertext have been around almost as long as cryptography itself, and they are still used today, even though we are not encrypting text on paper, but as bits and bytes on a computer.
Like most technical innovations, cryptography was developed to be a communications method in times of war. Most great innovations came out of armed conflict, and cryptography is no exception.
Ancient Times
If we take a look at the ancient Greeks, they favored a technique for encrypting messages by wrapping paper around a wooden pole of a particular diameter. They wrote the message on the paper while it was wrapped around the pole, and then unwound it and transported the message to its recipient. The recipient would then wrap the paper around another pole of the same diameter, which revealed the message. If the poles were not the same diameter, then the message would not be readable.
This may seem very rudimentary by today’s standards, but at the time, it was very effective. The key for the message wasn’t a passphrase or key, but a wooden pole of a particular diameter.
The Romans popularized an encryption technique called the Caesar cipher. It worked by shifting letters in the alphabet by a certain number of characters, generally three places. This means that in plaintext, A becomes D, B becomes E, C becomes F, and so on. So, the message “meet me at dawn” becomes “phhw ph dw gdzq” when the alphabet is shifted by three characters. To decrypt the message back to “meet me at dawn,” you just perform the reverse operation by shifting three places in the opposite direction.
Both the stick cipher and the Caesar cipher are known as a monoalphabetic substitution cipher , which means there is only one alphabet used for encryption and decryption. Ancient Greeks encrypted and decrypted a message with a pole of a fixed diameter. Romans used a single alphabet. The common key between encrypting and decrypting a message was the number of letters to shift by, three in the example we worked through.
As you can imagine, both of these techniques are very easy to break. With the stick cipher, you can try different diameter poles until you can read the message, and with the Caesar cipher, you try different shift positions until you can understand the message. Although the techniques were effective during their time, it didn’t take long before the ciphers were broken by anyone intercepting the messages.
Another way in which a monoalphabetic cipher can be broken is by performing frequency analysis of the ciphertext. Frequency analysis involves counting the number of times each letter appears in a message. Then by using knowledge and the rules of the English language, you can make certain assumptions—such as vowels like “a” and “e” are the most frequent letters used. Using this knowledge, letters with a high frequency rate can be substituted with the common vowels until you start to see word patterns forming. The longer the ciphertext, the easier this frequency analysis and pattern matching becomes.
The ease of breaking monoalphabetic ciphers meant that new encryption methods needed to be invented. This gave rise to the polyalphabetic cipher . With a monoalphabetic cipher, only one alphabet is used. With a polyalphabetic cipher, multiple alphabets are used. This works by frequently switching alphabets during the encryption process. The reason you do this is to make frequency analysis harder to achieve because the same letter in plaintext might appear as several different letters in ciphertext, which has the effect of flattening out the histogram created when performing frequency analysis. This makes finding patterns in words much harder.
Increasing Cipher Complexity
The first known polyalphabetic cipher is believed to be the Alberti cipher by Leo Battista Alberti from around 1467. This cipher used multiple alphabets to encrypt a message. Alberti switched alphabets many times during the encryption of a message. He indicated that the alphabet should be changed by including an uppercase letter or a number in the plaintext.
In 1470, Alberti developed a cipher disc to make encrypting and decrypting easier. This disc consisted of two circular plates, one larger than the other. The small plate was mounted on the larger plate and could rotate freely. These early cipher discs were made of copper and had the alphabet, in the correct alphabetic order, inscribed on the circumference of the outer plate. The inner plate had an alphabet written on it, but this alphabet was mixed. The outer plate was called the stationary , and the inner plate was called the moveable .
When encrypting a message, the inner disc was turned to a starting position so that the outer disc’s letter A was opposite the inner disc’s letter F. This was the starting position. Encrypting the message began when the person found the plaintext letter on the outer disc and wrote down the corresponding letter from the inner rotor. Not moving the inner rotor during the message encryption would create a standard monoalphabetic cipher, but the disc was designed to rotate throughout the encryption of the message, which made it a polyalphabetic cipher. Turning the disc one position for every letter of plaintext encrypted created a very effective encryption scheme that made frequency analysis very hard to achieve.
Vigenère cipher
Vigenère cipher key stream
To encrypt the message, you looked for the letter from the key along the top of the grid and then look down that column until you reached the row that contained the letter from the plaintext. In this case, the first key letter is s and the plaintext letter is m. First, we find the s along the top of the grid and look down the column until we reach the row that corresponds with m. This gives us the letter e. If we do this for the entire “meetmeatnoon” plaintext, we end up with “eigkqxkxlgsp” ciphertext. Notice that all spaces from the messages have been removed because spaces in ciphertext could give an attacker a clue about the words in the message. The Vigenère cipher was so secure that it was not broken for nearly three centuries.
The Vigenère cipher was very easy to implement, which meant it was easy to use as a field cipher in times of war if used in conjunction with cipher discs similar to the Alberti cipher. A good example of this occurred during the American Civil War. The Confederates used a brass cipher disc to implement the Vigenère cipher successfully.
The main weakness of the Vigenère cipher is the repeating key phrase that is used during the encryption process. If an attacker can guess the length of the key phrase, it is easier to decipher the message because they are treated like an intertwined series of Caesar ciphers, which can be broken individually. With that said, however, it was considered the gold standard of encryption for hundreds of years.
Enigma and Mechanical Ciphers
The ciphers discussed so far are manual ciphers because they are handled by a person with pen and paper. The twentieth century saw cryptography become machine automated. The most famous example is the Enigma Electronic Rotor machine used during World War II.
The Enigma machine (Source: Central Intelligence Agency)
The Enigma machine resembled a typewriter. It featured a series of mechanical rotors, a keyboard, an illuminated series of letters and a plug board that allowed you to insert short cables. The Enigma machine came with a set of five rotors, three of which were used in the machine.
The machine had 26 keys representing each letter of the alphabet. The letters were only uppercase. The keyboard did not contain any numbers, punctuation characters, carriage returns, or a space bar.
The plug board at the front of the machine contained 26 sockets. Each of these sockets had a letter printed next to it. To connect these sockets, ten leads had plugs on each end. If you plugged the leads into two sockets labeled A and Y, it had the effect of swapping the letters around. This meant that if the machine generated the letter A, it was substituted with a Y. The same was also true the other way around. If the machine generated a Y, it was substituted with an A.
Each of the five rotors that came with Enigma was surrounded by a rotating ring that could be fixed into 26 positions, each representing a letter of the alphabet. The rotor locked into the machine with a pin. Out of the five rotors, three could be placed into the machine at any one time. The rotors attached to the machine with a spindle and set to a predetermined position. This predetermined position represented part of the secret settings that set up the machine for encryption.
Once the machine was configured for use, as the operator pressed a key on the keyboard, the rotors turned one step at a time and one rotor at a time. The signal flowed from the keyboard in the plug board, through the rotors, in both directions, and through another lead on the plug board before lighting up one of the lamps, which indicated a letter. The machine operator wrote down this letter to form the encrypted message.
I mentioned that the machine settings form the secret key for encrypting and decrypting a message, but what do these settings look like? The Enigma operator was provided a codebook at midnight on any particular day. The codebook’s settings informed the operator how to configure the machine. The codebook gave five sets of settings each day to form the configuration.
The first setting in the codebook was the date on which the setting was valid. Next, was the rotor order, which stated which three of the five rotors had to be loaded into the machine and in what order. Next, the codebook indicated the rotor position for each rotor. Each rotor had to be turned to point to a specific letter setting. Next, the codebook contained the plug board settings, which told the operator which sets of letters to connect with the ten included cables. This parameter might be set to something like AR, WC, SD, GH, UF, XV, BL, PM, ZO, TY, KN. Once the machine was configured, the operator could encrypt three letters, whose results were included at the start of the message. This worked as a check for the recipient to know the machine had been configured correctly.
The contents of these codebooks were highly classified, and the German operators were under strict instruction that if they were ever in a position to be captured or in a situation where the enemy could seize the machines, they had to destroy the machines and codebooks.
Modern Cryptography
Machines like the Enigma and the many variations of rotor machines were the first era in automating cryptography. After World War II, as we entered the digital age, a new breed of cryptography was needed. This new cryptography had to work efficiently with modern computers, which meant working at a bits and bytes level instead of working with standard alphabets. While it is beyond the scope of this book to cover all developments in this space, let’s cover a few highlights in the advent of modern cryptography.
Symmetric Encryption
In 1973, a German mathematician named Horst Feistel published an article titled “Cryptography and Computer Privacy” in Scientific American magazine. The article discussed a new form of cryptography, which became known as a Feistel network. The Feistel network became the basis for many of the modern cryptographic algorithms in use today. The most popular is the Data Encryption Standard (DES), which was published in 1997 by the National Bureau of Standards (NBS) in a joint venture with IBM, where Horst Feistel worked.
Although the DES standard was set by NBS and IBM, the National Security Agency (NSA) insisted on modifications to the algorithm. The most prominent was changing the key size from 128 bits to 56 bits. NSA enforced modifications to give them a better chance at breaking the algorithm using special computer equipment. The reduction in key size eventually undid DES. Since the key length was reduced to 56 bits, and the Feistel network worked on 64-bit blocks, eight additional parity bits needed to be added to the input data because it is split to feed onto the blocks.
We look at DES as part of the .NET Framework later in this book. The internals of these algorithms are complicated, but the good news is that you don’t need to understand the inner workings to use them.
The DES algorithm is called a symmetric encryption algorithm, which means that the same key used to encrypt data is the same key that is used to decrypt the data. This is similar, in principle, to polyalphabetic ciphers.
In 1997, a competition called the DES Challenge (DESCHALL) ended after 140 days of trying to break a DES algorithm through a massive distributed computing effort on the Internet. It was done by a brute-force attack, trying different key combinations out of a total key space of 72 quadrillion keys. The attack worked by having a single server controlling the keys. This server acted as the brain for the entire operation. Each computer that took part in the challenge had to ask for a range of keys from the key server and then report their result. The key server also logged the unique IP addresses of the machines involved and reported that over 78,000 individual machines took part in the challenge.
Even though DES was cracked and compromised, a variation of DES called Triple DES, or 3DES, uses three iterations of DES to encrypt data. I talk about Triple DES in more detail later in the book.
DES was starting to show its age, and a three-year long public contest was launched in 1997 by the National Institute of Standards and Technology (NIST) to find a new encryption standard. In 1999, five finalists were narrowed down from more than 15 submissions. These finalists were algorithms such as Rijndael, RC6, Twofish, Mars, and Serpent. The submissions had to conform to two main requirements. The block size had to be 128 bits and the algorithm had to be fast and efficient. The winner was the Rijndael cipher, which was developed by two Belgian cryptographers, Joan Daemen and Vincent Rijmen. I talk about the Advanced Encryption Standard (AES) later in the book.
Public and Private Key Cryptography
The modern cryptographic algorithms discussed so far are all examples of a symmetric algorithm, which means that you use the same key for both encryption and decryption. Current symmetric algorithms—like DES, Triple DES, and AES—are very efficient at encrypting large amounts of data, but the main drawback of these algorithms is that it is very hard to share the keys between multiple parties. If you were to use the same key to encrypt and decrypt data, you need to make sure your recipient also has the same key. With this in mind, how do you get that key to someone else? Do you email it? That is not a good idea because it could be intercepted in transit. Do you post the key? Again, this could be intercepted. You could physically give the other person the key, but this is impractical. What you need is a viable alternative, which is where public and private key cryptography comes in.
One of the most common algorithms for this, which is explored later in the book, is RSA. RSA was designed in 1977 by Ron Rivest, Adi Shamir, and Len Adleman at MIT. The algorithm’s name, RSA, is the initials of each of their surnames.
Whereas ciphers like DES and AES are algorithmic by nature and designed to work with large amounts of data, RSA is mathematical by nature and is based on modular arithmetic. They keys are based on prime numbers, and RSA’s security comes from the fact that it is currently impossible to factor a large prime number into its constituent primes. An excellent way to build a mental model of this is that the public key is a huge prime number and the private key contains the numbers that are multiplied together to form the public key.
Anyone can know the public key; hence, the name public; the recipient only knows the private key. You encrypt data with the recipient’s public key, and the recipient uses their private key to decrypt the message.
There is a limitation to RSA, though, in the amount of data you can encrypt in one go. You cannot encrypt data that is larger than the size of the key, which is typically 1024 bits, 2048 bits, or 4096 bits. You could break down your data into smaller chunks and encrypt it, but this is inefficient. One of the topics that we tackle later in the book is using RSA and AES together to build a hybrid encryption scheme.
If you wish to learn more about the history of cryptography, I can recommend two books. The Code Book by Simon Singh (Anchor, 2000) is a fairly short book, but it is a fascinating read. If you want to go into a lot more depth, then I recommend The Code-Breakers by David Kahn (The Macmillan Company, 1967). This book goes into a tremendous amount of depth about the history of cryptography.
Why Is Cryptography Important?
Cryptography allows people to have the same confidence they have in the real world in the electronic world. It enables people to do business electronically without worry of wrongdoing by others. Every day, millions of people interact electronically, whether it is through email, ecommerce (on sites like Amazon), or on ATMs or cellular phones. The significant increase of information transmitted over the Internet or on private networks has led to an increased reliance on cryptography.
Cryptography makes the Internet more secure and the safe transmission of electronic data possible. For a website to be protected, all the data transmitted between the computers must be encrypted. This allows people to do online banking and online shopping with their credit cards, without worrying that any of their account information is being compromised. Cryptography is essential to the continued growth of the Internet and electronic commerce.
Examples of Modern Cryptography
We have talked a lot about how cryptography has been used in times of war, but what are some of the uses for modern cryptography? First is online shopping. Whenever you buy something from a website like Amazon, your transaction is done behind SSL, and your payment card information is encrypted. This is a level of protection that everyone has come to expect. Shopping online has become something that people take for granted these days, and it is cryptography that helps to ensure that shopping experiences are done safely.
The next example is authenticating with different systems or websites. To access various systems, you need to prove who you are. This is commonly done by authenticating yourself with a username and password. We cover secure password passing later.
Every time you put your bank card into an ATM and enter your pin, cryptography is used behind the scenes. This includes validating the pin number and authenticating the user. The communication between the ATM and the bank is also encrypted to protect a customer’s transaction. Because the bank is issuing cash to a customer, there is a good deal of integrity checking in play, and even non-repudiation, so that once money has been released, the customer cannot deny that cash was given to them.
These days, everyone has a cell phone and wants to make calls that are private. Modern digital cell phones employ cryptography to encrypt the phone call to help make this possible. Modern smartphones are also powerful computers in their own right. They connect to the Internet either via a cellular network or over Wi-Fi. As with a desktop computer, smartphones also use cryptography algorithms like SSL to protect traffic flowing on the Internet.
Another example of cryptography is the rise of the digital currency like Bitcoin. Bitcoin is a peer-to-peer payment processing system and digital currency in which users transact directly without an intermediary. Transactions are verified by network nodes and reported in a public distributed ledger called a blockchain . Bitcoin is commonly referred to as a cryptocurrency , because cryptography is at the heart of how the currency works.
A final example of cryptography is electronic voting. The concept of election vote verification through cryptography has emerged in academic papers to introduce transparency and trust in electronic voting systems. It will allow voters to verify that their votes have been recorded and counted correctly.
The examples of cryptography shown in this chapter are just a few in the real world. The one thing that you can be sure of is that cryptography and encryption are everywhere, so it is essential for developers to understand some of the cryptography tools available to them in their platform of choice.
The Four Pillars of Modern Cryptography
In modern cryptography, there are four core problems or pillars to solve: confidentiality, integrity, authentication, and non-repudiation.
Confidentiality
Confidentiality is commonly associated with cryptography and encryption. It is where you take data and encrypt it to be in a form that cannot be read by someone else. There are lots of different cryptographic algorithms in use today, and in this book, we look at DES, Triple DES, AES, and RSA.
Integrity
Data integrity is about maintaining and proving accuracy and consistency in the data sent between two parties. This means that if someone sends data to a third party, that individual should be able to detect if the data has been corrupted or tampered with in any way. I cover some different cryptography primitives that you can use to help enforce data integrity, including hashing algorithms such as MD5, and Secure Hash Algorithms, such as SHA-1, SHA-256, and SHA-512.
Authentication
Authentication is about establishing the identity of a person or system sending a message. A good example is with SSL certificates on a web server proving the identity of the server that you wish to connect to. The identity is authenticated by use of a cryptographic key. A less secure key means that there is lower trust between two parties. Authentication is also commonly used by everyone when they enter their username and password to gain access to a system. Your Facebook or Twitter account is an excellent example of this. To use those systems, you have to authenticate yourself with the Facebook or the Twitter website to prove who you are. We look at authentication when we discuss hash message authentication codes (HMACs) later in the book.
Non-Repudiation
Non-repudiation is about proving that someone has carried out an action or signed a document. A signature on a paper contract is a good example of this. If a contract has been signed and witnessed, then that person cannot deny having signed the agreement. This metaphor also carries into the digital world. In this book, I cover digital signatures that use the RSA cryptographic primitive.
Summary
In this chapter, we explored the history of cryptography through the ages. Ever since humans could communicate in writing, there has been a desire to communicate in code so that enemies cannot read intercepted messages. In the earliest days, encryption was based on simple alphabets, and then substitution ciphers, but in the digital age, complex symmetric and asymmetric encryption algorithms are available.
In this modern age, throughout your day you use encryption and cryptography— when you use your phone or your secure Internet connection, or buy goods on the Internet. Cryptography is fundamentally important to the very fabric of our lives as we rely on it to keep our data safe and secure.