8.1)

Understanding the functionality of groups, cyclic groups and subgroups is important for the use of public-key cryptosystems based on the discrete logarithm problem. Thats why we are going to practice some arithmetic in such structures in this set of problems. Lets start with an easy one. Determine the order of all elements of the multiplicative groups of:

1. Z 5

2. Z 7

3. Z13

Create a list with two columns for every group, where each row contains an element a and the order ord(a). (Hint: In order to get familiar with cyclic groups and their properties, it is a good idea to compute all ordersby hand,i.e.,use only a pocket calculator. If you want to refresh your mental arithmetic skills, try not to use a calculator whenever possible, in particular for the rst two groups.)

8.2)

We consider the group Z53. What are the possible element orders? How many elements exist for each order?

8.3)

We now study the groups from Problem 8.2.

1. How many elements does each of the multiplicative groups have?

2. Do all orders from above divide the number of elements in the corresponding multiplicative group?

3. Which of the elements from Problem 8.1 are primitive elements?

4. Verify for the groups that the number of primitive elements is given by (|Z p|).

8.5)

Compute the two public keys and the common key for the DHKE scheme with the parameters p=467, =2, and

1. a=3, b=5

2. a=400, b=134

3. a=228, b=57

In all cases, perform the computation of the common key for Alice and Bob. This is also a perfect check of your results.

8.7)

In the DHKE protocol, the private keys are chosen from the set {2,...,p2}. Why are the values 1 and p1 excluded? Describe the weakness of these two values.

8.11)

In this chapter, we saw that the DifeHellman protocol is as secure as the DifeHellman problem which is probably as hard as the DL problem in the group Z p. However, this only holds for passive attacks, i.e., if Oscar is only capable of eavesdropping. If Oscar can manipulate messages between Alice and Bob, the key agreement protocol can easily be broken! Develop an active attack against the DifeHellman key agreement protocol with Oscar being the man in the middle.

8.12)

Write a program which computes the discrete logarithm in Z p by exhaustive search. The input parameters for your program are p, , . The program computes x where = x mod p. Compute the solution to log10612375 in Z24691.

8.13)

Encrypt the following messages with the Elgamal scheme (p = 467 and

=

2):

1. kpr =d =105, i=213, x=33

2. kpr =d =105, i=123, x=33

3. kpr =d =300, i=45, x=248

4. kpr =d =300, i=47, x=248

Now decrypt every ciphertext and show all steps.

8.17)

Considering the four examples from Problem 8.13, we see that the Elgamal scheme is nondeterministic: A given plaintext x has many valid ciphertexts, e.g., both x=33 and x=248 have the same ciphertext in the problem above.

1. Why is the Elgamal signature scheme nondeterministic?

2. How many valid ciphertexts exist for each message x (general expression)? How many are there for the system in Problem 8.13 (numerical answer)?

3. Is the RSA cryptosystem nondeterministic once the public key has been chosen?