Modern Computing for Mathematicians (Math 587)
Written Assignment No. 2

due March 3, 2009

Prepare this assignment on paper by (a) writing your responses in LaTeX with no line longer than 70 characters, (b) compiling the LaTeX file with pdflatex to a PDF file, (c) printing the LaTeX source as plain text, (d) printing the compiled version, and (e) submitting the versions printed in (c) and (d) together at the class meeting. In the write-up for each exercise repeat its statement before introducing your solution. A very simple sketch of how this might be done is available in the course web as:

assgt/tex/assgt2-example.tex

assgt/tex/assgt2-example.pdf

Be sure to explain what you have done to answer these questions.

1. Two parties A and B agree to construct a private key in the multiplicative group modulo the number $40487$ by negotiations in public using the method of Diffie-Hellman key exchange. They agree to use $5$ as the generator. If A uses $127$ as secret exponent,

   1. what value does A send to B?

   2. if, for the same transaction, B sends the value $16874$ to A, what value is the jointly constructed private key?

2. Recall that ASCII codes corresponding to the characters used in normal English text strings are values from 1 to 126, and, therefore, may be regarded as elements of the multiplicative group modulo the prime $127$.

   Two parties agree to exchange messages using El Gamal cryptography based on the multiplicative group modulo $127$, generator $3$, and secret exponent $29$ with the resulting public key $55$. Under this agreement one of them sends the other the following vector of pairs representing coded text:

    [ [24, 116], [78, 38], [80, 108], [86, 50], [93, 90],

    [111, 98], [26, 32], [100, 94], [121, 126], [101, 50], [75, 73],

    [65, 51], [31, 40], [108, 41], [82, 27], [103, 17], [39, 106],

    [117, 67], [114, 13], [45, 86], [104, 23], [28, 10], [54, 59],

    [109, 75], [1, 103], [47, 54], [66, 69], [32, 57], [34, 43],

    [110, 94], [41, 126], [44, 105], [55, 47], [2, 105], [27, 33],

    [95, 69], [42, 21], [118, 101], [106, 1], [41, 112], [94, 106],

    [59, 114], [31, 56], [119, 57], [34, 86], [4, 1], [50, 30],

    [54, 94], [119, 25], [110, 3], [85, 76], [85, 25], [38, 5],

    [40, 11], [36, 104], [10, 41], [57, 74], [115, 72], [36, 75],

    [79, 37], [42, 118], [49, 79], [102, 13], [98, 39], [11, 65],

    [30, 103], [99, 90], [10, 120], [82, 125], [24, 47] ]

   What is the coded text? (A file suitable for reading this vector of pairs into gp is “assgt/coded-string”.)