Encryption and Cryptography

In the past, the science of Cryptography was applied only in secret chambers and utilized by governments and spies.
Today, encryption systems are everywhere around us, from the Automatic Teller Machine to transactions on the internet

In the Advanced Topics class discussion of Number Theory, we discuss the history of encryption systems and work our way up to modern cryptographic methods that utilize prime numbers and elliptic curves.

Some terminology:

key: the method used to encrypt and decrypt messages

plaintext: plain, unencrypted text
ciphertext: encrypted text
plaintext alphabet: the regular ABC...XYZ alphabet
ciphertext alphabet: a rearranged alphabet that can be written under the plaintext alphabet to aid in encrypting and decrypting messages
cryptography: the science of encrypting information
cryptanalysis : methods of deciphering encrypted information without knowledge of the key (this is a combination of a science and an art and involves a multitude of computer-based analyses of ciphertext messages)
cryptology the field comprised of both cryptography and cryptanalysis (most governments must do both of these)

The types of encryption discussed in the Advanced Topics class are:

Substitution Ciphers

Substitution ciphers methodically replace each letter of the alphabet with a new letter.
EXAMPLES:

Caesar Code
uses a simple shift of the alphabet to create the ciphertext

Keyword Substitution Ciphers
uses a keyword as the basis for creating a ciphertext alphabet to encrypt

Vigniere Substitution Cipher
uses a keyword along with a Trimethius table to encrypt

A Caesar code wheel that can be dialed up to represent any of the 25 Caesar shifts:

Transposition Ciphers

Transposition ciphers transpose, or shuffle, the letters in a message to encode the message. Hist nca eb a yvre fefciteve yaw ot tpyrcne

Rail fence ciphers
breaks a word up using every nth letter to first rearrange the message to resemble a rail fence, the reassemble in encrypted form

Anagram ciphers
rearranges plaintext message into alphabetical order (use by Galileo to publish discoveries in secret)

Scytale ciphers
A strip of paper is wrapped around the wooden octagonal stick and a message is written across the paper. When it is unraveled, the message will be encrypted (different size sticks represent different keys).

An image of a scytale cipher with a message ready to be encrypted by unraveling:
a wooden scytale, used for transposition ciphering

Steganography

Steganography involves hiding a message within another message so that it is not obvious that there is anything hidden.

Letter Steganography
- the message is read by selecting particular letters from a seemingly innocuous sentence (How else? Luck, perchance?)
Word Steganography
- the message is read by selecting particular words from a seemingly innocuous message
Digital Steganography
- a more complex process where a message is converted to it's ASCII binary representation and hidden in the bits of a digital representation of an image

An image that shows 1's and 0's hidden by Digital Steganography within the color values of individual pixels:
(the man shown is Simon Singh, author of The Code Book, which is highly recommended reading)
numbers hidden under a digital image

Public Key Cryptography

Public Key Cryptography usually involves at least two keys, where the encryption key is made public, allowing anyone to encrypt a message and send it to you, while the decryption key involves using a private key, in combination with the public key, to decrypt (this is similar to sending an email message: everyone knows how to send you a message, because your email address is generally public, but once the message is sent, the only person that can read it is the one that has the password to open your email account).
RSA Encryption
- RSA Encryption has been used worldwide since the 1970's to provide security for bank, governmental,and internet communications and transactions. RSA uses the product of two huge prime numbers as an encryption key and the two huge primes as the decryption key. Because the encryption and decryption keys are different, this is an example of asymmetric encryption. Although RSA has been the most secure form of encryption in the world since its inception, new developments in computer science could lead to a "cracking" of RSA (one example is the development of quantum computers which would increase computer processing speed to an unprecedented level)
- My attempt at explaining some of the mathematics behind RSA
Elliptic Curve Cryptography (ECC)

To get a taste of the types of encryption, here are some explanations:

EXAMPLE: Keyword Substitution Cipher:

A keyword of any length is chosen. The keyword could be a given word or sentence in a book agreed upon ahead of time. For example, it could be agreed that the next pair of words from the Chapter 5 of A Tale of Two Cities would be used for each new message.

Under the plaintext alphabet (the alphabet in it's usual order), write out all the letters of the keyword without repeats.

Let's say you've chosen It was the best of as your keyword phrase:

plaintext: ABCDEFGHIJKLMNOPQRSTUVWXYZ
ciphertext: ITWASHEBOFG...

Now continue the alphabet, from the last letter written underneath the ciphertext (again, without repeating):

plaintext: ABCDEFGHIJKLMNOPQRSTUVWXYZ
ciphertext: ITWASHEBOFGJKLMNPQRUVXYZCD

Encode the message by looking up the plaintext letters and finding the corresponding ciphertext letters. Decode by reversing the process.

The following does a good job of summarizing some steganography techniques:

from http://www.garykessler.net/library/steganography.html(Gary C. Kessler , Associate Professor and program director of the Computer Networking major at Champlain College in Burlington, Vermont)

While much of the steganography employed today is quite high-tech, steganography itself can make use of many low-tech methods. The goal of stego is merely to hide the presence of a message; remember how well the critical missive was hidden in plain sight in Poe's "The Purloined Letter"?

One common, almost obvious, form of steganography is called a null cipher. In this type of stego, the hidden message is formed by taking the first (or other fixed) letter of each word in the cover message. Consider this cablegram that might have been sent by a journalist/spy from the U.S. to Europe during World War I:
PRESIDENT'S EMBARGO RULING SHOULD HAVE IMMEDIATE NOTICE. GRAVE
SITUATION AFFECTING INTERNATIONAL LAW. STATEMENT FORESHADOWS RUIN
OF MANY NEUTRALS. YELLOW JOURNALS UNIFYING NATIONAL EXCITEMENT
IMMENSELY.
The first letters of each word form the character string: PERSHINGSAILSFROMNYJUNEI. A little imagination and some spaces yields the real message: PERSHING SAILS FROM NY JUNE I.

Another form of steganography uses a template (e.g., a piece of paper with holes cut in it) or a set of preselected locations on the page to hide a message. In this case, obviously, the sender and receiver must use the same template or rules. Consider this note:
THE MOST COMMON WORK ANIMAL IS THE HORSE. THEY CAN BE USED
TO FERRY EQUIPMENT TO AND FROM WORKERS OR TO PULL A PLOW.
BE CAREFUL, THOUGH, BECAUSE SOME HAVE SANK UP TO THEIR
KNEES IN MUD OR SAND, SUCH AS AN INCIDENT AT THE BURLINGTON
FACTORY LAST YEAR. BUT HORSES REMAIN A SIGNIFICANT FIND. ON
A FARM, AN ALTERNATE WORK ANIMAL MIGHT BE A BURRO BUT THEY
ARE NOT AS COMFORTABLE AS A TRANSPORT ANIMAL.
Applying a template or rule as to which words to read to this message might yield the following:
                                   HORSE
   FERRY
                                      SANK
      IN                                         BURLINGTON
                                                   FIND
           ALTERNATE
                            TRANSPORT
There are other alternatives to the template method such as:

Pinpricks in maps to use as an overlay for relevant letters in messages
Deliberate misspelling to mark words in the message
Use of small changes in spacing to indicate significant letters or words in a hidden message
Use of a slightly different font in a typeset message to indicate the hidden letters (e.g., the difference between Courier and Courier New is barely noticeable unless you are looking for it)

Steganography doesn't just apply to written forms of communication. Radio and TV messages, from World War II to today, can be used to hide coded or hidden messages. Some government sources suspect that Osama bin Laden's pre-recorded videos that are re-played on TV stations around the world contain hidden messages.

Some argue that the U.S. Marine Corps Navaho code talkers of WWII represent a form of steganography. The messages themselves weren't encrypted; the plaintext was right there in the open, just in a language that was unknown by the Japanese. Disappearing ink and microdots are other ways in which messages can be hidden from the casual observer.

One of the oldest stego schemes was to shave the head of a messenger and tattoo a message on the messenger's head. After the hair grows back, the messenger can be sent to the intended recipient, where the messenger's head can be shaved and the message recovered. This method is decidingly clever, patient, and very low-tech, and goes right to the heart of steganography's literal meaning of "covered writing."

More details on ECC:

This figure shows the addition of two points on an elliptic curve. Elliptic curves have the interesting property that adding two points on the elliptic curve yields a third point on the curve. Therefore, adding two points, P and Q, gets us to point R, also on the curve. Small changes in P or Q can cause a large change in the position of R. For encryption, a point Q is calculated as a multiple of the starting point, P, or, Q=nP. An attacker interested in decrypting might know P and Q but finding the integer, n, is a difficult problem to solve. Q is used as the public key, and n is the private key.

The concept of addition of points on an elliptic curve can be confusing. Here is an explanation from certicom.com (a company working towards implementing ECC on a large scale):

Adding distinct points P and Q :

Suppose that P and Q are two distinct points on an elliptic curve, and the P is not -Q. To add the points P and Q, a line is drawn through the two points. This line will intersect the elliptic curve in exactly one more point, call -R. The point -R is reflected in the x-axis to the point R. The law for addition in an elliptic curve group is P + Q = R. For example: