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: http://gmplib.org 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 Math::GMPz object.)
An implementation of the Micali-Schnorr pseudorandom bit generator.
use warnings; use Math::Random::MicaliSchnorr qw(ms ms_seedgen); use Math::GMP; # and/or: #use Math::GMPz; my $s1 = '1255031698703398971890886237939563492533'; my $s2 = '10512667662093824763131998324796018248471'; my $prime1 = Math::GMP->new($s1); my $prime2 = Math::GMP->new($s2); my $seed = Math::GMP->new(time + int(rand(10000))); my $exp; 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 following conditions: 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 340 (80 * 3). 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 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.
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, Sisyphus
Sisyhpus <sisyphus at(@) cpan dot (.) org>