Lab 5 - 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.

Part 0: Imports#

  • Make the following imports:

from math import gcd

from Lab5_Helper import (
                            only_letters,
                            weave, 
                            shift_string,
                            add_spaces,
                            to_base_b,
                            from_base_b,
                            factor_out_2
                        )

  • The only new function here is factor_out_2. Get a sense for what it is returning by evaluating factor_out_2(48) and factor_out_2(34) and factor_out_2(33).

  • 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.)

Part 1: The Miller-Rabin primality test#

Here is pseudo-code for implementing this primality test from Table 3.2 in Hoffstein, Pipher, Silverman.

Miller-Rabin primality test pseudo-code

Follow the pseudo-code to implement the Miller-Rabin primality test. To get you started, the skeleton of the function is written below.

def miller_rabin(n, a):
    if (n%2 == 0):
        return "Composite"
    if (1 < gcd(a,n)) and (gcd(a,n) < n):
        return "Composite"
    # Define k and q as in Step 2.
    # Step 3 goes here.
    if (a%n) == 1:
        return ??? # Step 4
    for i in range(k): # i = 0, 1, 2, ..., k-1
        if (a%n) == ???: # -1 by itself won't work
            return "Test Fails"
        ??? # Step 7 goes here.  Be sure to match this level of indentation.

    return "Composite" # Step 9

  • Check your work using Example 3.20, verifying that 23 witnesses the compositeness of n = 172947529 but that 17 and 3 do not.

  • Explain why we do not include i = k at the end of the for loop. (Hint. There are two possibilities for that step, either \(a \equiv 1 \bmod n\) or \(a \not\equiv 1 \bmod n\). Explain why in either case, the number \(n\) must be composite. This is why we just skip that iteration of the for loop and return "Composite".)

Part 2. Using an RSA decryption exponent to factor N#

  • Choose one of the posts from the “Lab 4 RSA” thread which includes a ciphertext Y (and not your own Post!). Define the relevant values from that post:

N = 
e1 = 
d1 = 
e = 
c = 
Y =

  • Paste in your definition of miller_rabin from above, but make the following two changes.

  1. Change the name of the function from miller_rabin to use_d and add two more arguments, e1 and d1 as inputs to the function.

  2. Instead of factoring out 2 from n-1, we want to factor 2 out of ???. Replace n-1 in Step 2 from the Miller-Rabin pseudo-code appropriately to match what is in the Boneh article.

  • Define k and q as inside this use_d function. (You should not be using N-1 here.)

  • Try various values of a with use_d(N, a, e1, d1) until you have a value of a for which the function returns "Composite". (One of the first values you try should work.)

  • By taking an appropriate power of a modulo N (for the same a as in the previous part, the values k and q you computed are relevant), find a value of z such that \(z \not\equiv \pm 1 \bmod N\) and \(z^2 \equiv 1 \bmod N\). (I expect this will require computing some powers of a. You do not need to automate this step unless you want to.)

  • Find a nontrivial factor p of N using the value of z you just found.

  • Check that the following both hold.

  1. p is neither 1 nor N.

  2. N%p is 0.

  • Define q to be the other prime factor. (This will overwrite the value of q you found above from factor_out_2, but we won’t need it again.) When defining q, use q = N//p (note the two slashes) to tell Python that q should be an integer.

  • Check that N == p*q is True.

Part 3. Decrypting the secret message#

This part is intended to be more straightforward than the previous parts.

  • Recall that c was created using e, not e1. Find d corresponding to e. (You will need to use the p and q you found above.)

  • Find the original secret integer x corresponding to c using the decryption exponent you just computed.

  • Convert x to a Vigenère key for decryption (thus the 26-a terms) using the following code.

decrypt_key = [26-a for a in to_base_b(x, 26)]

  • Decrypt the message Y using your vigenere function and this decryption key. If what you get seems to be English, then you’re done with this lab. (If you don’t get English and you can’t find a mistake in your work, try another message from Ed Discussion. It’s always possible a mistake was made during the original encryption.)

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