Complexity Essay Research Paper INTRODUCTIONOne important yet

Complexity Essay, Research Paper

INTRODUCTION

One important, yet practical, application of complexity theory is cryptography. It has become one of the main tools for privacy, trust, electronic payments, and other forms of security. It is no longer just a military tool and the advantages it provides should be used to the fullest extent. This paper will discuss basic terminology and main methods of cryptography.

BASIC TERMINOLOGY

Cryptography is the science of scrambling text so that no one can read it except for the intended recipient. The art of breaking ciphers without the proper key is called cryptanalysis. Cryptography deals with the secure message, digital signatures, authentication, and other similar applications. Cryptology is the branch of mathematics that studies the foundation of cryptographic methods. The process of transforming plaintext into a form that is meaningless to anyone that might intercept it is called encryption. The process of decoding the message is called decryption. This can be done by using an encryption algorithm, a decryption algorithm, and a secret or private key. The sender uses the encryption algorithm to encode the message, and the receiver uses the decryption algorithm and the key to decode the message. A third party intercepting the encoded message will have worthless data unless they can figure out the decryption algorithm and obtain a key. To best ensure that the key is kept safely out of the hands of the third party it is never to be sent with the encoded message.

HISTORY OF CRYPTOGRAPHY

The study of cryptography dates back thousands of years to the hieroglyphs of early Egyptian civilization. Cryptography has been used by such figures as Julius Caesar, Charlemagne, Louis XIV and Mary Queen of Scots. One of the simplest cryptographic algorithms ever used was the one called the Caesar cipher. It was used by Julius Caesar to send messages to his generals. It consisted of switching each alphabetic letter to the letter that was three letters down in the alphabet. For example, Caesar would become Fdhvdu . This algorithm was later improved and renamed ROT13. This algorithm allowed the letters to be shifted to any letter between 1 and 25 in the alphabet, and the number of letters shifted was the key. A simple step away from ROT13 is Monoalphabetic substitution. In this algorithm, each letter corresponds to another letter but in no particular order. For example a = m, s = p, and z = d, etc for all 26 letters. This made the algorithm harder to break, but also made for large keys that couldn t be memorized because they consisted of 26 pairs of letters.

Blaise de Vigenere developed a poly-alphabetic substitution known as the Vigenere cipher. The algorithm encrypts messages several letters at a time instead of letter by letter. For example fh = lm, yz = ef. To simplify making the key that would be required for this for such an algorithm, a table is used in conjunction with the key. The table would be fairly large, but the key would be small enough to be memorized and the table would be useless without the key. This cipher wasn t totally safe, but no sure method of breaking was developed until the 20th century.

Sir Francis Bacon s biliteral cipher employed an arrangement of the alphabetic letters a and b in five-letter combinations each representing a letter of the alphabet. This illustrates the principle that a code employing only two different signs can be used to transmit data.

Modern cryptography is concerned with four chief objectives:

1. Confidentiality (the information cannot be understood by anyone other than the intended recipient).

2. Integrity (the information cannot be altered during storage or transit without the alteration being detected).

3. Non-repudiation (the creator cannot deny at a later stage his intention in the creation and transmission of the information).

4. Authentication (the sender and receiver can confirm each other s identity and the origin or destination of the information).

The advances that have been made in technology such as Internet e-Commerce, communications satellites, and television signals have generated a serious need for more versatile and secure systems and methods of encryption. With the widespread use of the Internet for both private and commercial business, information security seems to touch every aspect of our lives yet the average Internet user doesn t realize that even their e-mail can be intercepted and read. Possibly the greatest barrier to computer security is the human factor. The average user is a non-programmer and most encryption software is not user friendly.

Prior to 1977 the algorithms used were symmetic, the same key was used to encrypt and decrypt the ciphertext. The United States adopted the Data Encryption Standard (DES), a symmetric algorithm, as a federal standard in 1977. A pair of American mathematicians, Whitfield Diffie and Martin Helbman, introduced the asymmetric or public key algorithm in 1977. There are advantages to using the asymmetric algorithms because you have to have both keys to break the cipher and you need fewer unique keys. Also in 1977, while at the Massachusetts Institute of Technology, Ronald Rivest, Adi Shami, and Len Adleman, invented a new asymmetric technique RSA which is the most commonly used technique today. Shortly after the devel