A Brief Timeline in Cryptography
As already mentioned, the earliest known use of cryptography dates from 1900 BCE, when non-standard hieroglyphs were carved into monuments in Egypt. However, these hieroglyphs are not considered to be a serious attempt at hiding information by experts. The main purpose of these is thought to be mystery, intrigue, or even amusement for onlookers.
Other examples of early attempts at cryptography include simple versions of letter substitutions, discussed later on in this article, and some very ingenious other methods. One of these methods was the so-called ‘skytale’ cipher used by Spartans in the 5th century BCE to send messages between Greek warriors. In this method, a thin sheet of papyrus was diagonally wrapped around a staff and the message was written down the length of the staff on the sheet of papyrus. Afterwards,the papyrus was unwrapped and sent. In order to read the message the papyrus would have to be wrapped around a staff of equal diameter. Another well-known tale regarding hidden messages also originates from Greece. In this case, Demaratus (a Spartan king) wrote a warning about a forthcoming attack on Greece from Persia on the wooden backing of a wax tablet and then applied the beeswax surface. The message was thus concealed in the wax tablet, appearing to be empty when checked by Persian soldiers. This is, however, more an example of steganography than cryptography. Steganography is the art of hiding and concealing written messages, such that no one but the sender or receiver even suspects their existence.
Another method is the Polybius Square. The letters of the alphabet would be laid out in a five by five square with i and j occupying the same square. Rows and columns would both be numbered, such that each letter had a unique pair (row, column), as can be seen in figure 1. Decryption is easily done by mapping the pairs back to the corresponding letters. This system was unique in the sense that it was the first to decrease the symbol set from 26 to 5. Therefore this method not only encrypts the message, it also makes sending it by use of torches or hand signals much easier.
Monoalphabetic Substituion
Monoalphabetic substitution is a method in which each letter in the alphabet is paired with another to which it will be encrypted. The earliest example of letter substitution is a Hebrew ciphering method used in the bible. This method is called ‘atbash’. It maps the first letter of the alphabet to the last, the second to the second to last, etcetera.
Julius Caesar is also well known for using monoalphabetic substitution. The system of cryptography he used, called the Caesar Cipher, shifted each letter two places further through the alphabet (e.g. A shifts to C and M shifts to O). This is closely related to what most of us have done in primary school, where you would have written the alphabet on the edge of two circular pieces of paper. When laid on top of each other you could turn one and then obtain a shift letter substitution of any number of places.
Cryptanalysis
Cryptanalysis is the practice of decrypting encrypted messages, without knowing the cipher used. The Arabian civilization was the first to discover anything significant in this field. Two Arabic authors are well known for their writings on cryptography and cryptanalysis, namely Al-Kindi and Ahmad al-Qalqashandi. Al-Kindi was the first to write on frequency analysis, a method for solving ciphers, which is still used today.
This method works for simple letter substitution ciphers, such as the monoalphabetic substitution method we discussed earlier. The method involves counting the frequency of each letter in the encrypted text. Besides the encrypted text, you also need a regular text in the same language as the encrypted text, of which you count the frequency of letters as well. Using this average frequency you can quite easily decrypt the encrypted text.
Of course, once cryptography became more and more important in the Middle Ages, more people discovered frequency analysis and consequently also the main weakness of a simple letter substitution cipher. Therefore, a more —› sophisticated method to encrypt information, called polyalphabetic substitution, was developed by Leon Battista Alberti. He was also referred to as ‘The Father of Western Cryptology’, because of his work in developing this method. The basic idea of his method was that in order to render frequency analysis useless, a different substitution cipher should be used every few words. However, he had not yet thought of a suitable idea on how to choose which cipher to use and when to switch between ciphers. This made communicating using his cipher very difficult, unless you could first secretly decide on these matters.
Polyalphabetic Substitution
Giovan Batista Belaso extended this method by coming up with a system on how to choose a cipher. First of all, you need a list of ciphers to choose from. To do this you must generate one random cipher (i.e. a random ordering of the alphabet). Using this cipher you can create 25 more by simply shifting the cipher to the left and right. By construction you now have 26 different ciphers each starting with a different letter (i.e. A is mapped to a different letter in each sentence). Now you might wonder how you determine which cipher you use to encrypt a sentence, a word or even a single letter. For this Belaso invented a keyword. This word would be written repetitively above the regular text, therefore assigning one of its letters to each letter of the regular text. The cipher that starts with this ‘keyletter’ will be the one used to encrypt the respective letter of the regular text. In this way it is close to impossible to decipher the text without using the keyword or the ciphers, let alone when not knowing either.
Mathematics
The method by Belaso was used as a basis for most encrypting methods throughout the centuries, until mathematics started to take a more prominent role in cryptography. For mathematics to become involved in cryptography, a translation from text into numbers or binary digits is needed. This is usually done by using the ASCII-codes for characters.
When this conversion is done, the problem simplifies to making sure the person you want to send a message to can figure out the corresponding numerical version. I will discuss one of the main methods here, the ‘Diffie-Hellman key exchange’, which is a method for agreeing on a key or cipher.
Diffie-Hellman
First of all, it is important to know what the modulo operation is. Although many of you will probably already know what it is, it is so fundamentally important to this method that I will explain it. The modulo operation gives the remainder of division of one number by another. For example, 8 mod 6 equals 2 and 24 mod 7 equals 3.
Now suppose Alice and Bob want to agree on a cipher with which they can communicate. Then they first of all need to agree on a prime number, p (in practice usually very large), and a base, g (usually 2, 3 or 5). Both of them will also choose a secret integer, a and b respectively, which they do not tell to anyone, each other included. These secret integers are also called private keys. Now both of them will compute their public keys, by A = ga mod p and B = gb mod p. They send these public keys to each other and are therefore known to anyone who cares enough to watch their communication.
Alice can use Bob’s public key together with her own private key to obtain the message they want to share. Bob can do the same thing, but then with A and b instead of B and a. They do this in the following way: Ba mod p = s = Ab mod p, since (ga)b mod p = (gb)a mod p (for some mathematical background consider the little section with extra information). In this way both Alice and Bob have obtained the same message (s), which they can now use as a cipher to communicate.
Example
Since the above explanation is quite abstract, an example is probably required. Let us take g equal to 2 and p equal to 11, which everyone may know. Now let Alice pick a equal to 8 and Bob choose b equal to 12. Both Alice and Bob will compute their public keys, A = 28 mod 11 = 256 mod 11 = 3 and B = 212 mod 11 = 4096 mod 11 = 4. Both these public keys will also be available to anyone interested. Note, however, that in this case it is quite easy to figure out which private key Alice and Bob chose. This is due to the fact that p is really small and there are therefore only 10 truly different options (i.e. a = 8 gives exactly the same results as a = 8 + 10 = 18 would give). However, also note that the ‘easiest’ way to obtain the value of the private key is to completely enumerate all possibilities. The complexity of this problem easily spirals out of control when p grows larger.
Now both public keys are known, it is time to compute the message/cipher that Alice and Bob actually want to communicate. This cipher can be computed by Alice by: s = Ba mod p = 48 mod 11 = 65536 mod 11 = 9. Bob can compute this by s = Ab mod p = 312 mod 11 = 531441 mod 11 = 9. A few things can be learned from this example. First of all choosing a private key larger than p (in this case b was larger than p, with values 12 and 11 respectively) does not contribute in any way to the security of communication. It does, however, make computations quite a bit more difficult, since 312 is a fair bit larger than 32, but gives the same value when calculated modulo p.
Secondly, it is important that g is a so-called primitive root of p. This means that if you list all possible values for gn mod p, for n ranging from 1 to p-1, you will obtain a list of all values ranging from 1 to p-1. If this is not the case, breaking the encryption of communication becomes much easier. Imagine that we would have picked g equal to 3 in our little example. In that case gn mod p can only give 5 different values for any input n: 3, 9, 5, 4 and 1, repeating in that order. This greatly simplifies the complexity of complete enumeration (in this case it halves the number of options, which is quite a big deal when dealing with large values for p).
The beauty of this algorithm is that there are only three things which are in fact secret, namely a, b and s. In spite of this, it is close to impossible to obtain s from the information publicly known (A, B, p and g). As long as you pick a, b and p large enough, which boils down to p at least 300 digits long and a and b both at least 100 digits long, even the fastest modern computers cannot find a, b or s within a reasonable amount of time.
RSA
RSA is a method with which you do not agree on a cipher but actually communicate the message you want to send. RSA is used as the main method for encryption nowadays, for instance for encrypting e-mail messages, cell phone signals and monetary transactions. RSA was first publicly described in 1977 by Ron Rivest, Adi Shamir and Leonard Adleman at MIT; the initials of their surnames becoming the title of the algorithm. RSA, unfortunately, is too complicated to mathematically describe in this article. It requires some extra definitions and theorems from number theory which would take up way too much space. I do, however, recommend you to read up on RSA if this article has made you curious!
This concludes a journey through the history and modern day use of cryptography. There is still a lot of other information out there, especially on modern cryptographic methods which involve more complicated mathematics and modulo computations. So if you got interested, be sure to search for that!
References
(1) Cohen, F. (1995). A Short History of Cryptography.
Retrieved from http://all.net/edu/curr/ip/Chap2-1.html
Text by: Ernst Roos
