1Crypt::Primes(3)      User Contributed Perl Documentation     Crypt::Primes(3)
2
3
4

NAME

6       Crypt::Primes - Provable Prime Number Generator suitable for
7       Cryptographic Applications.
8

VERSION

10        $Revision: 0.49 $
11        $Date: 2001/06/11 01:04:23 $
12

SYNOPSIS

14           # generate a random, provable 512-bit prime.
15
16           use Crypt::Primes qw(maurer);
17           my $prime = maurer (Size => 512);
18
19           # generate a random, provable 2048-bit prime and report
20           # progress on console.
21
22           my $another_prime = maurer (
23                                Size => 2048,
24                                Verbosity => 1
25                               );
26
27
28           # generate a random 1024-bit prime and a group
29           # generator of Z*(n).
30
31           my $hash_ref = maurer (
32                           Size => 1024,
33                           Generator => 1,
34                           Verbosity => 1
35                          );
36

WARNING

38       The codebase is stable, but the API will most definitely change in a
39       future release.
40

DESCRIPTION

42       This module implements Ueli Maurer's algorithm for generating large
43       provable primes and secure parameters for public-key cryptosystems.
44       The generated primes are almost uniformly distributed over the set of
45       primes of the specified bitsize and expected time for generation is
46       less than the time required for generating a pseudo-prime of the same
47       size with Miller-Rabin tests.  Detailed description and running time
48       analysis of the algorithm can be found in Maurer's paper[1].
49
50       Crypt::Primes is a pure perl implementation.  It uses Math::Pari for
51       multiple precision integer arithmetic and number theoretic functions.
52       Random numbers are gathered with Crypt::Random, a perl interface to
53       /dev/u?random devices found on most modern Unix operating systems.
54

FUNCTIONS

56       The following functions are availble for import.  They must be
57       explicitely imported.
58
59       maurer(%params)
60           Generates a prime number of the specified bitsize.  Takes a hash as
61           parameter and returns a Math::Pari object (prime number) or a hash
62           reference (prime number and generator) when group generator
63           computation is requested.  Following hash keys are understood:
64
65       Size
66           Bitsize of the required prime number.
67
68       Verbosity
69           Level of verbosity of progress reporting.  Report is printed on
70           STDOUT.  Level of 1 indicates normal, terse reporting.  Level of 2
71           prints lots of intermediate computations, useful for debugging.
72
73       Generator
74           When Generator key is set to a non-zero value, a group generator of
75           Z*(n) is computed.  Group generators are required key material in
76           public-key cryptosystems like Elgamal and Diffie-Hellman that are
77           based on intractability of the discrete logarithm problem.  When
78           this option is present, maurer() returns a hash reference that
79           contains two keys, Prime and Generator.
80
81       Relprime
82           When set to 1, maurer() stores intermediate primes in a class
83           array, and ensures they are not used during construction of primes
84           in the future calls to maurer() with Reprime => 1.  This is used by
85           rsaparams().
86
87       Intermediates
88           When set to 1, maurer() returns a hash reference that contains
89           (corresponding to the key 'Intermediates') a reference to an array
90           of intermediate primes generated.
91
92       Factors
93           When set to 1, maurer() returns a hash reference that contains
94           (corresponding to the key 'Factors') a reference to an array of
95           factors of p-1 where p is the prime generated, and also
96           (corresponding to the key 'R') a divisor of p.
97
98       rsaparams(%params)
99           Generates two primes (p,q) and public exponent (e) of a RSA key
100           pair. The key pair generated with this method is resistant to
101           iterative encryption attack. See Appendix 2 of [1] for more
102           information.
103
104           rsaparams() takes the same arguments as maurer() with the exception
105           of `Generator' and `Relprime'.  Size specifies the common bitsize
106           of p an q.  Returns a hash reference with keys p, q and e.
107
108       trialdiv($n,$limit)
109           Performs trial division on $n to ensure it's not divisible by any
110           prime smaller than or equal to $limit.  The module maintains a
111           lookup table of primes (from 2 to 65521) for this purpose.  If
112           $limit is not provided, a suitable value is computed automatically.
113           trialdiv() is used by maurer() to weed out composite random numbers
114           before performing computationally intensive modular exponentiation
115           tests.  It is, however, documented should you need to use it
116           directly.
117

IMPLEMENTATION NOTE

119       This module implements a modified FastPrime, as described in [1], to
120       facilitate group generator computation.  (Refer to [1] and [2] for
121       description and pseudo-code of FastPrime).  The modification involves
122       introduction of an additional constraint on relative size r of q.
123       While computing r, we ensure k * r is always greater than maxfact,
124       where maxfact is the bitsize of the largest number we can factor
125       easily.  This value defaults to 140 bits.  As a result, R is always
126       smaller than maxfact, which allows us to get a complete factorization
127       of 2Rq and use it to find a generator of the cyclic group Z*(2Rq).
128

RUNNING TIME

130       Crypt::Primes generates 512-bit primes in 7 seconds (on average), and
131       1024-bit primes in 37 seconds (on average), on my PII 300 Mhz notebook.
132       There are no computational limits by design; primes upto 8192-bits were
133       generated to stress test the code.  For detailed runtime analysis see
134       [1].
135

SEE ALSO

137       largeprimes(1), Crypt::Random(3), Math::Pari(3)
138

BIBLIOGRAPHY

140       1 Fast Generation of Prime Numbers and Secure Public-Key Cryptographic
141       Parameters, Ueli Maurer (1994).
142       2 Corrections to Fast Generation of Prime Numbers and Secure Public-Key
143       Cryptographic Parameters, Ueli Maurer (1996).
144       3 Handbook of Applied Cryptography by Menezes, Paul C. van Oorschot and
145       Scott Vanstone (1997).
146       Documents 1 & 2 can be found under docs/ of the source distribution.
147

AUTHOR

149       Vipul Ved Prakash, <mail@vipul.net>
150

LICENSE

152       Copyright (c) 1998-2001, Vipul Ved Prakash. All rights reserved. This
153       code is free software; you can redistribute it and/or modify it under
154       the same terms as Perl itself.
155

TODO

157       Maurer's algorithm generates primes of progressively larger bitsize
158       using a recursive construction method. The algorithm enters recursion
159       with a prime number and bitsize of the next prime to be generated.
160       (Bitsizes of the intermediate primes are computed using a probability
161       distribution that ensures generated primes are sufficiently random.)
162       This recursion can be distributed over multiple machines, participating
163       in a competitive computation model, to achieve close to best running
164       time of the algorithm.  Support for this will be implemented some day,
165       possibly when the next version of Penguin hits CPAN.
166

POD ERRORS

168       Hey! The above document had some coding errors, which are explained
169       below:
170
171       Around line 769:
172           Can't have a 0 in =over 0
173
174
175
176perl v5.32.1                      2021-01-27                  Crypt::Primes(3)
Impressum