History of Computer Cryptography and Secrecy Systems
Jacob Mathai
A secrecy technique where the existence of an actual message is hidden.
The word is derived from the Greek words steganos (covered) and graphein
(to write). Steganography is ancient technique that has been used for
thousands of years as a primitive for secrecy systems and secret
communications. In the first century, Pliny the Elder described how the
milk from a thitymallus plant could be used as invisible ink. Another
technique in ancient Greece and Persia involved shaving a messenger's
head, writing a message on his scalp and waiting for the hair to grow
back before sending the messenger to the destination. The technique
primarily achieves security through obscurity and it's basic weakness is
that if the message is discovered, the secret communication is
revealed.
Cryptography is a technique used to hide the
meaning of a message and is derived from the Greek word kryptos
(hidden). This is different from steganograhic techniques in that one is
not hiding the actual message, only the meaning of the message. If a
message were to fall into the hands of the wrong person, cryptography
should ensure that that message could not be read. Typically the sender
and receiver agree upon a message scrambling protocol beforehand and
agree upon methods for encrypting and decrypting messages. Cryptography
is further divided into two implementation techniques and those include
transposition and substitiution.
It is possible to combine Cryptography and
Steganography together to achieve a higher level of security. Combining
these two primitives should both hide the meaning of a message as well
as conceal the physical message. If the message is intercepted, it can
be blocked but not read. During WW II, the Germans would scramble
messages and then shrink the text down to a tiny dot and insert the dot
as a "period" in some unsuspecting letter or text for secret
communications.
Transpostion is a cryptographic technique
whereby the letters in a message are rearranged to provide secrecy.
Think of the word dog and all of the ways one could arrange the letters
-- dog, dgo, odg, ogd, dgo, odg -- this anagram is a simple example of
transpostion. The position of the original letters all retain thier
idenities but change there original positions. As you increase the size
of the message to over 40 letters however, the number of permutations
grow exponentially and it becomes very difficult to decrypt such a
communication. Typically the sender and receiver agree upon a technique
to encode and decode messages using transposition. One of the first
cryptographic devices using transposition dates back to the fifth
century and was named the Spartan Scytale. The Scytale worked as follows
-- a fabric was wrapped around a staff and a message was written on the
cloth. Once unwound, the cloth appreared to have a meaningless scamble
of letters. THe sender and the receiver would both have matching sized
staffs to secure mutual communications.
Rail Fence Transposition is a technique
where a message is written on two or more lines with each consecutive
letter of the message being written on the next consecutive line. The
text on the second and third lines are then appended to the first line
to create a the scrambled message. A simple 2 line rail fence
transposition of the message "Hello World" is demonstrated below :
Substitution is a cryptographic technique where
each letter of the plaintext message is replaced by a different letter.
Each letter retains its original position in the message text, but the
identity of the letter is changed. This type of technique was documented
during Julius Caesar's Gallic Wars.
Plain Text refers to the human readable alphabet used to compose the original message. Cipher Text
refers to the encrypted plaintext message once the original letters in
the message have been substituted with the cipher alphabet. Ciphers are any form of cryptographic substitution applied to message text.
A simple substitution cryptographic
technique where the cipher alphabet is shifted a certain number of
spaces relative to the original plain alphabet. It was named for Julius
Caesar who employed the technique to secure military communications.
This is generally a weak encryption method in that there are only 25
distinct variations of shifts before the original message is revealed. A
simple 4 letter shift example is demonstrated below :
An Algorithm is a general method of encryption and a Key specifies the details of that particular encryption. Together they form Ciphers
or encrypted messages. In the case of a substitution cipher, the
algorithm would be replacing plain text letters with cipher text letters
and the key would be the actual cipher text alphabet.
Auguste Kerckhoffs
was a military cryptologist in the late 19th century. He proposed a
radical departure from traditional methods of securing communications in
his day. He proposed that the one should assume that the encryption
algorithms should be open and transparent and the only secured piece of
the cryptographic system should be the key. It was a departure from many
of the Steganographic techniques of the past and is the basis of modern
cryptography. If you think about RSA or 3DES, the encryption algorithms
are well known and advertised and the keys are the only unknown element
of the system. If a key is compromised, it is quickly changed and
communications are secured once again. Knowledge of the algorithm itself
does not render communications any less secure.
Nomenclators are an encryption techniques that
use a combination of codewords and ciphertext alphabets to secure
communications. The weakness in this technique is that the codewords and
ciphertext are typically written down by both the sender and receiver
and is vulnerable to enemy capture. This is different than memorizing 26
ciphertext letters and or distributing a new key once an existing key
is comprimised. A code can be described as substitution at the 'word'
level and a cipher is substitution at the individual 'letter' level.
In a homophonic substitution cipher, each plaintext
letter is replaced with several different ciphertext letters. Generally
speaking, as the frequency of the letter increases, the number of
potential ciphertext letters would increase proportinatly. For example
the letter "E" may have a frequency of 12% for most communications and
would potentially have 12 different ciphertext letters representing it.
This would complicate simple attempts at frequency analysis because an
encrypted message would represent a single letter "E" with 12 distinct
ciphertext letters.
pt type="text/javascript">
A Vigenere Cipher, named after a
french diplomat Blaise de Vigener, is polyalphabetic substitution cipher
first documented in the 1500's. It is commonly called a Vigenere square
which consists of a plaintext alphabet, followed by 26 alphabets each
respectively shifted by a single letter. The strength of the cipher lies
in the fact that a single letter can be represented in several
different ways because 26 distinct alphabets are used and this poses a
challenge to traditional frequency analysis techniques.
Typically, the sender and receiver agree upon a key (in this case a
word) and use the key to synchronize on which of the 26 alphabets to use
to encrypt and decrypt messages. Here is an example :
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
If the sender and receiver agreed upon the keyword of
"JAKE" and the sender wanted to encypt the plaintext word "Unix" and
send it to the receiver, it would be similiar to the following :
Keyword JAKE
Plaintext UNIX
Ciphertext DNSB
To encrypt the plaintext letter "U" using the keyword
"JAKE", one would start with the leftmost row beginning with the letter
"J" and find the intersection point with the top most row with the
letter "U". In this case the first letter of the ciphertext would be
"D". Next, you would find the leftmost row beginning with the letter "A"
and find the intersection point with the top most row with the letter
"N" which happens to be the ciphertext letter "N". This process
continues iteratively and the keyword is reused over and over as the
plaintext message lengths increase. Generally speaking, a longer keyword
provides some additional security. Wilhelm Kasiski and Charles Babbage
seperately cracked the Vigenere cipher by using frequency analysis of
letters in the English language and comparing them to encrypted
ciphertext messages.
The One Time Pad is a technique that offers
'perfect theoretical secrecy' by using a truly random key only once per
communication. Imagine a sender and receiver, each having matching pads
filled with hundereds of pages of unique keys composed of truly random
letters. The sender would encrypt a message using a Vigenere square and
the first key in his pad and the receiver would decrypt it in the same
way. At this point, both the sender and receiver would discard the first
page of their pads (destroy the last used key) and continue using new
keys for future messages. This offers perfect secrecy because even if a
single key is compromised, it does not reveal anything about future or
past transmissions. The strength of the technique lies in randomness and
one time use of the keys. Claude Shannon
described how if the ciphertext, key, and plaintext are changing at a
consistent rate, you are have achieved perfect secrecy in his 1949 paper
Communication Theory of Secrecy Systems .
Invented by Arthur Scherbius, Enigma was Germany's main
cryptographic technology during WW II. Folllowing the decryption of
the Zimmerman note during World War I and the effects that weak ciphers
had on the war's outcome, Germany was looking for "the unbreakable
cipher" and was interested in leveraging automation and the use of
machinery to replace traditional paper and pencil techniques. The Enigma
machnie consisted of a basic keyboard, a display that would reveal the
cipher text letter, and a scrambling mechanism such that each plain text
letter entered as input via the keyboard was transcribed to its
corresponding cipher text letter. The machine was modular in design and
multiple scrambling disks were employed to thwart attempts at frequency
analysis and these scrambling disks and there particular positioning
inside engima emulated many different cipher alphabets. To decipher a
message, the receiver require a code book (shared by both the sender
and receiver) detailing all the specific scrambler settings for the day
and would also have an identical enigma machine. Breaking Enigma was
crucial to ending World War II and it was eventually broken due in large
part to the work of Marian Rejewski, a polish statistician,
mathematician, and code breaker. Although Rejewski never broke the
Enigma, he transfered all his research to the English and the French
weeks before Germany invaded Poland. Eventually, Alan Turing and the
code breakers at Bletchley used Rejewski's work to build Bombes which
were electromechanical machines that were designed specifically to break
Enigma.
Lucifer was a symmetric encryption algorithm created
by Horst Feistel in the 1970's while working at IBM. The scrambling
technique of Lucifer was quite involved and begins with translating the
plain text string to binary format. Next, the binary string is shuffled
and divided into 64 bit blocks and encryption happens on a per block
basis. Each of these 'blocks' are split into 2 32 bit blocks and they
are named "Left(0)" and "Right(0)". The "Right(0)" block is put through a
mangle function which rearranges the binary numbers using a fairly
complex substitution cipher. The "Right(0)" block is then added to the
"Left(0)" block to create a new half block called "Right(1)" and the
original "Right(0)" block is renamed Left(1). This series of steps is
called a "Fiestel Round" and is repeated 16 times in total. The
mangler function can change and is determined by a key the sender and
the receiver agree upon. A modifed version of Lucifer was adopted as the
American standard for encryption known as DES or the Data
Encryption Standard. The main difference between Lucifer and DES was
that the NSA limited DES to 56 bit keys to balance national security
interests against personal and corporate privacy needs.
Whitfield Diffie and Martin Hellman were
pioneers in the fields of asymmetric cryptographic techniques. Prior to
thier work, most encryption was symmetric and involved the send and
receiver sharing a key to secure communications. They focused on one-way
functions which is simple to run and very difficult to undo. THe
Diffie-Hellman key exchange enables sender and receiver to establish a
secret key publically without any prior key sharing. This asymmetric key
system is one in that the encryption and decryption keys are not
identical and revolutionized cryptography for years to come. For the
first time in history, Alice and Bob could secure communications without
any prior interaction. This idea was later incorporated into RSA named
after Rivest, Shamir, and Adleman and is a common cryptograhic technique
on the internet today.
RSA is the most common assymetric cryptographic technique
on the internet today. It was created by Rivest, Shamir, and Adleman at
Harvard University and was based upon the research of Whitfield Diffie
and Martin Hellman.
Additional information on the mathematics of RSA can be founds at http://www.garykessler.net/library/crypto.html#rsamath
mathai(at)dsm.fordham.edu
Jacob Mathai
