Oberon || Library || Module Index || Search Engine || Definition || Module

Ulm's Oberon Library:
BBS

NAME

BBS - implementation of the Blum, Blum, and Shub pseudo random number generator

SYNOPSIS

PROCEDURE CreateSequence(VAR sequence: RandomGenerators.Sequence; 
                         blumInt: IntOperations.Operand;
                         seed: IntOperations.Operand);

DESCRIPTION

BBS offers a cryptographically secure implementation of Random. The implementation uses a quadratic residue generator developed by Blum, Blum, and Shub. For references look at SIAM Journal on Computing, v. 15,n. 2, 1986, pp. 364-383: L. Blum, M. Blum, and M. Shub, A Simple Unpredictable Pseudo-Random Number Generator or RFC 1750, 6.3.2. This pseudo random generator is the most simple and efficient one for the generation of cryptographically secure random values. It is comparatively slow and less useful for stream ciphers, but for high security applications, like key generation, the generator is the best known. BBS does not replace the predefined sequence RandomGenerators.std.

CreateSequence creates and initializes a new sequence of pseudo random numbers. The sequence of random numbers depends on seed and on the given Blum integer blumInt.

A Blum integer is defined as the product of two large prime numbers which are congruent to 3 modulo 4. For cryptographically secure applications the Blum integer must have an appropriate length because the security rests on the difficulty of factoring the Blum integer. In Douglas R. Stinson, Cryptography, 4.4 and 4.8 at least 200 decimals (about 650 bit) are recommended but the larger the better. If blumInt is not given, then a default 128 bit Blum integer is used.

seed is expected to be a random integer which is relatively prime to blumInt. Relatively prime means that the greatest common divisor of seed and blumInt is 1. Good, hardly reproducible seed values are available in RandomGenerators.seed, for example by using UnixSeeds.

DIAGNOSTICS

BBS asserts seed to be not NIL and checks whether seed is relatively prime to blumInt or not. If not, then seed is slightly corrected.

AUTHOR

Frank B.J. Fischer

Edited by: borchert, last change: 1997/04/16, revision: 1.1, converted to HTML: 1997/04/28