Computer Lab 3
Friday, October 21

Previous labs

• First lab
• Second lab and a quick note on that lab.

Starting up

Tools &rarr Options...

and set the Kernel mode to shared.

You'll want to make sure the number theory package is loaded. Do this by typing

with(numtheory);

Downloads

• crypto.mws
• dhbb.mws ("Diffie-Hellman black box")

In either case, you'll need to copy them to My computer &rarr local disk c &rarr temp.

The problems

1. In this problem, we'll work with the prime p = 65537 and the primitive root &alpha = 3.

   After you define p and &alpha , you can check that p is prime by typing

   isprime(p);
   

   and verify that &alpha is a primitive root mod p using

   order(alpha,p);
   

   The file dhbb.mws has a function dhbb which solves the Computational Diffie-Hellman problem for this value of p and &alpha .

   • Convince yourself that dhbb works as advertised. Pick numbers x and y. Compute &alpha^x mod p and &alpha^y mod p. What should dhbb(&alpha^x, &alpha^y) return? What does it actually return?
   • The following message has been encrypted using the El Gamal cryptosystem with these values of p and &alpha , and &beta = 46735. (All pairs are given in the form (r,t).)

     23869, 42956

     4676, 29767

     42383, 44483

     What does it say? (You may want to read Proposition 4 on page 214.)

2. There's a relation between discrete logarithms and orders of elements. Pick yourself a prime p and a primitive root g modulo p.

   Maple has a few functions which will help you with this. You can learn about them by typing

   ?numtheory;
   

   You might be particularly interested in isprime, primroot and order.
   • For which numbers a is g^a a primitive root mod p?
   • More generally, what's the relation between a and ord_p(g^a)?
   Just show me the good stuff here -- print out some evidence and explanation.