Math::Random::MicaliSchnorr - the Micali-Schnorr pseudorandom bit generator.
To build this module the GMP C library needs to be installed. Source for
this library is available from:
The functions in this module take either Math::GMP or Math::GMPz objects
as their arguments - so you'll need either Math::GMP or Math::GMPz as
well. (Actually, *any* perl scalar that's a reference to a GMP mpz
structure will suffice - it doesn't *have* to be a Math::GMP or
An implementation of the Micali-Schnorr pseudorandom bit generator.
use Math::Random::MicaliSchnorr qw(ms ms_seedgen);
my $s1 = '615389388455725613122981570401989286707';
my $s2 = '8936277569639798554773638405675965349567';
my $prime1 = Math::GMP->new($s1);
my $prime2 = Math::GMP->new($s2);
my $seed = Math::GMP->new(time + int(rand(10000)));
my $bitstream = Math::GMP->new();
my $bits_out = 500;
# Generate the seed value
ms_seedgen($seed, $exp, $prime1, $prime2);
# Fill $bitstream with 500 random bits using $seed, $prime1 and $prime2
ms($bitstream, $prime1, $prime2, $seed, $exp, $bits_out);
# Other working examples (using Math::GMPz as well as Math::GMP can be
# found in the test script that ships with the
# Math::Random::MicaliSchnorr source.
ms($o, $prime1, $prime2, $seed, $exp, $bits);
"$o", "$prime1", "$prime2", and "$seed" are all Math::GMP or Math::GMPz
objects. $prime1 and $prime2 are large primes. (The ms function does
not check that they are, in fact, prime. Both Math::GMPz and Math::GMP
modules provide functions for creating large primes.)
Output a $bits-bit random bitstream to $o - calculated using the
Micali-Schnorr algorithm, based on the inputs $prime1, $prime2, $seed
and $exp. See the ms_seedgen documentation (below) for the requirements
regarding $seed and $exp.
ms_seedgen($seed, $exp, $prime1, $prime2);
$seed is a Math::GMP or Math::GMPz object. $exp is just a normal perl
scalar (that will have an unsigned integer value assigned to it). The
ms_seedgen function assigns values to both $seed and $exp that are
suitable for passing to the ms() function. You can, of course, write
your own routine for determining these values. (The ms function checks
that $seed and $exp values it has been passed are in the allowed range.)
Here are the rules for determining those values:
Let N be the bitlength of n = $prime1 * $prime2.
Let phi = ($prime1 - 1) * ($prime2 - 1). $exp must satisfy all 3 of the
i) 2 < $exp < phi
ii) The greatest common denominator of $exp and phi is 1
iii) $exp * 80 <= N
Conditions i) and iii) mean that N has to be at least 240 (80 * 3) - ie
the no. of bits in the product of the two primes must be at least 240.
The ms_seedgen function selects the largest value for $exp that
satisfies those 3 conditions. Having found a suitable value for $exp, we
then need to calculate the integer value k = int(N *(1 - (2 / $exp))).
Then calculate r = N - k, where r is the bitlength of the random value
that will be chosen to seed the MicaliSchnorr generator..
The ms_seedgen function uses the GMP library's mpz_urandomb function to
select a suitable value for $seed. The mpz_urandomb function itself is
seeded by the value *supplied* in the $seed argument. $seed is then
overwritten with the value that mpz_urandomb has come up with, and that
is the value that gets passed to ms().
By my understanding, the method of selecting $seed and $exp has no impact
upon the security of the MicaliSchnorr generator - save that the seed
needs to be r (or less) bits in size, that no seed value should be
re-used, and that $exp satisfies the 3 conditions given above.
Afaik, the security relies solely on the values of the 2 primes being
secret ... I could be wrong, but.
$bool = monobit($op);
$bool = longrun($op);
$bool = runs($op);
$bool = poker($op);
These are the 4 standard FIPS-140 statistical tests for testing
prbg's. They return '1' for success and '0' for failure.
They test 20000-bit pseudorandom sequences, stored in the
Math::GMPz/Math::GMP object $op.
$bool = autocorrelation_20000($op, $offset);
$op is a sequence (Math::GMPz/Math::GMP object) of 20000 + $offset bits.
Returns true ("success") if the no. of bits in $op not equal to their
$offset-leftshifts lies in the range [9655 .. 10345] (inclusive).
Else returns 0 ("failure").
($count, $x5val) = autocorrelation($op, $offset);
$op is a sequence (Math::GMPz/Math::GMP object) of 20000 bits.
Returns (resp.) the no. of bits in $op not equal to their
$offset-leftshifts, and the X5 value as specified in section 5.4.4
of "Handbook of Applied Cryptography" (Menezes at al).
You can get segfaults if you pass the wrong type of argument to the
functions - so if you get a segfault, the first thing to do is to check
that the argument types you have supplied are appropriate.
This program is free software; you may redistribute it and/or
modify it under the same terms as Perl itself.
Copyright 2006-2008, 2009, 2010, 2014, Sisyphus
Sisyhpus <sisyphus at(@) cpan dot (.) org>