Appendix G: Exercises - Codes: The Guide to Secrecy from Ancient to Modern Times - page 579

1. Show how Bob can form a computation to recover m , and uniquely
verify that this is Alice's signature.
2. How can Alice sign a message using Dickson polynomials and Bob's
public key to achieve the same effect?

4.54. The Dickson polynomial schemes devised above can be employed to
form a type of DiGe-Hellman key exchange as follows.

q be
chosen such that α = γ q − 1 + γ − ( q − 1) where γ is a primitive element of
F q 2 . Randomly chosen positive integers a and b , chosen by Alice and Bob,
respectively, are kept private, whereas q , α , D a ( α, 1), and D b ( α, 1) are
made public. The following is a Dickson key exchange .

Let α ∈ F

1. Alice gets Bob's public data, D b ( α, 1) and computes D a ( D b ( α, 1)) =
D ab ( α, 1).

2. Bob gets Alice's data D a ( α, 1) and computes D b ( D a ( α, 1) , 1) =

D ba ( α, 1).

.
Show that the shared key D ab ( α, 1) = D ba ( α, 1) in this key exchange
scheme depends on the DLP as does the DiGe-Hellman exchange.

4.55. The three-pass protocol (sometimes called Shamir's three-pass scheme )
discussed on pages 198 and 199, can be generalized to Dickson polynomials
developed in Exercises 4.50-4.54.
Assume that Alice wishes to send a message m ∈ F p ( p a prime), to Bob.

To do so, the following steps are executed.

Alice selects an integer a with gcd( a,p 2

−

1. 1) = 1, where a is kept

≡

c (mod p ) to Bob.
2. Bob picks an integer b such that gcd( b,p 2

secret. She sends D a ( m, 1)

− 1) = 1, where he keeps b

c (mod p ) to Alice. secret. Then he sends D b ( c, 1) ≡

3. Alice computes a

such that

aa ≡ 1 (mod p 2 − 1)

and sends

D a ( c , 1) d (mod p )

≡

to Bob.
4. Bob recovers m (mod p ) by computing b satisfying

bb ≡ 1 (mod p 2 − 1)

and

D b ( D a ( D b ( D a ( m, 1) , 1) , 1) , 1) ≡ m (mod p ) .