

 
Crypt::Primes(3) 
User Contributed Perl Documentation 
Crypt::Primes(3) 
Crypt::Primes  Provable Prime Number Generator suitable for Cryptographic
Applications.
$Revision: 0.49 $
$Date: 2001/06/11 01:04:23 $
# generate a random, provable 512bit prime.
use Crypt::Primes qw(maurer);
my $prime = maurer (Size => 512);
# generate a random, provable 2048bit prime and report
# progress on console.
my $another_prime = maurer (
Size => 2048,
Verbosity => 1
);
# generate a random 1024bit prime and a group
# generator of Z*(n).
my $hash_ref = maurer (
Size => 1024,
Generator => 1,
Verbosity => 1
);
The codebase is stable, but the API will most definitely change in a future
release.
This module implements Ueli Maurer's algorithm for generating large
provable primes and secure parameters for publickey cryptosystems. The
generated primes are almost uniformly distributed over the set of primes of
the specified bitsize and expected time for generation is less than the time
required for generating a pseudoprime of the same size with MillerRabin
tests. Detailed description and running time analysis of the algorithm can be
found in Maurer's paper[1].
Crypt::Primes is a pure perl implementation. It uses Math::Pari
for multiple precision integer arithmetic and number theoretic functions.
Random numbers are gathered with Crypt::Random, a perl interface to
/dev/u?random devices found on most modern Unix operating systems.
The following functions are availble for import. They must be explicitely
imported.
 maurer(%params)
 Generates a prime number of the specified bitsize. Takes a hash as
parameter and returns a Math::Pari object (prime number) or a hash
reference (prime number and generator) when group generator computation is
requested. Following hash keys are understood:
 Size
 Bitsize of the required prime number.
 Verbosity
 Level of verbosity of progress reporting. Report is printed on STDOUT.
Level of 1 indicates normal, terse reporting. Level of 2 prints lots of
intermediate computations, useful for debugging.
 Generator
 When Generator key is set to a nonzero value, a group generator of Z*(n)
is computed. Group generators are required key material in publickey
cryptosystems like Elgamal and DiffieHellman that are based on
intractability of the discrete logarithm problem. When this option is
present, maurer() returns a hash reference that contains two keys,
Prime and Generator.
 Relprime
 When set to 1, maurer() stores intermediate primes in a class
array, and ensures they are not used during construction of primes in the
future calls to maurer() with Reprime => 1. This is used by
rsaparams().
 Intermediates
 When set to 1, maurer() returns a hash reference that contains
(corresponding to the key 'Intermediates') a reference to an array of
intermediate primes generated.
 Factors
 When set to 1, maurer() returns a hash reference that contains
(corresponding to the key 'Factors') a reference to an array of factors of
p1 where p is the prime generated, and also (corresponding to the key
'R') a divisor of p.
 rsaparams(%params)
 Generates two primes (p,q) and public exponent (e) of a RSA key pair. The
key pair generated with this method is resistant to iterative encryption
attack. See Appendix 2 of [1] for more information.
rsaparams() takes the same arguments as maurer()
with the exception of `Generator' and `Relprime'. Size specifies the
common bitsize of p an q. Returns a hash reference with keys p, q and
e.
 trialdiv($n,$limit)
 Performs trial division on $n to ensure it's not
divisible by any prime smaller than or equal to
$limit. The module maintains a lookup table of
primes (from 2 to 65521) for this purpose. If
$limit is not provided, a suitable value is
computed automatically. trialdiv() is used by maurer() to
weed out composite random numbers before performing computationally
intensive modular exponentiation tests. It is, however, documented should
you need to use it directly.
This module implements a modified FastPrime, as described in [1], to facilitate
group generator computation. (Refer to [1] and [2] for description and
pseudocode of FastPrime). The modification involves introduction of an
additional constraint on relative size r of q. While computing r, we ensure k
* r is always greater than maxfact, where maxfact is the bitsize of the
largest number we can factor easily. This value defaults to 140 bits. As a
result, R is always smaller than maxfact, which allows us to get a complete
factorization of 2Rq and use it to find a generator of the cyclic group
Z*(2Rq).
Crypt::Primes generates 512bit primes in 7 seconds (on average), and 1024bit
primes in 37 seconds (on average), on my PII 300 Mhz notebook. There are no
computational limits by design; primes upto 8192bits were generated to stress
test the code. For detailed runtime analysis see [1].
largeprimes(1), Crypt::Random(3), Math::Pari(3)
 1 Fast Generation of Prime Numbers and Secure PublicKey Cryptographic
Parameters, Ueli Maurer (1994).
 2 Corrections to Fast Generation of Prime Numbers and Secure PublicKey
Cryptographic Parameters, Ueli Maurer (1996).
 3 Handbook of Applied Cryptography by Menezes, Paul C. van Oorschot and
Scott Vanstone (1997).
 Documents 1 & 2 can be found under docs/ of the source
distribution.
Vipul Ved Prakash, <mail@vipul.net>
Copyright (c) 19982001, Vipul Ved Prakash. All rights reserved. This code is
free software; you can redistribute it and/or modify it under the same terms
as Perl itself.
Maurer's algorithm generates primes of progressively larger bitsize using a
recursive construction method. The algorithm enters recursion with a prime
number and bitsize of the next prime to be generated. (Bitsizes of the
intermediate primes are computed using a probability distribution that ensures
generated primes are sufficiently random.) This recursion can be distributed
over multiple machines, participating in a competitive computation model, to
achieve close to best running time of the algorithm. Support for this will be
implemented some day, possibly when the next version of Penguin hits CPAN.
Hey! The above document had some coding errors, which are explained
below:
 Around line 770:
 Can't have a 0 in =over 0
Visit the GSP FreeBSD Man Page Interface. Output converted with ManDoc. 