Cryptography

Cryptography involves the processing of human-readable (or computer-readable) information (plaintext) using cryptographic algorithms for various purposes, including privacy (encryption into ciphertext); characterization of a message (message digest or cryptographic residue); or for two parties to agree upon an encryption key (key agreement). More complex benefits can be accomplished by building on these primitive operations, such as authentication (establishing and communicating someone's identity) and trust (being willing to accept various information as valid or correct, and hence suitable for basing decisions on). One such higher level construct is the digital signature, which includes sender authentication, unambiguous detection of tampering, and non-repudiation. These terms will be defined precisely later. Another is the digital envelope, which is a secure container for delivering information, e.g. via email. Yet another is trusted timestamping.

This processing can be done manually (by hand), mechanically (by machine) or by a computer. Computers have made it possible to use far more complex and powerful cryptographic algorithms, and to apply them in more situations than would otherwise be possible. Cryptography has been used for about 2,000 years in one form or another. Before computers, of the applications described above, only encryption was widely used, and that mostly mapped individual characters onto other characters. In more advanced systems, small groups of characters were mapped onto similar groups of characters. Computers are able to represent information as ordered sequences (strings) of bits, and slice and dice these bit strings at the bit level (rather than the character level). This allows far more thorough scrambling of the plaintext into binary ciphertext, as well as scrambling of any kind of data (not just text), such as images, data files, digitally encoded audio, etc.

Computers also can create message digests (or cryptographic residues) from any kind of information, as well as perform key agreement protocols that allow two parties to agree upon a key without anybody else being able to obtain that key.

Within the area of encryption, there are two broad schemes: symmetric key (a.k.a. secret key) and asymmetric key (a.k.a. public/private key). Both depend on the concept of a cryptographic key, which is itself a short (typically 256 bit or less) ordered sequence of bits. Without the concept of keys we would need to keep the details of the encryption algorithms secret (and those would certainly be quickly discovered or "reverse engineered"). This concept allows the need for secrecy to be moved from the algorithm to the key used in a particular usage.

All symmetric algorithms are built from simpler algorithms called substitution or transposition ciphers. The Caesar Cipher is a simple character based substitution cipher. It can replace one character with a different one. Newspapers used to have puzzles with the letters of words rearranged into a different order -like "PELAP" for "APPLE". That is a character based transposition cipher. Both substitution and transposition ciphers can be done at the bit level as well. I can replace any group of bits in a 64-bit block with a different group of bits, or move the bits in a 64-bit block around into a different order. For example:

Old Position    New Position

0               31
1               17
2               62
3               0
...
63              12

A modern symmetric encryption algorithm is like a complex machine - it can apply a variety of bit level substitution and transposition ciphers in various ways and in different orders, depending on the key being used. A key is like a cam for an engine - it controls the exact sequence of events that happen within the cryptographic engine. With a given key, the algorithm does one sequence of transforms and winds up with one ciphertext. With a different key, the algorithm uses a different sequence of transforms in a different order, and winds up with a very different ciphertext. For a given plaintext and key, a particular algorithm will always reliably produce the same ciphertext. The key can be used to encrypt something by applying certain ciphers in a particular order, or decrypt the resulting ciphertext by undoing those ciphers one by one in reverse order.

You can also think of a key as a "road map" of the transformations done getting from the plaintext to the ciphertext. Decryption involves following that map backwards, to get from the ciphertext to the plaintext. Of course every cipher must be reversible for this to work. Information cannot be lost at any point, in either direction. If I use the wrong map (wrong key) to decrypt I don't wind up at the original plaintext - I wind up at some gibberish.

The actual cryptographic algorithms do not need to be kept secret. In fact, all of the details are available to anyone - they are published in standards. The need for secrecy is moved to the keys. An attacker can know every aspect of your encryption algorithm, but without the correct key, assuming the algorithm is good and the key is big enough, they will never be able to recover the plaintext (at least not from the ciphertext).

It is more difficult to create strong algorithms than most people realize. There are quite a few that have been developed and extensively tested by cryptanalysts, looking for weaknesses. No good programmer tries to create their own algorithms - they use well known, vetted algorithms that have stood the test of time. The trick is to use the standard ones correctly and implement key management and data handling properly and securely.

Symmetric key cryptography uses the same key to encrypt and decrypt. This is intuitive.

Asymmetric key cryptography is something completely new. It is not very intuitive. It uses a matched pair of keys - you can encrypt with either key of a matched pair, and decrypt only with the other key of the matched pair. One of the keys is called the public key and the other is called the private key (hence "public/private key cryptography", or in shorter form "public key cryptography").