Lab 4 - 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#

  • First pip install pycryptodome, and then make the following imports:

from Crypto.Util.number import getPrime, getRandomNBitInteger
from sympy.ntheory import n_order, factorint

from Lab4_Helper import (
                            only_letters,
                            weave, 
                            shift_string,
                            add_spaces,
                            to_base_b,
                            from_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.)

Part 1: Factorization timings#

  • Define p and q to be two (different) 40-bit prime numbers (use getPrime).

  • Define N = p*q.

  • In a new cell, evaluate factorint(N) and time how long the computation takes using %%time at the top of the cell.

  • Define p1 to be a 28-bit prime number and define q1 to be a 54-bit prime number.

  • Define N1 = p1*q1.

  • In a new cell, evaluate factorint(N1) and time how long the computation takes.

  • Display p, q, p1, q1 to get a sense for how big these primes are.

Answer the following in a markdown cell.

  1. How do the two timings compare? (There is some randomness here, so don’t expect the same answer if you run the computations again.)

  2. How do the sizes of N and N1 compare? (For example, what is N1/N?)

  3. What do you think is most signficant to the difficulty of prime factorization, the size of N, the size of the smaller prime, or the size of the larger prime?

Part 2: Posting encryption keys#

  • Define p and q to be two (different) 500-bit prime numbers.

  • Define N = p*q.

  • Display p and q in this notebook. (This is important, because otherwise you won’t have any way to recover p and q, for example, if the Deepnote hardware resets.)

  • Choose a suitable encryption exponent e1. (What are the requirements for an encryption exponent? You can import gcd from math.)

  • Compute the corresponding decryption exponent d1. (Recall that you can use pow with a negative exponent.)

  • Go to the Lab 4 RSA pinned thread on Ed Discussion and post N, e1, d1. (Warning. Do not post p, q, or \(\varphi(N)\).)

  • Oops, we were not supposed to post the decryption exponent. Don’t worry, though, using the same value of N, find another appropriate encryption exponent e (not the same as e1). Post this value of e as a reply to your previous N, e1, d1 post.

Part 3: Sending a secret message#

Comment. This lab is a little different than Lab 2, because every group should post an RSA encryption key, and every group should also send a secret message.

  • Choose a 600-bit secret integer x using getRandomNBitInteger. (This integer will define the key for a Vigenere encryption. It’s important that x be smaller than N; do you see why?)

  • Display x in this notebook, so you can recover it (for example, if the Deepnote hardware resets).

  • Convert x to a list of digits from 0 to 25 (inclusive) using the imported to_base_b function. Name the resulting list vig_key.

vig_key = to_base_b(x, 26)

  • Choose a secret message M.

  • With the vigenere function, encrypt the secret message M using the list vig_key computed above, as in the following code.

Y = vigenere(M, vig_key)
Y = add_spaces(Y)
print(Y)

  • Choose a thread from another group. Using their N and e (not e1, we don’t want the decryption exponent to be public!), compute \(c := x^e \bmod N\). (So x is your value and N and e are the values from the other group.)

  • Post c and the encrypted message Y as a reply to the group’s thread on Ed Discussion.

Optional Part 4: Decrypting a received message#

If your group received an encrypted message, I recommend trying to decrypt it. If you can’t get something in English, try to figure out what went wrong, by checking over your work and the work by the other group.

Here is some useful code to use. If the resulting string M looks like English, then you have successfully received the message.

x = ??? # Being able to recover `x` from `c` is the whole point of RSA
vig_key = to_base_b(x, 26)
decrypt_key = [26-i for i in vig_key]
M = vigenere(Y, decrypt_key)
M

Cliffhanger#

Because we were careful to use e instead of e1 when encrypting the message, the decryption exponent is not publicly known.

Thus the exchanged message is secure…

Mr Burns evil smile

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