RandomTools[BlumBlumShub] - Maple Help

Online Help

All Products    Maple    MapleSim


Home : Support : Online Help : Programming : Random Objects : RandomTools package : BlumBlumShub Subpackage : RandomTools/BlumBlumShub/NewBitGenerator

RandomTools[BlumBlumShub]

  

NewBitGenerator

  

Blum, Blum and Shub Pseudo Random Bit Generator

 

Calling Sequence

Parameters

Description

Examples

Calling Sequence

NewBitGenerator( seed, opt1, opt2, ... )

Parameters

seed

-

an integer, the seed for the generator

opt1, opt2, ...

-

(optional) argument of the form option=value where option is one of primes, numbits, or output

Description

• 

The NewBitGenerator command outputs a Maple procedure, a pseudo-random bit generator, which when called outputs one pseudo-random bit, a 0 or 1. The generator is a Blum-Blum-Shub (BBS) generator. A BBS generator uses the following quadratic recurrence to generate a sequence of integers x1,x2, from which cryptographically secure pseudo-random bits z1,z2, are extracted:

xk+1=modxk2,n

zk+1=modxk+1,2m.

  

where

– 

n is a product of two large primes p and q,

– 

m=floorlog[2]log[2]n, and

– 

x0 is determined from the seed s.

  

Each iteration of zk+1, the least significant m bits of xk+1, generates m cryptographically secure bits. The output of the generator depends on the options described below. The default is to output one bit.

• 

The cryptographic security of the BBS generator assumes that the number theoretic problem of distinguishing a quadratic residue from a pseudo-square in Z mod n is computationally infeasible when n is the product of two primes p and q and the factorization of n is not known. Thus it also assumes that integer factorization is computationally infeasible. Recall the definitions of a quadratic residue and pseudo-square:

  

Definition: An integer x in Z mod n is a quadratic residue if (i) gcdx,n=1 and (ii) x=y2modn for some integer y.

  

Definition: An integer z in Z mod n where n=pq is a pseudo-square if (i) gcdz,n=1, (ii) z is not a quadratic residue in Z mod p, and (iii) z is not a quadratic residue in Z mod q.

• 

The primes p and q are chosen to be of the form p=2s+1 and q=2t+1 where s and t are prime and 2 is a primitive element in both Z mod s and Z mod t.  This choice guarantees that p and q are both congruent to 3 mod 4 (a requirement for the security of the generator) and also that the period of the generator for x0 for any quadratic residue other than 1 is either s1 or t1 or lcms1,t1, all of which are large. Random primes p and q, and their product n=pq, satisfying these requirements of lengths 512 bits, 768 bits, and 1024 bits have been precomputed and the prime factorization discarded (Maple does not have the factorizations). Thus there are three choices for n of lengths 308, 462, and 616 decimal digits, providing a range of security for cryptographic applications.

• 

The argument seed=s determines the seed for the generator. The value used for x0 used must be a "random" quadratic residue which is not equal to 1 (to avoid a short period). The value used for x0 is computed from the seed s. For cryptographic applications the seed should be chosen by the user to be a random integer from a large set, e.g., from 0..10^100. It will be automatically reduced modulo n.

• 

The following optional arguments are supported. They are input as equations in any order.

  

primes = 512, 768 or 1024

  

The integer l, which must be one of 512, 768 or 1024 specifies the length of the primes p and q in bits.  The default is 512.

  

numbits=integer

  

This specifies how many bits are computed and output by each call to the generator.  The default is 1.

  

output= bits or integer

  

This specifies how the bits are output.  If integer is specified, the output is a Maple integer in the range 0 to 2^b-1.  If bits is specified, the output will be a Maple sequence of b bits.  The default is bits.

• 

The RandomTools[BlumBlumShub] module also exports the NewGenerator function.  This function's interface is compatible with the NewGenerator functions of other RandomTools pseudo-random number generator subpackages.

Examples

withRandomTools[BlumBlumShub]

NewBitGenerator,NewGenerator

(1)

seed1050109365100103751001961108357097849013652340237134723870:

BNewBitGeneratorseed

B:=procz:=z&lsqb;1&plus;1..&minus;1&rsqb;&semi;whilenopsz<1dox:=iremx&Hat;2&comma;n&semi;z:=opz&comma;T&lsqb;iremx&comma;1024&rsqb;end do&semi;op1..1&comma;zend proc

(2)

B

1

(3)

B

0

(4)

seqB&comma;i&equals;1..10

0&comma;0&comma;1&comma;0&comma;1&comma;1&comma;0&comma;1&comma;1&comma;1

(5)

BNewBitGeneratorseed&comma;numbits&equals;10&comma;primes&equals;1024&colon;

B

0&comma;1&comma;1&comma;0&comma;0&comma;0&comma;1&comma;1&comma;0&comma;0

(6)

B

0&comma;0&comma;0&comma;1&comma;0&comma;1&comma;0&comma;1&comma;1&comma;1

(7)

BNewBitGeneratorseed&comma;numbits&equals;32&comma;output&equals;integer&colon;

B

3026219245

(8)

seqB&comma;i&equals;1..5

780542672&comma;3215656114&comma;4009826535&comma;4022932036&comma;3025225627

(9)

See Also

rand

RandomTools

RandomTools[BlumBlumShub]

RandomTools[BlumBlumShub][NewGenerator]

RandomTools[Generate]

 


Download Help Document

Was this information helpful?



Please add your Comment (Optional)
E-mail Address (Optional)
What is ? This question helps us to combat spam