For this question, see especially Sections 3.2.1 and 3.2.2 in Groups, Modular Arithmetic, and Cryptography

1. Find all the elements of the multiplicative group Z₈^*.
2. For Euler's Totient function Phi, see Section 4.4. Find Phi(8).
3. Find Phi(77).
4. Consider two prime numbers:
   3662502317
   2480067991
   What is Phi(3662502317) and Phi(2480067991)?
5. Consider 9083254763355035147 and note that:

   3662502317 * 2480067991 = 9083254763355035147
   

   What is Phi(9083254763355035147)?

Begin by reviewing some basic ideas:

1. Recall the definition of a cyclic subgroup of a group G given in definition 2.1.4 and further discussed in Section 4.2 of Groups, Modular Arithmetic, and Cryptography.

   The cyclic subgroup H_g of an element g is:

   G = { x | gⁱ = x for some integer i }
2. Recall the definition of a generator of a group G. A generator for G is an element g such that the cyclic subgroup H_g is equal to G:
   G = H_g = { x | gⁱ = x for some integer i }

Answer the following cyclic subgroup questions

1. Find all the generators for Z₇^*.
2. Find a member of Z₁₁^* which is a non-generator.
3. True or False: The generator of the multiplicative group of an integer n need not be relatively prime to n. If false give an example.

The Diffie-Hellman protocol goes like this:

First, Alice and Bob publically agree on on a large prime p and a generator g of Z^*_p.

1. Alice chooses a large random number x and sends Bob:
   X = g^x mod p
2. Bob chooses a large random number y and sends Alice:
   Y = g^y mod p
3. Alice computes
   K = Y^x mod p
4. Bob computes
   K = X^y mod p

The security of the protocol depends on the fact that it is easy to compute Z where

Z = X^y mod p

y = log_X Z mod p

1. Bob and Alice choose 11 as their modulus. Is 3 appropriate for g?
2. Explain why the computations in step C and D get the same result. That is, why is it the case that
   X^y = Y^x mod p?
3. The protocol would work even if g were not a generator. What is the security advantage of making g a generator?

For this question review Section 4.4 of Groups, Modular Arithmetic, and Cryptography. Section 4.3 may also be of help.

Recall the definition of the order of a group The order of a group G is just the number of elements in G. The order of an element g of a finite group G is just the number of elments in the cyclic subgroup of G H_g. Thus in Z₇^*, 2 has order 3 and 3 has order 6 because

H₂ = {1, 2, 4}
H₃ = {1, 2, 3, 4, 5, 6}

Now some questions:

1. What is the order of Z₇^*? What is the order of Z₁₁^*?
2. Within Z₇^*, what are the orders of 4,5, and 6?
3. True or False: The order of an element a of group G is the power i such that:
   aⁱ = e
   where e is the identity element.
4. Within Z₂₆^*, which of the following are possible orders for elements. 2,3,4,5,6? Justify your answer by citing a theorem.

   Hint: note 26 is an RSA number, the product of two primes!

5. The Diffie Hillman protocol requires finding an element g that is a generator the multiplicative group of prime number p. Here is a proposed algorithm for finding a generator g:
   Test each element x of Z_p^* as follows. Raise each element to the power Phi(p). If
   x^Phi(p) = 1 mod p
   then x is a generator. Why WON'T this work? (Hint: experiment with Z₇^*). Your answer should cite a theorem.
6. Since the previous algorithm won't work, we have to find the lowest power y to which x can be raised such that:
   x^y = 1 mod p
   Consider the following revised algorithm:
   Test each element x of Z_p^* and each even divisor y of Phi(p) as follows. Raise x to the power y. If the lowest y for which
   x^y = 1 mod p
   is Phi(p), then x is a generator. Why DOES this work? In particular, why is it okay to ONLY look at y's that evenl;y divide Phi(p)? Your answer should cite a theorem.

For this question use the RSA protocol described here and demonstrated here.

Use (3,33) as your public key. That is 3 is e and 33 is p*q.

1. Encrypt a message consisting entirely of the letter "c" (encode it as 2).
2. What is the private key? Hint: See Section 4.4.3 of Groups. Modular Arithmetic, and Cryptography for a methoid for finding this.

Write up a page summarizing what aspects of the new world predicted in Tim May's essay, Anarchy and Virtual Communities, have NOT come to pass.

In particular, address the question of why digital cash has not been a success. The links related to Digital Cash on the useful websites page may be useful.