Notes - Pseudo-random Bit Generation

The following are notes from Introduction to Cryptography with Coding Theory.

• Ways to generate random bits
• sampling thermal noise from semiconductor resistor
• flipping coins
• Sampling natural processes however is very slow and its difficult to ensure that the enemy does not view the process
• Pseudo-Random generation
• example rand()
• takes a seed as an input produces output bitstream
• based on linear congruential generators
• x_n = a x _n-1 + b (mod m)
• number x₀ is the initial seed
• this is suitable for experimental purposes but not for cryptographic purposes because it is too predictable
• one way functions
• functions f(x) that are easy to compute but is computationally infeasible to determine y = f(x)
• therefore we can define a x_j = f(s+j) for j = 1,2,3
• DES, SHA
• Blum-Blum Shub pseudo-random bit generator
• quadratic residue generator
• generate two large primes p, q that are congruent to 3 mod 4
• then set n = pq and chose random integer x that is relatively prie to n
• BBS produces a sequence by
• x_j ≡ x²_j-1 (mod n)
• b_j is the least significant bit of x_j
• However BBS is slow to calculate due to size of primes

Back to ToC