Wednesday, October 2, 2013

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
      • xn = a x n-1 + b (mod m)
      • number x0 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 xj = 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≡ x2j-1 (mod n)
        • bj is the least significant bit of xj
      • However BBS is slow to calculate due to size of primes

No comments:

Post a Comment