2.0.0 THE CONCEPT OF
CRYPTOSECURITY
Security is the quality or state of being secure: - a relief from
exposure to danger, and making safe against adverse contingencies. But
encryption alone is not sufficient. Proper key selection, key management,
physical security, people security and procedures to ensure that the plaintext
does not leak out of the system via loopholes are all essential for a secure
computer data system. The strength of a good cryptosystem does not depend on
keeping its algorithm secret; the security of the cipher text relies solely on
the secrecy of the key.
2.1.0 CRYPTOGRAPHY
Cryptography is the art or science of secret writing, or more exactly, of storing information (for a shorter or longer period of time) in a form which allows it to be revealed to those you wish to see it yet hides it from all others. A cryptosystem is a method to accomplish this. Cryptanalysis is the practice of defeating such attempts to hide information. Cryptology includes both cryptography and cryptanalysis.
2.1.0 CRYPTOGRAPHY
Cryptography is the art or science of secret writing, or more exactly, of storing information (for a shorter or longer period of time) in a form which allows it to be revealed to those you wish to see it yet hides it from all others. A cryptosystem is a method to accomplish this. Cryptanalysis is the practice of defeating such attempts to hide information. Cryptology includes both cryptography and cryptanalysis.
Stewart, Ed Tiltel and Mike (2000) defined Cryptography as added
security to data during processing, storage and communications. They further
described the various types of cryptography such as Symmetric Key Cryptography
and Asymmetric Key Cryptography or Public Key.
Kessler (1998), described
cryptography as the science of writing in secret code. He further describes it
as one essential aspect for secure communication.
In data communication and telecommunication, cryptography is
necessary when communicating over any untrusted medium, which includes just
about any network, particularly the internet. Cryptography, then, not only protects
data from theft or alteration, but can also be used for user authentication.
Burnett and Panini(2004) outline the security requirement which
include the following:
·
Authentication
·
Privacy/confidentiality
·
Integrity
·
Non-repudiation
Liddell and scolt(1996) stated in their book
that in the famous Greek drama the
'Iliad', cryptography was used when Bellerophon was sent to the king with a
secret tablet which told the king to have him put to death. The king tried to
kill him by having him fight several mythical creatures, but he won every
battle.
The Spartans used a
system which consisted of a thin sheet of papyrus wrapped around a staff (now
called a "staff cipher"). Messages were written down the length of
the staff, and the papyrus was unwrapped. In order to read the message, the
papyrus had to be wrapped around a staff of equal diameter. Called the
'skytale' cipher, this was used in the 5th century B.C. to send secret messages
between greek warriors. Without the right staff, it would be difficult to decode
the message using the techniques available at that time. The following version
of the alphabet demonstrates the technique. First we see the wrapped version of
the alphabet, then the unwrapped version.
ADGJMPSVY
BEHKNQTWZ
CFILORUX
ADGJMPSVYBEHKNQTWZCFILORUX
Skytale cipher
Another Greek method
was developed by Polybius (now called the "Polybius Square"). The
letters of the alphabet would be laid out in a five by five square (similar to
the later Playfair method) with i and j occupying the same square. Rows and
columns are numbered 1 to 5 so that each letter has a corresponding
(row,column) pair. These pairs could easily be signaled by torches or hand
signals. Decryption consists of mapping the digit pairs back into their
corresponding characters. This system was the first to reduce the size of the
symbol set, and in a loose sense it might be considered the forerunner of
modern binary representations of characters. Try decoding the message on the
right.
\ 1 2 3 4 5
\_________
1|A B C D E T=54
2|F G H I J H=32
5344 44 4435
3|K L M N O I=42 4224 24 3211
4|P Q R S T S=44
5|U V W X Y/Z
The Polybius Square
Julius Ceasar used a
system of cryptography (i.e. the 'Caesar Cipher') which shifted each letter 2
places further through the alphabet (e.g. Y shifts to A, R shifts to T, etc.).
This is probably the first cipher used by most school children. In figure 2.4,
the first row is plaintext, while the second row is the equivalent ciphertext.
The distance of the displacement is not important to the scheme, and in fact,
neither is the lexical ordering chosen. The general case of this sort of cipher
is the "monoalphabetic substitution cipher" wherein each letter is
mapped into another letter in a one to one fashion. Try decoding VJKU.
ABCDEFGHIJKLMNOPQRSTUVWXYZ
CDEFGHIJKLMNOPQRSTUVWXYZAB
The Caesar Cipher
Cryptanalysis is the
practice of changing ciphertext into plaintext without complete knowledge of
the cipher. The Arabs were the first to make significant advances in
cryptanalysis. An Arabic author, Qalqashandi, wrote down a technique for
solving ciphers which is still used today. The technique is to write down all
the ciphertext letters and count the frequency of each symbol. Using the
average frequency of each letter of the language, the plaintext can be written
out. This technique is powerful enough to cryptanalyze ANY monoalphabetic
substitution cipher if enough cyphertext is provided.
El Gamely(1989) in his
book stated how cryptography started to progress. All of the Western European
governments used cryptography in one form or another, and codes started to
become more popular. Ciphers were commonly used to keep in touch with
ambassadors. The first major advances in cryptography were made in Italy.
Venice created an elaborate organization in 1452 with the sole purpose of
dealing with cryptography. They had three cipher secretaries who solved and
created ciphers that were used by the government.
Shamir (1977) in his
book declared Leon Battista Albert as "The Father of Western
Cryptology" in part because of his development of polyalphabetic
substitution. Polyalphabetic substitution is any technique which allows
different ciphertext symbols to represent the same plaintext symbol. This makes
it more difficult to interpret ciphertext using frequency analysis. In order to
develop this technique, Alberti analyzed the methods for breaking ciphers, and
devised a cipher which would try to render these techniques invalid. He
designed two copper disks that fit into each other, each with the alphabet
inscribed upon it. To start enciphering, a predetermined letter on the inner
disk is lined up with any letter on the outer disk, which is written as the
first character of the ciphertext. The disks are kept stationary, with each
plaintext letter on the inner disk aligned with a ciphertext letter on the
outer disk. After a few words of ciphertext, the disks are rotated so that the
index letter on the inner disk is aligned with a new letter on the outer disk,
and in this manner, the message is enciphered. By rotating the disk every few
words, the cipher changed enough to limit the effectiveness of frequency
analysis. Even though this technique in its stated form is very weak, the idea
of rotating the disks and therefore changing the cipher many times within a
message was a major breakthrough in cryptography.
Rivest(1990) explained
how the next major step was taken in 1518, by Trithemius, a German monk who had
a deep interest in the occult. He wrote a series of six books called
'Polygraph', and in the fifth book, devised a table that repeated the alphabet
with each row a duplicate of the one above it, shifted over one letter. To
encode a message, the first letter of the plaintext is enciphered with the
first row of the table, the second letter with the second row, and so on. This
produces a message where all available ciphers are used before being repeated.
Figure 2.5 shows a changing key cipher of this sort. Notice that the assignment
of code symbols to plaintext symbols changes at each time step (T1,T2,...). In
this system, the key repeats every 26 letters of cipher text.
ABCDEFGHIJKLMNOPQRSTUVWXYZ Plaintext
FGUQHXSZACNDMRTVWEJBLIKPYO T00
OFGUQHXSZACNDMRTVWEJBLIKPY
T01
YOFGUQHXSZACNDMRTVWEJBLIKP T02
PYOFGUQHXSZACNDMRTVWEJBLIK T03
...
GUQHXSZACNDMRTVWEJBLIKPYOF T25
A Changing Key Cipher
Behrouz andforouzan(2004) in their book stated that
in 1553, Giovanni Batista Belasco extended this technique by choosing a keyword
that is written above the plaintext, in a letter to letter correspondence. The
keyword is restarted at the beginning of each new plaintext word. The letter of
the keyword above the letter of the plaintext is the first letter of the cipher
line to be used. In other words, if the plaintext letter is 'b', and it's
keyword letter is 'r', then the line of the Trithemius cipher beginning with
'r' is used to encipher the letter 'b'.
The most famous
cryptographer of the 16th century was Blaise de Vigenere (1523-1596). In 1585,
he wrote 'Tracte des Chiffres' in which he used a Trithemius table, but changed
the way the key system worked. One of his techniques used the plaintext as it's
own key. Another used the ciphertext. The manner in which these keys are used
is known as key scheduling, and is an integral part of the "Data
Encryption Standard" (DES) [DESDOC77]
which we will discuss later.
Robshaw (1994) stated
in his book that in the year 1628, a Frenchman named Antoine Rossignol helped
his army defeat the Huguenots by decoding a captured message. After this
victory, he was called upon many times to solve ciphers for the French
government. He used two lists to solve his ciphers: "one in which the
plain elements were in alphabetical order and the code elements randomized, and
one to facilitate decoding in which the code elements stood in alphabetical or
numerical order while their plain equivalents were disarranged." When
Rossignol died in 1682, his son, and later his grandson, continued his work. By
this time, there were many cryptographers employed by the French government.
Together, they formed the "Cabinet Noir" (the "Black
Chamber").
Shamir and
Adleman(1978) stated in their book that the father of American cryptology is
James Lovell. He was loyal to the colonies, and solved many British ciphers,
some which led to Revolutionary victories. In fact, one of the messages that he
deciphered set the stage for the final victory of the war.
According to
Panini(2004) he stated that the 'wheel cipher' was invented by Thomas Jefferson
around 1795, and although he never did very much with it, a very similar system
was still in use by the US navy only a few years ago. The wheel cipher
consisted of a set of wheels, each with random orderings of the letters of the
alphabet. The key to the system is the ordering in which the wheels are placed
on an axle. The message is encoded by aligning the letters along the rotational
axis of the axle such that the desired message is formed. Any other row of
aligned letters can then be used as the ciphertext for transmission. The
decryption requires the recipient to align the letters of the ciphertext along
the rotational axis and find a set of aligned letters that makes linguistic
sense as plaintext. This will be the message. There is a very small probability
that there will be two sensible messages from the decryption process, but this
can be checked simply by the originator. Without knowing the orderings of
symbols on the wheels and the ordering of wheels on the axle, any plaintext of
the appropriate length is possible, and thus the system is quite secure for one
time use. Statistical attacks are feasible if the same wheels are used in the
same order many times.
GJTXUVWCHYIZKLNMARBFDOESQP
W1
IKMNQLPBYFCWEDXGZAJHURSTOV
W2
HJLIKNXWCGBDSRVUEOFYPAMQZT
W3
...
BDFONGHJIKLSTVUWMYEPRQXZAC
Wn
A Wheel Cipher
Schneider (1996) stated
that In 1844, the development of cryptography was dramatically altered by the
invention of the telegraph. Communication with the telegraph was by no means
secure, so ciphers were needed to transmit secret information. The public's
interest in cryptography blossomed, and many individuals attempted to formulate
their own cipher systems. The advent of the telegraph provided the first
instance where a base commander could be in instant communication with his field
commanders during battle. Thus, a field cipher was needed. At first, the
military used a Vigenere cipher with a short repeating keyword, but in 1863, a
solution was discovered by Friedrich W. Kasiski for all periodic polyalphabetic
ciphers which up until this time were considered unbreakable, so the military
had to search for a new cipher to replace the Vigenere.
El Genial (1985) stated
that the 'Playfair' system was invented by Charles Wheatstone and Lyon Playfair
in 1854, and was the first system that used pairs of symbols for encryption.
The alphabet is laid out in a random 5 x 5 square, and the text is divided into
adjacent pairs. The two letters of the pair are located, and a rectangle is
formed with the two letters at opposite corners. The letters at the other two
corners are the two letters of ciphertext. This is very simple to use, but is
not extremely difficult to break. The real breakthrough in this system was the
use of two letters at a time. The effect is to make the statistics of the
language less pronounced, and therefore to increase the amount of work and the
amount of ciphertext required to determine a solution. This system was still in
limited use in world war II, and was very effective against the Japanese.
IKMNQ
LPBYF
PLAINTEXT =
PL AI NT EX TZ
CWEDX = =
GZAHU
LPMGMOXEAS = LP MG MO XE AS
RSTOV
A Playfair System
Vigenere (1972) stated
that in 1859, Pliny Earle Chase, developed what is known as the fractionating
or topographic cipher. A two digit number was assigned to each character of
plaintext by means of a table. These numbers were written so that the first numbers
formed a row on top of the second numbers. The bottom row was multiplied by
nine, and the corresponding pairs are put back in the table to form the cipher
text.
Hellman’(1976) started
in his book that Kasiski developed a cryptanalysis method in 1863 which broke
almost every existing cipher of that time. The method was to find repetitions
of strings of characters in the ciphertext. The distance between these
repetitions is then used to find the length of the key. Since repetitions of
identically ciphered identical plaintext occur at distances which are a
multiple of the key length, finding greatest common divisors of repetition
distances will lead to the key length. Once the key length (N) is known, we use
statistics on every Nth character and the frequency of use implies which
character it represents in that set of ciphertext symbols. These repetitions
sometimes occur by pure chance, and it sometimes takes several tries to find
the true length of the key using this method, but it is considerably more
effective than previous techniques. This technique makes cryptanalysis of
polyalphabetic substitution ciphers quite straight forward.
The story of
cryptography would be at an end if it weren't for the practical problem that in
order to send a secret message, an equal amount of secret key must first be
sent.
2.3
DES – DATA ENCRYPTION STANDARD
In
1972 the US NATIONAL BUREAU OF STANDARDS began the search for an encryption algorithm
that could be tested and certified. After several false starts in 1974 IBM
offered the US government an algorithm which was based on the early 1970’s
LUFICER algorithm. The offer was accepted and the algorithm was tested and
‘adjusted’ by the NSA and eventually released as a federal standard in 1976.
DES
is a SYMMETRIC BLOCK cypher based on a 64 bit block. The user feeds in a 64
block of plain text and is returned 64 bits of cyphertext. The same algorithm
and key are used for the encryption and decryption operations.