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



Annotate this POD

View/Report Bugs
Module Version: 0.02   Source   Latest Release: Math-Random-MicaliSchnorr-0.04


   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
   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>
syntax highlighting: