Random Sequence Ⅱ

SP800-22

SP800-22 is a document released by the National Institute of Standards and Technology (NIST) in the United States. Specifically, it is a part of "A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications." The document describes a set of statistical test suites used to evaluate the randomness and pseudorandomness of generators, ensuring they meet the requirements for cryptographic applications.

The SP800-22 test suite includes a series of independent tests designed to assess the performance of generators. Here are some of these tests:

  1. Frequency (Monobit) Test: Checks whether the frequency of 0s and 1s in the bitstream is roughly equal.

  2. Frequency Test within a Block: Examines the frequency of 0s and 1s within fixed-size blocks of the bitstream.

  3. Runs Test: Tests the distribution of consecutive sequences (runs) of "1s" and "0s" in the bitstream.

  4. Longest Run of Ones in a Block Test: Examines the distribution of the longest sequence of "1s" within blocks.

  5. Binary Matrix Rank Test: Evaluates the generated bitstream by checking the matrix rank.

  6. Discrete Fourier Transform (Spectral) Test: Examines the spectral distribution by performing a Fourier transform on the bitstream.

  7. Non-overlapping Template Matching Test: Checks if the bitstream contains predefined templates of fixed size.

  8. Overlapping Template Matching Test: Similar to the previous test but allows overlapping between templates.

  9. Maurer's Universal Statistical Test: Evaluates based on the compressibility of the bitstream.

  10. Linear Complexity Test: Assesses performance by checking the linear complexity of the bitstream.

  11. Serial Test: Examines the distribution of adjacent bit pairs in the bitstream.

  12. Approximate Entropy Test: Evaluates by calculating the approximate entropy of the bitstream.

  13. Cumulative Sums (Cusum) Test: Checks the distribution of cumulative sums sequences in the bitstream.

  14. Random Excursions Test: Examines the random excursions in the bitstream.

  15. Random Excursions Variant Test: Similar to the previous test but includes some variants.

These tests collectively provide a method to assess the randomness and pseudorandomness of generators, ensuring they can offer sufficient security in cryptographic applications. Generators meeting the standards of these tests can be considered compliant with specific security standards.

Frequency test

Let's start with the Frequency Test.

The Frequency Test is a fundamental test in the SP800-22 test suite, commonly referred to as the Monobit test. The goal of this test is to check whether the frequencies of 0s and 1s in the generated bitstream are roughly equal. This is a simple yet crucial test because in a truly random bitstream, the occurrences of 0s and 1s should be approximately equal. If a generator fails this test, it may indicate that its output is not sufficiently random.

Here are the steps and principles of the Frequency Test:

Steps:

  1. Generate a bitstream: Use the pseudorandom number generator (or random number generator) to produce a sequence of bits.

  2. Count 0s and 1s: Count the number of 0s and 1s in the generated bitstream.

  3. Calculate frequencies: Compute the frequencies of 0s and 1s, representing their relative occurrences in the bitstream.

  4. Compare frequencies: Check whether the calculated frequencies are within a reasonable range, typically expecting them to be close to 50%.

Principles: The core idea behind the Frequency Test is that, in an ideal random bitstream, the occurrences of 0s and 1s should be equally probable. Therefore, if the generated bitstream deviates statistically from this expectation, it may suggest that the generator's output is not sufficiently random.

Specific statistical tests may involve the use of theoretical probability distributions, such as the binomial distribution. Typically, statistical hypothesis testing methods are employed, such as calculating p-values, to determine whether the generated bitstream passes the Frequency Test. If the p-value is less than a predetermined significance level, there is reason to reject the hypothesis that the generator's output is random.

In summary, the Frequency Test is a foundational assessment to verify if the generator's output possesses basic random properties. However, it does not cover all possible issues related to randomness. Therefore, SP800-22 includes other more complex tests to comprehensively evaluate the performance of the generator.

def frequency_test(binary_sequence):
    if not all(bit in {0, 1} for bit in binary_sequence):
        raise ValueError("Binary sequence should only contain 0s and 1s")

    n = len(binary_sequence)
    count_ones = binary_sequence.count(1)
    count_zeros = n - count_ones

    expected_frequency = n / 2  # Expected frequency of 0s and 1s is equal in a truly random sequence

    # Calculate the difference in frequencies
    difference = abs(count_ones - expected_frequency)

    # Allowing for a certain margin of error, set here as 10% of the total length
    return difference <= 0.1 * n  

# Generate a binary random sequence
import random

random_binary_sequence = [random.randint(0, 1) for _ in range(1000)]

# Perform the Frequency Test
result = frequency_test(random_binary_sequence)

# Print the result
print("Frequency Test Result:", result)

This code implements a simple Monobit Test function and tests it on a binary random sequence of length 1000:

  1. def frequency_test(binary_sequence): - Defines a function named frequency_test that takes a binary sequence as a parameter.

  2. if not all(bit in {0, 1} for bit in binary_sequence): - Checks if the input sequence contains only 0s and 1s; raises a ValueError if other values are present.

  3. n = len(binary_sequence): - Retrieves the length of the binary sequence.

  4. count_ones = binary_sequence.count(1): - Counts the occurrences of 1 in the binary sequence.

  5. count_zeros = n - count_ones: - Calculates the number of 0s by subtracting the count of 1s from the total length.

  6. expected_frequency = n / 2: - Computes the expected frequency of 0s and 1s in a truly random sequence.

  7. difference = abs(count_ones - expected_frequency): - Calculates the absolute difference between the count of 1s and the expected frequency.

  8. return difference <= 0.1 * n: - Determines if the difference is within an allowable error range (set to 10% of the total length). The function returns a boolean indicating whether the frequency test passes.

  9. random_binary_sequence = [random.randint(0, 1) for _ in range(1000)]: - Generates a random binary sequence of length 1000 using list comprehension.

  10. result = frequency_test(random_binary_sequence): - Calls the frequency_test function to perform the frequency test on the random sequence and stores the result.

  11. print("Frequency Test Result:", result): - Prints the result of the frequency test. If the result is True, the test passed; if False, the test did not pass.

Runs test

Runs Test, also known as the Monobit Run Test, is a statistical test within the SP800-22 test suite. The objective of this test is to examine the distribution of consecutive sequences of "1" and "0" (also known as runs or runs) in the generated bitstream to assess its randomness.

Steps:

  1. Generate the bitstream: Use the pseudo-random number generator (or random number generator) under test to create a sequence of bits.

  2. Mark the runs: Identify consecutive sequences of "1" or "0" in the generated bitstream as runs. For example, if the bitstream is 11010011101110, there are five runs: 11, 0, 1, 000, 111.

  3. Calculate the number of runs: Determine the total number of runs in the bitstream.

  4. Calculate the expected number of runs: Based on theoretical expectations, calculate the average number of runs expected to occur in an ideal random bitstream. For a uniformly distributed bitstream, the expected number of runs can be calculated using the following formula:

  1. Compare Actual and Expected: Check whether the actual number of runs falls within a reasonable range of the expected number. Typically, statistical hypothesis testing methods, such as calculating p-values, can be employed to determine if the generated bitstream passes the runs test.

Principle: The Runs Test is based on the assumption that in an ideal random bitstream, the distribution of run lengths (consecutive sequences of 1s or 0s) is uniform. Therefore, by comparing the actual number of runs with the expected number of runs, one can assess whether the generated bitstream exhibits sufficient randomness.

In runs testing, if the actual number of runs deviates from the expected, it may suggest that the output of the generator lacks randomness to some extent. This test helps detect repeating patterns or irregularities in the generator output, which could compromise the security of cryptographic applications.

In summary, the Runs Test is a crucial test within the SP800-22 test suite for evaluating the randomness of generator output. However, a comprehensive assessment of generator performance often requires conducting multiple tests of different types.

def run_test(binary_sequence):
    # Check if the binary sequence contains only 0s and 1s
    if not all(bit in {0, 1} for bit in binary_sequence):
        raise ValueError("Binary sequence should only contain 0s and 1s")

    n = len(binary_sequence)
    count_ones = binary_sequence.count(1)
    count_zeros = n - count_ones

    # Calculate the run count for 0s and 1s
    run_count_zeros = calculate_run_count(binary_sequence, 0)
    run_count_ones = calculate_run_count(binary_sequence, 1)

    # Calculate the expected run count
    expected_run_count_zeros = 1 + 2 * (n - count_zeros) / n
    expected_run_count_ones = 1 + 2 * (n - count_ones) / n

    # Check if the actual run count is within the expected range
    result_zeros = abs(run_count_zeros - expected_run_count_zeros) <= 3 * (n ** 0.5)
    result_ones = abs(run_count_ones - expected_run_count_ones) <= 3 * (n ** 0.5)

    return result_zeros, result_ones

def calculate_run_count(binary_sequence, target_bit):
    run_count = 0
    for bit in binary_sequence:
        if bit == target_bit:
            run_count += 1
        else:
            break
    return run_count

# Generate a random binary sequence
import random
random_binary_sequence = [random.randint(0, 1) for _ in range(1000)]

# Perform the runs test
result_zeros, result_ones = run_test(random_binary_sequence)

# Print the results
print("Run Test Result (Zeros):", result_zeros)
print("Run Test Result (Ones):", result_ones)

This code implements a Runs Test function and tests it on a binary random sequence of length 1000. The Runs Test is used to examine the distribution of consecutive sequences (runs) of "1" and "0" in the generated bitstream to assess its randomness.

  1. def run_test(binary_sequence): - Defines a function named run_test that takes a binary sequence as a parameter.

  2. if not all(bit in {0, 1} for bit in binary_sequence): - Checks if the input sequence contains only 0s and 1s; raises a ValueError if other values are present.

  3. n = len(binary_sequence): - Retrieves the length of the binary sequence.

  4. count_ones = binary_sequence.count(1): - Counts the occurrences of 1 in the binary sequence.

  5. count_zeros = n - count_ones: - Calculates the number of 0s by subtracting the count of 1s from the total length.

  6. run_count_zeros = calculate_run_count(binary_sequence, 0): - Calculates the run count for 0s by calling the calculate_run_count function.

  7. run_count_ones = calculate_run_count(binary_sequence, 1): - Calculates the run count for 1s by calling the calculate_run_count function.

  8. expected_run_count_zeros = 1 + 2 * (n - count_zeros) / n: - Calculates the expected run count for 0s.

  9. expected_run_count_ones = 1 + 2 * (n - count_ones) / n: - Calculates the expected run count for 1s.

  10. result_zeros = abs(run_count_zeros - expected_run_count_zeros) <= 3 * (n ** 0.5): - Checks if the actual run count for 0s is within the expected range, using a specified error range (set to 3 times the square root of the total length).

  11. result_ones = abs(run_count_ones - expected_run_count_ones) <= 3 * (n ** 0.5): - Checks if the actual run count for 1s is within the expected range, using the same error range.

  12. return result_zeros, result_ones: - Returns two boolean values, indicating whether the runs test for 0s and 1s passes.

  13. def calculate_run_count(binary_sequence, target_bit): - Defines a helper function named calculate_run_count for calculating the run count of a specified bit.

  14. for bit in binary_sequence: - Iterates through each bit in the binary sequence.

  15. if bit == target_bit: - If the current bit is equal to the target bit (0 or 1), increment the run count.

  16. else: - If the current bit is not equal to the target bit, indicating the end of a run, exit the loop.

  17. return run_count: - Returns the calculated run count.

  18. random_binary_sequence = [random.randint(0, 1) for _ in range(1000)]: - Generates a random binary sequence of length 1000 using list comprehension.

  19. result_zeros, result_ones = run_test(random_binary_sequence): - Calls the run_test function for the runs test and stores the results in result_zeros and result_ones variables.

  20. print("Run Test Result (Zeros):", result_zeros): - Prints the result of the runs test for 0s.

  21. print("Run Test Result (Ones):", result_ones): - Prints the result of the runs test for 1s.

Maurer's Universal Statistical Test

Maurer's Universal Statistical Test is one of the tests in the SP800-22 test suite, designed to assess the performance of a generator by examining the compressibility of a bitstream. Proposed by Ueli M. Maurer in 1992, this test aims to determine whether the output of a generator can be effectively compressed.

Steps:

  1. Generate the bitstream: Use the pseudo-random number generator (or random number generator) under test to create a sequence of bits.

  2. Split the bitstream: Divide the generated bitstream into multiple non-overlapping blocks.

  3. Calculate compression ratio: Compress each block and calculate the compression ratio for each block, i.e., the ratio of the original block length to the compressed block length.

  4. Calculate average compression ratio: Compute the average compression ratio for all blocks.

  5. Calculate p-value: Based on the theoretical expectation, calculate the p-value for the average compression ratio to determine if the actual compression ratio falls within the range of randomness.

Principle: The core idea behind Maurer's Universal Statistical Test is that an ideal random bitstream should be resistant to effective compression. Therefore, if the output of a generator can be significantly compressed, it may indicate the presence of predictable patterns or structures in the output, diminishing its randomness.

The calculation of compression ratio typically involves the use of general-purpose lossless compression algorithms, such as the Lempel-Ziv compression algorithm. The theoretical expectation is based on the length of the bitstream and the inherent incompressibility of blocks in an ideal random bitstream.

For each block, Maurer's test employs the χ² (chi-squared) statistic to compare the actual compression ratio with the expected compression ratio. By computing the average χ² value for all blocks, a p-value is obtained to determine whether the generated bitstream passes Maurer's Universal Statistical Test.

Maurer's Universal Statistical Test is a more advanced test as it involves both compression algorithms and statistical analysis, aiming to detect more complex patterns in the generator output. Through this test, a more comprehensive evaluation of the generator's performance can be achieved, particularly when conducting deeper analyses of the generator output. If the generator's output can be easily compressed, it may indicate the presence of defects or structures that warrant further investigation.

import math

def maurer_universal_test(binary_sequence, block_size):
    # Check if the binary sequence contains only 0s and 1s
    if not all(bit in {0, 1} for bit in binary_sequence):
        raise ValueError("Binary sequence should only contain 0s and 1s")

    n = len(binary_sequence)
    L = int(math.ceil(n / block_size))

    # Check if the sequence is too short for the chosen block size
    if L < 5 * (2 ** block_size) / 3:
        raise ValueError("Sequence is too short for the chosen block size")

    # Compress the binary sequence using the specified block size
    compressed_sequence = compress_sequence(binary_sequence, block_size)
    compressed_length = len(compressed_sequence)

    # Check if the compressed length is less than or equal to 0.5 * n * log2(n)
    if compressed_length <= 0.5 * n * math.log2(n):
        return True
    else:
        return False

def compress_sequence(binary_sequence, block_size):
    n = len(binary_sequence)
    L = int(math.ceil(n / block_size))
    
    compressed_sequence = []
    for i in range(L):
        block = binary_sequence[i * block_size : (i + 1) * block_size]
        decimal_value = int("".join(map(str, block)), 2)
        compressed_sequence.append(decimal_value)

    return compressed_sequence

# Generate a random binary sequence
import random
random_binary_sequence = [random.randint(0, 1) for _ in range(1000)]

# Perform the Maurer Universal Statistical Test
block_size = 4
result = maurer_universal_test(random_binary_sequence, block_size)

# Print the result
print("Maurer Universal Statistical Test Result:", result)

This code implements Maurer's Universal Statistical Test, which is used to assess the randomness of a binary sequence:

  1. import math: Import the math module for mathematical calculations.

  2. def maurer_universal_test(binary_sequence, block_size): Define the function for Maurer's Universal Statistical Test, taking a binary sequence and block size as parameters.

  3. if not all(bit in {0, 1} for bit in binary_sequence): Check if the input sequence contains only 0s and 1s; raise a ValueError if other values are present.

  4. n = len(binary_sequence): Get the length of the binary sequence.

  5. L = int(math.ceil(n / block_size)): Calculate the number of blocks, using math.ceil to ensure rounding up.

  6. if L < 5 * (2 ** block_size) / 3: If the sequence is too short for the chosen block size, raise a ValueError.

  7. compressed_sequence = compress_sequence(binary_sequence, block_size): Call the compress_sequence function to compress the input sequence.

  8. compressed_length = len(compressed_sequence): Get the length of the compressed sequence.

  9. if compressed_length <= 0.5 * n * math.log2(n): Check if the compressed length meets the expected criteria; if so, return True, indicating the test passed.

  10. return False: If the compression test is not passed, return False.

  11. def compress_sequence(binary_sequence, block_size): Define a helper function to compress a binary sequence into a sequence of decimal values.

  12. n = len(binary_sequence): Get the length of the binary sequence.

  13. L = int(math.ceil(n / block_size)): Calculate the number of blocks.

  14. compressed_sequence = []: Create an empty list to store the compressed sequence.

  15. for i in range(L): Loop through each block.

  16. block = binary_sequence[i * block_size : (i + 1) * block_size]: Get the current block.

  17. decimal_value = int("".join(map(str, block)), 2): Convert the binary block to a decimal value.

  18. compressed_sequence.append(decimal_value): Add the converted value to the compressed sequence.

  19. return compressed_sequence: Return the compressed sequence.

  20. random_binary_sequence = [random.randint(0, 1) for _ in range(1000)]: Generate a random binary sequence of length 1000 using list comprehension.

  21. block_size = 4: Set the block size.

  22. result = maurer_universal_test(random_binary_sequence, block_size): Call the Maurer's Universal Statistical Test function for testing.

  23. print("Maurer Universal Statistical Test Result:", result): Print the result of Maurer's Universal Statistical Test. If True is returned, the test passed; if False is returned, the test did not pass.

Unpredictability

Random number streams should exhibit two forms of unpredictability: forward unpredictability and backward unpredictability, used to describe the predictability of the generated random number sequence. These two concepts involve the difficulty in predicting future outputs or reconstructing previous outputs when a portion of the output is known.

Forward Unpredictability:

  • Definition: Forward unpredictability describes the difficulty in accurately predicting future random number outputs given a known portion of the random number sequence.

  • Example: If a random number generator can be accurately predicted after a series of outputs, it lacks forward unpredictability. Forward unpredictability refers to the inability to accurately predict future outputs given the random number outputs before a certain moment.

Backward Unpredictability:

  • Definition: Backward unpredictability describes the difficulty in accurately reconstructing previous random number outputs given a known portion of the random number sequence.

  • Example: If a random number generator's previous outputs can be deduced, it lacks backward unpredictability. Backward unpredictability refers to the inability to accurately deduce previous outputs given the random number outputs after a certain moment.

In secure cryptographic applications, both forward and backward unpredictability are crucial properties. If the generator's output can be predicted, attackers may be able to deduce keys or other sensitive information, posing a threat to the system's security.

Typically, forward and backward unpredictability are evaluated through mathematical analysis and statistical testing of the generator's output. When designing and selecting random number generators, it is essential to ensure their strength in both aspects to resist various attacks.

PRNG-LCG

Now let's learn about two algorithms used for PRNG.

One of them is the Linear Congruential Generator.

The Linear Congruential Generator (LCG) is a simple pseudorandom number generator (PRNG) algorithm. Its basic idea involves generating the next pseudorandom number by applying a linear transformation to the current one. LCG is a class of PRNG widely used in computer programs, and its simplicity and efficiency make it one of the commonly employed methods for generating random numbers.

The generation rule of LCG is typically expressed using the following recurrence relation:

In the context:

  • (X_n) is the current pseudo-random number,

  • (X_{n+1}) is the next pseudo-random number,

  • (a) is the multiplier (constant),

  • (c) is the increment (constant),

  • (m) is the modulus (constant).

The initialization of LCG requires a seed value (X_0), and each subsequent pseudo-random number is generated through the aforementioned recurrence relation. The periodicity of LCG depends on the chosen parameters (a), (c), and (m), with different parameters leading to different properties.

Characteristics and Properties:

  1. Periodicity: The period of LCG is finite, meaning it repeats the same sequence after a certain number of steps. The length of the period depends on the chosen parameters and should not be too small to avoid repetition.

  2. Linear Relationship: Due to its linear recurrence relation, the pseudo-random number sequence generated by LCG has a linear relationship, which may result in some limitations.

  3. Sensitivity: For certain parameters, LCG may be sensitive to the initial seed value, causing the generated random number sequence to exhibit patterns.

  4. Statistical Properties: In some bits, the random numbers generated by LCG may not be uniformly distributed, impacting certain applications.

  5. Not Suitable for Cryptography: LCG is not suitable for cryptographic applications as its pseudo-random number sequence may be too predictable and vulnerable to attacks.

Parameter Selection for LCG: Choosing appropriate values for (a), (c), and (m) is crucial to ensure the generated pseudo-random number sequence exhibits desirable properties. Knuth recommends (m) to be a large prime number, (a) to be a primitive root modulo (m), and (c) to be a coprime integer with (m).

In practical applications, mathematical analysis and testing are often employed to select suitable parameters for achieving desired properties.

class LinearCongruentialGenerator:
    def __init__(self, seed, a, c, m):
        # Initialize the Linear Congruential Generator with provided parameters.
        self.state = seed
        self.a = a
        self.c = c
        self.m = m

    def generate(self):
        # Generate the next pseudo-random number using the linear congruential formula.
        self.state = (self.a * self.state + self.c) % self.m
        return self.state

# Set parameters
seed_value = 42
a_value = 1664525
c_value = 1013904223
m_value = 2**32

# Create a Linear Congruential Generator
lcg = LinearCongruentialGenerator(seed_value, a_value, c_value, m_value)

# Generate random numbers
random_numbers = [lcg.generate() for _ in range(10)]

# Print the results
print("Random Numbers:", random_numbers)

This code implements a basic Linear Congruential Generator (LCG). LCG is a type of pseudo-random number generator that generates the next random number through a linear recurrence relation.

  • LinearCongruentialGenerator class:

    • init method: Initialization method, taking four parameters – seed, multiplier (a), increment (c), and modulus (m), and storing them as instance variables.

    • generate method: Generation method, calculating the next random number based on the linear congruential relation, updating the state, and returning the new state value.

  • Setting parameters: Defines a set of parameters including seed_value, a_value, c_value, and m_value.

  • Creating a Linear Congruential Generator: Creates an instance of LinearCongruentialGenerator using the specified parameters, which will be used for generating random numbers.

  • Generating random numbers: Uses the generate method to generate a list containing 10 random numbers.

  • Printing results: Prints the generated list of random numbers.

Code execution flow:

  1. Creates an instance 'lcg' of the LinearCongruentialGenerator class, passing the initialization parameters.

  2. Uses the lcg.generate() method to generate 10 random numbers, storing them in the 'random_numbers' list.

  3. Prints the generated list of random numbers.

Considerations:

  • Choosing appropriate parameters is crucial for the quality of a linear congruential generator. Different parameters may result in different properties of the generated random number sequence.

  • The periodicity of a linear congruential generator is finite, so in practical applications, if a longer period or higher quality random numbers are needed, other pseudo-random number generator algorithms may be considered.

PRNG-BBS

The BBS (Blum-Blum-Shub) generator is a pseudo-random number generator (PRNG) algorithm proposed by Manuel Blum, Shafi Goldwasser, and Silvio Micali in 1982. It is based on number theory principles, particularly relying on powerful number-theoretic challenges.

The basic principles of the BBS generator are as follows:

  1. Choose two large prime numbers, p and q: These two primes should satisfy the condition of being congruent to 3 modulo 4, i.e.

This selection is made to ensure

The quadratic residues form the entire set.

  1. Calculate ( n ):

  1. Select a seed ( s ): Choose an integer ( s ) that is coprime with ( n ), meaning that ( \text{gcd}(s, n) = 1 ).

  2. Generate a random number sequence: For each subsequent random number ( x_i ), calculate

Generating random numbers is the lowest bit of the binary representation of ( x_{i+1} ). Properties and Characteristics:

  • Security: The security of the BSS generator relies on number-theoretic assumptions, particularly the difficulty of the factorization problem. If an attacker can effectively factorize.

...then they can predict the generator's output. However, under current mathematical knowledge, this is a challenging problem.

  • Slowness: The BSS generator is relatively slow since it requires large integer squaring modulo operations at each step.

  • Long Period: Due to ( n ) being the product of two large primes, the BSS generator has a long period.

  • Uniformity: Theoretically, the output of the BSS generator should be uniformly distributed.

  • Not suitable for cryptographic applications: Despite its theoretical security, the BSS generator is not commonly used in cryptographic applications in practice because there are faster and more extensively tested cryptographic pseudorandom number generators available.

def is_prime(num):
    # Check if a number is prime
    if num < 2:
        return False
    for i in range(2, int(num**0.5) + 1):
        if num % i == 0:
            return False
    return True

def generate_bbs_sequence(seed, p, q, n):
    # Generate BBS sequence based on given parameters
    M = p * q
    x = seed
    result = []

    for _ in range(n):
        x = (x**2) % M
        result.append(x % 2)

    return result

# Choose two large prime numbers, p and q
p = 499
q = 547

# Calculate M = p * q
M = p * q

# Choose seed and sequence length
seed = 12345
sequence_length = 10

# Generate BBS sequence
bbs_sequence = generate_bbs_sequence(seed, p, q, sequence_length)

# Print the result
print("BBS Sequence:", bbs_sequence)

The provided code implements a basic Blum-Blum-Shub (BBS) sequence generator, which is a pseudorandom number generator (PRNG) based on number theory principles. Let's analyze the code step by step:

  1. is_prime Function:

    • Purpose: Determines if a given number is a prime number.

    • Input: num - the number to be checked for primality.

    • Output: Returns True if the number is prime, and False otherwise.

    • Implementation: It checks divisibility from 2 to the square root of the number.

  2. generate_bbs_sequence Function:

    • Purpose: Generates a BBS sequence based on the specified parameters.

    • Inputs:

      • seed - the initial seed for the generator.

      • p and q - two large prime numbers used in the BBS algorithm.

      • n - the length of the sequence to generate.

    • Output: Returns a list containing the generated BBS sequence of 0s and 1s.

    • Implementation: It iteratively applies the BBS algorithm, squaring the current value (x) and taking the modulus to obtain the next value.

  3. Choosing Parameters:

    • Two large prime numbers p and q are chosen (in this case, 499 and 547).

    • The product M of p and q is calculated.

  4. Generating BBS Sequence:

    • The BBS sequence is generated with an initial seed (seed), prime numbers (p and q), and the desired sequence length (sequence_length).

  5. Printing Result:

    • The generated BBS sequence is printed.

Note:

  • The BBS generator's security relies on the difficulty of certain number theory problems, specifically the difficulty of factoring the product M. However, in practice, BBS is not commonly used for cryptographic applications due to its relatively slow execution and the availability of faster and more widely-tested cryptographic PRNGs.

Reference

1. https://en.wikipedia.org/wiki/Linear_congruential_generator

2. https://www.geeksforgeeks.org/linear-congruence-method-for-generating-pseudo-random-numbers/

3. https://rosettacode.org/wiki/Linear_congruential_generator

4. https://asecuritysite.com/random/linear?val=2175143%2C3553%2C10653%2C1000000

5. https://en.wikipedia.org/wiki/Blum_Blum_Shub

PreviousRandom Sequence ⅠNextRandom Sequence Ⅲ

Last updated