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



Annotate this POD

View/Report Bugs
Module Version: 0.05   Source  


   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 = '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: