Cryptography: Descriptions of Historical Ciphers

[anitsh]

http://turing.cs.trincoll.edu/~crypto/historical

Human ingenuity cannot concoct a cypher which human ingenuity cannot resolve. -- Edgar Allen Poe

“Virtues of a perfect cipher: ‘… that they be not laborious to write and read; that they be impossible to decipher; and, in some cases, that they be without suspicion.’” - Francis Bacon

http://turing.cs.trincoll.edu/~crypto/download/cryptotoolj.html

[anitsh]

Types Ciphers:

• Substitution Substitution cipher, in which the plaintext letters are replaced by letters from another alphabet (or by different letters from the same alphabet).

• Polyalphabetic One of the main problems with simple substitution ciphers is that they are so vulnerable to frequency analysis.

Given a sufficiently large ciphertext, it can easily be broken by mapping the frequency of its letters to the know frequencies of, say, English text. Therefore, to make ciphers more secure, cryptographers have long been interested in developing enciphering techniques that are immune to frequency analysis. One of the most common approaches is to suppress the normal frequency data by using more than one alphabet to encrypt the message.

A polyalphabetic substitution cipher involves the use of two or more cipher alphabets. Instead of there being a one-to-one relationship between each letter and its substitute, there is a one-to-many relationship between each letter and its substitutes.

• Transposition A transposition cipher involves the rearranging of the letters in the plaintext to encrypt the message.

Popular Cipher And Their Keys

CIPHER	Description of the Key
Caesar	An integer by which each letter is shifted
Simple Substitution	A keyword or a permutation of A..Z
Transposition	A String, such as 1023, describing the reordering of a block of text
Vigenere	A keyword
Gronsfeld	A keyword
Beaufort	A keyword
Autoclave	A keyword
Playfair	A keyword
Railfence	An integer > 0 giving number of rows

RSA, PGP

[anitsh]

PGP

PGP: Pretty Good Privacy. In private-key cryptography one key is used by both parties. One problem with this kind of encryption is that if the key is intercepted, a third party could decrypt the messages. So, the idea of public-key cryptography was developed. Here's how it works...

Everyone has two keys: a public and a private key. When someone wants to send something to a recipient, they (the sender) encrypt it with the recipient's public key. Then the only way to decrypt it is with the recipient's private key. One of the other benefits to PGP is that it allows the sender to "sign" their messages. This proves that the message came from the sender and has not been altered in transport.

Based on this theory, PGP allows everyone to publicize their public keys, while keeping their private keys secret. The result is that anyone can encrypt a message to someone else, as long as they have that person's public key.

In actuality, PGP uses a seies of private key, public key and one-way hash functions to encrypt a message. A one-way hash function takes some plaintext and translates it into a specific hash. The hash is unique to the message (like a fingerprint is to a person). The hash is also non-reversable, hence the name one-way. An example of what PGP does to encrypt and decrypt an e-mail message. Our sender will be Chris and our receiver will be Brian.

-Chris writes his message.

-Chris uses a one-way hash function (such as MD5) to create a hash for the message.

-Chris, via RSA or some other digital signature algorithm, signs the hash with his private key.

-Chris merges the message and the signature, resulting in a new signed message.

-A random encryption key is generated, the session key.

-Chris uses the session key to encrypt the message, using DES or some other private key method.

-Chris gets Brian's public key.

-Chris then encrypts the key with Brian's public key, via RSA or some other public key method.

-Chris merges the encrypted message and the encrypted key and mails it to Brian.

Once Brian receives the message he can have PGP decrypt it. Here's what it would do:

-Brian seperates the encrypted message and the encrypted session key.

-Using RSA, Brian decrypts the session key.

-Using DES, Brian decrypts the message with the decrypted session key.

-Brian then seperates the message and the signature.

-Using MD5, Brian calculates the hash value of the message.

-Brian gets Chris' public key.

-Via RSA, and Chris' public key, Brian decrypts the signature.

-Brian then compares the hash value and the decrypted signature. If they are the same, Brian knows that the message is authentic and has not been altered since Chris signed it.

Note: While we have used RSA,DES and MD5 in our example (that is what PGP uses) other similar algorithms could be used in their place. It is the combination of these three functions that makes PGP so strong. Remember, however, that the overall security of the method you choose is only as good as the weakest encryption method you choose to substitute for the three forms in the above example.

[anitsh]

Vigenere Cipher

It is a polyalphabetic substitution based on the following tableau:

    *    A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
    A   A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
    B   B C D E F G H I J K L M N O P Q R S T U V W X Y Z A 
    C   C D E F G H I J K L M N O P Q R S T U V W X Y Z A B
    D   D E F G H I J K L M N O P Q R S T U V W X Y Z A B C 
    E   E F G H I J K L M N O P Q R S T U V W X Y Z A B C D 
    F   F G H I J K L M N O P Q R S T U V W X Y Z A B C D E 
    G   G H I J K L M N O P Q R S T U V W X Y Z A B C D E F 
    H   H I J K L M N O P Q R S T U V W X Y Z A B C D E F G 
    I   I J K L M N O P Q R S T U V W X Y Z A B C D E F G H 
    J   J K L M N O P Q R S T U V W X Y Z A B C D E F G H I 
    K   K L M N O P Q R S T U V W X Y Z A B C D E F G H I J 
    L   L M N O P Q R S T U V W X Y Z A B C D E F G H I J K 
    M   M N O P Q R S T U V W X Y Z A B C D E F G H I J K L 
    N   N O P Q R S T U V W X Y Z A B C D E F G H I J K L M 
    O   O P Q R S T U V W X Y Z A B C D E F G H I J K L M N 
    P   P Q R S T U V W X Y Z A B C D E F G H I J K L M N O 
    Q   Q R S T U V W X Y Z A B C D E F G H I J K L M N O P 
    R   R S T U V W X Y Z A B C D E F G H I J K L M N O P Q 
    S   S T U V W X Y Z A B C D E F G H I J K L M N O P Q R  
    T   T U V W X Y Z A B C D E F G H I J K L M N O P Q R S 
    U   U V W X Y Z A B C D E F G H I J K L M N O P Q R S T 
    V   V W X Y Z A B C D E F G H I J K L M N O P Q R S T U
    W   W X Y Z A B C D E F G H I J K L M N O P Q R S T U V 
    X   X Y Z A B C D E F G H I J K L M N O P Q R S T U V W 
    Y   Y Z A B C D E F G H I J K L M N O P Q R S T U V W X 
    Z   Z A B C D E F G H I J K L M N O P Q R S T U V W X Y 

Note that each row of the table corresponds to a Caesar Cipher. The first row is a shift of 0; the second is a shift of 1; and the last is a shift of 25.

Note that each row of the table corresponds to a Caesar Cipher. The first row is a shift of 0; the second is a shift of 1; and the last is a shift of 25.

The Vigenere cipher uses this table together with a keyword to encipher a message. For example, suppose we wish to encipher the plaintext message: to be or not to be that is the question

using the keyword RELATIONS. We begin by writing the keyword, repeated as many times as necessary, above the plaintext message. To derive the ciphertext using the tableau, for each letter in the plaintext, one finds the intersection of the row given by the corresponding keyword letter and the column given by the plaintext letter itself to pick out the ciphertext letter.

Keyword: RELAT IONSR ELATI ONSRE LATIO NSREL Plaintext: tobeo rnott obeth atist heque stion Ciphertext: KSMEH ZBBLK SMEMP OGAJX SEJCS FLZSY

Decipherment of an encrypted message is equally straightforward. One writes the keyword repeatedly above the message:

Keyword: RELAT IONSR ELATI ONSRE LATIO NSREL Ciphertext: KSMEH ZBBLK SMEMP OGAJX SEJCS FLZSY Plaintext: tobeo rnott obeth atist heque stion

This time one uses the keyword letter to pick a row of the table and then traces across the row to get the column containing the ciphertext letter. The index of that column is the plaintext letter.

The strength of the Vigenere cipher against frequency analysis can be seen by examining the above ciphertext. Note that there are 7 'T's in the plaintext message and that they have been encrypted by 'H,' 'L,' 'K,' 'M,' 'G,' 'X,' and 'L' respectively. This successfully masks the frequency characteristics of the English 'T.' One way of looking at this is to notice that each letter of our keyword RELATIONS picks out 1 of the 26 possible substitution alphabets given in the Vigenere tableau. Thus, any message encrypted by a Vigenere cipher is a collection of as many simple substitution ciphers as there are letters in the keyword.

Although the Vigenere cipher has all the features of a useful field cipher -- i.e., easily transportable key and tableau, requires no special apparatus, easy to apply, etc. -- it did not catch on its day. A variation of it, known as the Gronsfeld cipher , did catch on in Germany and was widely used in Central Europe. The Gronsfeld variant used the digits of a keynumber instead of a the letters of keyword, but remained unchanged in all other respects. So in fact the Gronsfeld is a weaker technique than Vigenere since it only uses 10 substitute alphabets (one per digit 0..9) instead of the 26 used by Vigenere.

Cryptanalyzing the Vigenere Cipher: The Kasiski/Kerckhoff Method

Vigenere-like substitution ciphers were regarded by many as practically unbreakable for 300 years. In 1863, a Prussian major named Kasiski proposed a method for breaking a Vigenere cipher that consisted of finding the length of the keyword and then dividing the message into that many simple substitution cryptograms. Frequency analysis could then be used to solve the resulting simple substitutions.