| Blum Blum Shub |
Article Index for Blum |
Website Links For Pseudorandom |
Information AboutBlum Blum Shub |
|
BBS takes the form: x where M=pq is the product of two large Primes ''p'' and ''q''. At each step of the algorithm, some output is derived from ''x''''n''; the output is commonly either the Bit Parity of ''x''''n'' or one or more of the least significant bits of ''x''''n''. The two primes, ''p'' and ''q'', should both be Congruent to 3 (mod 4) (this guarantees that each Quadratic Residue has one Square Root which is also a quadratic residue) and Gcd ( φ (''p''-1), φ(''q''-1)) should be small (this makes the cycle length large). SECURITY The generator is not appropriate for use in simulations, only for Cryptography , because it is not very fast. However, it has an unusually strong security proof, which relates the quality of the generator to the Computational Difficulty of Integer Factorization . When the primes are chosen appropriately, and O ( Log log ''M'') bits of each ''xn'' are output, then in the limit as ''M'' grows large, distinguishing the output bits from random will be at least as difficult as factoring ''M''. If Integer Factorization is difficult (as is suspected) then BBS with large ''M'' will have an output free from any nonrandom patterns that can be discovered with any reasonable amount of calculation. This makes it as secure as other encryption technologies tied to the factorization problem, such as RSA Encryption . REFERENCES
EXTERNAL LINKS |
|
|