Survey of Encryption & Cryptography
Summary
I began this paper thinking that
the primary topic would be a detailed analysis of encryption technology. Exposing mathematical algorithms in fine
detail and having brilliant words of analysis to provide as a result of my
efforts.
Well, much like evolution, what I started with and what actually came
in to being were not the same. I
discovered a topic far more vast than I had imagined. A topic rich in history, application, and politics. With this discovery I decided this topic
would be best served, and better received, from an introductory perspective. Besides, math is
really boring anyway, right?
This paper starts with the history of encryption and cryptography. There was far more history than I ever could have of suspected, approximately 4000 years worth.
As a substitute for the mathematics of today’s cryptographic algorithms, I have chosen to outline the major subjects that have had the greatest impact on the use of the Internet and e-commerce. You will later see the invention/discovery that makes security over the Internet even possible.
In to the future… I have addressed two technologies, once far-fetched and one that is getting a foothold as we speak. The other future topic is on the political side. I have provided a small glimpse of one of the major controversies between politics and encryption.
This being said…. I hope you enjoy the read.
Encryption in the Past
Merriam-Webster defines encryption as derived from the verb ‘encrypt’, also known as ‘encipher’ or ‘encode’. The verb encrypt means ‘to convert (as information) from one system of communication into another; especially : to convert (a message) into code.’[1]
The word encryption is derived from the Greek word kryptos which means ‘hidden’. While the Greek word is what has carried forward to today, the Greeks were not, in fact, the origin of encryption itself.
Each encryption system necessarily consists of three parts: 1) The algorithm, 2) The key, and 3) The key management system. The algorithm is the process by which the plain text information is transformed to the encoded, or encrypted, information. The key is the information that tells the algorithm where to begin, a point of origin if you will. The key management system is a system implemented for the purpose of determining how the keys will be used, which keys will be used, and how they will be controlled.
The Chronology of Encryption[2]
1900 BC A scribe in Egypt creates an inscription using non-standard
hieroglyphs. This may have been the
first implementation of an encryption algorithm.
1500 BC Assyrian merchants, fearing misrepresentation in the marketplace,
institute a primitive form of identification.
They began using intaglio.
This was a flat stone with engravings on it unique to a specific
trader. In this manner, people could be
guaranteed of whom they were actually dealing with in business
transactions. This is the ancient
history equivalent to the modern day ‘digital signature’ used for transacting
business on the Internet.
500-600 BC The book of Jeremiah is written by Hebrew scribes using the ATBASH
cipher. The ATBASH cipher will be
explained later.
487 BC “Skytale” encryption method is created by the Greeks. This method used a belt, a staff, and a
writing utensil. The belt was wrapped
around the staff, the message was written, the belt would then be worn as
usual. Once at the destination, the belt would be re-wrapped around an
identical sized staff, and the message could be decoded.
100-44 BC Alphabetical substitution is implemented by Julius Caesar for sending
government communications.
1379 Gabrieli di Lavinde created a combination substitution alphabet and
small code. His encryption method was used, largely by diplomats, for about 450
years. While stronger methods were
developed, this one held favor due to simplicity.
1466 Leon Battista Alberti invented and published the first polyalphabetic
cipher. He also created a cipher
disk. A tool used to simplify the
process of encoding and decoding messages.
This later became known to Americans as the Captain Midnight Decoder
Badge. This class of cipher was not broken until the 1800’s.
1518 Johannes Trithemius wrote the first printed book on cryptology. He
invented a steganographic cipher in which each letter was represented as a word
taken from a succession of columns. The resulting series of words would be a
legitimate prayer. He also described polyalphabetic ciphers in the now-standard
form of rectangular substitution tables. He introduced the notion of changing alphabets
with each letter.
1563 Giovanni Battista Porta wrote a text on ciphers, introducing the
digraphic cipher. He classified ciphers as transposition, substitution and
symbol substitution (use of a strange alphabet). He suggested use of synonyms
and misspellings to confuse the cryptanalyst. He apparently introduced the
notion of a mixed alphabet in a polyalphabetic tableau.
1585 Blaise de Vigenère documented the first autokey system for plain- and
cipher-text.
1623 Sir Francis Bacon described a 5-bit binary encoding that he later
advanced in to a steganographic device.
1790 With the help of Dr. Robert Patterson,Thomas Jefferson invented the
wheel cipher. This was reincarnated and used in WW-II by the US Navy as the
Strip Cipher, M-138-A.
1917 William Frederick Friedman began work as a cryptanalyst for the U.S.
government. He later started the first
military school for cryptanalysis.
1933-1945 The Enigma machine is implemented as the premier cryptographic device
for Germany.
1976 A modified Lucifer cipher, designed by IBM, was chosen to be the U.S.
Data Encryption Standard(DES). It is still in use today, although the advances
in computing power have reduced its relative strength. It has found life in TripleDES.
1976 Whitfield Diffie and Martin Hellman published ``New Directions in
Cryptography''. This paper introduces the idea of public key cryptography and
the challenge/response utility.
1977 Ronald L. Rivest, Adi Shamir and Leonard M. publish the RSA algorithm
in the September issues of Scientific American. The RSA algorithm is the first to use a public, or asymmetric,
key system.
1990 Xuejia Lai and James Massey in Switzerland publish a new block
encryption method called International Data Encryption Algorithm (IDEA). IDEA
was designed to replace DES. IDEA uses
a 128-bit key and is designed to be efficiently employed on computing systems.
1991 Pretty Good Privacy (PGP) is released by Phil Zimmermann. His release is spurred by the threat of the
FBI to demand access to communications of U.S. citizens. PGP is particularly notable because it is
released as freeware, thereby provided every person the ability to secure their
personal communications.
1994 Professor Ron Rivest publishes the proposed algorithm, RC5. This algorithm allows the user to vary the block size, number of rounds and key length.
Classic Cryptographic Methods[3][4]
Many different cryptographic methods have been developed over the past several thousand years. Most of them have been rendered obsolete with the invention of the computer. Many of these methods’ greatest weakness was not the method itself, but in the loss of the keys. As long as the keys were secure, the code was secure.
The 20th century has brought with it computational power that is far more powerful than everything that has preceded. Algorithms that were once secure are now crushed in seconds by a home personal computer.
Below are a few of the classic encryption methods. Some are so simple, a child could break it in seconds. The only one’s that are still relatively secure are methods that rely on physical materials.
Transpositions – This uses a table with words placed in them, then the words are read in an order different from how they were input. Using a horizontal to vertical transposition. Example….. ‘Get me an ice cold beer’ = ‘geioee cletaedr n m cb ‘. Pay close attention to the spaces, they count too.
|
|
1 |
2 |
3 |
4 |
5 |
|
1 |
G |
E |
T |
|
M |
|
2 |
E |
|
A |
N |
|
|
3 |
I |
C |
E |
|
C |
|
4 |
O |
L |
D |
|
B |
|
5 |
E |
E |
R |
|
|
Pig-Latin – Familiar to most Americans from childhood. Basically… Take the first set of constants of a single word. Move them to the end of the word. Take ‘ay’ and add it to the end of the new word, and you are done. Example…’Go home’ = ‘Ogay omehay”.
Grille – This method is deciphered by physically laying a sheet with holes punched out, over a document. The visible characters through the holes are the actual message. This method is not viable for computer systems, but is still serviceable for physical messages.
Caesar Substitution – This simply substitutes a letter with the one 3 letters down the alphabetic line. Example… ‘Go home’ = ‘jr krph’.
Atbash – This encoding method reverses the alphabetic order.
Example… ‘Go home’ = ‘tl slnv’.
Additional Classic Encryption Methods
Playfair
Bifid – Type of columnar or matrix transposition
Monoalphabetic
Substitution
Map Cipher
Diagraphic Substitution
Jefferson Cipher
Polybius Chequerboard
Basic Types of Ciphers
The two types of ciphers that have
formed over the years are Block Ciphers and Stream Ciphers.
A block cipher accepts a predefined quantity, or
space, to be encrypted. If the message
is too long to fit in a single block, the message will be broken in to as many
blocks as necessary. Once the message
is broken in to blocks, each block is then encrypted. An example of a block cipher is the Transpositions encryption method.
Stream ciphers do not rely on predefined data spaces or blocks of data. A stream cipher modifies each character at a time, without concern for the quantity of data being transmitted. This type of cipher is generally considered faster, but less secure than block ciphers. An example of a stream cipher is Atbash.
Importance of Encryption
Historically, encryption
has found a home in the marketplace, the government, and in the military. However, it has not even been approached
from the perspective of the individual.
In the marketplace, this
was largely in the form of assuring the identities of the parties involved in a
transaction. The Assyrians and
Babylonians used these signatures to protect the manufacturing secrets for
pottery. The Chinese were concerned
about the protecting their silk trade.
The loss of a trade secret to an industrial entity can easily cause it
to lose its competitive edge. The use
of encryption allows the businesses to maintain their advantage.
From a militaristic
perspective, armies have always been concerned about guarding information
pertaining to force strength, location, and orders. An enemy who knows these factors gains a distinct advantage over
their opponent. The Germans knew this
and implemented the Enigma machine to ensure this type of information was kept
from the Allies. The Allies, knowing
the importance of intercepting communications, spent exorbitant amounts of
money, time, and lives to acquire this machine.
For an entertaining look
into the importance of encryption, I recommend the movie ”U-571” (2000). It is a fiction, based on fact, of the
pursuit of the Enigma machine.
Encryption Today
The primary use of encryption today is for communicating data across the Internet. Individuals, businesses, and the government are all concerned about ensuring that only the intended targets have the ability to correctly read the information being sent. To this end, there are considerable monies being spent in pursuit of security.
Modern day encryption, like any science or field of study, has built itself on the shoulders of those that have come before. The two main types of ciphers, block and stream, are still the two types used today. Technology has however added its own unique twist to the classical methods. Technology has allowed the addition of a new key system.
Keys and Key Systems
Keys are the means by which encoded messages are decoded. Historically, it was possible that the keys be physical. This physical accountability all but guaranteed whether or not the key had been compromised. Systems that did not require a physical component meant that possessors of the key were more difficult to identify. Both of these systems had their advantages and disadvantages, however, they were both symmetric key systems.
The operating environment of the internet precludes the use of physical keys. In addition, it also makes difficult the use of symmetric keys. The use of symmetric keys requires an un-encoded pre-arrangement between sender and receiver. This presents a significant security risk. The use of asymmetric key systems is what differentiates classical methods with modern methods of encryption.
Symmetric Key System[5] –Requires access to, and the use of, the same key for both sender and receiver. All of the classical encryption methods used this key system. This system also known as a private key system.
Asymmetric Key System[6] - This system uses a public key and a private key. It uses as a trap-door one-way function, in that it is very easy for anyone to encrypt the message, but very difficult to decrypt the message unless attempted by the intended recipient. This is the type of key system that the Diffie-Hellman paper described and is commonly referred to today as the Public Key Infrastructure (PKI).
Public Key – A value provided by a trusted designated authority. This key is readily available to the public and is used to encrypt data.
Private Key – A value held secret by each party and is known only to that party. This key is used for encryption and decryption of data.
Encryption Standards and Algorithms
The following is a description of the more common algorithms and standards in use today for encrypting data.
Data Encryption Standard (DES)[7] – Also known as Federal Information Processing Standard (FIPS) 46-3. DES uses an improved IBM Lucifer algorithm called data encryption standard (DEA) which is defined in the American National Standards Institute (ANSI) X9.32. DEA is a 64-bit block cipher that uses a 56-bit key. DES is no longer considered as secure by the cryptographic community and is no longer allowed for government use. However, since it still takes ~22 hours to crack a DES encryption, it may be considered serviceable for personal, non-financial use.
Advanced Encryption Standard (AES)[8] – AES is a U.S. government standard, required by the National Institute of Standards and Technology (NIST), that specifies a cryptographic algorithm for protecting sensitive, but un-classified, information. AES is identified in FIPS Publication 197. AES uses the Rijndael (pronounced ‘rhine-doll’) algorithm. The Rijndael algorithm is a block cipher that uses 128-, 192-, or 256-bit blocks with 128-, 192-, or 256-bit keys.
Rivest-Shamir-Adleman (RSA)[9] – Created by Ron Rivest, Adi Shamir, and Leonard Adleman. This is the first asymmetric key system. As this is the basis of today’s’ Public Key Infrastructure, I have included a plain-English, detailed description of the algorithm as described by Francis Litterio:
1.
“Find P and Q,
two large (e.g., 1024-bit) prime numbers.
2.
Choose E such that E
is greater than 1, E is less than PQ, and 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.
3.
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.
4.
The encryption function is C = (T^E) mod PQ,
where C is the ciphertext (a positive integer), T is the
plaintext (a positive integer), and ^ indicates exponentiation. The message
being encrypted, T, must be less than the modulus, PQ.
5.
The decryption function is T = (C^D) mod PQ,
where C is the ciphertext (a positive integer), T is the
plaintext (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.”[10]
TripleDES[11] – This uses the DES encryption standard, but instead of using a single key and encrypting once. This is a 3 key system that encrypts the message 3 time in succession. While TripleDES offers a more secure method of encrypting data, it does not offer the additional security one might expect. If n= the # of possible keys, and we use a 3 key system, it is intuitively reasoned that the effective # of steps to find all possible keys is 3n. However, there are algorithms that effectively reduce the steps to 3n-x, where x is a value representing eliminated keys at the outset.
MD5[12]
- This is latest incarnation of a message digest algorithm created by
Ron Rivest in 1991. The predecessors
were MD2 and MD4. MD5 has been
optimized for efficiency on 32-bit systems.
MD5 is a block cipher that uses 512-bit blocks. MD5 is an Internet Engineering Task Force
(IETF) standard RFC1321.
Pretty Good Privacy (PGP)[13][14] – This is a freely available encryption standard introduced by Philip Zimmerman. This standard was introduced to ensure that every individual had the ability to freely protect their data transmissions. PGP is an asymmetric key system that uses the DES, RSA, and MD5 encryption algorithms.
Public Key Infrastructure(PKI)[15]
The PKI is the system that is in place on the Internet today that allows users to verify the authenticity of other users and to encrypt or decrypt messages between one another without requiring an out-of-band communication of required keys. This is referred to as an asymmetrical key system.. This system is only responsible for issuing keys, this system does not actually perform encryption itself, it only provides the keys to be used for encryption.
Components of a
Public Key Infrastructure
Certificate Authority(CA)[16] - Grants requests for digital certificate if the Registration Authority approves the requestor’s credentials.
Registration Authority[17] - At the request of the CA, the RA performs user identity verification.
Certificate Repository – The one or more locations where digital certificates, including their public keys are stored.
Certificate Management System – The parent system that governs the operation of a public key infrastructure.
Digital Certificate[18] - This is basically a ‘credit card’. It contains a serial number, the user’s name, a copy of the assigned public key, expiration date, and the digital signature of the CA.
Digital Signature[19] - Much like it sounds, this is a piece of digital information that authenticates the sender, and is used to verify the message received is an unaltered copy of the message sent. Digital signatures may be used with or without encryption. A digitally signed message is not necessarily and encrypted message.
How PKI Works[20]
Please note that this entire section is quoted from the above footnoted source.
Step 1.
Subscriber applies to Certification Authority for Digital Certificate.
Step 2.
CA verifies identity of Subscriber and issues Digital Certificate.
Step 3.
CA publishes Certificate to Repository.
Step 4.
Subscriber digitally signs electronic message with Private Key to ensure Sender
Authenticity, Message Integrity and Non-Repudiation and sends to Relying Party.
Step 5.
Relying Party receives message, verifies Digital Signature with Subscriber's
Public Key, and goes to Repository to check status and validity of Subscriber's
Certificate.
Step 6.
Repository returns results of status check on Subscriber's Certificate to
Relying Party.
How Public Key Encryption (PKE)
Works
1. Both sender and receiver request, receive and publish their public keys.
2. The sender retrieves the receiver’s public key and uses it to encrypt the message.
3. The sender then signs the message with a private key and sends the message.
4. Once the receiver retrieves the message, it is decrypted using the receiver’s private key.
5. The receiver then verifies the sender’s signature using the sender’s public key, then reads the message.
Encryption in the Future
The future of encryption is as uncertain as the future of technology itself. The more powerful the technology at hand, the harder it will be to create encryption methods that can withstand the onslaught of the computational power readily available to the average PC owner. The future of encryption appears to lie in the hands of forthcoming technology and the politics of our time. It is on these battlegrounds that the future of our society’s privacy will reside. It is my hope that these concluding sections will both spark your imagination and give you concern for our future.
New Technologies
Quantum cryptography is on the leading edge of cryptographic implementations. It is currently relegated to the laboratory for reasons of technical feasibility. Quantum cryptography is conceptually simple. Signals have a certain polarization, as long as the polarization remains unchanged, the signal has not been intercepted or monitored in any way. Interception or monitoring causes a polarization shift.
Quantum cryptography uses this technology to publicly distribute key information. The receiver records a polarization and asks the sender if the recorder polarization is correct. If it is, then the receiver knows it has a valid key unknown to anyone else. Here is the magic…. The Heisenberg principle states that a state cannot be monitored without changing the state itself. So far, on a quantum level, this is true. This means that if the key is monitored during transmission, the polarization will change, and the sender will detect this because the polarization information returned from the receiver will be in-correct. Poof…It’s like magic!!
Side Note – In reviewing this topic, I also discovered that the Los Alamos test facility has successfully performed teleportation on the quantum level. Maybe Transporters are in our future.
Biometrics[23][24]
Biometric encryption uses an individuals own physical body characteristics as the encryption key. Anyone who watches science-fiction movies is familiar with how they are used. Capt. Picard ( Star Trek) simply speaks in to the air and the computer responds to him. Capt. Leo Davidson ( Planet of the Apes) placed his palm on a screen, thereby imprisoning Thade. Both of these are classic sci-fi examples of biometric encryption. The systems would identify each individual for who they were, not allowing for impersonation, and respond accordingly.
While biometric encryption is in use today, it is far from being mainstream. The primary reason for this is that it is very costly to implement. For this reason I consider biometric encryption a future technology.
Below is a list of typical biometric encryption techniques and a brief description.
Fingerprint – This type of encryption registers either fingerprints or the imprints left by a person’s palm. These devices are considered to have an error rate of 1 in 100,000. Finger print scanners are relatively cheap, but palm scanners cost ~$2000.
Optical – This method used either the iris or retina of the human eye. These scanners have an error rate of 1 in 2,000,000. Financial institutions are looking in to these types of devices for ATMs. Cost is ~$6,500.
Facial Structure – As the name implies, the scanner examines the overall facial structure of the individual. The two major factors that impact the error rate are differences in the lighting conditions and the distance from the scanner to the subject. These devices are rather cumbersome, but have a low cost around ~$150.
Voice – Voice recognition systems use the characteristics of an individuals voice to identify the person. Voice lends itself extremely well for use in telecommunication systems, however it has an error rate of 2-5%. Voice recognition is generally considered more secure than PINs. Cost is relatively low at ~$100.
Signature – This biometric is actually more of a present technology than a future technology. Many retail stores are now using this for credit card purchases. The individual applies their signature on a digital device and the signature is then recorded by computers. It is important to note, however, that the stores are not actually verifying the person with this signature, but simply recording it. The error rate can be fairly high simply due to the fact that an individual’s signature is not always exactly the same. These are relatively low cost devices.
Keystroke – This is a slight derivation of the standard password or PIN method. One might accurately refer to it as the ‘Rhythm Method of Access Control’ J. This system does not simply use the password or PIN, it also uses information on how the key was entered. It senses the rate the key is entered and detects the rhythm of the entry as well. It is argued that this is one of the less secure biometric methods, however it has a low cost of implementation.
Political Ramifications
First Amendment Issues[25] - The issue at hand here is whether or not encryption is a right protected under the First Amendment. Under the Clinton administration, the government made an attempt to impose standards on society with regards to the use of encryption. One attempt was the ‘Clipper Chip’. This was a device that would be placed in all telecommunications equipment to ensure the government could access encrypted messages. It was determined that this would only be effective if all encryption device used this chip. Due to a lack of market interest, this initiative failed.
The main argument of the government is that encryption can hide the work of evildoers, and that this is reason enough to justify a regulated standard for encryption. Fear of this use is not grounds for restricting free speck. As Justice Brandeis wrote in Whitney vs. California(1927):
“Fear of serious injury cannot
alone justify suppression of free speech and assembly. Men feared witches and
burnt women. It is the function of speech to free men from the bondage of
irrational fears. To justify suppression of free speech there must be
reasonable ground to fear that serious evil will result if free speech is practiced.
There must be reasonable ground to believe that the danger apprehended is
imminent.”[26]
It is important that we not allow the government to control how we encrypt our information, for with the loss of that control is the loss of our privacy of life. It is information systems of the future that will be the battlegrounds for peoples freedom of thought and expression. The Truth may be out there, but that does not make it everyone else’s business.
Guard well your freedoms, else they may be no more.