Written by Jose Mari Reyes
Copyright(C)2001, Jose Mari Reyes
Manila, Philippines

No part of this document may be used or reproduced in any form or by any means, or stored in
a database or retrieval system, without prior written permission of the author. Making copies
of any part of this document for any purpose other than your own personal use is prohibited

This document is presented as is, without warranty of any kind, either express or implied,
respecting the contents of this document. The author disclaim all types of liabilities, loss
or damage caused or alleged to be caused directly or indirectly by this document.

What is Cryptograpy

Some say it is an art, to other it is science. Cryptography (from Greek hidden + writting) is the art and science of writting of message in coded form.  This black art of hidding and retrieving message plays an important role in the history of every nation.  Basically the idea is to transform a plain message into a specially coded form that only the trusted party knows the encoding algorithm, this method is known as encryption.  Transforming the encrypted message back to its original content is the reverse of the process, this method is known as decryption.
 
 

Meet me tonight --------------- Encrypt ----------------------> #49isjd2l3j5lwd#(

#49isjd2l3j5lwd#(--------------- Decrypt ----------------------> Meet me tonight
 
 
 
 
 

Short History

Perhaps the oldest type of encryption was device by the Egyptians where scribe use a non-standard hieroglyphs in an inscription.
Another one is the Spartan scytale; Plutarch tells how the Lacedaemonian generals exchanged messages, they wind a narrow ribbons of parchment spirally around a cylindrical staff, then the message is written on the parchment.  When the ribbon was unwound, the writting appeared no meaning, the message can only be read only by the person who had a cylinder of exactly the same size.

Another ancient type of encryption scheme was created by an ingenious Histiaeus at the Persian court.  He wish to send message to Aristagoras, his son-in-law who was in Greece, to revolt.  To hide the message against the Persian, Histiaeus shaved the head of his most trusted servant, tattoed it with the message and waited until the hair grew.  The servant was instructed to tell Aristogoras about the message on his head and should be shave. Aristogoras revolted.  Although very inefficient, it was even use during World War 1 where it was practice to send spies across the enemy lines with the messages written in their body using invisible ink.

More sophisticated cryptograms were devised by the early Greeks,they frequently used arithmetical figures.  One of their method of substituting mathematical figures in place of letters was to block the alphabet into a square and number each vertical and horizontal row from one to five. As one letter of a 26 letter alphabet must be omitted, I, in our alphabet, can be made to serve both as I and J or U as both U and V.
 
 

The suffling of letters to make the message unreadable is known as transposition encipherment.  It is one of the two basic principle of moden cryptography.  This substititution  of one letter for another to a prearranged method was a favorite device of the Romans.  Julius Caesar, seems to have lacking in cryptography subtlety. What he did is he transpose the letter to the third letter, D for A and E for B, this system is easily breakable even by a novice cryptographer.

One  of the most interesting substitution cipher was that of Charlemagne, Instead of transposition, he replace the whole alphabet with symbols that caused his generals many sleepless night trying to memorize these symbols.

Here are some of Charlemagne esoteric symbols

Many variations of cipher appeared during the fifteenth century, most are diagrammatic cipher, in modern times these can easily be created by embedding the message in pictures, maps, photographs etc.. Hoewever these type encryption is very weak and can easily be solved.
 

1585 civ Kahn p.146 Blaise de Vigenère wrote a book on ciphers, including the first authentic plaintext and ciphertext autokey systems (in which previous plaintext or ciphertext letters are used for the current letter's key). [Kahn p.147: both of these were forgotten and re-invented late in the 19th century.] [The autokey idea survives today in the DES CBC and CFB modes.]
 

In 1623 Sir Francis Bacon describe a cipher which now bears his name, bilateral cipher know today as a 5 bit encoded binary, then
he further advance it into steganographic device by using variation in type face to carry each bit of the encoding.

Thomas Jefferson in 1790's, invented a wheel cipher which later be redevelop as the Strip Cipher, M-138-A used by the US Navy during World War II.

During the whole 19th century there are lots of new development in this art.  Colonel Decius Wadsworth a progressive cipher, a greared cipher disk with a different number of letters in the plain and crypted alphabets which are used irregularly.  Charles Wheatstone introduce the Playfair cipher, it was publicized by his friend Lyon Playfair.  This type of cipher use a keyed array of letters to make a digraphic cipher that can be use in field. Admiral Sir Francis Beaufort invented a variant of Vigenere cipher which is know as Beaufort Cipher. In 1861 Friedrich W. Kasiski published a book about the first general solution of a polyalphabetic cipher
with repeating passphrase, this ends the era of strength of polyalphabetic cipher.

The most probably unbreakable or secure cipher was invented in 1917 by Gilbert S. Vernam, working for AT&T. Vernam cipher use a key with the same length as the message, this key will be used once and will never be use again, this is why it is know also as one time pad cipher.  The power of this cipher is that there is no pattern recognizable within the cipher text.  The security of this cipher is unbreakable if use properly, the key should be random as posible and once use it should be discarded and never be use again.  Technically One-Time Pad is nothing more than a large nonrepeating set of truly random key letter written on sheets of paper and glued together in a pad (schneier c1.5 p15)

Example (schneier c1.5 p15)

Message is:   ONETIMEPAD
Key is:          TBFRGFARFM
Ciphertext is: IPKLPSFHGQ

because:

          O + T mod 26 = I
          N + B mod 26 = P
          E + F mod 26 = K
         etc.
 

In 1919 Hugo Alexander Koch filed a patent on a rotor based cipher machine, the patent rights is assigned in 1927 to Arthur Scherbius who invented and market the Enigma machine since about 1923. The German Enigma is surely the best known cipher machine during WWII, its a polyalphabetic substitution system.  [It was broken by the Polish mathematician, Marian Rejewski, based only on captured ciphertext and one list of three months worth of daily keys obtained through a spy. Continued breaks were based on developments during the war by Alan Turing, Gordon Welchman and others at Bletchley Park in England. Kahn p.422 (and many others)].

(photos of Enigma Machines in this site http://www.math.arizona.edu/~dsl/ephotos.htm)
more info for enigma http://home.us.net/~encore/Enigma/enigma.html

The Purple Machine is used primarily by Japan for their secure communication, it uses telephone stepping relays instead of rotors, this way it achieved a totally different permuation of each step rather than the related permutaions of rotor in different positions. it was broken by a team headed by William Frederick Friedman.

In the late 1960's Horst Feistel and Walt Tuchman led a research program called Lucifer at IBM IBM Watson Research Lab , it is also the name of the of a block algorithm that came out of that program. Lucifer is a substitution permutation network with a building block similar to DES.  Biham and Shamir using differential cryptanalysis against the first Lucifer showed that with 32bit block and 8 rounds can be broken with 40 chosen plaintext, same strategy can break a 128bit block and 8 rounds with 60 chosen plaintext Lucifer.

So far everything is a private key cryptosystem.  In 1976 Withfield Diffie and Martin Hellman published the "New Directions in Cryptography", this introduce a new idea of public key cryptography.  The public key system is system with two types of keys, the private and the public key, the idea is that the public key can be publish and send across unsecure transmission media, this public key will be use to encrypt the plaintext and thats it, it can only use to encrypt but never decrypt. The decryption of the cipher text can be achieved by using the private key, only this key can restore back the ciphertext to its original plaintext.  For this system to work, at least the following conditions must be satisfied:

1. S(P(M) = M for every message M
2. All (S, P) pairs are distinct
3. Deriving S from P is hard as reading M
4. Both S and P are easy to compute

Having inspired with Diffie-Hellman paper, Ronald L. Rivest, Adi Shamir and Leonard M. Adleman created the RSA public key algorithm and presented it Martin Gardner on 1974 for publication in Scientific America.  RSA gets its security from the difficulty of factoring large number.  Here's the relatively easy to understand math behind RSA public key encryption.
 

Find P and Q, two large (e.g., 1024-bit) prime numbers.

Choose E such that E is less than PQ, and such that E and (P-1)(Q-1) are relatively prime, which means they have no prime factors in common. E does not have to be prime, but it must be odd. (P-1)(Q-1) can't be prime because it's an even number.

Compute D such that (DE - 1) is evenly divisible by (P-1)(Q-1). Mathematicians write this as DE = 1 (mod (P-1)(Q-1)), and they call D the multiplicative inverse of E. This is easy to do -- simply find an integer X which causes D = (X(P-1)(Q-1) + 1)/E to be an integer, then use that value of D.

The encryption function is encrypt(T) = (T^E) mod PQ, where T is the plaintext (a positive integer) and ^ indicates exponentiation. The message being encrypted, T, must be less than the modulus, PQ.

The decryption function is decrypt(C) = (C^D) mod PQ, where C is the ciphertext (a positive integer) and ^ indicates exponentiation.
Your public key is the pair (PQ, E). Your private key is the number D (reveal it to no one). The product PQ is the modulus (often called N in the literature). E is the public exponent. D is the secret exponent.

You can publish your public key freely, because there are no known easy methods of calculating D, P, or Q given only (PQ, E) (your public key). If P and Q are each 1024 bits long, the sun will burn out before the most powerful computers presently in existence can factor your modulus into P and Q.

(An example of this can be found in http://world.std.com/~franl/crypto/rsa-example.html)
 
 
 
 
 
 
 
 
 

Symmetric and Asymetric Cipher Algorithms
 

There are two general types of key based algorithms, these are the Symmetric or private key system and the
Asymetric or better known as the public key system.

Symmetric

Symmetric algorithm can be divided into two categories: stream cipher and block cipher.  The stream cipher sometimes work in single bit or sometimes byte at a time. this type of cipher algorithm use mostly on communication system where transmission of data cannot be measured, sometimes it may come in bytes or a single bit.

                     encrypted message
message ---> 101000100101110101 ---->receiver
 
 
 

The simplest implementation of stream cipher by using a keystream generator or sometimes called running-key generator, the output of this generator is a stream of bits that is XORed with the stream of plaintext bits to product ciphertext bits.

while (p[i])
{
     c = k[i] ^ p[i];
     i++;
}

p = plaintext
k = keystream
c = ciphertext bit

To decrypt this, XOR the x with the k

while (x[i])
{
    p = k[i] ^ c[i];
   i++;
}
 
 

Some algorithms that implements stream cipher

A5	stream cipher use to encrypt GSM(Group Special Mobile)
Hughes XPD/KPD	created by Hughes Aircraft Corp, used in army tactical radios and direction finding equiptment.
Rambutan	is designed by Communications Electronics Security Group, sold only as a hardware and not commercially available
Gifford	invented by David Gifford and is use to encrypt news wire reports in the Boston area from 1984 until 1988
RC4	is variable key size stream cipher develop by Ron Rivest for RSA Data Security Inc. In September 1994 someone posted a source code to the Cypherpunks.  Readers with legal copies of RC4 confirmed its compatibility.
Seal	designed at IBM by Phil Rogaway and Don Coppersmith, it was optimized for 32-bit processor.

 
 

Block cipher on the other hand, operates on the plaintext in group of bits (1 character is 8bit), for a modern computer the typical block is 64bits.
 
 

Some of the algorithms uses block cipher are:

DES	Data Encryption Standard has been standard for more than 20 years now, known as Data Encryption Algorithm by ANSI and the DEA-1 by ISO.
Multiple DES	is another variant of DES where it uses triple DES to do the encryption and decryption.
Crypt	is a variant of DES found on most UNIX systems.  It is primarily used as oneway function for passwords. but sometimes use as file encryption.
Lucifer	Invented by Horst Feistel and later by Walt Tuchman at IBM.
Feal	designed by Akihiro Shimizu and Shoji Miyaguchi from NTT Japan, it uses 64bit block and 64bit key.
LOKI	is an Australian alternative to DES and was presented in 1990.
RC2	is a variable key size encryption algorithm designed by Ron Rivest of RSA Data Security Inc.
GOST	is a block cipher algorithm develop by the  former Soviet Union, GOST is an acronym for "Gosudarstvennyi Standard or Goverment Standard".
Blowfish	is designed by Bruce Schneier, president of Counterpane System.  it is a public domain system.  it was designed for applications where key does not change.  Blowfish is a variable key length 64bit block cipher.
RC5	is a block cipher invented by Ron Rivest and analyzed by RSA Laboratories, There are three operations: XOR, addition and rorations, it has a variable length block.

 
 
 
 

Asymetric

Also called Public-Key algorithms are designed so that the used for encryption is different from the key used for decryption.  The decryption key cannot be calculated from the encryption key.  The idea is that the public key can be made public meaning a complete stranger can use the encryption key to encrypt a message, only the person who has the private key can decrypt the message, there is no way to decrypt the message using the encryption key. see the portion of Diffie, Hellman and RSA in the History

Security of Public-Key

Since a cryptanalyst has access to the public key, he can always choose any message to encrypt. This means that the a cryptanalyst, given C=Ek(P), can guess the value of P and easily check his guess.  This is a serious problem if the number of possible palintext message is small enough to allow exhaustive search, but can be solved by padding message with a string  of random bits. This makes identical plaintext messages, encrypt to different ciphertext messages. (Taken from Schiener c19 p461)
 

Some of the Algorithms that uses Public-Key

Knapsack Algorithms	Develop by Ralph Merkle and Martin Hellman, this is the first algorithm to implement public key.  It could only be use for encryption. Later Adi Shamir adapted the system for digital signature.
RSA	The first full fledged public key algorithm, one that also works for encryption and digital signatures. created by  Ronald L. Rivest, Adi Shamir and Leonard M. Adleman. see history(RSA)
Pohlig-Hellman	Similar to RSA
McEliece	Developed by Robert McEliece in 1978.  Based from algebraic coding theory. The algorithm makes use of the existence of a class of error correcting cods know as Goppa Codes. In 1991, two Russian cryptographers claimed that they have broken the McEliece, however their papers contained no evidence to substantiate their claim.
Elliptic Curve Cryptosystems	Elliptic Curve FAQ

Terminology

plaintext	is the original message
ciphertext	is the encrypted plaintext
encryption	is the process of disguising a message to hide its original content
decryption	is the process of turning back the ciphertext to its original form(plaintext)
cryptography	is the art and science of keeping the message secure
cryptographers	refers to someone practice cryptography
cryptoanalysis	is the art and science of breaking ciphertext
cryptology	is the branch of mathematics encompassing both cryptography and crytanalysis (scheiner p1.)
cryptologists	refers to the practitioner of cryptology

 
 
 

References

Applied Cryptography Second Edition by Bruce Schneier. Published by John Wiley &Sons Inc. ISBN 0-471-12845-7

Diffie: Whitfield Diffie and Martin Hellman, ``New Directions in Cryptography'', IEEE Transactions on Information Theory, Nov 1976.

RSA: Rivest, Shamir and Adleman, ``A method for obtaining digital signatures and public key cryptosystems'', Communications of the ACM, Feb. 1978, pp. 120-126.

Codes, Cipher and Secret Writing by Martin Gardner, Dover 0-486-24761

Cryptography the science of scret writing by Laurence Dwight Smith, Dover 0-486-20247
 

Links

Cryptography FAQ

Web pages of interest to cryptography researchers

Elliptic Curve Cryptography

Counterpane Literature
 
 
 

This page have been accessed