Cryptography has a very long history, dating back thousands of years. Indeed, a means for secret writing, a literal translation of the word cryptography from the Greek words cryptos, which means hidden, and graphia, writing, is probably as old as writing itself. Writing gives us a way of conveying a message to someone else without actually meeting. Sometimes the messenger may not be trusted to keep the message secret. This led to the need for methods for encryption or ciphers, ways of transforming or encrypting a message into a form which hides its true content, what is usually called the ciphertext, and which can only be transformed back into its original form, known as the plaintext, by the intended recipient. This process is usually called decryption. Examples of ciphers are known that date back well over 2,000 years. The Greek Scytale cipher involved wrapping a strip of parchment in a helical fashion around a rod of agreed diameter. The message is then written on the parchment in rows along the rod. The strip will then contain the letters of the message in shuffled order, i.e., the message will be unintelligible. The original message can then be read by wrapping the strip around a rod of the same diameter. Other examples of early ciphers from 2,000 or more years ago, include systems from India, Iran, and the Roman Empire. A notable example from Rome is the Caesar cipher, said to have been used by Julius Caesar. In the context of a 26-letter alphabet, this technique involves choosing a number between one and 25, the shift, and a plaintext is transformed into a ciphertext by moving every letter in the message forward in the alphabet by the value of the shift. That is, with a shift of two, A becomes C, B becomes D, and so on. The recipient simply shifts the letters back by the appropriate shift. As ciphers evolved, so did the parallel science of cryptanalysis, that is the study of methods of breaking ciphers, i.e. finding ways to recover the plaintext from the ciphertext without being one of the authorized parties. An individual performing cryptanalysis is known as a cryptanalyst. A further idea that's also emerged during the evolution of ciphers is the separation of the method of encryption, the encryption algorithm, from the secret used with the method, the secret key. In our examples of historic ciphers, for the Scytale the encryption algorithm is the idea of using a strip and winding it around a rod before writing the message; the secret key is the diameter of the rod. For the Caesar cipher, the algorithm is letter shifting and the secret key is the size of the shift, i.e. the number between one and 25. In both cases, the authorized decryptor must use the same secret key as the encryptor in order to recover the original plaintext. This leads to the simple model of encryption shown in the slide. The slide shows the process of encrypting the plaintext data to obtain a ciphertext using an encryption algorithm and a secret key. In practice, the algorithm will typically be implemented in software, for example, as part of an operating system or application, and so is easily discovered. The second slide shows the process of decrypting the ciphertext to recover the plaintext. The same secret key used to do the encryption must be used. In the context of cryptanalysis, this is a very important distinction. As we just observed, the encryption algorithm is likely to be readily discoverable; indeed, in anything other than top-secret government applications, it is very likely to be a standardized method, and so we must assume it's known by the cryptanalyst. That is, the only thing that the users of a cipher can rely on remaining secret is the key. Of course, keeping the method secret as well is probably desirable, but it is unlikely to always hold. The designer of a cipher must therefore assume that the method is known to the cryptanalyst. As we have just discussed, in practice the only thing we can rely on remaining unknown to the cryptanalyst is the secret key. Of course, there must be a way for the authorized decryptor to have a way of obtaining the appropriate secret key. There are many ways of achieving this. This is part of a much larger topic called Key Management. For the moment, we'll only consider one issue, namely the number of possible secret keys. To illustrate what I mean, the Caesar cipher key is a number between one and 25, and so there are 25 possible secret keys with this cipher. Pause the video for a moment, and think about how many possible secret keys a cipher must have, if it is to be able to resist cryptanalysis by a determined opponent. To make things simpler, suppose the cryptanalyst knows the same key was used to encrypt a number of plaintext messages for which the cryptanalyst has the ciphertext. Also, suppose the cryptanalyst knows the plaintext message for one of the ciphertext messages and wishes to discover the other plaintexts. This plaintext value is referred to as a known plaintext. Hello, again, the simplest method of cryptanalysis is known as a brute force key search. This involves working one-by-one through every possible key value until the correct one is found. For each key value, the ciphertext is decrypted using this key. If the result matches the known plaintext, then the key is assumed to be correct and the search halts. Otherwise, the next key is tried. In practice, this will almost certainly reveal the correct key unless the plaintext is very short. This attack gives a simple way of assessing the number of keys a cipher should have. If the number of keys is small, then performing a brute force key search will be simple. For example, for the Caesar cipher, it will only take at most 25 possible tries, until the correct key is found. If decryption is implemented in software, this may only take a fraction of a second, and so clearly 25 is not enough and the Caesar cipher is completely insecure. We might suppose that a fast computer with optimized software might be able to try a million keys a second. This means that if there are 10 to the power 12 keys, i.e. a million, million, then it will be possible to try every key in little more than a week. If we had a million computers all doing the same calculations at the same time, not so infeasible given the total number of devices online, then searching for 10 the power 18 keys, a billion, billion could be done in a similar time. In practice, to give ourselves a margin of error, most modern ciphers will at least have 10 to the power 38 keys, meaning that brute-force key searches are completely infeasible. Of course, having a large number of keys is no guarantee of security. So far we've discussed encryption and ciphers. Indeed, until the middle of the 20th century, cryptography was only concerned with encryption, and encryption is designed to protect data confidentiality. However, over the last 60 or 70 years, with the massive growth in IT and digital communications, the need for ways to protect the integrity of data grew rapidly. For example, if financial transactions are being sent over a network, then while it may be useful to keep them confidential, maintaining their integrity is absolutely vital. That is, encryption alone no longer addresses all the cyber security needs. At this point, you might be tempted to ask why encryption can't be used to protect the integrity of data. After all, an encrypted message has no meaning to an attacker, so doesn't this mean the integrity of the plaintext is also protected? Take a moment to think about whether encryption can provide integrity protection. Welcome back. The simple answer is no. There's nothing to stop an unauthorized party that's able to manipulate messages in transit from modifying the ciphertext. When decrypted by the authorized receiver, the modified ciphertext will yield modified plaintext, and there's no way the receiver will know this. In many cases, the properties of the encryption algorithm mean that it may be possible for a malicious party to have some control over what the modified plaintext will look like. As a result, we need other techniques specifically tailored to protect data integrity. The concept of a message authentication code or MAC, emerged in the 1970s to address this need. A MAC is computed as shown in the diagram. Just as with encryption, using a MAC requires the sender and receiver to share a secret key. When sending a message, the sender uses the MAC algorithm and the secret key to compute the MAC, a fixed length bit string or check value, which is then sent with the message. The recipient of a message does exactly the same calculation using the received message, and if the newly computed MAC agrees with the value sent with the message, then the recipient knows the message has not been modified in transit. Obviously, the MAC function needs to meet certain requirements to prevent forgeries, but we avoid getting into the details here. The important thing is the general concept. If both integrity and confidentiality protection are required, the sender can first encrypt the message and then compute a MAC on the encrypted message using two separate keys. The receiver can verify the MAC before decrypting the message. Finally, in the late 1970s, Diffie and Hellman introduced the notion of a digital signature. This functions in rather a similar way to a MAC, but it uses keys in a somewhat different way. We'll return to this topic in a later lesson.
