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 $`$p$0`$ using the $`$getPrime$`$ function. $($See the next few instructions to help you decide how large the prime should be$.)$

$*$ Find a generator $`$g$0`$ for $$(\backslash$mathbb$\{$Z$\}\_\{$p$\_0\})^\{*\}$$$.($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$($g$0,0,$ p$0)`,$ and time how long it takes using $`\%\%$time$`$ at the top of the cell. 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 $`$p$0`$ and $`$g$0`$ above until you find values for which it takes $1-4$ seconds.

$*$ Again using the getPrime function, find a prime $`$p$`$ which is $`20`$ bits larger $($add$,$ don't multiply$)$ than the prime $`$p$0`$ you found above.

$*$ As above, find a generator $`$g$`$ for $$(\backslash$mathbb$\{$Z$\}\_\{$p$\})^\{*\}$$$.$

$*$ We estimate that multiplying $`$p$0`$ 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$/$p$0`$ 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.$)$

$*$ One of the two groups $("$Alice$")$ should post the above values $`$p$`$ and $`$g$`$ on the "Lab $2$ Key Exchanges" thread on Canvas 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$`.$

$*$ Alice and Bob should then compute $`$A$`$ and $`$B$`($using $`$a$`$ and $`$b$`,$ respectively$),$ in the notation of the textbook, Section $2\mathrm{.}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.