1.\" $OpenBSD: BN_generate_prime.3,v 1.19 2020/06/24 18:15:00 jmc Exp $
2.\" full merge up to: OpenSSL f987a4dd Jun 27 10:12:08 2019 +0200
3.\"
4.\" This file was written by Ulf Moeller <ulf@openssl.org>
5.\" Bodo Moeller <bodo@openssl.org>, and Matt Caswell <matt@openssl.org>.
6.\" Copyright (c) 2000, 2003, 2013, 2014, 2018 The OpenSSL Project.
7.\" All rights reserved.
8.\"
9.\" Redistribution and use in source and binary forms, with or without
10.\" modification, are permitted provided that the following conditions
11.\" are met:
12.\"
13.\" 1. Redistributions of source code must retain the above copyright
14.\"    notice, this list of conditions and the following disclaimer.
15.\"
16.\" 2. Redistributions in binary form must reproduce the above copyright
17.\"    notice, this list of conditions and the following disclaimer in
18.\"    the documentation and/or other materials provided with the
19.\"    distribution.
20.\"
21.\" 3. All advertising materials mentioning features or use of this
22.\"    software must display the following acknowledgment:
23.\"    "This product includes software developed by the OpenSSL Project
24.\"    for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
25.\"
26.\" 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
27.\"    endorse or promote products derived from this software without
28.\"    prior written permission. For written permission, please contact
29.\"    openssl-core@openssl.org.
30.\"
31.\" 5. Products derived from this software may not be called "OpenSSL"
32.\"    nor may "OpenSSL" appear in their names without prior written
33.\"    permission of the OpenSSL Project.
34.\"
35.\" 6. Redistributions of any form whatsoever must retain the following
36.\"    acknowledgment:
37.\"    "This product includes software developed by the OpenSSL Project
38.\"    for use in the OpenSSL Toolkit (http://www.openssl.org/)"
39.\"
40.\" THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
41.\" EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
42.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
43.\" PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE OpenSSL PROJECT OR
44.\" ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
45.\" SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
46.\" NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
47.\" LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
48.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
49.\" STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
50.\" ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
51.\" OF THE POSSIBILITY OF SUCH DAMAGE.
52.\"
53.Dd $Mdocdate: June 24 2020 $
54.Dt BN_GENERATE_PRIME 3
55.Os
56.Sh NAME
57.Nm BN_generate_prime_ex ,
58.Nm BN_is_prime_ex ,
59.Nm BN_is_prime_fasttest_ex ,
60.Nm BN_GENCB_call ,
61.Nm BN_GENCB_new ,
62.Nm BN_GENCB_free ,
63.Nm BN_GENCB_set_old ,
64.Nm BN_GENCB_set ,
65.Nm BN_GENCB_get_arg ,
66.Nm BN_generate_prime ,
67.Nm BN_is_prime ,
68.Nm BN_is_prime_fasttest
69.Nd generate primes and test for primality
70.Sh SYNOPSIS
71.In openssl/bn.h
72.Ft int
73.Fo BN_generate_prime_ex
74.Fa "BIGNUM *ret"
75.Fa "int bits"
76.Fa "int safe"
77.Fa "const BIGNUM *add"
78.Fa "const BIGNUM *rem"
79.Fa "BN_GENCB *cb"
80.Fc
81.Ft int
82.Fo BN_is_prime_ex
83.Fa "const BIGNUM *p"
84.Fa "int nchecks"
85.Fa "BN_CTX *ctx"
86.Fa "BN_GENCB *cb"
87.Fc
88.Ft int
89.Fo BN_is_prime_fasttest_ex
90.Fa "const BIGNUM *p"
91.Fa "int nchecks"
92.Fa "BN_CTX *ctx"
93.Fa "int do_trial_division"
94.Fa "BN_GENCB *cb"
95.Fc
96.Ft int
97.Fo BN_GENCB_call
98.Fa "BN_GENCB *cb"
99.Fa "int a"
100.Fa "int b"
101.Fc
102.Ft BN_GENCB *
103.Fn BN_GENCB_new void
104.Ft void
105.Fo BN_GENCB_free
106.Fa "BN_GENCB *cb"
107.Fc
108.Ft void
109.Fo BN_GENCB_set_old
110.Fa "BN_GENCB *gencb"
111.Fa "void (*callback)(int, int, void *)"
112.Fa "void *cb_arg"
113.Fc
114.Ft void
115.Fo BN_GENCB_set
116.Fa "BN_GENCB *gencb"
117.Fa "int (*callback)(int, int, BN_GENCB *)"
118.Fa "void *cb_arg"
119.Fc
120.Ft void *
121.Fo BN_GENCB_get_arg
122.Fa "BN_GENCB *cb"
123.Fc
124.Pp
125Deprecated:
126.Pp
127.Ft BIGNUM *
128.Fo BN_generate_prime
129.Fa "BIGNUM *ret"
130.Fa "int num"
131.Fa "int safe"
132.Fa "BIGNUM *add"
133.Fa "BIGNUM *rem"
134.Fa "void (*callback)(int, int, void *)"
135.Fa "void *cb_arg"
136.Fc
137.Ft int
138.Fo BN_is_prime
139.Fa "const BIGNUM *a"
140.Fa "int checks"
141.Fa "void (*callback)(int, int, void *)"
142.Fa "BN_CTX *ctx"
143.Fa "void *cb_arg"
144.Fc
145.Ft int
146.Fo BN_is_prime_fasttest
147.Fa "const BIGNUM *a"
148.Fa "int checks"
149.Fa "void (*callback)(int, int, void *)"
150.Fa "BN_CTX *ctx"
151.Fa "void *cb_arg"
152.Fa "int do_trial_division"
153.Fc
154.Sh DESCRIPTION
155.Fn BN_generate_prime_ex
156generates a pseudo-random prime number of at least bit length
157.Fa bits .
158The returned number is probably prime, but there is a very small
159probability of returning a non-prime number.
160If
161.Fa ret
162is not
163.Dv NULL ,
164it will be used to store the number.
165.Pp
166If
167.Fa cb
168is not
169.Dv NULL ,
170it is used as follows:
171.Bl -bullet
172.It
173.Fn BN_GENCB_call cb 0 i
174is called after generating the i-th potential prime number.
175.It
176While the number is being tested for primality,
177.Fn BN_GENCB_call cb 1 j
178is called as described below.
179.It
180When a prime has been found,
181.Fn BN_GENCB_call cb 2 i
182is called.
183.It
184The callers of
185.Fn BN_generate_prime_ex
186may call
187.Fn BN_GENCB_call
188with other values as described in their respective manual pages; see
189.Sx SEE ALSO .
190.El
191.Pp
192The prime may have to fulfill additional requirements for use in
193Diffie-Hellman key exchange:
194.Pp
195If
196.Fa add
197is not
198.Dv NULL ,
199the prime will fulfill the condition p %
200.Fa add
201==
202.Fa rem
203(p %
204.Fa add
205== 1 if
206.Fa rem
207==
208.Dv NULL )
209in order to suit a given generator.
210.Pp
211If
212.Fa safe
213is true, it will be a safe prime (i.e. a prime p so that (p-1)/2
214is also prime).
215.Pp
216.Fn BN_is_prime_ex
217and
218.Fn BN_is_prime_fasttest_ex
219test if the number
220.Fa p
221is prime.
222The following tests are performed until one of them shows that
223.Fa p
224is composite; if
225.Fa p
226passes all these tests, it is considered prime.
227.Pp
228.Fn BN_is_prime_fasttest_ex ,
229when called with
230.Fa do_trial_division
231== 1, first attempts trial division by a number of small primes;
232if no divisors are found by this test and
233.Fa cb
234is not
235.Dv NULL ,
236.Sy BN_GENCB_call(cb, 1, -1)
237is called.
238If
239.Fa do_trial_division
240== 0, this test is skipped.
241.Pp
242Both
243.Fn BN_is_prime_ex
244and
245.Fn BN_is_prime_fasttest_ex
246perform a Miller-Rabin probabilistic primality test with
247.Fa nchecks
248iterations.
249If
250.Fa nchecks
251==
252.Dv BN_prime_checks ,
253a number of iterations is used that yields a false positive rate
254of at most 2\(ha-64 for random input.
255The error rate depends on the size of the prime
256and goes down for bigger primes.
257The rate is 2\(ha-80 starting at 308 bits, 2\(ha-112 at 852 bits,
2582\(ha-128 at 1080 bits, 2\(ha-192 at 3747 bits
259and 2\(ha-256 at 6394 bits.
260.Pp
261When the source of the prime is not random or not trusted, the
262number of checks needs to be much higher to reach the same level
263of assurance: It should equal half of the targeted security level
264in bits (rounded up to the next integer if necessary).
265For instance, to reach the 128-bit security level,
266.Fa nchecks
267should be set to 64.
268.Pp
269If
270.Fa cb
271is not
272.Dv NULL ,
273.Fa BN_GENCB_call cb 1 j
274is called after the j-th iteration (j = 0, 1, ...).
275.Fa ctx
276is a pre-allocated
277.Vt BN_CTX
278(to save the overhead of allocating and freeing the structure in a
279loop), or
280.Dv NULL .
281.Pp
282.Fn BN_GENCB_call
283calls the callback function held in the
284.Vt BN_GENCB
285structure and passes the ints
286.Fa a
287and
288.Fa b
289as arguments.
290There are two types of
291.Vt BN_GENCB
292structures that are supported: "new" style and "old" style.
293New programs should prefer the "new" style, whilst the "old" style is
294provided for backwards compatibility purposes.
295.Pp
296A
297.Vt BN_GENCB
298structure should be created through a call to
299.Fn BN_GENCB_new
300and freed through a call to
301.Fn BN_GENCB_free .
302.Pp
303For "new" style callbacks a
304.Vt BN_GENCB
305structure should be initialised with a call to
306.Fn BN_GENCB_set ,
307where
308.Fa gencb
309is a
310.Vt BN_GENCB * ,
311.Fa callback
312is of type
313.Vt int (*callback)(int, int, BN_GENCB *)
314and
315.Fa cb_arg
316is a
317.Vt void * .
318"Old" style callbacks are the same except they are initialised with a
319call to
320.Fn BN_GENCB_set_old
321and
322.Fa callback
323is of type
324.Vt void (*callback)(int, int, void *) .
325.Pp
326A callback is invoked through a call to
327.Fn BN_GENCB_call .
328This will check the type of the callback and will invoke
329.Fn callback a b gencb
330for new style callbacks or
331.Fn callback a b cb_arg
332for old style.
333.Pp
334It is possible to obtain the argument associated with a
335.Vt BN_GENCB
336structure (set via a call to
337.Fn BN_GENCB_set
338or
339.Fn BN_GENCB_set_old )
340using
341.Fn BN_GENCB_get_arg .
342.Pp
343.Fn BN_generate_prime
344(deprecated) works in the same way as
345.Fn BN_generate_prime_ex
346but expects an old style callback function directly in the
347.Fa callback
348parameter, and an argument to pass to it in the
349.Fa cb_arg .
350Similarly
351.Fn BN_is_prime
352and
353.Fn BN_is_prime_fasttest
354are deprecated and can be compared to
355.Fn BN_is_prime_ex
356and
357.Fn BN_is_prime_fasttest_ex
358respectively.
359.Sh RETURN VALUES
360.Fn BN_generate_prime_ex
361returns 1 on success or 0 on error.
362.Pp
363.Fn BN_is_prime_ex ,
364.Fn BN_is_prime_fasttest_ex ,
365.Fn BN_is_prime ,
366and
367.Fn BN_is_prime_fasttest
368return 0 if the number is composite, 1 if it is prime with an error
369probability of less than
370.Pf 0.25^ Fa nchecks ,
371and -1 on error.
372.Pp
373.Fn BN_generate_prime
374returns the prime number on success,
375.Dv NULL
376otherwise.
377.Pp
378.Fn BN_GENCB_new
379returns a pointer to a
380.Vt BN_GENCB
381structure on success, or
382.Dv NULL
383otherwise.
384.Pp
385.Fn BN_GENCB_get_arg
386returns the argument previously associated with a
387.Vt BN_GENCB
388structure.
389.Pp
390Callback functions should return 1 on success or 0 on error.
391.Pp
392The error codes can be obtained by
393.Xr ERR_get_error 3 .
394.Sh SEE ALSO
395.Xr BN_new 3 ,
396.Xr DH_generate_parameters 3 ,
397.Xr DSA_generate_parameters 3 ,
398.Xr RSA_generate_key 3
399.Sh HISTORY
400.Fn BN_generate_prime
401and
402.Fn BN_is_prime
403first appeared in SSLeay 0.5.1 and had their
404.Fa cb_arg
405argument added in SSLeay 0.9.0.
406These two functions have been available since
407.Ox 2.4 .
408.Pp
409The
410.Fa ret
411argument to
412.Fn BN_generate_prime
413was added in SSLeay 0.9.1 and
414.Ox 2.6 .
415.Pp
416.Fn BN_is_prime_fasttest
417first appeared in OpenSSL 0.9.5 and has been available since
418.Ox 2.7 .
419.Pp
420.Fn BN_generate_prime_ex ,
421.Fn BN_is_prime_ex ,
422.Fn BN_is_prime_fasttest_ex ,
423.Fn BN_GENCB_call ,
424.Fn BN_GENCB_set_old ,
425and
426.Fn BN_GENCB_set
427first appeared in OpenSSL 0.9.8 and have been available since
428.Ox 4.5 .
429.Pp
430.Fn BN_GENCB_new ,
431.Fn BN_GENCB_free ,
432and
433.Fn BN_GENCB_get_arg
434first appeared in OpenSSL 1.1.0 and have been available since
435.Ox 6.3 .
436