# NAME

` Math::Random::MicaliSchnorr - the Micali-Schnorr pseudorandom bit generator.`

# DEPENDENCIES

```
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.)
```

# DESCRIPTION

` An implementation of the Micali-Schnorr pseudorandom bit generator.`

# SYNOPSIS

```
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.
```

# FUNCTIONS

```
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).
```

# BUGS

```
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.
```

# LICENSE

```
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
```

# AUTHOR

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