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

Assignment: due Monday, 11:59 pm

  1. Factor the number \(512570921342230510551921091960529004047\) using Lenstra’s method, with an elliptic curve of your choice. Use your ecPowModp function. Show your work. You will probably want to work in the console, so when your ecAddModp function prints a warning, you will be able to see the denominator \(d\) that failed. (You don’t have to implement Lenstra’s method as a function, just step through it for this example.)

  2. Let \(E\) be the group defined by the elliptic curve \(y^2 = x^3 -3x + 3\) modulo 7. (In the last assignment you showed that there were six points on this curve.) Use your ecPowModp function to find a generator for the group. That is, find a single point \(P\) on \(E\) such that the powers \(P, 2P, 3P, \ldots\) give all the elements of \(E\). (The presence of such a generator shows that this group is cyclic.)

  3. Let \(E\) be the group defined by the elliptic curve \(y^2 = x^3 - x\) modulo 71. (In the last assignment, you showed that this curve has 72 points.) Show that no element of \(E\) can generate \(E\). That is, show that, for every \(P\), the list \(P, 2P, 3P, \ldots\) never gives all the elements of \(E\). (Hence, this group is not cyclic.)

  4. Illustrate the ElGamal cryptosystem on the elliptic curve \(y^2=x^3+4x-12063\) modulo \(34543427\). Let \(\alpha = G = (23,14)\).

    1. Alice wants to send the message \(m=20161908\). Find a point \(P_m = (m,y)\) on the curve, if possible. If no such point exists, pad \(m\) to obtain a point \(P_m\) on the curve.
    2. For his private key, Bob chooses \(a = 1945\). What information does Bob publish?
    3. What message does Alice send? (Pick a secret random \(k\).)
    4. Show how Bob can decrypt the message.

  5. Illustrate the elliptic curve Diffie-Hellman key exchange on the elliptic curve \(y^2=x^3+4x-12063\) modulo \(34543427\). Let \(G = (23,14)\). Suppose Alice’s secret number is \(N_A = 1984\), and Bob’s secret number is \(N_B = 2003\).

    1. Compute the messages that Alice and Bob send to each other.
    2. Compute the shared key.