Lab 2 - 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:

(You will also work together with another group below. In particular, you will perform the Diffie-Hellman key exchange with another group.)

Suggestion#

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

Imports#

  • Install the Python library pycryptodome by executing the following in a code cell.

!pip install pycryptodome

Deepnote will suggest moving this to a requirements.txt file. Do that by clicking the “move packages” link that Deepnote shows. Now every time you start the Deepnote hardware for this Lab 2 project, this package will be automatically installed and available to you.

Comment 1. One of the times I tried this, I couldn’t get the requirements.txt file to be created. If that happens to you, it’s not a big deal, you’ll just have to run the !pip install pycryptodome command each time you start the hardware.

Comment 2. We also need the sympy library, but I believe that is pre-installed in Deepnote. If it does not seem to be installed for you, then repeat the above procedure for sympy as well.

  • Import some functions we will use by executing the following code. (This will raise an error if pycryptodome hasn’t been successfully installed.)

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

from Lab2_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.)

  • Paste in your code defining the naive_dlog function that you write as part of Homework 2, 4g.

Update 7/5/23: I realized my naive discrete logarithm function is a little more naive than I had intended. In the implementation from the homework, we compute (for example) pow(g, 100000, p) in one step, and then pow(g, 100001, p) in the next step, and then pow(g, 100002, p) in the next step, and so on. The modular exponentiation function is fast, but it’s still a waste of computing power to compute the power “from scratch” each step. Instead, we can use the fact that if we know \(y := g^{100000} \bmod p\) (for example), then we can simply compute (g*y)%p to find \(g^{100001} \bmod p\), and so on. For this lab, you can either use the code template from Homework 2, 4g, or you can adjust the algorithm to this “multiply the previous value by g and then reduce modulo p” algorithm that I just described. The algorithm described here will be a little faster than the algorithm from Homework 2.

Setup for Diffie-Hellman key exchange#

Finding a smallish prime#

The getPrime function imported above takes as input an integer N and as output returns a random N-bit prime number. (For example, 37 = 32 + 4 + 1 written in binary is 100101, which is 6 digits, so 37 is a 6-bit prime number. You can verify this by evaluating to_base_b(37, 2) and checking that the resulting list is length 6. The from_base_b function goes in the opposite direction.)

  • Choose a prime p0 using the getPrime function. (See the next few instructions to help you decide how large the prime should be.)

  • Find a generator g0 for \((\mathbb{Z}/p_0\mathbb{Z})^\times\). (Hint. Use the n_order function that we imported from SymPy. Call help(n_order) to see how this function works. What order do we need to have a generator? You will have to do some guessing-and-checking (or better, use a for loop, calling break when you’ve found a generator), but it shouldn’t take many guesses before you find a generator.)

  • Call naive_dlog(g0, 0, p0), and time how long it takes using %%time at the top of the cell, as in Homework 2, Exercise 4. We already know that no discrete logarithm exists in this case (why?), so the point of this is just to see how long the naive discrete logarithm takes to run in the worst-case scenario.

  • We want a prime for which this naive discrete logarithm calculation takes 1-4 seconds. If your prime takes an amount of time outside of this range, then change the values of p0 and g0 above until you find values for which it takes 1-4 seconds.

Finding a medium prime#

  • Again using the getPrime function, find a prime p which is 20 bits larger (add, don’t multiply) than the prime p0 you found above.

  • As above, find a generator g for \((\mathbb{Z}/p\mathbb{Z})^{\times}\).

  • We estimate that multiplying p0 by M will multiply the amount of time the naive discrete logarithm takes by M. Using this estimate, how many days would you expect the naive discrete logarithm to take for p? (Your answer should depend on p/p0 and on the number of seconds given by your timing computation above. Do not try to run the naive discrete logarithm function on p directly. Be sure your answer is in days, not in seconds.)

Performing a Diffie-Hellman key exchange#

  • Find another student/group to work with (for example, post on Ed Discussion). Put their names here.

Names for group 2:

  • One of the two groups (“Alice”) should post the above values p and g on the “Lab 2 Key Exchanges” thread on Ed Discussion.

  • Alice and Bob should choose random secret exponents a and b (respectively). To find a and b, use the getRandomNBitInteger function we imported above, calling getRandomNBitInteger(N), where N is 1 or 2 less than the number of bits of p.

(Homework 2, question 6b, asks why it is not secure to choose a secret exponent like 500000.)

  • Alice and Bob should then compute A and B (using a and b, respectively), in the notation of Hoffstein, Pipher, Silverman, Section 2.2, using the pow function (the three-argument version). Alice and Bob should post these public values A and B on Ed Discussion (as replies to the message posting p and g).

Be sure that a and b never get posted (nor exchanged between Alice and Bob), but you probably want to display your secret exponent in this notebook so you still have access to it if the hardware resets.

  • Alice and Bob should both (independently) compute their shared secret key k.

  • Alice and Bob should both (independently) convert k to a list of digits from 0 to 25 (inclusive) using the imported to_base_b function. Name the resulting list vig_key. This list vig_key will be the shared private key for a Vigenere cipher.

vig_key = to_base_b(k, 26)

  • Bob should choose a secret message M that he wishes to send to Alice. (It does not have to be a long message, not nearly as long as the messages in Lab 1. We don’t want the Vigenère ciphertext to be vulnerable to decryption using frequency analysis.)

  • With the vigenere function, Bob should encrypt his secret message M using the list vig_key computed above, as in the following code. Bob should post this encrypted message Y as a reply on the same thread.

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

  • Alice should take this public message Y and decrypt it. Notice that the list vig_key was used for encryption, so a slightly different list should be used for decryption. (What shift amounts do the decryption, in terms of the encryption shift amounts?)

Here we are defining the decryption key decrypt_key using a list creation method in Python called “list comprehension”; be sure to ask if the syntax is confusing.

decrypt_key = [??? for x in vig_key]
M = vigenere(Y, decrypt_key)
M

  • Do not post the decrypted plaintext in the thread. Alice and Bob should not exchange any information in private. The public information (which is the same as the information shared between Alice and Bob) should be p, g, A, B, and Y.

  • If Alice has successfully decrypted the message (meaning she gets something that is English), then you are done with this lab.

Cliffhanger#

We chose our prime p above so that the discrete logarithm is not computable in a reasonable amount of time using the naive algorithm.

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