Cryptography Reference
In-Depth Information
which can be written as a string or as a list
4
(with the most significant byte first) as
follows:
> Bits:-String(s, msbfirst);
"101101101000000101100010010011011111101111101100111110110101001101000000101001000\
11000001111111101000111000000111111101110010011"
> ListTools:-Reverse(Bits:-Split(s));
[1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 0,
0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0,
1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0,
1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0,
0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 1]
If we now want to generate, for example, a 512-bit string by means of BBS, using
s
as seed, we just compute:
> BBS := RandomTools:-BlumBlumShub:-NewBitGenerator(s, primes = 1024):
pb := cat("", seq(BBS(), i=1..512));
"101100110110100100010101000110001000001100100111110010000110000011001101000011111\
00000001010100110011010111100001001000110111000001110000011101011010110111101011\
01011010110011100001010101011100111010101011011000000100001100001001010000110011\
10000100001010110000101110111111111001100101101100110111011010110100010000000110\
11100110101000011100011111111000111101000110000101010100111000110110110000111010\
11011011110010001000011000111011100010111110011001011110001000001010011101110100\
0011100111101011111100100111110"
If we prefer the output of BBS given as a list—which is often more convenient for
carrying out further operations with it—then we would instead call (without printing
the output):
> pb := [seq(BBS(), i = 1..512)]:
The security of the BBS generator is, as we have seen, conditional on the hypoth-
esis that the factoring problem is hard and, in this specific case, on the hardness of the
factorization of the three numbers
n512, n768, n1024
. When using Maple's
BBS as a source of pseudo-randomness for cryptographic purposes one has to trust
that this factorization is indeed hard and also that no one knows the factors. In the
help page of
NewBitGenerator
it is mentioned that the factorization of these
numbers was discarded and that Maple does not have it ...
On the other hand, if one does not trust this particular choice of integers, it is very
easy to replace them by one's favorite Blum integers. For this it suffices to create
a new procedure using Maple's
NewBitGenerator
code, in which the variable
names
n512
,
n768
, and
n1024
are replaced by the numbers you choose (or by
other names that point to these numbers). One must be careful, however, in case the
size of these numbers is changed, for then other parameters inside this procedure
should be changed too. Also, one should take care to choose numbers which make
the BBS generator have a long period, as explained in [144].
4
Here we use Maple's package
Bits
available only from version 12 onwards but, with a little
further work, this can also be done with previous versions of Maple.
