Sisyphus >
Math-Random-MicaliSchnorr >
Math::Random::MicaliSchnorr

Module Version: 0.05
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 = '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 $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 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, Sisyphus

Sisyhpus <sisyphus at(@) cpan dot (.) org>

syntax highlighting: