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