<jupyter_start><jupyter_text>One time padIn the previous lesson we performed an attack over the Monoalphabetic cipher where the attacker (Charlie) only knew that Alice and Bob were communicating in english and that they were using this concrete cipher. Therefore the ciphertext is leaking information. Can we find a cipher whose ciphertext doesn't leak any information on the original message?. We are going to answer this question using the Vigenere cipher. Table of contents:* [Vigenere revisited](vigenere-revisited)* [Gathering plain english data](nineteen-eighty-four)* [Counting letter frequencies](counting-frequencies)* [Frequencies with short key](counting-frequencies-2)* [Frequencies with large key](counting-frequencies3)* [The One Time Pad](onetimepad)* [Why is the one time pad impractical?](impractical-onetimepad)    Author: [<NAME>](https://github.com/sebastiaagramunt) for [OpenMined](https://www.openmined.org/) Privacy ML Series course.  Vigenère cipher revisited First, lets copy paste the code for the Vingenère cipher already coded in the first notebook<jupyter_code>from copy import deepcopy
from random import randrange
import string

def vigenere_key_generator(secret_key_size: int) -> str:
    n = len(string.ascii_lowercase)
    secret_key = ''
    while len(secret_key) < secret_key_size:
        secret_key += string.ascii_lowercase[randrange(n)]
    return secret_key


def shift_letter(letter: str, shiftby: str, forward: bool=True) -> str:
    n = len(string.ascii_lowercase)
    
    letter_int = ord(letter) - 97
    shiftby_int = ord(shiftby) - 97
    
    if forward:
        return string.ascii_lowercase[(letter_int+shiftby_int)%n]
    else:
        return string.ascii_lowercase[(letter_int-shiftby_int)%n]


def vigenere_encrypt_decrypt(message: str, secret_key: str, encrypt:bool = True) -> str:
    key_len = len(secret_key)
    
    encoded = ''
    for i, letter in enumerate(message):
        if letter != " ":
            encoded += shift_letter(letter, secret_key[i%key_len], forward=encrypt)
        else:
            encoded += letter
    return encoded<jupyter_output><empty_output><jupyter_text>Downloading data from the book Nineteen Eighty Four<jupyter_code>from utils import download_data, process_load_textfile
import string
import os

url = 'http://gutenberg.net.au/ebooks01/0100021.txt'
filename = 'Nineteen-eighty-four_Orwell.txt'
download_path = '/'.join(os.getcwd().split('/')[:-1]) + '/data/'

#download data to specified path
download_data(url, filename, download_path)

#load data and process
data = process_load_textfile(filename, download_path)<jupyter_output><empty_output><jupyter_text>Have a look at the data<jupyter_code>data[10000:11000]<jupyter_output><empty_output><jupyter_text>Counting letter frequencies First we write a function to count the frequency of the letters for a given text and outputs a sorted tuple with the letter and the counts of that letter<jupyter_code>from typing import List, Tuple
from collections import Counter

def letter_count(text: str) -> List[Tuple[str, int]]:
    text2 = text.replace(" ", "")
    letters = [c for c in text2]
    return Counter(letters).most_common()<jupyter_output><empty_output><jupyter_text>And calculate the frequency for the book nineteen eighty four<jupyter_code>freq = letter_count(data)
freq<jupyter_output><empty_output><jupyter_text>And let's write a function that gives a bar plot for the frequencies:<jupyter_code>import matplotlib.pyplot as plt

def freq_plotter(text: str, title: str) -> plt.figure:
    plt.clf()
    freq = letter_count(text)
    names = [x[0] for x in freq]
    values = [x[1] for x in freq]

    fig = plt.figure(figsize=(16,7))

    plt.bar(names, values)
    plt.title(title)
    return fig
fig = freq_plotter(data, "Frequencies of letters for Nineteen Eighty Four")<jupyter_output><empty_output><jupyter_text>And finally let's code another nice utility, a function that randomly draws a random portion of the text<jupyter_code>from random import randrange, seed

def draw_sample(text: str, size: int) -> str:
    n = len(text)
    i_init = randrange(n)
    i_final = i_init + size
    
    c = ''
    for i in range(i_init, i_final):
        c += text[i%n]
    return c
seed(3)
draw_sample(data, 100)<jupyter_output><empty_output><jupyter_text>Counting frequencies with short key Now let's count the frequency in the ciphertext for a randomly sampled text from the book. Let's begin with the shift cipher (i.e. Vigenere with key size 1)<jupyter_code>seed(10)
message_size = len(data)//4
secret_key_size = 1
print(f"message_size = {message_size}\nsecret_key_size = {secret_key_size}")

# generating random message
message = draw_sample(data, message_size)

# generating secret key
secret_key = vigenere_key_generator(secret_key_size)

# calculating ciphertext that Alice sends to Bob
ciphertext = vigenere_encrypt_decrypt(message, secret_key, encrypt=True)

# just to make sure Vigenere is well coded
assert message==vigenere_encrypt_decrypt(ciphertext, secret_key, encrypt=False), "something went wrong"
fig = freq_plotter(ciphertext, f"Frequencies for ciphertext size {message_size} and key size {secret_key_size}")<jupyter_output><empty_output><jupyter_text>We observe that the frequencies of the letters are not the same, and therefore if the attacker knows Alice and Bob communicate in english he will probably be able to say that the shift is 1, i.e. the secret key is "b" because the most frequent letter in english is "e" and that corresponds to the peak in "f", therefore the shift is of one position. Here we can extract information from the ciphertext.  Counting frequencies with large key Instead of having a short key, let's take a super long key, actually the size of our message:<jupyter_code>seed(10)
message_size = len(data)//4
secret_key_size = message_size
print(f"message_size = {message_size}\nsecret_key_size = {secret_key_size}")

# generating random message
message = draw_sample(data, message_size)

# generating secret key
secret_key = vigenere_key_generator(secret_key_size)

# calculating ciphertext that Alice sends to Bob
ciphertext = vigenere_encrypt_decrypt(message, secret_key, encrypt=True)

# just to make sure Vigenere is well coded
assert message==vigenere_encrypt_decrypt(ciphertext, secret_key, encrypt=False), "something went wrong"
fig = freq_plotter(ciphertext, f"Frequencies for ciphertext size {message_size} and key size {secret_key_size}")<jupyter_output><empty_output><jupyter_text>Great!. The attacker computes the frequency of the letters in the ciphertext and determines that the probability for each letter to appear is almost the same. In this context we can say that the ciphertext does not contain any information from the original message.  The one time pad Let's have a deeper look on what we've done in the previous section. First let's see what is the frequency for each letter when randomly generating the key<jupyter_code>rdm_secret_keys = [vigenere_key_generator(secret_key_size=1) for _ in range(15000)]
count = Counter(rdm_secret_keys)
count.most_common()<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.08329815674686929, 'fraction_numerical': 0.007316729984522302, 'mean_word_length': 5.352100089365505, 'pattern_counts': {'":': 1, '<': 43, '<?xml version=': 0, '>': 48, 'https://': 2, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 7, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '10', 'dir': 'jupyter-structured-clean-dedup', 'id': '23086', 'license': 'MIT', 'n_tokens_mistral': 2246, 'n_tokens_neox': 2149, 'n_words': 726, 'path': 'Foundations_of_Private_Computation/Cryptography_cipher_basics/notebooks/The_One_Time_Pad.ipynb', 'repo_name': 'gonzalo-munillag/Private_AI_OpenMined', 'size': '7123'}