1Crypt::Primes(3) User Contributed Perl Documentation Crypt::Primes(3)
2
6 Crypt::Primes - Provable Prime Number Generator suitable for
7 Cryptographic Applications.
8
10 $Revision: 0.49 $
11 $Date: 2001/06/11 01:04:23 $
12
14 # generate a random, provable 512-bit prime.
15 use Crypt::Primes qw(maurer);
17 my $prime = maurer (Size => 512);
18 # generate a random, provable 2048-bit prime and report
20 # progress on console.
21 my $another_prime = maurer (
23 Size => 2048,
24 Verbosity => 1
25 );
26 # generate a random 1024-bit prime and a group
29 # generator of Z*(n).
30 my $hash_ref = maurer (
32 Size => 1024,
33 Generator => 1,
34 Verbosity => 1
35 );
36
38 The codebase is stable, but the API will most definitely change in a
39 future release.
40
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 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
56 The following functions are availble for import. They must be
57 explicitely imported.
58 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 Size
66 Bitsize of the required prime number.
67 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 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 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 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 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 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 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 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
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
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
137 largeprimes(1), Crypt::Random(3), Math::Pari(3)
138
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
149 Vipul Ved Prakash, <mail@vipul.net>
150
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
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
168 Hey! The above document had some coding errors, which are explained
169 below:
170 Around line 769:
172 Can't have a 0 in =over 0
173perl v5.32.1 2021-01-27 Crypt::Primes(3)