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):
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):
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 
(m) is divisible by only small primes. But the
basic principle is right: if we choose m so 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 2135791 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 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.
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 1Louis 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
We check that r is a primitive root modulo m in the next applet.
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:
Similarly, we can decode a message with the a corresponding decoding applet:
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.
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 (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 ![[Graphics:primitgr222.gif]](primitgr222.gif)
, 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 ![[Graphics:primitgr224.gif]](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.
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 ordm(13):
We see that the order of 13 modulo m is 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 2Alice 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). |