$*$ Install the Python library $`$pycryptodome$`$ by executing the following in a code cell.

$```$

$!$pip install pycryptodome

$```$

$*$ 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 Lab$2\_$Helper import $($

only$\_$letters,

weave,

shift$\_$string,

add$\_$spaces,

to$\_$base$\_$b$,$

from$\_$base$\_$b

$)$

$```$

def naive$\_$dlog$($g$,$ h$,$ p$)$:

output $=1$

for i in range$($p$-1)$:

output $=$ output$*$g$\%$p

if output $==$ h:

return i

return None

import string

import textwrap

def string$\_$for$\_$code$\_$block$($X$,$ linewidth$=60)$:

return $\text{'}$

$\text{'}.$join$($textwrap$.$wrap$($X$,$ width$=$linewidth$))$

def add$\_$spaces$($X$,$ width$=5,$ linewidth$=60)$:

one$\_$line $=\text{'}\text{'}.$join$($textwrap$.$wrap$($X$,$ width$=$width$))$

many$\_$lines $=$ string$\_$for$\_$code$\_$block$($one$\_$line, linewidth$=$linewidth$)$

return many$\_$lines

def only$\_$letters$($X$,$ case$=$None$)$:

$\text{'}\text{'}\text{'}$Returns the string obtained from X by removing everything but the letters.

If case$=$"upper" or case$=$"lower", then the letters are all

converted to the same case.$\text{'}\text{'}\text{'}$

X $=\text{'}\text{'}.$join$($c for c in X if c in string.ascii$\_$letters$)$

if len$($X$)==0$:

return None

if case is None:

return X

elif case $==$ "lower":

return X$.$lower$()$

elif case $==$ "upper":

return X$.$upper$()$

def shift$\_$char$($ch$,$ shift$\_$amt$)$:

$\text{'}\text{'}\text{'}$Shifts a specific character by shift$\_$amt.

Example:

shift$\_$char$("$Y$",3)$ returns $"$B$"$

$\text{'}\text{'}\text{'}$

if ch in string.ascii$\_$lowercase:

base $=\text{'}$a$\text{'}$

elif ch in string.ascii$\_$uppercase:

base $=\text{'}$A$\text{'}$

# It's not clear what shifting should mean in other cases

# so if the character is not upper or lower$-$case, we leave it unchanged

else:

return ch

return chr$(($ord$($ch$)-$ord$($base$)+$shift$\_$amt$)\%26+$ord$($base$))$

def shift$\_$string$($X$,$ shift$\_$amt$)$:

$\text{'}\text{'}\text{'}$Shifts all characters in X by the same amount.$\text{'}\text{'}\text{'}$

return $\text{'}\text{'}.$join$($shift$\_$char$($ch$,$ shift$\_$amt$)$ for ch in X$)$

def weave$($string$\_$list$)$:

output $=\text{'}\text{'}.$join$([\text{'}\text{'}.$join$($tup$)$ for tup in zip$(*$string$\_$list$)])$

# The rest is just to deal with the case of unequal string lengths

# We assume the only possibility is that the early strings are one character longer

last$\_$length $=$ len$($string$\_$list$[-1])$

extra $=[$s$[-1]$ for s in string$\_$list if len$($s$)>$ last$\_$length$]$

return output $+\text{'}\text{'}.$join$($extra$)$

def to$\_$base$\_$b$($num$,$ base$)$:

$\text{'}\text{'}\text{'}$Returns the digits of $`$num$`$ when written in base $`$base$`.$

Adapted from code on Stack Overflow.$\text{'}\text{'}\text{'}$

digits $=[]$

while num $>0$:

num, rem $=$ divmod$($num$,$ base$)$

digits.append$($rem$)$

return digits$[$::$-1]$

def from$\_$base$\_$b$($digit$\_$list, base$)$:

$\text{'}\text{'}\text{'}$Converts from a list of digits in base $`$base$`$ to an integer.$\text{'}\text{'}\text{'}$

return sum$($d$*$base$**$i for i$,$ d in enumerate$($digit$\_$list$[$::$-1]))$

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