<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 Vigenere cipher cryptoanalysis
This notebook studies the cryptoanalysis of the Vigenere cipher, which is polyalphabetic, namely two occurrences  $a_{1}, a_{2}$ of character $a$ belonging to the plaintext are associated with occurrences $c_{1}, c_{2}$ in the ciphertext, such that $c_{1}\neq c_{2}$ with very high probability.
Our implementation closely follows a class lecture given by Prof. Orazio Puglisi within Cryptography course at the University of Florence. In order to fully understand the last part, where the concept of mutual coincidence index is crucial, we rest on the explanation at pag. 20 of this notes.
Step1:  alphabet
Let $\mathcal{A}$ be our alphabet composed of standard English characters plus the space character. It will be sufficient to encode simple and (not so quite) short messages. To define it as a group $\frac{\mathbb{Z}}{n\mathbb{Z}}$ in the Python language we use a dict object, which can be reversed because it is a bijection.
Step2:  string encoding and the plaintext
We define a function encode that consumes a string and produces a list of integer in our field. In parallel, function decode goes backwards, it consumes a list of integers and return a string. Such functions are useful in order to use the cipher and analyze it using str objects instead of the coded version using lists of integers.
Step3:  The following plaintext is a prose taken from here; before using it we have to swipe out punctuation marks
Step4:  With the following assert we ensure that function decode is the inverse of function encode
Step5:  key
Let $\textbf{k}=(k_{0},\ldots,k_{m-1}) \in \left(\frac{\mathbb{Z}}{n\mathbb{Z}}\right)^{m}$ be a key of length $m\in\mathbb{N}$. In order to have a meaningful analysis we build a function generate_random_key which generate a random key of random length, keeping it safe...we will uncover it only at the end to check our work
Step6:  encryption and the ciphertext
Now we are in the position to define encrypt and decrypt functions, both of them consumes an encoded message, namely a list of integers, and a key. The encryption work by repeating the key as long as necessary to match the same length of the input $\textbf{x}=(x_{0},\ldots,x_{h})$, where $h > m-1$ otherwise the cipher is a OneTimePad which is unbreakable, 
$$(\underbrace{x_{0},\ldots,x_{m-1}}{k{0},\ldots,k_{m-1}}
\underbrace{x_{m},\ldots,x_{m-1}}{k{0},\ldots,k_{m-1}}
\ldots
\underbrace{x_{lm},\ldots,x_{h}}{k{0},\ldots,k_{h \mod m}}) = 
(y_{0},\ldots,y_{h}) = \textbf{y}$$
truncating the very right block to match plaintext suffix. At last, the ciphertext $\textbf{y}$ is obtained by addition modulo $n$ of corresponding symbols, where $n$ is the length of the alphabet. Decryption follows the same scheme, using modular subtraction.
Step7:  the following is the ciphertext produced by the application of function encrypt to the plaintext
Step8:  Assuming to know the secret_key, we ensure that function decrypt is the inverse of function encrypt
Step12:  coincidence index
Let $I_{c}$ be the coincidence index of a sequence $\alpha$, over an alphabet $A$, defined as 
$$ I_{c}(\alpha) = \sum_{i=0}^{n}{\frac{f_{a_{i}}^{(\alpha)}(f_{a_{i}}^{(\alpha)}-1)}{m(m-1)}} $$ where $n$ is the length of the alphabet, $m$ is the length of $\alpha$ and $f_{a_{i}}^{^{(\alpha)}}$ is the frequency of symbol $a_{i}\in A$, namely the number of occurrences of $a_{i}$, in $\alpha$. In other words, $I_{c}$ is the probability to sample two occurrences of the same symbol $a$, forall $a\in A$, from the sequence $\alpha$. 
Index $I_{c}$ is invariant to shifting by the same constant $v$. Let $\alpha,\beta$ be two sequences of integers of length $l$ such that $\beta_{i} \equiv_{n} \alpha_{i} + v$, forall $i\in\lbrace0,\ldots,l\rbrace$; moreover, let $q_{\gamma_{i}}^{(\gamma)}$ be the probability to sample two occurrences of $\gamma_{i}$ from a sequence $\gamma$, we can state the relations
$$
    I_{c}(\beta) = \sum_{a_{i}\in\frac{\mathbb{Z}}{n\mathbb{Z}}}{q_{a_{i}}^{(\beta)}}
                = \sum_{a_{i}\in\frac{\mathbb{Z}}{n\mathbb{Z}}}{q_{a_{i}-v}^{(\alpha)}}
                = \sum_{\hat{a}{i}\in\frac{\mathbb{Z}}{n\mathbb{Z}}}{q{\hat{a}{i}}^{(\alpha)}}
                = I{c}(\alpha)
$$
where $\hat{a}{i}\equiv{n}a_{i}-v$, proving the invariance of $I_{c}$ when a sequence is produced by another one shifted by a constant $v\in\frac{\mathbb{Z}}{n\mathbb{Z}}$.
Step13:  frequencies comparison
The following are frequencies of alphabet symbols in the plaintext
Step14:  The following histogram shows frequencies in the ciphertext
Step15:  A first approach to encryption finishes computing the coincidence indexes of both plaintext and ciphertext
Step16:  finding the key length by spreading
The following set of functions allows us to probe the key length by repeatedly fixing a candidate length $l$, then spreading the ciphertext in a matrix with $l$ columns, then computing $I_{c}$ of each column and, finally, report $l$ if the majority of $I_{c}$ scores is greater than a threshold (.06 for English).
Step17:  here are $I_{c}$ scores witnesses for the candidate key length after spreading the ciphertext by columns
Step18:  The following is the ciphertext spread over a matrix with a number of column equals the candidate length found in the previous cell.
Step19:  mutual coincidence index
Once the length $m$ of key $\textbf{k}$ has been "established", we're left with finding actual key symbols $k_{i}$, for $i\in{0,\ldots,m-1}$. In order to fullfil this step, we need another object, which resembles the index of mutual coincidence $I_{c}$ but it is more general, in the sense that sampling occurs on two given sequences instead of the same one. Formally, let $I_{mc}(\alpha, \beta)$ be the index of mutual coincidence of sequences $\alpha$ and $\beta$, defined as
$$
I_{mc}(\alpha,\beta) = \sum_{a_{i}\in\frac{\mathbb{Z}}{n\mathbb{Z}}}{q_{a_{i}}^{(\alpha)}q_{a_{i}}^{(\beta)}}
$$
where $q_{a_{i}}^{(\nu)}$ is the probability to draw an occurrence of symbol $a_{i}$ in sequence $\nu$.
Let $\eta$ and $\gamma$ be two sequences of length $l$, produced by adding shifts $v_{\alpha}$ and $v_{\beta}$ to sequences $\alpha$ and $\beta$, respectively (formally, $\eta_{i} \equiv_{n} \alpha_{i} + v_{\alpha}$ and $\gamma_{i} \equiv_{n} \beta_{i} + v_{\beta}$, forall $i\in\lbrace0,\ldots,l-1\rbrace$). The inequality
$$
    I_{mc}(\eta,\gamma) 
                = \sum_{a_{i}\in\frac{\mathbb{Z}}{n\mathbb{Z}}}{q_{a_{i}}^{(\eta)}q_{a_{i}}^{(\gamma)}}
                = \sum_{a_{i}\in\frac{\mathbb{Z}}{n\mathbb{Z}}}{q_{a_{i}-v_{\alpha}}^{(\alpha)}q_{a_{i}-v_{\beta}}^{(\beta)}}
                = \sum_{a_{i}\in\frac{\mathbb{Z}}{n\mathbb{Z}}}{q_{a_{i}}^{(\alpha)}q_{a_{i}+v_{\alpha}-v_{\beta}}^{(\beta)}}
                \neq \sum_{a_{i}\in\frac{\mathbb{Z}}{n\mathbb{Z}}}{q_{a_{i}}^{(\alpha)}q_{a_{i}}^{(\beta)}}
                = I_{mc}(\alpha,\beta)
$$
holds unless factor $v_{\alpha}-v_{\beta}$ in each subscript. We can define an even more general version of $I_{mc}$ as
$$
    I_{mc}(\eta,\gamma,g) 
                = \sum_{a_{i}\in\frac{\mathbb{Z}}{n\mathbb{Z}}}{q_{a_{i}-g}^{(\eta)}q_{a_{i}}^{(\gamma)}}
                = \sum_{a_{i}\in\frac{\mathbb{Z}}{n\mathbb{Z}}}{q_{a_{i}}^{(\alpha)}q_{a_{i}+v_{\alpha}-v_{\beta}+g}^{(\beta)}}
$$
where sequence $\eta$ is shifted back by $g\in\mathbb{N}$. Therefore we can state the equality with the usual definition according to
$$
    I_{mc}(\eta,\gamma,g) = I_{mc}(\alpha,\beta) \leftrightarrow v_{\beta}-v_{\alpha}=g
$$
proving the invariance of $I_{mc}$ when two sequences are produced by shifting two other ones by constant values $q,w$ respectively, providing that $g = w-q$.
Step20:  Previous generalization allows us to set the basis to break the cipher. It works as follows
Step21:  The following cell report the set of difference equation collected respect the first column of the spread matrix
Step22:  The following function implements the last observation, namely it produces the complete keys space where we've to look for the good one.
Step23:  In order to instantiate candidates keys, for each index column $c$ we use the set of equations ${k_{a}-k_{c}=g_{u}}$, for some $u\in\mathbb{N}$ and $a\in{0,\ldots,m-1}\setminus{c}$ as follows
Step24:  The last step to filter out mistaken keys, we use each candidate key to perform a decryption, checking it against frequencies of an arbitrary English prose
<ASSISTANT_TASK:>
Python Code:
import itertools
from itertools import *
from copy import copy, deepcopy
from heapq import *
from random import *
import matplotlib.pyplot as plt
from collections import Counter
from sympy import *
init_printing()
%matplotlib inline
plt.rcParams['figure.figsize'] = (10.0, 10.0)
Explanation: Vigenere cipher cryptoanalysis
This notebook studies the cryptoanalysis of the Vigenere cipher, which is polyalphabetic, namely two occurrences  $a_{1}, a_{2}$ of character $a$ belonging to the plaintext are associated with occurrences $c_{1}, c_{2}$ in the ciphertext, such that $c_{1}\neq c_{2}$ with very high probability.
Our implementation closely follows a class lecture given by Prof. Orazio Puglisi within Cryptography course at the University of Florence. In order to fully understand the last part, where the concept of mutual coincidence index is crucial, we rest on the explanation at pag. 20 of this notes.
End of explanation
def make_alphabet_entry(i):
    alpha = i + ord('a')
    return chr(alpha),i
A = dict(map(make_alphabet_entry, range(26)))
A.update({' ':26})
inverse_A = {v:k for k,v in A.items()}
A
Explanation: alphabet
Let $\mathcal{A}$ be our alphabet composed of standard English characters plus the space character. It will be sufficient to encode simple and (not so quite) short messages. To define it as a group $\frac{\mathbb{Z}}{n\mathbb{Z}}$ in the Python language we use a dict object, which can be reversed because it is a bijection.
End of explanation
def encode(s, alphabet=A): return list(map(lambda i: alphabet[i], s))
def decode(e, inverse_alphabet=inverse_A): return "".join(map(lambda i: inverse_alphabet[i], e))
Explanation: string encoding and the plaintext
We define a function encode that consumes a string and produces a list of integer in our field. In parallel, function decode goes backwards, it consumes a list of integers and return a string. Such functions are useful in order to use the cipher and analyze it using str objects instead of the coded version using lists of integers.
End of explanation
def clean_text(text):
    remove_chars = [',', '.', ';', ':', '-', '(', ')', "'", '"']
    for rc in remove_chars: text = text.replace(rc, '')
    text = text.replace('\n', ' ')
    return "".join(filter(lambda c: not c.isdigit(), text))
with open('rest_plain_text.txt', 'r') as f:
    plain_text = clean_text(f.read().lower())
    
encoded_plain_text = encode(plain_text)
chunk = 500
"{}...".format(plain_text[:chunk])
Explanation: The following plaintext is a prose taken from here; before using it we have to swipe out punctuation marks:
End of explanation
assert decode(encode(plain_text)) == plain_text
Explanation: With the following assert we ensure that function decode is the inverse of function encode:
End of explanation
def generate_random_key(given_key=None, required_length=None, max_length=None, alphabet=A):
    
    if given_key is not None: return given_key
    
    if required_length is None and max_length is None: max_length = len(alphabet)
    
    # the minimum length of the key is 3 to build interesting cases
    length = required_length if required_length else randint(3, max_length)
    key = [0] * length
    # -1 in the following max limit because it is inclusive in the sense of `randint`.
    for i in range(length): 
        key[i] = randint(0, len(alphabet)-1)
    return key
#key = encode("ericsmullyan")
secret_key = generate_random_key(required_length=17)
Explanation: key
Let $\textbf{k}=(k_{0},\ldots,k_{m-1}) \in \left(\frac{\mathbb{Z}}{n\mathbb{Z}}\right)^{m}$ be a key of length $m\in\mathbb{N}$. In order to have a meaningful analysis we build a function generate_random_key which generate a random key of random length, keeping it safe...we will uncover it only at the end to check our work:
End of explanation
def encrypt(message, key, alphabet=A):
    n = len(alphabet)
    return [(p+v)%n for p,v in zip(message, cycle(key))]
def decrypt(cipher, key, alphabet=A):
    n = len(alphabet)
    return [(c-v)%n for c,v in zip(cipher, cycle(key))]
Explanation: encryption and the ciphertext
Now we are in the position to define encrypt and decrypt functions, both of them consumes an encoded message, namely a list of integers, and a key. The encryption work by repeating the key as long as necessary to match the same length of the input $\textbf{x}=(x_{0},\ldots,x_{h})$, where $h > m-1$ otherwise the cipher is a OneTimePad which is unbreakable, 
$$(\underbrace{x_{0},\ldots,x_{m-1}}{k{0},\ldots,k_{m-1}}
\underbrace{x_{m},\ldots,x_{m-1}}{k{0},\ldots,k_{m-1}}
\ldots
\underbrace{x_{lm},\ldots,x_{h}}{k{0},\ldots,k_{h \mod m}}) = 
(y_{0},\ldots,y_{h}) = \textbf{y}$$
truncating the very right block to match plaintext suffix. At last, the ciphertext $\textbf{y}$ is obtained by addition modulo $n$ of corresponding symbols, where $n$ is the length of the alphabet. Decryption follows the same scheme, using modular subtraction.
End of explanation
cipher_text = encrypt(encoded_plain_text, secret_key)
'{}...'.format(decode(cipher_text)[:chunk])
Explanation: the following is the ciphertext produced by the application of function encrypt to the plaintext:
End of explanation
assert decode(decrypt(cipher_text, secret_key)) == plain_text
Explanation: Assuming to know the secret_key, we ensure that function decrypt is the inverse of function encrypt:
End of explanation
def frequencies(lst, alphabet=A, inverse_alphabet=inverse_A):
     Produces a `dict` counting occcurrences of each object of the alphabet within the iterable.
    
    `frequencies` consumes an iterable $lst$ and an alphabet $A$, 
    produces a dictionary of entries $(k,v)$ where $k$ is a character 
    in $A$ and $v$ is the number of occurrences of $k$ in $lst$
    
    counter = Counter(lst)
    return {k:counter[v] for k,v in alphabet.items()} # Counter handles the case of missing key returning 0
    
def length_from_frequencies(freqs):
     Returns the length of the original sequence by summation of symbols frequencies. 
    return sum(freqs.values())
def coincidence_index(freqs, alphabet=A):
     Produces the I_{c} relative to frequencies matched against an alphabet. 
    denom = length_from_frequencies(freqs)
    if denom in range(2): return None
    def mapper(a):
        v = freqs[a] if a in freqs else 0
        return v*(v-1)
    return sum(map(mapper, alphabet.keys()))/(denom*(denom-1))
def draw_frequencies_histogram(seq, alphabet=A, y_maxlimit=None, normed=None):
    
    #plaintext_length = len(plain_text)
    #freqs = [plaintext_frequencies[inverse_A[ia]] for ia in sorted(inverse_A.keys())]
    n, bins, patches = plt.hist(seq, len(alphabet),facecolor='green', alpha=0.5)
    plt.xlabel('alphabet symbols')
    plt.ylabel('frequencies' + (', normed respect: {}'.format(str(normed)) if normed else ''))
    #plt.xticks(range(-1, len(alphabet)), sorted(alphabet.keys()))
    if y_maxlimit: plt.ylim([0, y_maxlimit])
    plt.grid(True)
    plt.show()
    
    return None
Explanation: coincidence index
Let $I_{c}$ be the coincidence index of a sequence $\alpha$, over an alphabet $A$, defined as 
$$ I_{c}(\alpha) = \sum_{i=0}^{n}{\frac{f_{a_{i}}^{(\alpha)}(f_{a_{i}}^{(\alpha)}-1)}{m(m-1)}} $$ where $n$ is the length of the alphabet, $m$ is the length of $\alpha$ and $f_{a_{i}}^{^{(\alpha)}}$ is the frequency of symbol $a_{i}\in A$, namely the number of occurrences of $a_{i}$, in $\alpha$. In other words, $I_{c}$ is the probability to sample two occurrences of the same symbol $a$, forall $a\in A$, from the sequence $\alpha$. 
Index $I_{c}$ is invariant to shifting by the same constant $v$. Let $\alpha,\beta$ be two sequences of integers of length $l$ such that $\beta_{i} \equiv_{n} \alpha_{i} + v$, forall $i\in\lbrace0,\ldots,l\rbrace$; moreover, let $q_{\gamma_{i}}^{(\gamma)}$ be the probability to sample two occurrences of $\gamma_{i}$ from a sequence $\gamma$, we can state the relations
$$
    I_{c}(\beta) = \sum_{a_{i}\in\frac{\mathbb{Z}}{n\mathbb{Z}}}{q_{a_{i}}^{(\beta)}}
                = \sum_{a_{i}\in\frac{\mathbb{Z}}{n\mathbb{Z}}}{q_{a_{i}-v}^{(\alpha)}}
                = \sum_{\hat{a}{i}\in\frac{\mathbb{Z}}{n\mathbb{Z}}}{q{\hat{a}{i}}^{(\alpha)}}
                = I{c}(\alpha)
$$
where $\hat{a}{i}\equiv{n}a_{i}-v$, proving the invariance of $I_{c}$ when a sequence is produced by another one shifted by a constant $v\in\frac{\mathbb{Z}}{n\mathbb{Z}}$.
End of explanation
plaintext_frequencies = frequencies(encoded_plain_text)
draw_frequencies_histogram(encoded_plain_text, y_maxlimit=1800)
plaintext_frequencies
Explanation: frequencies comparison
The following are frequencies of alphabet symbols in the plaintext: in the analysis they are used as a dict produced by function frequencies, moreover it is possible to draw an histogram with the relative function.
End of explanation
draw_frequencies_histogram(cipher_text, y_maxlimit=1800)
Explanation: The following histogram shows frequencies in the ciphertext: using the same y_maxlimit value, we see that they are spread "uniformly" over symbols.
End of explanation
print("coincidence index of *plaintext*: {}\ncoincidence index of *ciphertext*: {}".format(
        coincidence_index(plaintext_frequencies), coincidence_index(frequencies(cipher_text))))
Explanation: A first approach to encryption finishes computing the coincidence indexes of both plaintext and ciphertext:
End of explanation
def spread(message, block_length):
    return [message[i:i+block_length] for i in range(0, len(message), block_length)]
    
def col(spreaded, c, join=False, joiner=lambda c: ''.join(decode(c))):
    column = [lst[c] if c < len(lst) else None for lst in spreaded]
    ready = list(filter(lambda i: i is not None, column))
    return joiner(ready) if join else ready
def decode_spreaded(spreaded, join_as_str=False):
    decoded_spread = list(map(decode, spreaded))
    return '\n'.join(decoded_spread) if join_as_str else decoded_spread
def analyze(cipher_text, max_key_length=None):
    res = {}
    # we discard the case where the key length equals the
    # length of the cipher text, since it is the case of 
    # OneTimePad cipher, which is unbreakable!
    for d in range(2, len(cipher_text) if max_key_length is None else max_key_length + 1):
        spreaded = spread(cipher_text, d)
        res[d] = []
        for c in range(d):
            ci = coincidence_index(frequencies(col(spreaded, c)))
            if ci: res[d].append(ci)
                
    return res
def guess_key_length(analysis, threshold=0.06):
    candidates = {}
    for k,v in analysis.items():
        cs = list(filter(lambda i: i > threshold, v))
        if cs and len(cs) > ceiling(k/2): candidates[k] = cs
    return candidates
Explanation: finding the key length by spreading
The following set of functions allows us to probe the key length by repeatedly fixing a candidate length $l$, then spreading the ciphertext in a matrix with $l$ columns, then computing $I_{c}$ of each column and, finally, report $l$ if the majority of $I_{c}$ scores is greater than a threshold (.06 for English).
End of explanation
analysis = analyze(cipher_text, max_key_length=20)
guess = guess_key_length(analysis)
guess
probing_key_length = 17
Explanation: here are $I_{c}$ scores witnesses for the candidate key length after spreading the ciphertext by columns:
End of explanation
spreaded = decode_spreaded(spread(cipher_text, probing_key_length))
print("{}\n...\n{}".format("\n".join(spreaded[:10]), "\n".join(spreaded[-3:])))
Explanation: The following is the ciphertext spread over a matrix with a number of column equals the candidate length found in the previous cell.
End of explanation
def mutual_coincidence_index(fst_freqs, snd_freqs, offset=0, 
                             alphabet=A, inverse_alphabet=inverse_A):
    fst_len = length_from_frequencies(fst_freqs)
    snd_len = length_from_frequencies(snd_freqs)
    n = len(alphabet)
    return sum(fst_freqs[k] * snd_freqs[inverse_alphabet[(v+offset) % n]] 
               for k,v in alphabet.items())/(fst_len * snd_len)
Explanation: mutual coincidence index
Once the length $m$ of key $\textbf{k}$ has been "established", we're left with finding actual key symbols $k_{i}$, for $i\in{0,\ldots,m-1}$. In order to fullfil this step, we need another object, which resembles the index of mutual coincidence $I_{c}$ but it is more general, in the sense that sampling occurs on two given sequences instead of the same one. Formally, let $I_{mc}(\alpha, \beta)$ be the index of mutual coincidence of sequences $\alpha$ and $\beta$, defined as
$$
I_{mc}(\alpha,\beta) = \sum_{a_{i}\in\frac{\mathbb{Z}}{n\mathbb{Z}}}{q_{a_{i}}^{(\alpha)}q_{a_{i}}^{(\beta)}}
$$
where $q_{a_{i}}^{(\nu)}$ is the probability to draw an occurrence of symbol $a_{i}$ in sequence $\nu$.
Let $\eta$ and $\gamma$ be two sequences of length $l$, produced by adding shifts $v_{\alpha}$ and $v_{\beta}$ to sequences $\alpha$ and $\beta$, respectively (formally, $\eta_{i} \equiv_{n} \alpha_{i} + v_{\alpha}$ and $\gamma_{i} \equiv_{n} \beta_{i} + v_{\beta}$, forall $i\in\lbrace0,\ldots,l-1\rbrace$). The inequality
$$
    I_{mc}(\eta,\gamma) 
                = \sum_{a_{i}\in\frac{\mathbb{Z}}{n\mathbb{Z}}}{q_{a_{i}}^{(\eta)}q_{a_{i}}^{(\gamma)}}
                = \sum_{a_{i}\in\frac{\mathbb{Z}}{n\mathbb{Z}}}{q_{a_{i}-v_{\alpha}}^{(\alpha)}q_{a_{i}-v_{\beta}}^{(\beta)}}
                = \sum_{a_{i}\in\frac{\mathbb{Z}}{n\mathbb{Z}}}{q_{a_{i}}^{(\alpha)}q_{a_{i}+v_{\alpha}-v_{\beta}}^{(\beta)}}
                \neq \sum_{a_{i}\in\frac{\mathbb{Z}}{n\mathbb{Z}}}{q_{a_{i}}^{(\alpha)}q_{a_{i}}^{(\beta)}}
                = I_{mc}(\alpha,\beta)
$$
holds unless factor $v_{\alpha}-v_{\beta}$ in each subscript. We can define an even more general version of $I_{mc}$ as
$$
    I_{mc}(\eta,\gamma,g) 
                = \sum_{a_{i}\in\frac{\mathbb{Z}}{n\mathbb{Z}}}{q_{a_{i}-g}^{(\eta)}q_{a_{i}}^{(\gamma)}}
                = \sum_{a_{i}\in\frac{\mathbb{Z}}{n\mathbb{Z}}}{q_{a_{i}}^{(\alpha)}q_{a_{i}+v_{\alpha}-v_{\beta}+g}^{(\beta)}}
$$
where sequence $\eta$ is shifted back by $g\in\mathbb{N}$. Therefore we can state the equality with the usual definition according to
$$
    I_{mc}(\eta,\gamma,g) = I_{mc}(\alpha,\beta) \leftrightarrow v_{\beta}-v_{\alpha}=g
$$
proving the invariance of $I_{mc}$ when two sequences are produced by shifting two other ones by constant values $q,w$ respectively, providing that $g = w-q$.
End of explanation
def build_offsets_eqs(cipher_text, key_length, indexed_sym, threshold=.06, alphabet=A):
    
    n = len(alphabet)
    eqs = {c:{} for c in range(key_length)}
    spreaded = spread(cipher_text, key_length)
    for c,a in itertools.product(range(key_length), repeat=2):
    
        if a == c: continue
        
        eqs[c][a]=[]
        
        for g in range(1,n):
            column_freqs = frequencies(col(spreaded, c))
            another_freqs = frequencies(col(spreaded, a))
            mci = mutual_coincidence_index(column_freqs, another_freqs, g)
            if mci > threshold: 
                eqs[c][a].append(tuple([Eq(indexed_sym[a]-indexed_sym[c],g,evaluate=True), mci]))
    
    return eqs
k_sym=IndexedBase('k')
eqs_dict = build_offsets_eqs(cipher_text, key_length=probing_key_length, indexed_sym=k_sym)
Explanation: Previous generalization allows us to set the basis to break the cipher. It works as follows: for each pair $(\eta,\gamma)$ of different columns in the spread-matrix form of the ciphertext, fix a $g\in\frac{\mathbb{Z}}{n\mathbb{Z}}$ to compute $I_{mc}(\eta,\gamma,g)$: if such index value is close to $I_{c}(\nu)$, where $\nu$ is a structured sequence using the English language, namely close to $0.065$, then collect equation $k_{i(\beta)}-k_{i(\alpha)}=g$, where function $i(\nu)$ return the zero-based index of column $\nu$ in the matrix spread. Such equations are important since state difference relations over symbols of the key.
End of explanation
eqs_dict[0]
Explanation: The following cell report the set of difference equation collected respect the first column of the spread matrix: we observe that such set fails to instantiate $k_{6}$ because no likely equation gives a relation for it. On the contrary, it can be the case that collecting equations for a pair of columns with indexes $(c,a)$ yields one or more equations, namely ${k_{a}-k_{c}=g_{u_{0}},\ldots,k_{a}-k_{c}=g_{u_{v}}}$, for some $v\in\mathbb{N}$: to properly explore all keys space, we have to consider the product of each list of "equally-likely" equations.
End of explanation
def explode_key_space(eqs_dict):
    
    res = {}
    for c, eq_dict in eqs_dict.items():
        eqs_list = []
        for a, eqs in eq_dict.items():
            if not eqs: 
                res[c] = [] # no equations in `eqs` causes the product to be empty as well
                break
            eqs_list.append([[a] + list(eq_pair) for eq_pair in eqs])
        else: # if no empty eqs was found then it is meaningful to cross product them
            res[c] = list(itertools.product(*eqs_list))
    return res
eqs_dict_pure = explode_key_space(eqs_dict)
eqs_dict_pure
print(eqs_dict_pure)
Explanation: The following function implements the last observation, namely it produces the complete keys space where we've to look for the good one.
End of explanation
def candidate_keys(eqs_dict, indexed_sym, alphabet=A):
    key_length = len(eqs_dict)
    n = len(alphabet)
    candidates=set()
    for c, eqs_tuples in eqs_dict.items():
        for d in range(len(alphabet)):
            for eq_tuple in eqs_tuples:
                key = [indexed_sym[i] for i in range(key_length)]
                key[c] = d
                for a, eq, mci in eq_tuple:
                    subs_eq = eq.subs(indexed_sym[c],d)
                    key[a] = solve(subs_eq, indexed_sym[a])[0]
                    key[a] = key[a] % n
                for k in key:
                    if isinstance(k, Indexed): break 
                else:
                    candidates.add(tuple(key)) # `tuple` application to make `key` hashable
    return candidates
possible_keys = candidate_keys(eqs_dict_pure, k_sym)
Explanation: In order to instantiate candidates keys, for each index column $c$ we use the set of equations ${k_{a}-k_{c}=g_{u}}$, for some $u\in\mathbb{N}$ and $a\in{0,\ldots,m-1}\setminus{c}$ as follows: for each equation $k_{a}-k_{c}=g_{u}$, instantiate $k_{c} = s$, for $s\in\frac{\mathbb{Z}}{n\mathbb{Z}}$, and solve it respect $k_{a}$. Therefore for each column index $c$ we have a candidate key if each symbol $k_{i}$ has been instantiated.
End of explanation
def arbitrary_frequencies(length, filename='rest_plain_text.txt'):
    with open(filename, 'r') as f:
        text = clean_text(f.read().lower())
    text = text[:length]
    return frequencies(encode(text))
def attempt_keys(candidate_keys, cipher_text, threshold=.06, arbitrary_freqs=None):
    sols = set()
    for key in candidate_keys:
        decrypted = decrypt(cipher_text, key)
        freqs = frequencies(decrypted)
        if arbitrary_freqs:
            good = True
            for k,v in arbitrary_freqs.items():
                if 1-abs((freqs[k]-v)/v) < .6: good = False
            if good: sols.add(decode(key))
        else:
            ci = coincidence_index(freqs)
            if ci > threshold: sols.add(decode(key))#sols.add((ci, decode(key)))
    return sols
sols = attempt_keys(possible_keys, cipher_text, arbitrary_freqs=arbitrary_frequencies(len(cipher_text)))
len(sols), sols
for sol in sols: 
    key = sol
    print("key:({})\nplaintext:\n{}\n\n".format(
            key, decode(decrypt(cipher_text, encode(key)))[:chunk]))
decode(secret_key)
Explanation: The last step to filter out mistaken keys, we use each candidate key to perform a decryption, checking it against frequencies of an arbitrary English prose:
End of explanation
<END_TASK>