- 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
_{0}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^{2}_{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

## Wednesday, October 2, 2013

### Notes - Pseudo-random Bit Generation

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

Subscribe to:
Post Comments (Atom)

## No comments:

## Post a Comment