Objective:

Generate a random sequence of 0's and 1's.

How to prove randomness?

If we generate a sequence of 0's and 1's, how can we convince everyone (or better prove) that it is random? A random binary sequence will have the following two properties:

1. Uniform properties: The frequency of 1's and 0's is almost equal
2. Independence: No number can be inferred from previous values

<aside> 💡 It is easy to prove point [1], but it is extremely difficult, or infeasible, to prove [2].

</aside>

However, there are tests that can prove dependence. These tests are also known as polytime statistical tests.

If a stream passes these tests, we say that the stream exhibits strong resemblance to randomness. For most applications, including many cryptographic functions, this is sufficient.

Why are they called Pseudo-random?

The algorithms used to generate seemingly random bits normally need an initial value to start, also called the seed. The algorithm is completely deterministic if the seed is known.

Therefore, not all parts of the algorithm are non-deterministic. The term pseudo-random describes such behavior.

PRNG Algorithms:

In this course, we will learn about two methods: 1- Linear Feedback Shift Registers (LFSR) 2- Blum Blum Shub (BBS)

<aside> 💡 The LFSR is described in another document. The rest of the document describes the BBS algorithm.

</aside>

The Blum Blum Shub Algorithm:

• Developed in 1986 by Lenore Blum, Manuel Blum and Michael Shub. • So far, the strongest algorithm that has a public proof of its cryptographic strength.

BBS Design:

1- Select two large primes p and q such that, p and q are congruent to 3 mod 4 $𝑝 ≡ 𝑞 ≡ 3 \mod 4$

2- Compute n: $𝑛 = 𝑝 × 𝑞$