Upload to Canvas a PDF of your work for the following problems.

Assignment: due Monday, 11:59 pm

  1. Use the shortcut to find a primitive root modulo 811177151133889. (Use the gmp function factorize to find the unique factors of 811177151133888. Also use powm.) Explain how you know that you have found a primitive root.

  2. Suppose Alice and Bob conduct a Diffie-Hellman key exchange as follows.

    • Alice and Bob agree on prime \(p = 240922393\) and primitive root \(\alpha=103\).
    • Alice chooses secret \(x = 120461539\) and sends \(\alpha^x\) to Bob.
    • Bob chooses secret \(y = 81635591\) and sends \(\alpha^y\) to Alice.

    Compute the shared secret key. Remember to do your calculations in \(U(p)\).

  3. Suppose, in the situation in question 2, that Eve is able to intercept messages between Alice and Bob and alter them (i.e., Eve is an “intruder in the middle”) as follows:

    • Eve chooses a “fake” exponent \(z = 49182605\).
    • Eve intercepts Alice’s message \(\alpha^x\) and sends Bob \(\alpha^z\) instead.
    • Eve intercepts Bob’s message \(\alpha^y\) and sends Alice \(\alpha^z\) instead.

    If Alice and Bob are not aware that Eve is doing this, what “shared secrets” do they compute? Is it possible for Eve to also know these secrets? Explain.

  4. The recipe for the ElGamal cryptosystem is in the slides. Suppose that Alice and Bob are communicating using the ElGamal cryptosystem with \(p = 179841529021446883498969891\) and \(\alpha = 7\). Bob’s secret exponent is \(a = 10000\).

    1. Give the triple that Bob makes public.
    2. Suppose Alice wants to send the message 370288657646690981668211. Compute a ciphertext pair that Alice could send.
    3. Decrypt to check your answer.

  5. In \(U(53457634678734567834567367867346003)\), compute \(L_5(31224112303063959919880288679125645)\) modulo 2. Show your work.

  6. Show that the implementation of Baby Step Giant Step given in the slides can be sped up considerably by using character vectors rather than lists of bigz. Replace the assignment of baby and giant with the following.

baby <- sapply(1:N, function(j){as.character(powm(alpha, j, p))})
giant <- sapply(1:N, function(k){as.character((beta*powm(alpha, -N*k, p)) %% p)})

Compute system.time(match(baby,giant)) for the original baby and giant (given in the slides) and also for the above version of baby and giant. Compare the elapsed times. Also look in the environment tab and compare the sizes of the lists/vectors for both versions.