Mathematics of Information Security
Computer Lab 4. M360. Friday 10/29/2004

Opening the program:
1) Open (My computer -> Math on Pop G: -> m360).
2) Open (My computer -> local disk c -> temp).
3) Move the file "crypto.mws" from 1) to 2) (Zube wants it done this way).
4a) Either double click on "crypto.mws" or do 4b).
4b) Open Maple 9.5 and open the file "crypto.mws" from c:temp.
5) Press "return" somewhere in the midst of the file and ignore the warning signs.

Goals for today: (These problems are part of the homework set due Friday 11/5, so you can try whichever you like).

Warm-up: It is possible to do many calculations simultaneously using Maple.
Type "for i from 1 to 30 do (i, 2^i mod 31) od;" and describe what the output tells you. What is the order of 2 mod 31?

A. Modify the command in the warm-up to find all the powers of 3 mod 31. Is 3 a primitive root mod 31?
Use this table of powers of 3 to find the order of every a between 1 and 30.
Conjecture from class: if g is a primitive root mod p, then the order of g^e is (p-1)/gcd(e,p-1).

B. Find a command that will list all the values of x^2 mod 31 as x ranges from 1 to 30. For what exponents e is 3^e mod 31 on this list?
Finish this conjecture: Suppose g is a primitive root mod p and a=g^e for some exponent e. Then a=x^2 mod p has a solution if and only if e is ______.

C. Alice works for a company that has just made a job offer to Bob. It turns out that Alice and Bob are friends and she would like to help him negotiate the offer.
Since all her e-mail is watched by the company's anti-privacy server, they decide to use the El Gamal cryptosystem.

1. Bob chooses the prime p=65537. Show that a=3 is a primitive root mod p.
Hint: it will take too long to compute 3^i for all i between 1 and 65536.
Make a short list of the possible values for the order of 3 mod p and check all of these with successive squaring.

2. Bob chooses a secret value f=617. He computes b=a^f mod p. What is b?

3. Bob publishes (p,a,b). Explain why no one else can (easily) find f.

4. Alice decides to test the system with the message "hibob". She chooses a secret value k=13.
She breaks her message into 2 parts ("hi" and "bob") and converts the parts to numbers m and n.
Alice sends the numbers (c1:=a^k mod p, c2:=b^k*m mod p) (d1:=a^k mod p, d2:=b^k*n mod p) to Bob. What are these numbers?

5. Bob tests the decryption with the formula m=c2*c1^(-f) mod p and n=d2*d1^(-f) mod p. Check to make sure your decryption process works.

6. Alice's next message is (21435, 24019), (21435, 46689), (21435, 40131). What is she telling Bob?

D. (Bonus) We say that a is a primitive root mod n if phi(n) is the order of a mod n.
List all the values of n between 1 and 50 for which there is at least one primitive root mod n.