Lab 3 - Math 173A#

You are encouraged to work in groups of up to 3 total students, but each student should make their own submission on Canvas. (It’s fine for everyone in the group to have the same upload.)

Put the full names of everyone in your group (even if you’re working alone) here. (This makes grading easier.)

  • Names:

Suggestion#

Follow the instructions from the Lab 0 worksheet to make an Education Workspace for this lab.

Overview#

In the previous lab, you played the role of Alice or Bob. In this lab, you will play the role of Eve. It turns out that most if not all of the primes used last week were too small. In particular, the discrete logarithm problem for these primes can be solved, not using the naive algorithm, but using the Collision Algorithm described in Hoffstein, Pipher, Silverman, Section 2.7.

Choose one of the Lab 2 threads from Canvas (not your own thread!). You will reveal their secret message by solving the relevant discrete log problem.

Record the relevant values below. Execute the code so you have access to these values below.

p = 
g = 
A = 
B = 
Y = # the encrypted message

Imports#

  • Import the following. (Most of these functions are just here so your vigenere function works.)

from Lab3_Helper import (
                            only_letters,
                            weave, 
                            shift_string,
                            add_spaces,
                            to_base_b
                        )

  • Paste in your code defining the vigenere function from Lab 1. (I believe I have included all the necessary imports like only_letters, but feel free to add more if your vigenere function depends on them.)

  • The first step in the Babystep-Giantstep algorithm involves computing a square root and the floor of that square root. We can import these functions from NumPy using the following.

from numpy import sqrt, floor

Implementing the Collision Algorithm#

Follow Shanks’s Babystep-Giantstep Algorithm (Proposition 2.21) to find a value of \(a\) such that \(g^a \equiv A \bmod p\).

Suggestions.

  • I wanted to use range(n+1), with n as in the notation from Proposition 2.21, but an error was raised because n was not an integer. You can convert an element x to an integer in Python using int(x).

  • When you make the two lists baby_list and giant_list, be sure all elements in the lists are between \(0\) and \(p\). When you are computing powers, use pow(???, ???, ???). (Note that the pow function can even accept negative exponents, but think about how you would create giant_list if you were only allowed to use positive exponents.) When you are multiplying for the elements in the Giantstep list, be sure you reduce modulo \(p\) after the multiplication (use %p).

  • It will be too slow to naively compare all pairs of elements in the two lists looking for a collision (why?). One approach, suggested by Bing Chat, is to convert these lists into Python sets (using for example set(baby_list) and similarly for giant_list), and then compute the intersection of these two sets (using for example baby_set & giant_set).

(A less magical approach would be to first create sorted versions of the two lists using the Python function sorted, and then to step through these sorted lists, looking for a collision. But how to implement this second part, where we look for the collision, taking advantage of the fact that the lists are sorted, is not immediately clear to me.)

  • Once we have an element C that is in both lists, we can find its position in the lists (counting starts at number 0 in Python) using the following: baby_list.index(C) and similarly for finding the index in giant_list. What are these index values in terms of the notation from Proposition 2.21?

Revealing the message#

  • Compute the shared secret key k, and then convert it into a key for Vigenère encryption/decryption using to_base_b(k, 26). (Make sure k is between 0 and p. If not, then you probably did not compute it using the correct approach.)

  • The resulting list was used for encryption. Adjust the list so it can be used for decryption, like what Alice did in last week’s lab.

  • Decrypt the message using the vigenere function. If the result is English, then you’re done with this lab. If not, check over your work, or try to decrypt a different group’s post on Ed Discussion. (It’s always possible the original posting had a mistake in it.)

Submission#

  • Using the Share button at the top right, enable public sharing, and enable Comment privileges. Then submit the created link on Canvas.

(Don’t just copy the browser URL. Copy the link that is provided after you click the “Share” button. It won’t be available until you enable public sharing.)

  • Reminder: Everyone in the group needs to submit this link on Canvas.

Created in deepnote.com Created in Deepnote