Dr. John Polhill

Coding and Cryptology

53-361

Spring 2001

Basic Concept – Putting information that is to be transmitted (or stored) into numerical form so that errors can be automatically corrected by the mechanism.

Consists of the competing sciences of making a message unreadable by various transformations (cryptography) and trying to break encoded messages (cryptanalysis).

· "kryptos" – secret or hidden

· "logos" – word or study

· "ology" – science

· "graphia" – writing

· "ana" – up or throughout

· "lysys" – a loosing (unraveling)

Can be defined as communication in the presence of adversaries.

Is the message that you want to make unreadable.

The "unreadable" message, after it has been changed (encrypted).

The basic problems in cryptology are:

1. For cryptographers, how can we modify (encode, encrypt) our message so that it will be unreadable to anyone except its intended recipient?
2. For cryptanalysts, having intercepted an encoded message (Ciphertext), how can we decode it?

For both problems there are two basic categories of techniques:

1. Abstract "Pure" Mathematics
1. Linear Algebra
2. Abstract Algebra
3. Analysis
4. Number Theory
2. Real World Methods
1. Frequency counts

Where is cryptology used?

Wars – Armies have encrypted messages since ancient times.

NSA – National Security

Computers – Credit Card Information

Cable TV – Pay channels

Around 1500 BCE

Inhabitants of Mesopotamia used cryptography to hide a guarded formula for pottery glaze by jumbling the cuneiform figures, which described the ingredients.

Around 500 BCE

Indian writing used phonetic substitutions (exchanging positions of consonants and vowels), reversed letters, and was written at odd angles. Knowledge of concealed writing is listed as one of 60 skills to be mastered by women according to the Kama Sutra.

Around 5^th Century BCE – Greeks and Persians

Two accounts written by Herodotus "The Father Of History"

1. Demaratus vs. Xerxes – message covered with wax
2. Shaved head of messenger – A message was written on a head of a messenger, then the messenger grew his hair back out before he was sent to deliver the message.

· Both of these examples are examples of steganography - physically hiding the message but still the message is plaintext.

Caesar Cipher: Julius Caesar used a simple substitution cipher to encode military messages.

Substitution

It is the method of exchanging symbols for symbols.

Transposition

It is the method of rearranging letters; e.g. AND Þ DAN

· Substitution is more commonly used, easier to implement.

Julius Caesar » 1^st century

· Used a particular substitution cipher

Plaintext:

Ciphertext:

(Lower case = plaintext, upper case = ciphertext)

Encode "find me"

"IRVA XK" (Spaces are usually left out.)

In a simple substitution cipher, each plaintext letter is assigned a unique ciphertext letter. To encode, replace each letter in the plaintext with its corresponding ciphertext letter. In general, these are easy to crack.

A Caesar Cipher is a particular type of simple substitution cipher – here the cipher alphabet is just a shift of the plaintext alphabet.

Caesar’s original cipher was a shift by 3 letters.

(Linear algebra – just a linear transformation)

· We call this an X-shift since X was shifted to A

Encode "along the way"

"DORQTWKHZDB" (Spaces have been left out.)

A cipher is any cryptographic substitution where a letter is replaced by a letter or symbol. (Letter by letter, not word by word.)

Our above example is a monoalphabetic because it uses only one cipher alphabet. (Very easy to attack via cryptanalysis.) Monoalphabetic ciphers are fairly easy to crack – we will see how people as early as the 9^th century AD could crack them. Still they were used widespread even into recent centuries.

- Proposed a cipher using 2 alphabets

Encode/Encrypt by alternating cipher alphabets

(1) Is a V-shift and is cipher 1

(2) Is a O-shift and is cipher 2

"hello there" becomes

"MQQXT FMQWQ"

· Not that l’s show up as Q and X but E’s show up all as Q

How can we crack such codes?

- French diplomat born in 1523

- Developed more fully Alberti’s ideas » 1565

· Encode using prescribed rows.

Possible methods

1. Cycling through by using progressive rows

hello there Þ

HFNOS YNLZN

2. Method of Vigenère – Use a keyword (sometimes called repeating keyword)

Keyword: BIG

Encode "hello there" BIGBI GBIGB

HELLO THERE

hello there Þ IMRMW ZIMXF

Much more difficult to crack, but it can be done and we will look at how.

 

 

Rossignols – The Great Cipher (Louis XIV)

 

 

 

Invented by Sir Charles Wheatstone, popularized by Baron Lyon Playfair (Last half of 19^th Century)

Again choose a keyword. Write the alphabet in a 5X5 square, beginning with the keyword and combining I with J.

Keyword: MONEY

G H ^I/_J K L

Take desired plaintext message:

"hello there"

Break it into parts:

HE LL OT HE RE

You cannot have double letters, so separate with an X:

HE LX LO TH ER EX

Encode in pairs by the following rules -

Rules of Playfair:

1. When the two letters of plaintext are in the same column, each is encrypted as the letter below it (the bottom letter is encoded as the top letter in that column).
2. When the two letters are in the same row, each is encrypted as the letter to its right (the far right letter in a row gets assigned the far left letter).
3. When the letters are in a different row and column then they are encrypted by the two letters that form a rectangle with them, beginning with the letter in the same row as the first letter of plaintext.

Try:

"Loverboy Rocks" (this is a rock band)

· Used by Freemasons in 1700’s

· Schoolchildren still use it today

· Simple monoalphabetic cipher

· Replace letters with symbols.

This is easy to decode.

 

 

 

Ciphers pre-second century and references:

· Edgar Allan Poe - "The Gold Bug"

· Beale Papers