10.4   Going Farther: Cryptography Using the "Lumberjack's Rock and Roll" Discretely

An applet in Section 10.2, which wrote every element of Zn* as a power of a primitive root, has an application to cryptography. The output gives all of the values of a certain function. If r is a primitive root modulo m, then the output of the applet tells us: for each c, what is an exponent x such that c === rx (mod m). Here is an example (it is easy to check that 2 is a primitive root modulo 19):

Your browser does not support java.

If we wanted to find an x such that 2x === 3 (mod 19), we could easily read off that x = 13 works.

The next applet lets us compute this value a little bit more directly. For the congruence rx === c (mod m), the applet will return the smallest nonnegative exponent x which satisfies the congruence.

This function is generally known as a discrete logarithm because its defining property is so similar to logarithm functions in calculus. We include the adjective discrete to distinguish it from its more familiar continuous counterparts. The applet above works by trying successive values for x, starting with x = 0, until it finds one which works.

Let's try our new discrete log applet to find the same value as above: find x such that 2x === 3 (mod 19):

Your browser does not support java.

Good news, we found the same answer (and with less output than the applet above).

The discrete logarithm is important to cryptography (thus the title of this section). Ironically, it is important because discrete logarithms are difficult to compute quickly. By contrast, the inverse of discrete logs (computing bn % m) can be accomplished quickly using the algorithm described in Chapter 8. On average, the time required to compute c = (bn % m) is proportional to the number of digits in m whereas the time to undo this and compute n from b, c, and m is proportional to the value of m. When m is large enough, this makes the exponentiation direction reasonably fast and the discrete logarithm direction impossible for all practical purposes. For this reason, modular exponentiation is called a one-way function.

The previous paragraph oversimplifies the situation a little bit. There are faster methods for computing discrete logarithms, especially if phi(m) is divisible by only small primes. But the basic principle is right: if we choose m so that phi(m) is divisible by a very large prime, then the computation of discrete logs is impractical.

We have seen an applet before which uses the fast modular exponentiation algorithm described in Chapter 8. We can use this to quickly compute 2135791 mod 1234577:

Your browser does not support java.

We can reverse this computation with our applet for computing discrete logs:

Your browser does not support java.

Below we look at two cryptographic applications of discrete logarithms. There are others, including a public key cryptosystem named El Gamal after its inventor.

10.4.1  Password Files

Many computers allow many different users to login by providing a login name and a password. The passwords are typically kept in a file on the system, and they are encrypted so that users cannot discover each other's password. The problem is to keep users from spending their time trying to decrypt each other's password.

The problem is solved by using a one-way function. The system can then encrypt passwords, but no one is able to decrypt them, not even the computer! Interestingly, this is sufficient for password checking. When a user attempts to login, the computer takes whatever the user types as his or her password and runs it through the encryption process. It can then check to see if the encrypted version of whatever the user typed matches the encrypted version of the password it has stored in a file.

We are almost ready. We will use m = 27449 as our modulus and r = 3 as our primitive root for a running example. Running the next applet will compute the order of 3 modulo 27449, which verifies that 3 is in fact a primitive root.

Your browser does not support java.

To encode the password "Hi", we convert it to a number, encrypt the number, and then convert the resulting number back to text. The next applet lets us do this one step at a time. Click on the buttons in succession starting with the first one (Text->Num). Note that the Text->Num button will convert the text to a single number using text blocking (where the entire text is treated as one block). Similarly the Num->Text button will convert a number into a single block of text.

Your browser does not support java.

To decode this, we reverse the process. We undo the exponentiation step by taking a discrete log. As a result, you may notice that the discrete log step of decoding takes longer than encoding. As above, you have to click on the sequence of buttons to take the text through the sequence of steps for decoding.

Your browser does not support java.

In this example, we used a small modulus so that we could compute the required discrete logarithm in our lifetimes. Because of the small modulus, we needed a very short password.

In practice, computer passwords are often cracked in a very nonmathematical way. The "mischievous user" who gets other people's passwords often does it by guessing! Sometimes, this takes a certain amount of trial and error.

Exercise 1

Louis Reasoner is very proud of the new password system he installed on his computer. It uses the method we described above, but with a large modulus for better security. In fact, Louis's modulus is 1017 + 3 and his base is 2.

Louis is so confident in his system that he brags "No one can crack my passwords. My system is so secure that I do not even use capital letters or punctuation in my passwords. I also like to change my password every day. I have one password for every day of the week!" When Louis heads off to watch his favorite movie, Disney's Snow White, his friends try to guess Louis's password. The encoded version of today's password is "vI41~,w](" (not including the quotation marks).

Use (one of) the applets above to determine what Louis's password is today.

10.4.2  Key Exchange: Creating Shared Secrets

Suppose Alice and Bob are communicating through the internet. They want to set up encryption for sending messages, so they will need a key. All communications on the internet can be observed by an outsider, so Alice cannot simply send a key to Bob.

One solution is for Alice and Bob to work out a "shared secret". The secret is just a large number which Alice and Bob know, but nobody else knows including Oscar who is watching all of the transmissions between Alice and Bob. The shared secret can then be used as the key for any of a number cryptosystems.

The Diffie-Hellman protocol was one of the first methods for creating shared secrets. The security of Diffie-Hellman depends on discrete logarithms' being difficult to compute. Here is how it works.

Alice and Bob will be sending messages back and forth, and Oscar is eavesdropping. First, Alice sends a modulus m and and base r to Bob. Typically, m will be a large prime and r will be a primitive root modulo m. Now, everyone knows these two numbers. Here we will set

m = 27449      and      r = 3
for a working example.

We check that r is a primitive root modulo m in the next applet.

Your browser does not support java.

Alice and Bob secretly pick random numbers, which we will call a and b respectively. Then, Alice computes ra % m and Bob computes rb % m. These values are exchanged. Now, everyone knows r, m, ra % m, and rb % m. Only Alice and Bob know their secret random values. To simulate how this looks to Oscar, we have picked values for a and b for this example, but we are not telling them to you. We will say that

ra % m = 955      and      rb % m = 11859.

Finally, Alice takes rb % m, which she got from Bob, and uses it to compute

(rb)a % m = rab % m

(only she can do this because only she knows the value of a). Similarly, Bob computes

(ra)b % m = rab % m

using b. In the end, both Alice and Bob know rab % m. In our example, this turns out to be 8081.

Now that Alice and Bob have their key, they will use it with some cryptosystem. Normally, people use a fairly sophisticated system such as the Digital Encryption Standard, or DES for short. DES is pretty secure and was designed to run especially fast on a computer. However, DES is not very interesting from a number theoretic point of view, so we will use a simple shift cipher instead (with text blocking).

To encode a message, just run the message and key through the following applet:

Your browser does not support java.

Similarly, we can decode a message with the a corresponding decoding applet:

Your browser does not support java.

Oscar could figure out this "secret" value rab % m if he could compute discrete logarithms. He would take a discrete logarithm of ra % m to find a, and then proceed as Alice did to find rab % m. Our modulus is small, so we can try that now.

Your browser does not support java.

For comparison, the value of a we used above was 11478.

No one knows of a better way for Oscar to proceed. If the modulus were bigger, Oscar would be stuck, so we assume that this exchange between Alice and Bob is secure.

We mentioned above that discrete logarithms are only difficult to compute if phi(m) is divisible by a very large prime. The next applet implements an algorithm which computes discrete logarithms quickly if phi(m) is divisible by only small primes. If [Graphics:primitgr222.gif], then the running time of our first discrete log applet is proportional to [Graphics:primitgr222.gif]. The running time for the faster discrete log applet below is proportional to [Graphics:primitgr224.gif]. We will discuss the method used by this faster applet in the chapter summary.

To get set up, we start by carefully choosing m. Here we will use m = 174636001. First, we check that m is prime.

Your browser does not support java.

Next we check that phi(m) = m–1 has only small prime factors.

Your browser does not support java.

After a little searching, it is not hard to discover that our modulus has a primitive root, namely 13. We check that here by computing ordm(13):

Your browser does not support java.

We see that the order of 13 modulo m is the same as phi(m) = m–1. Next we raise 13 to a moderately large power:

Your browser does not support java.

Finally, we can undo this with our fast discrete log applet:

Your browser does not support java.

Computing this value using our original discrete log applet would take more than an hour on most computers.

Exercise 2

Alice and Bob cannot wait to try using the Diffie-Hellman protocol to establish encrypted communication with someone. They think that the only thing he needs to get a high level of security is a large modulus m. So, Alice picks the following modulus m and primitive root r.

m = 15 * 278+1      and      r = 11.

We can easily check that m is prime (see below).

We are able to observe the values exchanged by Alice and Bob.

Alice sends: 3268170018038853053202889

Bob sends: 4168860017312113121130990

This is enough to establish the key for Alice and Bob. Then Alice sends an encrypted message to Bob: 42874365609190013943874393, 43796660115814483912883243, 46561806814964037976439092, 4197584748237556580656485, 4367214525356700096276646, 3981076401286882248383284, 11546127082303475414202004, 10989014362120551587081329, 3964323935927860666114792

Decode the message. Note, since some of the numbers are very large in this problem, it may take the Java applets a few minutes to do some of the computations. Also, input and output areas may not look large enough to hold some of the numbers. They will hold the numbers, but you will not be able to see the whole number at once. By clicking in the area, you can use the arrow keys to move left and right within the number. Finally, you may want to use your mouse to copy-and-paste numbers from one place to another (if that is possible with your browser).

Your browser does not support java.

Your browser does not support java.

Section 10.1 | Section 10.2 | Section 10.3 | Section 10.4

Chapter 10 | DNT Table of Contents

Copyright © 2001 by W. H. Freeman and Company