import string

import textwrap

import re

from collections import Counter

from itertools import combinations

import numpy as np

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 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 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 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

def ind$\_$co$($X$)$:

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

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

n $=$ sum$($ctr$.$values$())$

return $(1/($n$*($n$-1)))*$sum$($f$*($f$-1)$ for f in ctr$.$values$())$

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 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$,$ case$=$"lower"$)$:

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

if case $==$ "lower":

letters $=$ string.ascii$\_$lowercase

elif case $==$ "upper":

letters $=$ string.ascii$\_$uppercase

else:

raise ValueError$("$case should be 'upper' or 'lower'."$)$

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

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

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

output $=\{\}$

for char in letters:

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

return output

def kasiski$\_$diffs$($Y$,$ case$=$"upper"$)$:

Y $=$ only$\_$letters$($Y$,$ case$=$case$)$

ctr $=$ count$\_$substrings$($Y$,3)$

tri$\_$reps $=[$k for k$,$v in ctr$.$items$()$ if v $>1]$

diffs $=[]$

for tri in tri$\_$reps:

starts $=[$m$.$start$()$ for m in re$.$finditer$($f$\text{'}(?=\{$tri$\})\text{'},$ Y$)]$

diffs.extend$([$abs$($x$-$y$)$ for x$,$y in combinations$($starts$,2)])$

return np$.$array$($sorted$($diffs$))$

$*$ When we encrypt using the Vigen$$re cipher with a key length of $5($for example$),$ we shift all the characters at integer positions $0$ modulo $5$ by the same amount, all characters at integer positions $1$ modulo $5$ by the same amount, and so on$.$ Assume $`$X$`$ is the string we want to encrypt using the Vigen$$re cipher with a key length of $`5`.$ Notice you can get all the characters in $`$X$`$ at integer positions $2$ modulo $5($for example$)$ using $`$X$[2$::$5]`.($You can think of this as shorthand for $`$X$[2$:len$($X$)$:$5]`,$ which means, start at position $`2`,$ go until reaching $`$len$($X$)`,$ go up by $`5`.)$ Test this out by setting $`$X $=$ string.ascii$\_$uppercase$`$ and then printing $`$X$`$ and $`$X$[2$::$5]`.$

$*$ We need a way of $"$re$-$assembling" these strings. We can do that using the imported $`$weave$`$ function. Evaluate the following code to get a sense for how it works. $($Here $`$X$`$ should be the same as above. If you know list comprehension, try to recreate this list using list comprehension.$)$

$```$

weave$([$X$[0$::$5],$ X$[1$::$5],$ X$[2$::$5],$ X$[3$::$5],$ X$[4$::$5]])$