Overview - Maple Help

Overview of the RandomTools:-BlumBlumShub Subpackage

 Calling Sequence RandomTools:-BlumBlumShub:-function(arguments) function(arguments)

Description

 • The RandomTools:-BlumBlumShub subpackage contains functions for creating pseudo-random number generators using the Blum, Blum, and Shub algorithm.  The integers x[1], x[2], ... are generated using the quadratic recurrence

${x}_{k+1}={x}_{k}^{2}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{mod}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}n$

 where $n$ is a product of two primes and ${x}_{0}$, the seed, may be specified by the user.  They use the least significant bits of the x's to form the random numbers.
 • The Blum, Blum, and Shub generator is intended to be used for cryptographic applications.  For this purpose it uses very large primes, primes of length 308, 462 or 616 digits so that n cannot be factored.  It extracts the log[2](log[2](n)) least significant bits of the x's which are known to be cryptographically secure.  The primes used have certain properties so that ${x}_{0}$ can be chosen so that the sequence of bits generated will have a provably very long period.
 • Each command in the RandomTools:-BlumBlumShub subpackage can be accessed by using either the long form or the short form of the command name in the command calling sequence.
 The long form, RandomTools:-BlumBlumShub:-command, is always available. The short form can be used after loading the package.

List of RandomTools:-BlumBlumShub Subpackage Commands

 To display the help page for a particular BlumBlumShub command, see Getting Help with a Command in a Package.

Examples

 > $\mathrm{with}\left(\mathrm{RandomTools}:-\mathrm{BlumBlumShub}\right)$
 $\left[{\mathrm{NewBitGenerator}}{,}{\mathrm{NewGenerator}}\right]$ (1)

The NewBitGenerator command outputs cryptographically secure random bits. It takes as input a random seed S which can be used as a secret key in an encryption protocol.

 > $S≔749174032174023174398217651252100347882175301621678436520:$
 > $B≔\mathrm{NewBitGenerator}\left(S,\mathrm{numbits}=10\right):$
 > $B\left(\right)$
 ${1}{,}{0}{,}{1}{,}{1}{,}{0}{,}{0}{,}{1}{,}{1}{,}{1}{,}{0}$ (2)
 > $B\left(\right)$
 ${1}{,}{0}{,}{1}{,}{1}{,}{1}{,}{1}{,}{0}{,}{0}{,}{1}{,}{1}$ (3)

Suppose Alice wants to send a message M to Bob and suppose Alice wants to encrypt the message so that no one else can read it.  Suppose

 > $M≔\left[0,1,1,1,0,1,1,0,0,1,1,0,0,0,1,1,0,1,0,1\right]$
 ${M}{≔}\left[{0}{,}{1}{,}{1}{,}{1}{,}{0}{,}{1}{,}{1}{,}{0}{,}{0}{,}{1}{,}{1}{,}{0}{,}{0}{,}{0}{,}{1}{,}{1}{,}{0}{,}{1}{,}{0}{,}{1}\right]$ (4)

is the 20 bit message Alice wants to encrypt. If Alice and Bob both know S then Alice can do the following. First she creates 20 random bits Z as follows.

 > $B≔\mathrm{NewBitGenerator}\left(S,\mathrm{numbits}=10\right):$
 > $Z≔\left[B\left(\right),B\left(\right)\right]$
 ${Z}{≔}\left[{1}{,}{0}{,}{1}{,}{1}{,}{0}{,}{0}{,}{1}{,}{1}{,}{1}{,}{0}{,}{1}{,}{0}{,}{1}{,}{1}{,}{1}{,}{1}{,}{0}{,}{0}{,}{1}{,}{1}\right]$ (5)

Now the ciphertext C is formed by adding Z to M modulo 2  (equivalent to an exclusive or of the bits).

 > $C≔M+Z\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathbf{mod}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}2$
 ${C}{≔}\left[{1}{,}{1}{,}{0}{,}{0}{,}{0}{,}{1}{,}{0}{,}{1}{,}{1}{,}{1}{,}{0}{,}{0}{,}{1}{,}{1}{,}{0}{,}{0}{,}{0}{,}{1}{,}{1}{,}{0}\right]$ (6)

Now Alice sends C to Bob.  Bob, who knows S, can determine M from C as follows.

 > $B≔\mathrm{NewBitGenerator}\left(S,\mathrm{numbits}=10\right):$
 > $Z≔\left[B\left(\right),B\left(\right)\right]$
 ${Z}{≔}\left[{1}{,}{0}{,}{1}{,}{1}{,}{0}{,}{0}{,}{1}{,}{1}{,}{1}{,}{0}{,}{1}{,}{0}{,}{1}{,}{1}{,}{1}{,}{1}{,}{0}{,}{0}{,}{1}{,}{1}\right]$ (7)
 > $C+Z\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathbf{mod}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}2$
 $\left[{0}{,}{1}{,}{1}{,}{1}{,}{0}{,}{1}{,}{1}{,}{0}{,}{0}{,}{1}{,}{1}{,}{0}{,}{0}{,}{0}{,}{1}{,}{1}{,}{0}{,}{1}{,}{0}{,}{1}\right]$ (8)
 > $M$
 $\left[{0}{,}{1}{,}{1}{,}{1}{,}{0}{,}{1}{,}{1}{,}{0}{,}{0}{,}{1}{,}{1}{,}{0}{,}{0}{,}{0}{,}{1}{,}{1}{,}{0}{,}{1}{,}{0}{,}{1}\right]$ (9)

The security of the Blum, Blum, and Shub generator depends on the size of the primes used.  Choices available are 512, 768, and 1024 bit primes. See NewBitGenerator for further details, examples and other options.