$*$ 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.