Introduction to Cryptography

If some information is meant to be kept private, the best means is to keep it well hidden. This is not, of course, always possible. One way around this is to hide the information or message in plain sight, that is, encode it in some way so that even if it is seen, it will be unreadable. The study of such encoding processes is called Cryptography^4.1. The name ``Cryptography'' comes from the Greek words kryptos ( $\kappa$$\rho$$\nu$$\pi$$\tau$o$\sigma$), meaning ``hidden'' or secret, and graphia ( $\gamma$$\rho$$\alpha$$\phi$$\iota$$\alpha$), meaning writing.

Since ancient times, cryptography has been a part of military and governmental communications. More recently it has become part of nearly everyone's life because of the Internet, electronic banking, and so on.

The usual jargon is as follows: the message you want to hide is called the plaintext, and the act of encoding it is called encryption or enciphering. The encoded plaintext is called the crypttext or the ciphertext, and the act of decoding it is called decryption or deciphering (or ``cracking the code'', if the decoder wasn't the intended reader). Usually, an encryption system (also called a cipher) has an auxiliary piece of information called the key needed for the encoding and decoding process. Mathematically, we can represent the encryption process as

f_key($$\cal{P}$$) = $$\cal{C}$$,

where $\cal{P}$ is the plaintext and $\cal{C}$ is the ciphertext. To decrypt the message, one applies f^-1 to the ciphertext. Note that to be able to decipher a message without ambiguity, f^-1 must be a well-defined function (although f needn't be! It is perfectly all right to have the same message encode to two different ciphertexts, as long as we can get the original when deciphering.)

Footnotes

...Cryptography^4.1

Cryptography is related to, but distinct from, steganography, which is the process of hiding the fact that a message exists at all. Using ``invisible ink'' is steganography, as is hiding messages within other messages. For example, looking at the second letter of each word in the message below (which was actually sent by a German spy during World War I [Kahn, p. 521]),

Apparently neutral's protest is thoroughly discounted and ignored. Isman hard hit. Blockade issue affects pretext for embargo on byproducts, ejecting suets and vegetable oils.

one finds a rather different message, namely

Pershing sails from NY June I.

Steganography is often used to augment cryptography, and is also related to ``digital watermarking''. We will not be considering steganography here.