\documentstyle{report}

\pagestyle{myheadings}
\def\headlineaux{\sc Math 322: C Programming and Unix
\hrulefill
}
\markboth{\headlineaux}{\headlineaux}

\setlength{\textwidth}{6.25in}
\setlength{\oddsidemargin}{0in}
\setlength{\evensidemargin}{0in}

\newcommand{\assignmentNumber}{5}
\newcommand{\outdate}{8 November, 1994}
\newcommand{\duedate}{22 November, 1994}

\begin{document}
\begin{titlepage}\begin{centerline}{\Huge \framebox{Burt Rosenberg}}
\end{centerline}\end{titlepage}

\section*{Problem Set \assignmentNumber \hfill{\parbox{3in}
    {\small\sc\begin{flushright} Out: \outdate
    \\ Due: \duedate\end{flushright}}}}

\subsection*{Assignment}

  Write a C program to play the game of Rock Paper Scissors against
another (program) opponent. Play many games against who is ever logged
in, keep score and records. The most winning games wins.
This assignment will exercise file sharing and communication protocols
between programs. You will learn about file locking and public key
cryptography. It serves as a model for some important new issues
in programming which arise from the importance of parallelism and
networks.

\subsection*{Players}
  Players are named A and B. The A player goes first, proposing
  a game. The B player then joins. Once A and B are so matched, 
  play proceeds to the end of the single game.

\subsection*{Files}
  Communication between players is through a common file directory,
  the {\em spool directory}. Players must lock the spool directory
  before changing the contents of the directory,
  and must unlock the spool directory immediately afterwards.
  This is accomplished by creating, or failing to create,
  a common {\em lock file}.
  The communication continues through a series of files, 
  the {\em protocol files}, also called the A, B, C, D and E
  files, according to the first letter of their names.
  The A player is must create and delete the
  A, C and E files, while the B player must create and delete the B
  and D files. 

\subsection*{File Names}
  Each game has a unique number, the combination of a serial number
  and the UID's of players A and B. The A through E files derive
  their names from the letter A through E, the A player's UID
  and the serial number. The A player chooses a serial number, and
  it should be unique for player A. The file names are:
\begin{center}
 $[${\bf A}$|${\bf B}$|${\bf C}$|${\bf D}$|${\bf E}$]${\em uid}$_A${\bf .}{\em sernum}
\end{center}
  As an example, \verb,A1212.1102001, is the A file of player with
  UID 1212, and the game has sequence number 1102001.

\subsection*{Outline of Protocol}
  Any player can be an A player, proposing a game. It does so
  by creating an A file and waiting for another player to adopt
  a B position. The B player will respond with a B file.
  Player A will then create a C file, and delete its A file.
  In normal play, the protocol will continue in this manner,
  with players A and B alternating turns of waiting for the
  other player to post the next file in the protocol and deleting
  its previously posted file.

  The contents of these files exchange information between players
  A and B. The intent of the A file is for the A player to announce
  its intent to play and to publish its play in encrypted form
  The intent of the B file is to announce player B's intent to
  accept play against A, to identify B to A, to
  signal that B has read the A file and recorded A's encrypted play,
  and to publish B's encrypted play.
  The C file announces to player B that player A has read the B file,
  has accepted B as opponent for this game, has recorded B's
  encrypted play, and reveals A's play in unencrypted form.
  Player B will respond to the C file with a D file. The D file
  announces to player A that player B has read the C file, accepts
  that the revealed play agrees with the encrypted play, and
  reveals player B's play.
  The final file of the sequence is file E. In response to file
  D, player A posts file E which signals that player A has read
  the D file and accepts that the revealed play agrees with the
  encrypted play.
  Seeing the E file, player B deletes the D file. Seeing the
  D file deleted, player A deletes the E file.

  The protocol is now finished. The two
  parties have no further responsibilities to each other.
  It is important to observe the correct locking of the spool
  directory. If two players decide simultaneously to create B
  files, one will succeed in locking the directory first.
  The second player will lock the directory and observe the A
  file already has a responding B file and conclude that it was
  too late to join as A's opponent.

\begin{verbatim}
   >>> start of protocol <<<
   (Player A)         (Player B)
   lock
   create A
   unlock
                       lock
                       create B
                       unlock
   lock
   create C
   delete A
   unlock
                       lock
                       create D
                       delete B
                       unlock
   lock
   create E
   delete C
   unlock
                       lock
                       delete D
                       unlock
   lock
   delete E
   unlock
   >>> end of protocol <<<
\end{verbatim}

\subsection*{Directory Locking}
Each player temporarily gets exclusive control over the spool directory
by locking it.
This is done by creating the lock file:
\begin{verbatim}
   /u/1mth322s/e0l47v0m/spool/.lock
\end{verbatim}
The player desiring to lock the directory first
looks for the presence of the \verb,.lock, file in the directory.
It it does not exist, the directory is free to be locked. The player
then creates a \verb,.lock, in the spool file. It the create succeeds,
the player has successfully locked the directory. If it fails, another
user has simultaneously attempted to create a  \verb,.lock, file
in the spool directory, and that user was judged to have ``asked
first''.

After locking the directory, the player looks at the directory again
and confirms the situation. The player than makes the required changes
and unlocks the directory. The directory is unlocked simply by deleting
the lock file. If the lock file is left behind, all play action will
stop.

\subsection*{Glossary of Protocol Elements}
To describe the contents of the protocol files in detail, this
glossary of their contents is provided.
\begin{enumerate}
\item{\it sernum:}\/ A seven digit integer chosen by player A.
It must be unique as far as player A is concerned. When the
sernum is combined with player A's UID, it is the unique identifier
of the game. 
\item{\it uid}$_A$: The UID of player A.
\item{\it uid}$_B$: The UID of player B.
\item{\it cry}$_A$: The encrypted version of player A's choice of
Rock, Paper or Scissors.
\item{\it cry}$_B$: The encrypted version of player B's choice of
Rock, Paper or Scissors.
\item{\it key}$_A$: The decryption key for {\it cry}$_A$.
\item{\it key}$_B$: The decryption key for {\it cry}$_B$.
\item{\it ack/nack:}\/ The literal \verb.OK. or \verb.NO. to
acknowledge or refuse a communication. Each protocol file ends
with one of these.
\end{enumerate}

\subsection*{Protocol}
\begin{enumerate}
\item The {\bf A}{\it uid}$_A${\bf .}{\it sernum} file:\\
   {\bf A}{\it uid}$_A${\bf .}{\it sernum}{\bf :} {\it cry}$_A$ {\bf OK}
\item The {\bf B}{\it uid}$_A${\bf .}{\it sernum} file:\\
   {\bf B}{\it uid}$_A${\bf .}{\it sernum}{\bf :} 
   {\it uid}$_B$ {\it cry}$_B$ {\bf OK}
\item The {\bf C}{\it uid}$_A${\bf .}{\it sernum} file:\\
   {\bf C}{\it uid}$_A${\bf .}{\it sernum}{\bf :}
   {\it uid}$_B$ {\it key}$_A$ {\it ack/nack}
\item The {\bf D}{\it uid}$_A${\bf .}{\it sernum} file:\\
   {\bf D}{\it uid}$_A${\bf .}{\it sernum}{\bf :}
   {\it uid}$_B$ {\it key}$_B$ {\it ack/nack}
\item The {\bf E}{\it uid}$_A${\bf .}{\it sernum} file:\\
   {\bf E}{\it uid}$_A${\bf .}{\it sernum}{\bf :}
   {\it uid}$_B$ {\it ack/nack}
\end{enumerate}

\subsection*{Error Paths}

Rather than acknowledge, a player can negative-acknowledge a
message by using \verb.NO. instead of \verb.OK. as the final
two letters of a protocol file. When this occurs, the opposing
player removes its file, and in response to this, the nack'ing
player removes its file. The two players have no further
responsibilities to each other.

To avoid cheating, two additional rules apply. A nack'ing
C message need not contain a valid {\it key}$_A$. However
a nack'ing D message must contain the valid {\it key}$_B$.
Else player B can annul any game which it has lost and attempt
to hide this loss from player A. 

\subsection*{Encryption}

Each player chooses a play, then a key to suit the play,
then encrypts the key.
It is claimed that from the encryption it is difficult to recover
the key.
Also, it is not possible that two different keys give the same
encryption. Therefore, although disclosure of the encrypted key
does not make the key public, it is impossible to change the key once
the ecryption is revealed.

Choose {\it key}$_l$ where $l=A$ or $l=B$ to be an 
integer in the range of 0 to 1,000,000,006
and so that,
\[ {\it key}_l \pmod{3} = \left\{ \begin{array}{ll}
            0 & \mbox{if player $l$ is Paper,}\\
            1 & \mbox{if player $l$ is Rock,}\\
            2 & \mbox{if player $l$ is Scissors.}\end{array}\right.
\]
Calculate the encryption of {\it key}$_l$ as follows:
\[  5 ^{ {\it key}_l } = {\it cry}_l \pmod{1,000,000,007},\] 
where $l$ can be either $A$ or $B$.
For your protection, {\it key}$_l$ should be chosen randomly subject 
to the above constraints, and it should not be too small.
The claim of secrecy rests on the difficulty of recovering
{\it key}$_l$ from {\it cry}$_l$. If {\it key}$_l$ is small,
an exhaustive search starting from 0 would find it quickly.
If {\it key}$_l$ it is random, however, the chances of its discovery are
but one in a billion.
Keys must be in the stated range. Keys outside this range are
not legal play.

\subsection*{Keeping Score}

There are several ways to cheat if a record of play is not kept.
For instance, you can impersonate another player and play both
sides to give yourself wins. The programs should keep a game log.
A sample entry is,
\begin{center}
   {\it time-and-date-stamp} {\bf A}{\it uid}$_A${\bf .}{\it seqnum uid}$_B$
   {\it cry}$_A$ {\it cry}$_B$ {\it key}$_A$ {\it key}$_B$
   {\it ack/nack}
\end{center}
where the the time and date stamp is the creation date of the A file
for this game, and the ack/nack determines whether the game was not
aborted in error. 
\end{document}