#!/usr/bin/python3
# For simplicity, we fix domain and range of PRGs here:
# The domain is the set of 32-bit integers
# The random is the set of ten-element lists of 32-bit integers
# (equivalent to 320-bit integers)
import random
# A very bad pseudo-random generator
# Seed is supposed to be a 32-bit integer
# Output is a ten element list of 32-bit integers
def G(seed):
return [4267243**i*seed % 2**32 for i in range(1,11)]
# The game: it gets a prg and an adversary as arguments
def prg_game(G,adv):
b = random.randint(0,1) # Random bit
seed = random.randint(0,2**32-1) # Random seed
rand = [random.randint(0,2**32-1) for i in range(10)] # Truly random output
if b==0: badv = adv(G(seed))
else: badv = adv(rand)
return b==badv
def adv(rand):
if rand[1]==4267243*rand[0] % 2**32: return 0
else: return 1
def test_prg(G,adv):
num_true = 0
num_tries = 100000
for i in range(num_tries):
if prg_game(G,adv): num_true += 1
ratio = float(num_true)/num_tries
print(ratio)
# An output near 0.5 means no attack
# An output neat 0.0 or 1.0 means a successful attack
test_prg(G,adv)