An applet in Section 10.2, which wrote every element of

Z_{n}^{*}as a power of a primitive root, has an application to cryptography. The output gives all of the values of a certain function. Ifris a primitive root modulom, then the output of the applet tells us: for eachc, what is an exponentxsuch thatcr^{x}(modm). Here is an example (it is easy to check that 2 is a primitive root modulo 19):

If we wanted to find an

xsuch that 2^{x}3 (mod 19), we could easily read off thatx= 13 works.The next applet lets us compute this value a little bit more directly. For the congruence

r^{x}c(modm), the applet will return the smallest nonnegative exponentxwhich satisfies the congruence.This function is generally known as a

discrete logarithmbecause its defining property is so similar to logarithm functions in calculus. We include the adjectivediscreteto distinguish it from its more familiar continuous counterparts. The applet above works by trying successive values forx, starting withx= 0, until it finds one which works.Let's try our new discrete log applet to find the same value as above: find

xsuch that 2^{x}3 (mod 19):

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

b%^{n}m) can be accomplished quickly using the algorithm described in Chapter 8. On average, the time required to computec= (b%^{n}m) is proportional to the number of digits inmwhereas the time to undo this and computenfromb,c, andmis proportional to the value ofm. Whenmis 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

_{}(m) is divisible by only small primes. But the basic principle is right: if we choosemso that_{}(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 2

^{135791}mod 1234577:

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

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 andr= 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.

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.

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.

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 10

^{17}+ 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

mand and baserto Bob. Typically,mwill be a large prime andrwill be a primitive root modulom. Now, everyone knows these two numbers. Here we will set

for a working example. m= 27449 andr= 3We check that

ris a primitive root modulomin the next applet.

Alice and Bob secretly pick random numbers, which we will call

aandbrespectively. Then, Alice computesr%^{a}mand Bob computesr%^{b}m. These values are exchanged. Now, everyone knowsr,m,r%^{a}m, andr%^{b}m. Only Alice and Bob know their secret random values. To simulate how this looks to Oscar, we have picked values foraandbfor this example, but we are not telling them to you. We will say that

r%^{a}m= 955 andr%^{b}m= 11859.

Finally, Alice takes

r%^{b}m, which she got from Bob, and uses it to compute(

r)^{b}^{a}%m=r%^{ab}m(only she can do this because only she knows the value of

a). Similarly, Bob computes(

r)^{a}^{b}%m=r%^{ab}musing

b. In the end, both Alice and Bob knowr%^{ab}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:

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

Oscar could figure out this "secret" value

r%^{ab}mif he could compute discrete logarithms. He would take a discrete logarithm ofr%^{a}mto finda, and then proceed as Alice did to findr%^{ab}m. Our modulus is small, so we can try that now.

For comparison, the value of

awe 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

_{}(m) is divisible by a very large prime. The next applet implements an algorithm which computes discrete logarithms quickly if_{}(m) is divisible by only small primes. If_{}, then the running time of our first discrete log applet is proportional to_{}. The running time for the faster discrete log applet below is proportional to_{}. 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 usem= 174636001. First, we check thatmis prime.

Next we check that

_{}(m) =m–1 has only small prime factors.

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 ord

_{m}(13):

We see that the order of 13 modulo

mis the same as_{}(m) =m–1. Next we raise 13 to a moderately large power:

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

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 modulusmand primitive rootr.

m= 15 * 2^{78}+1 andr= 11.We can easily check that

mis 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).

Section 10.1 | Section 10.2 | Section 10.3 | Section 10.4

Copyright © 2001 by W. H. Freeman and Company