import string

from collections import Counter

# Computed from "A Tale of Two Cities". Compare Table $1\mathrm{.}3$ in Hoffstein, Pipher, Silverman.

english$\_$freq $=\{$

$\text{'}$a$\text{'}$: $0\mathrm{.}0803,$

$\text{'}$b$\text{'}$: $0\mathrm{.}014,$

$\text{'}$c$\text{'}$: $0\mathrm{.}0232,$

$\text{'}$d$\text{'}$: $0\mathrm{.}0467,$

$\text{'}$e$\text{'}$: $0\mathrm{.}1247,$

$\text{'}$f$\text{'}$: $0\mathrm{.}0226,$

$\text{'}$g$\text{'}$: $0\mathrm{.}0209,$

$\text{'}$h$\text{'}$: $0\mathrm{.}065,$

$\text{'}$i$\text{'}$: $0\mathrm{.}0683,$

$\text{'}$j$\text{'}$: $0\mathrm{.}0012,$

$\text{'}$k$\text{'}$: $0\mathrm{.}008,$

$\text{'}$l$\text{'}$: $0\mathrm{.}0367,$

$\text{'}$m$\text{'}$: $0\mathrm{.}0255,$

$\text{'}$n$\text{'}$: $0\mathrm{.}0706,$

$\text{'}$o$\text{'}$: $0\mathrm{.}0776,$

$\text{'}$p$\text{'}$: $0\mathrm{.}0166,$

$\text{'}$q$\text{'}$: $0\mathrm{.}0011,$

$\text{'}$r$\text{'}$: $0\mathrm{.}0621,$

$\text{'}$s$\text{'}$: $0\mathrm{.}0626,$

$\text{'}$t$\text{'}$: $0\mathrm{.}0902,$

$\text{'}$u$\text{'}$: $0\mathrm{.}0279,$

$\text{'}$v$\text{'}$: $0\mathrm{.}0087,$

$\text{'}$w$\text{'}$: $0\mathrm{.}0236,$

$\text{'}$x$\text{'}$: $0\mathrm{.}0012,$

$\text{'}$y$\text{'}$: $0\mathrm{.}0203,$

$\text{'}$z$\text{'}$: $0\mathrm{.}0004$

$\}$

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 count$\_$substrings$($X$,$n$)$:

$\text{'}\text{'}\text{'}$Returns a Python Counter object of all n$-$grams in X$.\text{'}\text{'}\text{'}$

if not X:

return $\{\}$

X $=$ only$\_$letters$($X$)$

shifts $=[$X$[$i:$]$ for i in range$($n$)]$

grams $=[\text{'}\text{'}.$join$($chrs$)$ for chrs in zip$(*$shifts$)]$

return Counter$($grams$)$

def get$\_$freq$($X$)$:

$\text{'}\text{'}\text{'}$Returns the proportion that each letter occurs in $"$X$".$

I might change this later, but for now, it converts everything to lowercase.

The reason is to match what appears in the english$\_$freq dictionary.$\text{'}\text{'}\text{'}$

X $=$ only$\_$letters$($X$,$ case$=$"lower"$)$

n $=$ len$($X$)$

ctr $=$ count$\_$substrings$($X$,1)$

output $=\{\}$

for char in string.ascii$\_$lowercase:

output$[$char$]=$ ctr$[$char$]/$n

return output

def mut$\_$ind$\_$co$($d$1,$ d$2)$:

$\text{'}\text{'}\text{'}$For letter frequency dictionaries d$1$ and d$2,$ return the Mutual Index of Coincidence.

See Equation $(5\mathrm{.}9)$ on page $222$ in Hoffstein, Pipher, Silverman.$\text{'}\text{'}\text{'}$

s $=0$

for k in d$1.$keys$()$:

s $+=$ d$1.$get$($k$,0)*$d$2.$get$($k$,0)$

return s

import numpy as np

def naive$\_$decrypt$($Y$)$:

holder $=$ np$.$zeros$(26)$

for i in range$(26)$:

X $=$ shift$\_$string$($Y$,$ i$)$

holder$[$i$]=$ X$.$count$("$E$")$

# np$.$argmax finds the location of the maximum value.

# $($If the maximum is obtained multiple times, only the first index is returned.$)$

shift$\_$amt $=$ np$.$argmax$($holder$)$

X $=$ shift$\_$string$($Y$,$ shift$\_$amt$)$

return $($X$,$ shift$\_$amt$)$

def shift$\_$decrypt$($Y$)$:

$"""$

Automatically decrypt ciphertext that has been encrypted using a shift cipher.

This function returns the decrypted string and the shift amount.

$"""$

max$\_$ic $=0$

best$\_$shift $=0$

best$\_$decryption $=""$

for i in range$(26)$:

decrypted$\_$text $=$ shift$\_$string$($Y$,$ i$)$

freq$\_$dict $=$ get$\_$freq$($decrypted$\_$text$)$

ic $=$ mut$\_$ind$\_$co$($freq$\_$dict, english$\_$freq$)$

if ic $>$ max$\_$ic:

max$\_$ic $=$ ic

best$\_$shift $=$ i

best$\_$decryption $=$ decrypted$\_$text

return best$\_$decryption, best$\_$shift

Encrypt the string $`"$INTROCRYPTOGRAPHY$"`$ using a shift cipher. $($Use the $`$shift$\_$string$`$ function... don't do this by hand.$)$ Store the resulting ciphertext using the variable name $`$Y$`.$

Evaluate $`$Y$`($there$\text{'}$s no need to use $`$print$`,$ just execute a code cell with $`$Y$`$ in it$)$ to see what the encrypted text looks like.

Does your $`$shift$\_$decrypt$`$ function find the true plaintext in this case?

$*$ Notice that the returned shift amount is different from the shift amount you used for encryption $($unless you chose a shift amount of $`0`$ or $`13`).$ Briefly explain why that's the case in a markdown cell.

$($Notice that a different shift amount being returned is not an indication of a mistake in our code.$)$

Try evaluating $`$naive$\_$decrypt$`$ on the ciphertext you made. $($You$\text{'}$ll first need to execute the $`$naive$\_$decrypt$`$ code by pasting it into a code cell and then evaluating that cell.$)$

How could we have known in advance that the naive strategy would not work in this case? Briefly explain in a markdown cell.

$*$ Find an example of text for which your $`$shift$\_$decrypt$`$ function does not work. Try to make the original English text at least a few words.