Cryptography Reference
In-Depth Information
3.4.1 The Blum-Blum-Shub PRG in Maple
The default algorithm used by Maple to generate pseudo-random numbers (the
one called by the function
rand()
) is the Mersenne Twister algorithm which,
although very fast and useful for Monte Carlo simulations, is not cryptograph-
ically secure and hence is not a PRG in the sense of Definition 3.4. Thus we
shall not use this function, except in cases where unpredictability is not required.
Among Maple's pseudo-random algorithms, only the Blum-Blum-Shub genera-
tor satisfies the conditions in Definition 3.4 and is suitable for cryptographic use.
This is the PRG we are going to use in our implementations of cryptographic
algorithms.
The BBS PRG is implemented in Maple as a subpackage of the
RandomTools
package. We will use, in particular, the function
NewBitGenerator
of this sub-
package, whose long name is (taking into account that these packages are imple-
mented as modules, see Maple's help)
RandomTools:-BlumBlumShub:-New
BitGenerator
. This function has a required input parameter for the seed, which
is a positive integer different from 1. There are also three optional input parame-
ters called
numbits
,
output
, and
primes
and the output of the function is a
Maple procedure which is itself an implementation of BBS with the parameters
specified when calling
NewBitGenerator
.
numbits
is an integer that speci-
fies the number of bits that are computed in each call to the generator,
output
specifies whether the output is given as a sequence of bits or as an integer and,
finally,
primes
takes as value either 512 (the default), 768 or 1024. In the first
case, the Blum integer used as modulus by BBS is a product of two 512-bit
primes, and a product of two 768-bit or two 1024-bit primes in the other two
cases. These integers have 308, 462, and 616 decimal digits, respectively, and are
stored in three variables local to the module
RandomTools:-BlumBlumShub
called
n512
,
n768
, and
n1024
, respectively. We can easily learn what the pos-
sible values for the modulus
n
are and, for example,
n1024
is the following
integer:
> kernelopts(opaquemodules = false):
print(RandomTools:-BlumBlumShub['n1024']);
6358895565833034702208523084557621229832212772877790391642907586084929071132845514\
208579772157672029249844241528[...413 digits...]24238308875102402123685071832322\
54239727512835259549723357647718327998754795646911307672321
We will use
NewBitGenerator
to output a list of pseudo-random bits obtained
from a random seed. Suppose that our random seed is the following 128-bit
integer:
> s := 242591295382282583902940438229126740883:
