Crypt::Primes - Provable Prime Number Generator suitable for Cryptographic Applications.
$Revision: 0.49 $ $Date: 2001/06/11 01:04:23 $
# generate a random, provable 512-bit prime.
use Crypt::Primes qw(maurer);
my $prime = maurer (Size => 512);
# generate a random, provable 2048-bit prime and report
# progress on console.
my $another_prime = maurer (
Size => 2048,
Verbosity => 1
);
# generate a random 1024-bit 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 public-key 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 pseudo-prime of the same size with Miller-Rabin 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.
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.
This module implements a modified FastPrime, as described in [1], to facilitate group generator computation. (Refer to [1] and [2] for description and pseudo-code 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 512-bit primes in 7 seconds (on average), and 1024-bit primes in 37 seconds (on average), on my PII 300 Mhz notebook. There are no computational limits by design; primes upto 8192-bits were generated to stress test the code. For detailed runtime analysis see [1].
largeprimes(1), Crypt::Random(3), Math::Pari(3)
Vipul Ved Prakash, <mail@vipul.net>
Copyright (c) 1998-2001, 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.