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.
1 | 2 | 3 | 4 | 5 | |
1 | A | F | L | Q | V |
2 | B | G | M | R | W |
3 | C | H | N | S | X |
4 | D | I | O | T | Y |
5 | E | K | P | U | Z |
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
Web pages of interest to cryptography researchers
This page have been accessed
Email: jet_reyes@jetemail.net