<jupyter_start><jupyter_text>Table of contents:* [Pseudorandom number generators](prng)* [Linear congruential generators](lcg)* [Building a psedodrandom number generator](prng2)* [Better ways to generate pseudorandom numbers](randnumb)* [The quest for the perfect random generator](perfectr)    Author: [<NAME>](https://github.com/sebastiaagramunt) for [OpenMined](https://www.openmined.org/) Privacy ML Series course.  Pseudorandom number generators In this section we will learn how to create "random" numbers using a computer. Why do we even need to generate random numbers in the context of cryptography?. Actually we constantly use random numbers in cryptography, e.g. to generate a completely random secret key. There's a quest in cryptography to generate purely random numbers. First, let's take inspiration from the one time pad to see why one would need random numbers<jupyter_code>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
message = "helloworld"
secret_key = vigenere_key_generator(len(message))
ciphertext = vigenere_encrypt_decrypt(message, secret_key, encrypt=True)

print(f"message = {message}\nsecret_key = {secret_key}\nciphertext = {ciphertext}")<jupyter_output>message = helloworld
secret_key = bdvdhclaby
ciphertext = ihgovyzrmb<jupyter_text>The one time pad in bits:<jupyter_code>from random import randrange

message = "01011101000101110101"
secret_key = ''.join([str(randrange(2)) for _ in range(len(message))])
ciphertext = ''.join([str((int(m)+int(s))%2) for m, s in zip(message, secret_key)])
print(f"message:\n\t{message}")
print(f"secret_key\n\t{secret_key}")
print(f"ciphertext\n\t{ciphertext}")<jupyter_output>message:
	01011101000101110101
secret_key
	01100000001111010011
ciphertext
	00111101001010100110<jupyter_text>If the secret_key is a sequence known by Alice and Bob and generated completely random, then the cryptosystem is perfectly secret. Problems for one time pad?* key lenght has to be at least the same as message lenght* the key has to be completely random * Alice and Bob have to meet each time to exchange the secret keyLet's design a system very close to pure random: Linear congruential generators A linear congruential generator (LCG) is an algorithm that yields a sequence of pseudo-randomized numbers calculated with a discontinuous piecewise linear equation.$$X_{n+1}=X_n*a+c \textrm{ (mod m)}$$.There are several LCGs, in the example we take the one of numerical recipes correspoding to the values: a = 1664525, c = 1013904223 and m = $2^{32}$. The initial value $X_0$ is called the seed of the pseudoradom generator.<jupyter_code>a = 1664525
c = 1013904223
m = 2**32

def lcg(x0: int, a: int, c: int, m: int) -> int:
    return (x0*a+c)%m
x0 = 433

l = []

xn = x0
for _ in range(100000):
    xn = lcg(xn, a, c, m)
    l.append(xn/m)
import matplotlib.pyplot as plt

plt.clf()
fig = plt.figure(figsize=(16,7))
plt.hist(l, bins=50)
plt.show()<jupyter_output><empty_output><jupyter_text>The good thing about pseudorandom generators is that you can reconstruct the pseudorandom numbers taking the same initial seed<jupyter_code>x0 = 53

xn = x0
for _ in range(10):
    xn = lcg(xn, a, c, m)
    print(xn)
x0 = 53

xn = x0
for _ in range(10):
    xn = lcg(xn, a, c, m)
    print(xn)<jupyter_output>1102124048
368793647
468461506
2704688185
3035635780
1075818195
810411542
842425981
2017260984
2691087799<jupyter_text>This can be useful!. Alice and Bob can generate the same randomness if they keep the seed as a secret!. The secret is the Diffie-Hellman key they generated. Building PRNG function We will use the common function ```randrange``` from random to create a binary pseudorandom generator.<jupyter_code>from random import seed

def PRNG(s: int, l: int) -> list:
    seed(s)
    
    prng = []
    while len(prng) < l:
        prng.append(randrange(2))
    return ''.join([str(n) for n in prng])
s = 134323

# Alice's end
prng_alice = PRNG(s, 10)

# Bob's end
prng_bob = PRNG(s, 10)

print(prng_alice)
print(prng_bob)<jupyter_output>0110011011
0110011011<jupyter_text>Better ways to generate random numbers in the computer Our PRNG uses a seed as the source for the entropy for the random numbers. We can use **other seeds like environmental computer noise** (frequency of typing, temperature variation...).  Using your system ```/dev/urandom```, e.g generate 10 random bytes (using MacOS). Open a terminal and run:```head -c 10 /dev/urandom```to see the output.<jupyter_code># calling the urandom function
import subprocess
# 10 are the bytes
command = "head -c 10 /dev/urandom"
process = subprocess.Popen(command.split(), stdout=subprocess.PIPE)
output, error = process.communicate()

print(f"Random bytes:\n\t{output}")
# transform to integer bytes
int_bytes = [b for b in output]

print(f"Random bytes:\n\t{output}\nconverted integers:\n\t{int_bytes}")
# transform to integer
int.from_bytes(output, "big")<jupyter_output><empty_output><jupyter_text>With the system random we can generate random bits of information. For instance:<jupyter_code># using secrets to acess the sytem random
import secrets

r = secrets.SystemRandom()
# It allows you to add a seed on top of the random values samplede from your computer environment
r.seed(23123)
bin(r.getrandbits(512))[2:]<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.09937187952971493, 'fraction_numerical': 0.04880012884522467, 'mean_word_length': 4.869565217391305, 'pattern_counts': {'":': 1, '<': 28, '<?xml version=': 0, '>': 31, 'https://': 2, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 1, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '7', 'dir': 'jupyter-structured-clean-dedup', 'id': '317180', 'license': 'MIT', 'n_tokens_mistral': 2253, 'n_tokens_neox': 2008, 'n_words': 672, 'path': 'Foundations_of_Private_Computation/Practical cryptography/notebooks/Pseudorandom_Generators.ipynb', 'repo_name': 'gonzalo-munillag/Private_AI_OpenMined', 'size': '6225'}