\font\largerbold = cmbx10 scaled \magstep1
\font\largerrm = cmr10 scaled \magstep1
\font\largestbold = cmbx10 scaled \magstep3
\font\largerrm =cmr10 scaled \magstep1
\nopagenumbers
\def\H{\char `\^}
\def\map{{\tt Maple}}
\font\sc=cmcsc10.tfm
\font\show = cmdunh10.tfm
%\magnification=\magstep1
\def\al{\smallskip\item{\show Alice}}
\def\bo{\smallskip\item{\show Bob}}
\rightline{\sevenrm February 23, 2000}
\centerline{\largerbold Diffie-Hellman practice} 

\bigskip
%\smallskip

\noindent {\bf Silly (multiplicative) Diffie-Hellman} 

\bigskip

{\narrower \noindent
You are {\show Eve}, sitting half-asleep in the corridor outside the
cells of {\show Alice} and {\show Bob}, and listening to {\show
Alice} and {\show Bob}. You hear the following dialog:

}
\medskip
{\narrower\narrower

\bo Oh, come on, we'll just multiply, it's easier than
exponentiating! 
\overfullrule=0pt

\al Oh, fine. {\it Maybe}\/ we can compensate by using a rather large
prime so that {\it she}\/ {\sc[Indicating Eve]} will have
trouble. We'll use {\bf 1211211211211}.

\bo That's such a lovely prime! Why don't we start with another neat
number like {\bf 842842842}.

\al So here's my result: {\bf 763030992727}.

\bo And here's mine: {\bf 370114094368}.

\bo Now, without much work, we can get a common key $\ldots$ 

\al I'm still worried! {\sc [Glancing towards a drowsy Eve]} Well,
convert the letters in your message to an integer using {\bf
A}$\to${\bf 01}, {\bf B}$\to${\bf 02}, $\ldots$, {\bf Y}$\to${\bf 25},
and {\bf Z}$\to${\bf 26}, and then add the result, mod {\bf
1211211211211}, to our common key.

\bo No problem, no problem. You're being silly. After all, Eve's just
a {\bf 794453124413} $\ldots$ {\sc [Laughs loudly.]} Hah, hah, hah.

\smallskip

{\narrower \noindent \sc [This noise wakes up Eve completely. She
sniffs, thinks for a few seconds, and throws a bucket of cold water on
Bob.] \par}



}

\bigskip\smallskip

\noindent {\bf True (exponential) Diffie-Hellman}

\bigskip Again, you are {\show Eve}, listening to {\show Alice} and
{\show Bob}. You hear the following dialog:

\medskip
{\narrower\narrower

\al We need a prime.

\bo How about {\bf 3}?

\al No, no, a \underbar{big} prime!

\bo How about {\largestbold 3}?

\al Nitwit. She's sitting there, our executions are in the morning,
and the sun is beginning to make the sky glow faintly.

\bo O.k., I'll consult an oracle $\ldots$ let's use {\bf 120001201}, a
lovely prime. 

\al And we'll use {\bf 2} as the base for our powers. Let's get to
work. 

\centerline{\sc [Time passes.]}

\bo Here's mine: {\bf 75056128}.

\al I've got {\bf 60616573}.

\centerline{\sc [More time passes.]}

\al Done!

\bo Me, too.

\al Convert the letters in your message to an integer using {\bf
A}$\to${\bf 01}, {\bf B}$\to${\bf 02}, $\ldots$, {\bf Y}$\to${\bf 25},
and {\bf Z}$\to${\bf 26}, and then add the result, mod {\bf
120001201}, to our common key.

\bo So I say to you, {\bf 95368077}!

\smallskip
\item{\show Eve} {\sc [Snarls]}


}
\bigskip

\rightline{\hsize=3.35in\hbox{\vtop{\noindent After you finish reading
and enjoying these magnificent dramatic scenes, please consider your
homework assignment on the other side of this page. Golly, the true
human drama and depth of characterization shown here is remarkable.}}}

\vfil\eject

{\noindent \largerbold Homework/Contest}

\medskip

Of course I want you to discover the messages that Bob has sent. Note
that there is a discussion of Diffie-Hellman key exchange in section
5.4 (pages 120--124) of the text. You may work alone or in a group of
at most 4 students.

\medskip

\noindent 1.~Send me e-mail with either message (or both). Your
message should contain a list of the people who worked on the problem,
a short description of the strategy that you used to decode the
messages, and should also have some accounting of what computing power
(and how much computing time) you needed to discover the message.

\smallskip

\noindent 2.~a)~The first person/group to send me Bob's exponential
message decoded properly \underbar{accompanied by} the description
requested above wins {\largerbold First Prize with \underbar{reward}}. 
\smallskip

\noindent \hphantom{2.\ }b) The first person/group to send me Bob's
multiplicative message decoded properly \underbar{accompanied by} the
description requested above wins {\largerbold Second Prize with
\underbar{reward}}.

\medskip



\centerline{\bf To help distribute the rewards more equitably} 

\centerline{No winning group may
contain more than one (1) person from a previous winning group!!!}


\medskip

{\bf \noindent Some useful \map\ comments}

\smallskip

\noindent I remind you that \map\ can remember numbers if you tell it
to. The statements 

\smallskip

{\it key:=12345; number:=55511;}

\smallskip

\noindent will cause \map\ to remember 12345 and 55511 with the
names designated. This is useful if you are similar to me: my error
rate in typing (and retyping!) numbers is high. 

\smallskip

\noindent \map\ can also do modular arithmetic. One way is to use the
{\it mod}\/ command. 

\smallskip

{\it 42 mod 5;}

\smallskip

\noindent The result is just 2 (the remainder after dividing 42 by
5). Using {\it mod}\/ and labeling numbers is likely to really save
time and effort. For example, with the values of {\it key}\/ and {\it
modulus}\/ mentioned above, the command

\smallskip

{\it frog:=72*key\H 2 mod number;}

\smallskip

\noindent produces the answer 36963 and assigns it the name {\it
frog}. \map\ still has the values of {\it key}\/ and {\it modulus}
(and {\it frog}\/ also!) to work with later.





\vfil\eject\end


abcde fghij klmno pqrst uvwxy z
1   5 6  10 11 15 16 20 21 25 26

nitwit
140920230920   

purple

162118161205

enigma

051409071301


smile
1913091205
maple



there's a p*ri*m*e!!!

1201201201;

LUCK
12210311
TREE

120001201;

