Cryptography
In 404 BC when the Persians conspired to attack the Spartans, a messenger to Lysander of Sparta carried a secret message written upon his belt. Lysander wound this belt around a tapered wooden staff and read the message that enabled him to prepare for, and ultimately defeat, the Persian invaders.
The Spartans used a very simple method to hide the message. The tapered staff is called a scytale. To use it the Spartans would wind a strip of parchment around it and write the message upon the strip along the length of the scytale; once the strip was unwound, it could not be read again until it was wound around a scytale of the same size as the original.
Broadly put, cryptography is the science of keeping communications private so only the people for whom they are intended can read them; cryptanalysis is the science of breaching the protection that cryptography affords. Originally, largely because of the nature of the available transmission media, cryptography was chiefly concerned with keeping individual messages like letters or military dispatches and orders from the eyes of the enemy. In more recent times, however, cryptography has been applied very successfully to securing satellite communications systems, mobile phones, facsimile transmissions, and computer data.
Moreover, modern cryptography is concerned with more than just secrecy. It can be used to authenticate the originator of a communication and ensure the integrity of the message; that is, cryptography can prove the message received is the same as the message that was sent.
Transforming an unencrypted message, or plaintext, into its unintelligible form, or ciphertext, is encryption; changing it back into a readable form is decryption.
Modern cryptographic systems use an algorithm to carry out the transformation according to a set of rules that are modified by a key. An algorithm is a sequence of operations carried out systematically to yield a result in a finite number of steps. A cryptographic algorithm is used to transform data from its normal form to another form under the control of a key. The mathematical properties of a strong cryptographic algorithm make performing the transformation without the key very difficult, even if the details of how the algorithm works are common knowledge.
Thus, if only the sender and the intended recipient of the message know the key, then it should be difficult for anyone else to decrypt the message and read it in its plain form.
Algorithms and Operations
Exactly how difficult it is to decrypt encrypted data without the key depends on the algorithm, and there is a constant effort in the cryptographic community to cryptanalyse the most popular cryptographic algorithms.
While there are hundreds, if not thousands, of cryptographic algorithms being used in the world, each of them makes use of very simple and fundamental operations of transposition or substitution, or a mixture of both. Substitution replaces one element or symbol for another. Transposition moves the symbols around within the message. It is these patterns of substitution and transposition that the key influences as the algorithm operates on the data. A cryptographic algorithm that transposes the plain text in a message, or substitutes it with arbitrary symbols, in accordance with certain predetermined rules, is called an "encipherment algorithm" or just "cipher." Ciphers that use both transposition and substitution are called product ciphers.
The dawn of modern cryptography came in World War II with the Enigma Machine cipher. The Enigma machine operated on the 26 letters of the alphabet and was a very sophisticated substitution cipher. Rather than simply replacing one letter for another, an operation that is trivially easy to break if you know the properties of the language of the original message, the Enigma's substitutions at any stage of the encryption process were governed by a combination of rotors and plugboards, the settings of which represented the key. What this meant was that there was no one-to-one mapping between a plain character and its encrypted equivalent. For example, if the letter A was enciphered as B the first time it appeared, the next time it appeared it would most likely be enciphered as something entirely different, and so on. The number of rotors and the number of possible permutations of rotor and plugboard settings meant that the total number of possible combinations was so large that it could not be guessed or derived in any reasonable amount of time using the technology of the day.
It is possible to divide cryptographic algorithms broadly into two types: block ciphers and stream ciphers.
Block ciphers operate on discrete blocks of data, cascading each block in turn through a series of stages, or rounds, of transpositions and substitutions. A block of data is a collection of a pre-defined number of binary bits. Block ciphers usually, but not always, operate on blocks of data that are the same size as the key. That is, if the key is 128-bits long, then the algorithm will break the data it is encrypting into 128-bit chunks as it encrypts it. The most common form of block ciphers are called Feistal ciphers after Horst Feistal who first described the particular pattern they follow. A Feistal cipher has the property of being invertible; that is, the algorithm for decryption is the same as encryption.
Stream ciphers operate differently by generating a stream of seemingly random output that is then Exclusive-ORed (XORed) with the plain text to give the ciphertext. Exclusive-ORing is essentially binary addition without the carry. The operation is such that any bit XORed with a bit of the same value always results in a 0 and a bit XORed with a different value always gives a 1. This means that XORing with the same value twice yields the original again. For example 101 XORed with 010 gives 111, and 110 XORed with 010 gives 101, which is the original value.
In 1976 the U.S. National Bureau of Standards (NBS) established the Data Encryption Standard, or DES. The DES is a block cipher that encrypts 64-bit blocks of data, one at a time using a 56-bit key over 16 stages, or rounds, of substitution and transposition.
When DES was first introduced, a 56-bit key was long enough to secure the data for a very long time. Nowadays 56-bits are considered to be hopelessly insecure and the industry standard calls for at least a 128-bit key.
DES is still used, however, and has been given a new lease on life by using it in "encrypt-decrypt-encrypt" mode, where the encryptions are done with one key, and the decryptions with a second key. This means that triple-DES, or 3DES, has an effective key length of 112 bits.
DES is no longer considered computationally secure, but it is likely that 3DES will be computationally secure for some time.
A cipher that cannot be broken by an attack on the algorithm, and which has a keyspace that cannot be searched exhaustively, is called computationally secure. A cipher that cannot be broken under any circumstances is called unconditionally secure.
The NSA has recently chosen a new standard called the Advanced Encryption Standard, or AES. The cipher chosen for the AES is called Rijndael, which is a block cipher that has a variable block length and key length. It is designed to use keys with a length of 128, 192, or 256 bits to encrypt blocks with lengths of 128, 192, or 256 bits. These key and block lengths can be used in any combination. Both block length and key length can be extended very easily to multiples of 32 bits.
Surprisingly, perhaps, there does exist an unconditionally secure cipher, it's called the One Time Pad. This is a stream cipher that uses a random key of exactly the same length as the original plaintext. If the key is genuinely random then it is impossible to break this system with any amount of computation. The length of the key means that the OTP is practically restricted to situations where this kind of secrecy is absolutely necessary, such as certain diplomatic and military communications. This is because, with the key being the same length as the original text, it becomes necessary to keep the key as secure as the original document--thus doubling the security needs. The real advantage of the OTP is that the key can be distributed ahead of time and thereafter anything encrypted with it is unconditionally secure for all time. It is important to note that if an OTP key is ever used more than once, then the two communications thereby encrypted can be broken with ease. The reason for this is that the two encrypted texts can be compared for similar coding.
Cryptographic Keys
Most cryptographic systems are broken because of errors either in the way they are used or the way they are implemented. For example, errors in use include a user writing a password down on a piece of paper, and an error in implementation might be having the software inadvertently write the key to the hard disc where an attacker can retrieve it. But assuming the algorithm itself is difficult to break and is implemented perfectly, the next thing to do is make sure the key is long enough not to be easily guessed.
Computers represent data as a sequence of 1s and 0s. These are called "bits" (short for "Binary digIT"). Cryptographic algorithms work at the "bit level" on the data, meaning they operate on the individual bits within the data they are encrypting. The exact sequence of the changes that are made is governed by a key, which is also represented as a sequence of bits. In general, the more bits a key has, the more secure it is because it is obviously harder to guess.
If a key has a known number of random bits, then the easiest way to discover it is to try every possible combination. It is necessary, therefore, to choose a cipher that has a key long enough so that even the fastest computers will take a very long time to search all possible keys. Because of this, it is now commonplace to describe ciphers in terms of the length of their key in binary digits. For example, IDEA is a 128-bit cipher because its key comprises a string of 128 binary bits of data. 128 bits may not sound like a dauntingly large number of anything, but consider this: if you took a 1-gigahertz processor that could test one key for every clock cycle, it would take slightly over ten thousand billion billion years to test every possible key. This is a very long time.
Cryptographic systems can be divided into one-key and two-key systems. In a one-key system the same key is used for decryption and encryption. In a two-key system the keys for encryption and decryption are different (though they are typically related by a mathematical function).
Two-key systems are often called asymmetric cryptographic systems and are based on trap-door one-way functions. A one-way function is a function that is easy to compute in one direction, but substantially harder to reverse. An everyday example of a one-way function is making an omelette: breaking the eggs and mixing in the grated cheese is easy, but getting the eggs back into their shells is another matter entirely.
The "trap door" in a trap-door one-way function is some extra information that makes reversing the one-way function easy. An example would be stripping a car down to its component parts on the driveway; the key to the trapdoor is the manual you hope you have in the garage.
Strictly speaking no one knows if genuine one-way functions exist. There exist lots of functions that appear one-way, and most mathematicians believe they are one-way. But there is no proof. In many respects this lack of proof--one way or the other--is disconcerting; but proof that one-way functions do not exist would throw the entire science of cryptography into turmoil, since it would prove that all current asymmetric systems can be broken. The two keys of an asymmetric cryptographic system are referred to as the private key and the public key.
The private key is the decryption key and represents the trap-door in the one-way function the asymmetric system is based on. Decryption is easy with this key, and only the person who chooses it knows its value. The public key can then be promulgated widely to anyone who wants it. Anyone who has the public key can encrypt data and send them securely, to the person who has the private key.
The concept of asymmetric encryption and decryption leads directly to a method of creating digital signatures: encrypting with the private key can be done only by the person who has it, yet anyone who has the public key can check the signature. With proper checks and administration, a digital signature scheme can be made to provide non-repudiation, where the originator of a message cannot later deny having sent it. In case of a dispute, it would be possible to demonstrate that only the possessor of the private key could have created the signature on the data.
The invention of asymmetric cryptography is generally attributed to Whitfield Diffie and Martin Hellman, but recent information released by the British reveal that it was actually invented in the early 1970's by James Ellis and others at the Government Communications Headquarters in Cheltenham, England. Over the years various patents have been granted for asymmetric systems, but the last of the important ones, RSA, named after the credited inventors--Ronald L. Rivest, Adi Shamir, and Leonard M. Adleman--expired in September 2000. Oddly, the RSA patent was valid only in the United States.
There are several different types of asymmetric systems, but only a few are both practical and secure. And of the ones that are both practical and secure, only some are suitable for encryption and decryption, and by extension digital signatures. Others are suitable for key exchange alone, and yet others are suitable only for exchanging or agreeing a common value.
The most popular asymmetric systems today are all based on two similar problems that rely heavily on the use of very large prime numbers. In practice, asymmetric cryptography is rarely used to encrypt large amounts of data, because the algorithms are computationally intensive and are much slower than symmetric systems.
Instead, symmetric and asymmetric systems are put together to form a hybrid system in which the two communicating parties will use each other's public and private keys to encrypt and exchange a small amount of random data. They then use this as the key for a symmetric system for exchanging large amounts of data.
Cryptography has also allowed the development of digital signatures. A digital signature is a cryptographic means for verifying the identity of an individual, a process, computer system, or any other entity, in much the same way as a handwritten signature verifies the identity of a person. Digital signatures use the properties of public-key cryptography to produce pieces of information that verify the origin of data. The potential problem that arises is that data can be very, very large, and the process of public-key encryption is very computationally intensive, and that makes it both slow and expensive to apply to large amounts of data.
To overcome this, digital signature schemes first create what is called a "hash" or "digest" of the data. A digest is formed by taking the original data and reducing it to a much smaller length. Digests use cryptographic functions that ensure small differences in the input produce large changes in the output. In other words, two memos, for example, that differ by a single word will yield very different digests. Once the digest has been obtained, it can be encrypted with the private key and published as the signature for the data that yielded the digest.
On receipt of the data that is allegedly signed, the recipient can create her own version of the digest. The recipient can also use the sender's public key to decrypt the digest the sender encrypted with her private key. If the two digests match, i.e. the decrypted one is the same as the locally created one, then the recipient knows that the signature is valid and the purported sender is in fact the actual sender.
Cryptography Today
In the last decade of the twentieth century, public interest in, and use of, cryptography increased dramatically. In 1991 Phil Zimmerman released his Pretty Good Privacy (PGP) software into the world. The software and the source-code were, and still are, freely available for anyone to use (see these websites: <http://www.pgp.com> and <http://web.mit.edu/network/pgp.html>). PGP uses a hybrid system of symmetric and asymmetric cryptography to provide an extremely secure method of communication between computers.
The appearance of PGP, along with the massive increases in affordable computing power available to anyone who wanted it, meant that military-grade cryptography became available for free. It became possible for anyone with a computer to send messages so securely that even the best efforts and massed computing power of all the secret services in the world would not be able to read them.
Ten years later the Internet is a vast repository of cryptographic resources and knowledge. There are open-source cryptographic libraries written in C (<http://www.openssl.org>), Java (<http://www.cryptix.org>), and in almost every other computer programming language there is. Even the standard Java distribution from Sun Microsystems (<http://java.sun.com>) comes with excellent support for symmetric and asymmetric cryptography.
This state of affairs has caused much consternation among the various governments of the world and has led to calls in the United States for laws to force people to hand over their secret keys on demand. These moves have been strongly resisted on Constitutional grounds, but pressure to do something remains. In the United Kingdom the Regulation of Investigatory Powers Act explicitly forces people to hand over the keys to encrypted material without the need even for a court order.
Other countries have had mixed reactions to the advances in cryptography. France, for instance, has outlawed any cryptography that uses a key over 40-bits in length; whereas the Republic of Ireland has legislated explicitly to protect people's right to privacy.
This is the complete article, containing 2,978 words
(approx. 10 pages at 300 words per page).
