Encryption

Encryption

By:

Athena Roberts

IT 319

Western International University: SRP Campus

Instructor: Michael Jacques

23 Sep 2002.

Executive Summary

This paper covers encryption. It gives a brief history starting with letter substitution and ending with the first secure key creation method that didn’t require transmission of the actual key. The paper then shows how modern encryption works and gives a look into the possible future of encryption.

Introduction

Everyone has always wanted privacy. In earlier times, that usually meant going out of earshot with someone who you wanted to talk privately with. Today, that still works well for most people provided no one really wants to hear what those two people are talking about. Problems arose when you tried to communicate with someone you were not with and you wanted to eliminate the chances that an unintended person might be able to read your transmission. That was the beginning of encryption.

In this paper I will not get into detail about all the early forms of encryption and how they worked. Because this paper relates to the information technology industry, I will mainly focus on cryptography and cryptanalysis (code breaking) and how they work as they relate to that industry. However, some introduction to the subject is reasonable. The beginning of the next section summarizes the history of encryption over the last two thousand years.

Encryption

From Ancient Times to Today

All of cryptography divides into transposition and substitution methods. The first substitution method was the monoalphabetic substitution cipher. This worked by simply substituting one letter for another in a message. One well-known version of that is the Caesar Shift Cipher. Scholars considered it to be unbreakable until late in the first millennium when the Arab peoples discovered that some letters appeared more often than others in any given language. That was the beginning of cryptanalysis and frequency analysis and the end of the security of monoalphabetic substitution.

Transposition, another form of cryptography, developed about the same time. In that case, the letters were scrambled using a certain method that the receiver also used to unscramble them. This method doesn’t seem as popular as the other method according to the books I’ve read. They didn’t really get into the reason. However, both substitution and transposition were part of the Data Encryption Standard (DES) that IBM developed in the mid-1960s and later.

About five hundred years later, Blaise de Vigenère, a former French diplomat, developed a new cipher that used twenty-six substitution alphabets instead of one. Even though it was immune to frequency analysis, it did not become very popular for about two to three hundred years because it was much more complex than earlier ciphers. When the telegraph started to become popular in the mid-1700s and a sender had to rely on multiple anonymous people to relay his message, more secure encryption became popular. People started using the Vigenère cipher. It was unbreakable until Charles Babbage broke it 1854 due to a challenge from an acquaintance. However, he never published his findings so it was not well known until the next century. By then, someone else had also figured out how to crack it.

It wasn’t until the end of the First World War when Major Joseph Mauborgem of the U.S. Army introduced the idea of using a random key in concert with the Vigenère cipher. Cryptographers used a key only once and then threw it out. Because it was impossible to discover any pattern in the encrypted message or in conjunction with other messages, this was the first truly unbreakable code. The problem was in creating the random keys and securely distributing them to everyone who needed one. Because of those difficulties, it didn’t get much use.

After World War One, Germany learned how terrible its encryption methods were and that the Allies had been able to read every message they sent for most of the war. They conducted an investigation to determine how to keep that from happening again. From their research they learned of a German inventor named Arthur Scherbius and his new invention the Enigma machine. The Germans immediately saw the benefit and began ordering them in 1925. Over the next twenty years they purchased more than 30,000 of his machines.

When World War Two started, the Allies found themselves in a bad situation because they had paid little attention to Germany’s new invention. Only Poland had been trying to break the code before that time. They had gained quite a bit of information about it via espionage and the cryptanalysis of Marian Rejewski. When the invasion of Poland seemed imminent, the Polish government passed on what it had learned to the French and British governments. With the genius of Alan Turing, occasionally capturing books that listed a month’s worth of keys, and performing missions that they knew the Germans would talk about via encryption, they were able to break the Enigma code.

Another code Hitler used to communicate only with his generals was the Lorenz cipher. This operated similarly to Enigma but it was much more complicated. The British were able to break the code but it took weeks for each message. Max Newman was able to automate the process by drawing on the ideas of Alan Turing to create the first programmable electronic computer. Called Colossus, it was the first usage of a computer in cryptanalysis.

Other encryption methods followed after the war. Horst Feistel, a German immigrant who came to America in 1934, developed the Lucifer system in the early 1970s. The NSA (National Security Agency) helped make it a standard for civilian encryption in 1976. That was after they weakened it to the point where they would be able to crack it. Data Encryption Standard (DES) was the official name of that standard. However, it had the same problem all encryption methods of the past had. It required distribution of keys to anyone a company wanted to send messages to. The only safe way to do that was to deliver them personally. That became very expensive especially when a company became global and they had to change the key regularly to maintain security. A system that didn’t require the exchange of a secret key still didn’t exist.

That changed in 1976 when Martin Hellman, Whitfield Diffie, and Ralph Merkle discovered a way to for to people to agree on a key without having to send it or exchange it person to person. This was possible using one-way mathematical functions. Most functions are two-way. That means it’s possible to use the function in reverse to get what you started with. One-way functions do not allow that. One branch of math that has many one-way functions is modular arithmetic. In that type of math, the answer is the remainder from division by a number.

For example: 8 mod 7 = 1; 5 mod 9 = 5; 15 mod 5 = 0.

However, if you were trying to do the operation in reverse, the possible answers would be infinite.

For example: Solve for x in the following

X mod 5 = 2 (X could equal 2, 7, 12, 17, . . .)

X mod 2 = 1 (X could be any odd number)

In the case of exchanging keys for DES encryption they came up with the function Y^x(mod P). Y and P can be any value but Y must be smaller than P and it’s better if they are both prime numbers. Creating a secret key would work like this: Alice and Bob (two characters that often appear when discussing cryptography) want to exchange a key. So, they talk on the phone and agree that Y = 17 and P = 23. Now, they both work separately to develop the key. Alice chooses the number 3 and keeps it secret. We will call it A. Alice puts A into the function 17^A(mod 23) and gets 14 which we call “a.” Bob chooses 7 and also must keep it secret. We’ll call that number B. Using the same function 17^B(mod 23) he gets 20 which we call “ß.” Alice and Bob exchange a and ß over the phone or via -mail. In both cases it, does not matter wether or not they are communicating over a secure channel. I will explain why later. Next Alice takes the result she received from Bob and plugs it into the formula ß^A(mod 23) and gets 19. Bob does the same thing with the number he received from Alice (a^B(mod 23) and also gets 19. That number is the key.

Would someone who was listening be able to figure out the key? The answer is “No.” Let’s say Eve (the traditional nemesis in these scenarios) was listening and understands how this key development process works. She would have 17^X(mod 23), a, and ß. She would not have A or B and she can’t find it because 17^X(mod 23) is a one-way function. Therefore she also can’t get the key because to use ß^A(mod 23) or a^B(mod 23) she would need A or B. Eve is out of the loop and Bob and Alice can exchange files with reasonable confidence.

The only weakness is the brute force attack where Eve would use a computer to try every possible combination to find something that worked. With the DES 56-bit standard, that would be about 72,000,000,000,000,000 possible keys. Trying one million per second would take more than 2200 years. While that seems very secure, linking enough computers together to work in parallel or building a computer holding thousands of CPUs would dramatically reduce the time to something more realistic. While it doesn’t seem like that anyone would go to all that expense, history shows that people do just that. One of the cardinal rules of cryptography is never underestimate the lengths your enemy will go to break your code. The consequence of that led people to look for something even more secure than DES’s 56-bit encryption. Another driving force was that people concerned about privacy knew that the NSA had weakened DES from its original 128-bit encryption level. So, they considered DES to be an inferior product. Another problem was that creating a secret key still required two people to work together even though they didn’t have to see each other.

Encryption Today

Encryption really became practical for everyday people with the invention of public-key cryptography. This is a process where one encrypts a message with a key that the receiver distributes to anyone who wants it. However, the key only works one way. It is not possible to use the public-key to decrypt the message. That requires the receiver’s secret-key.

Public-key cryptography began as an idea from the fertile mind of Whitfield Diffie in 1975 while Hellman was developing the key exchange method I wrote about earlier. His idea was the asymmetric key. Typical encryption calls for a symmetric key that one uses for encryption and decryption. In the asymmetric method keys for encryption and decryption are not the same. Diffie’s only problem was he did not have a specific example of that type of key. However, his idea was original because up to that point the existing paradigm was to use only one key for both processes. Actually finding a formula that had those characteristics was the job of Ronald Rivest, Adi Shamir, and Leonard Adleman. That happened about two years later and the group called it RSA (after the initials of their last names). The R came first because Rivest was the one who originally thought of the idea.

Before I go into how RSA works, I should let you know that all the people I just mentioned as having discovered the concept and formulas for public-key cryptography, were not the original creators. Two very brilliant Englishmen who worked at Britain’s Government Communication Headquarters (GCHQ) were the original creators. James Ellis had discovered the concept in 1969 and Clifford Cocks had figured out the formulas needed to make it possible in 1973. Unfortunately for them, their work was classified because they worked for the government. So, they could never publish or patent their findings.

RSA works uses the same type of math as the DES key exchange scheme I wrote about earlier. Alice secretly picks two large prime numbers (bigger is better) p and q and finds N using the one-way function N=(p-1) x (q-1). She also picks another number e. N and e are her public key. She would publish those two numbers as widely as possible. That let anyone who wanted to send her a private message could do it without having to contact her first. The neat thing about this is that even if you know N, you still can’t easily solve for p and q because N is the result of a one-way function. If N is a very large number, on the order of 10^400 for example, it would take millions of years for a modern computer to crack it. Having a large number of computers would lessen the time, but still not enough to solve it sometime before many generations had gone by.

To encrypt the message, Bob uses C=M^e(mod N) where M is each letter to be encrypted and C is the product of the encryption. He wants to send her the letter X meaning a kiss. In ASCII that letter is 01011000 or 88 in decimal form. The formula would look like this: C=88^e(mod N). Exponentials in modular arithmetic are one-way functions. So, even if Eve knows what C, e, and N are, she would not be able to discover the value of M because it has so many possible values.

To decrypt the message, Alice would use her secret prime numbers to create a private key for decryption called d. The formula for creating it is d=(1(mod(p-1)(q-1)))/e. Once she has d, she solves for M in the formula M=C^d(mod N). The result would be 88 and that converts to X in ASCII. If you want to see if this would work, I invite you to try it yourself by choosing values for e, p, and q and then using the formulas above. My only caution is that it is easy to get it mixed up. So, if it doesn’t work, please be sure to check your math.

The downside to all this was that RSA was still not in wide use by anyone who wanted it. The reason for that was RSA required a lot more computing power compared to traditional encryption and the personal computer did not exist as it does today. The consequence was that it was only governments, militaries, and large companies that could afford computers powerful enough to run RSA. The common people were definitely not part of that picture and the company that marketed it, RSA Data Security, Inc., did not develop it with them in mind.

It wasn’t until 1991 when Phil Zimmermann, who believed all people had a right to secure communications, developed Pretty Good Privacy (PGP) that everyone could have the same security that major governments had. It was also about this time that computers became much less expensive and more powerful. Intel’s 80386 CPU was a great improvement that allowed people access to decent computing power at a low cost.

Zimmermann created his program using RSA as its base. That was a potential problem because RSA is patented. That required Zimmermann to get a license from RSA Data Security, Inc. before he could make his program available to the public. His hope was that because he was selling his program to individuals, thus not directly competing with them, RSA Data Security would give him a free license. That is what ultimately happened, but that was not his main obstacle. As has always been the case throughout the history of the struggle for freedom, the government was the major player in keeping Phil Zimmerman from releasing his product.

The arguments against PGP were the same as other arguments against allowing everyone access to something. Namely that criminals and terrorists would misuse it. A joint effort by the communications industry and pro-freedom groups helped ease restrictions. The problem was that there was a general consensus that the government would be back to ban PGP completely. Zimmermann didn’t want that to happen. Although he had intended to sell it, he decided to post it on the Internet and give it away for free to make sure it got the widest distribution possible before the government could ban it. The government didn’t like that and when they discovered that PGP was now overseas, they decided to prosecute him for illegal exporting. For the next three years he was the harassed by the FBI and grand-jury investigations. Eventually the government had to give up its case because they couldn’t prove he had done anything wrong. Also, most of the country was against the government in this case. Everyone had something to gain from his technology. That was especially true of companies trying to do business over a very unsecure medium like the Internet.

Future Encryption

Simon Singh’s book The Code Book: The Evolution of Secrecy from Mary, Queen of Scots to Quantum Cryptography gives a fascinating view of what encryption and computing might be like in the future. Because encryption algorithms like PGP are so difficult to crack, a new type of computer will be necessary if there is any chance of finding p and q in a reasonable amount of time. The type of computer they are looking for is the quantum computer. This is an idea that David Deutsch of England came up with. He reasoned that computers ought to obey quantum physics rather than classical physics because those were more fundamental. A computer that could do that would be a machine that is billions of times faster than what exists today. To understand it requires a little understanding of theories of quantum physics.

I’ll say at the start that I am not sure whether or not I agree with the theories of quantum physics. While they do accurately predict what the workings of many real world things like nuclear reactions, DNA, how the sun shines, and how to design the laser that reads CD-ROMs, I am not sure that makes them valid (ie. a truly accurate description of what is happening behind the scenes). I say that because what I am going to describe next really doesn’t make a lot of sense.

There are two theories I will describe that relate to quantum computing. The first one is superposition of states. This is the idea that because we really don’t know the exact path a photon would take when it travels from a source to a single destination, we state that it travels all possible paths at the same time. The second is the many-worlds interpretation. This theory states that while a photon travels to its destination, the universe divides into multiple universes (one for each possible path). This large group of universes is the multiverse. I agree that neither makes any sense and that it sounds more like mysticism than real science. My theory is there is some undiscovered property that elementary particles have that will resolve those apparent contradictions. When we discover it, quantum theories will be more sensible. However, these and other quantum theories have been very effective in describing and predicting how our universe works.

The idea behind a quantum computer is instead of taking a problem one step at a time, as modern computers do, a quantum computer would be able to do all the steps or check all the possibilities at the same time. If a modern computer had to perform 200 operations and each one took one second, the total task time would be 200 seconds. A quantum computer would be able to do them all in one second. That is because of the two theories I just mentioned.

Computers all use transistors that are either off or on. So, their value is either 1 or 0. Quantum computers would use particles, each in a certain state, to represent 1s and 0s. The name of those particles is quantum bits or qubits. By increasing the number of particles, one can increase the number of simultaneous computations. A 300 qubit computer could check 2x10^90 possible combinations at once. With that technology, all modern encryption would be completely useless no matter how large you made your key. Such is the theory. However, there are many problems with developing this technology. The big ones are discovering the state of a particle without changing its state and that the simultaneous possibility scenario only exists while the true state of the particles is unknown.

On the other side, quantum mechanics also makes possible the first truly unbreakable code. It works like this: (1) Alice sends Bob a series of photons of various polarities, and Bob measures them using either a + or x template. (2) Alice tells Bob on which occasions he used the correct template but not what the actual polarity was. (3) Alice and Bob discard the incorrect measurements and use the correct measurements to create a pair of one-time pads or keys that only get one use. (4) Alice and Bob check the integrity of their one-time pads by testing a few of the digits. (5) If the verification is successful, then they can use the pad to encrypt a message. If not, then that means Eve has been tapping the photons, thus changing their polarity, and they need to create another key.

While that might sound a little weird, it has already been done in a limited form. 1988, Charles Bennett, co-inventor with Gilles Brassard of quantum cryptography, built two computers to test the idea. After hours of tinkering with the two systems, he witnessed the first quantum cryptographic exchange in the world. It traveled through the air for a total distance of 30 cm. The problem is photons do not maintain their states well in travel. The solution to implementing this new cryptography revolved around solving that problem. The solution came a little closer in 1995 when researchers at the University of Geneva used quantum cryptography over a 23km fiber-optic cable. Later, Los Alamos National Laboratory did the same thing through the air over a 1 km distance.

When this encryption will become a reality is hard to say. The other factor will be expense. The hardware to pull this off is certainly quite expensive. For this new technology to reach the masses, it will have to become much cheaper. For now, until the creation of quantum computers, PGP will work just fine for most people.

Conclusion

This paper contained a brief history of encryption and then went into the modern public-key encryption system. It concluded with some likely possibilities on what the future will hold. I am sympathetic to the desire for privacy. It is true that some will misuse their rights to rob, murder, and terrorize others. That is not a justification for annulment of freedom or even its “curtailment.” Criminals misuse thousands of things. Gloves are an example of that. Most of us use them to protect our hands. Criminals use them to keep from leaving finger prints. Of all the gloves sold today, a small percentage will end up as a tool to commit a crime. Yet, no one calls for licensing gloves. Another thing to realize is privacy advocates are not asking for anything that hasn’t existed throughout history. There were no recording devices or parabolic microphones in ancient times. Nor was there any prohibition against using the encryption that existed at the time. As anyone can see, civilization survived. We are still here. Why people argue to restrict the right of individual privacy without evidence he has done anything wrong is something that I have a hard time understanding. Nonetheless, as long as people have free will, some will always advocate statism. It is the job of those of us who value freedom to be competent in its defense and to be able to expose the fallacies behind the arguments of those who would enslave us.

Mind your p's and q's

References

Beckett, B. (1988). Introduction to Cryptology. Oxford, England: Blackwell Scientific

Publications.

Crume, J. (2000). Inside Internet Security: What Hackers Don’t Want You to Know. Harlow,

England: Pearson Production Limited.

Endrijonas, J. (1995). Data Security. Rocklin, CA: Prima Publishing.

Internet Security Systems, Inc. (2000). Microsoft Windows 2000 Security Technical Reference.

Redmond, WA: Microsoft Press.

Jennings, C., & Fena, L. (2000). The Hundredth Window: Protecting Your Privacy in the Age of

the Internet. New York: The Free Press.

Levy, S. (2001). Crypto: How the Code Rebels Beat the Government - Saving Privacy in the

Digital Age. New York: Viking Penguin.

Network Associates, Inc. (1999). An Introduction to Cryptography. Santa Clara, CA: Network

Associates, Inc.

Nichols, R.K., & Lekkas, P.C. (2002). Wireless Security: Models, Threats, and Solutions. USA:

McGraw-Hill.

Nichols, R.K., Ryan, D.J., & Ryan, J.J.C.H. (2000). Defending Your Digital Assets Against

Hackers, Crackers, Spies, & Thieves. USA: McGraw-Hill.

Schmidt, J. (2000). Microsoft Windows 2000 Security Handbook. USA: Que Corporation.

Singh, S. (1999). The Code Book: The Evolution of Secrecy from Mary Queen of Scots to

Quantum Cryptography. New York: Doubleday.