This post is part one of a series on an introduction to applied cryptography. While a PhD in math is not required to understand this material, it is helpful if you know some university level math (elementary linear algebra / number theory, calculus, and discrete math). It is also assumed that you have a basic understanding of network security and programming. Part one is going to cover an overview of crypto, symmetric, asymmetric ciphers and historical ciphers. Further posts are going to delve into more advanced topics such as elliptic curves and modern encryptions schemes such as AES 256.
What is cryptography? Cryptography is the science of keeping text secret. Cryptanalysis, on the other hand, is the process of trying to break secure cryptosystems (Alan Turing is a famous cryptanalysis because of his research during World War 2). We will mostly be focusing on cryptography and not cryptanalysis in this series. If you are interested in cryptanalysis, view the references at the end of this article for more information. Let’s start with first going over some definitions that are commonly used.
In symmetric algorithms, two people have an encryption and decryption method, and share a secret key. To give a better understanding, let’s take a look at Alice and Bob. Alice and Bob want to communicate over an insecure channel. Now let’s look at Oscar, who wants to eavesdrop on this channel. Symmetric algorithms offer a solution to this problem; a key has to only be generated once between Alice and Bob, and then can be used for more communications. PGP (Pretty Good Privacy), for example, uses a hybrid encryption scheme that first generates a symmetric key and then uses an asymmetric key to protect that information.
Asymmetric (aka Public-Key) Algorithms:
Asymmetric algorithms work a lot like symmetric key algorithms. As with symmetric cryptography, a user has a public key and secret key. Unlike asymmetric keys, symmetric keys use different keys for encryption and decryption. Asymmetric algorithms are used in digital signatures, key establishment, and classical data encryption. Also, note that the asymmetric / symmetric algorithms in the two approaches have different characteristics and are not directly comparable with each other.
Key distribution: Sometimes called a key distribution center (KDC), it is how we convey keys to those who need to establish a secure communication.
Key management: Like the term implies, key management answers the question on given a large amount of keys, how we store them and make them as needed.
One of the most simplest ciphers is called the Caesar cipher. The Caesar cipher is said to have been used by Julius Caesar to communicate with his army. He is one of the first persons to have used encryption for the sake of securing messages. In the Caesar cipher, each letter is shifted. If you had the text “RETURN TO ROME”, the encrypted text would be “UHWXUA WR URPH”. The example shows that the “R” is shifted to “U”, the “E” is shifted to “H”, etc. It would be useless if an enemy intercepted the message because only Caesar’s generals could read it. Caesar ciphers can easily be broken even in a ciphertext-only scenario. In breaking Caesar ciphers, two situations can be considered: 1) an attacker knows or guesses that some sort of simple substitution cipher has been used, but not specifically that it is a Caesar cipher; and 2) an attacker knows that a Caesar cipher is in use, but does not know the shift value.
The next cipher we are going to talk about is called the substitution cipher. The substitution cipher is a cipher where each letter of the plaintext is replaced by another symbol. While symbols that replace the text are usually letters of the alphabet, the text can be replaced by anything, such as hieroglyphics. The process to crack a substitution cipher is similar to cracking a Caesar cipher, because a Caesar cipher is a variant of the substitution cipher.
The final historical cipher we are going to discuss is the German Enigma Machine. It is most well known for its contributions during WW2 on the German’s side. The Enigma Machine was based on a system of three rotors that substituted ciphertext letters for plain letters. These rotors would spin in conjunction with each other, which acted much like a Caesar cipher. After a letter was typed into the keyboard on the machine, it was sent through the rotor which would then shift it according to its preset settings. What made Enigma so powerful was at the time only one rotor would be spinning, while the rest would be stationary until the first rotor had completed 26 cycles (the number of letters in the alphabet). The cycle would continue like this for the entire length of the message. After all the rotations were finished, the output would be a shifting shift. An s could be encoded as a b in the first part of the message, and then as an m in another part of the message. This allowed for around 17,576 (26x26x26) possible positions of the rotors.
For one to decode a message, one would need to have the initial settings of the rotors, and then put the ciphertext through the machine to find the plain text. Each Enigma operator had a book detailing the settings for each day. This obviously presented a weakness, because if anyone could figure out the settings of the rotors were for a particular day, they would be able to decode that day’s messages (assuming they had an Enigma machine themselves). The Enigma cipher was eventually broken by Alan Turing and a team of scientists during the war. It is speculated that if the Enigma machine was never broken, that the war would have turned out much differently.
We have now briefly covered the basics of cryptography. If you wish to learn more, there are links at the end of this article. Part two of this series will cover modular arithmetic, block ciphers and stream ciphers. If you have any questions, you can contact me (64Bytes) at [email protected].
References / more links:
Bruce Schneier on Security: Website of accomplished cryptographer who writes about crypto and network security.
CS255: Introduction to Cryptography: Stanford course on cryptography