/src/boringssl/include/openssl/bn.h
Line | Count | Source (jump to first uncovered line) |
1 | | /* Copyright (C) 1995-1997 Eric Young (eay@cryptsoft.com) |
2 | | * All rights reserved. |
3 | | * |
4 | | * This package is an SSL implementation written |
5 | | * by Eric Young (eay@cryptsoft.com). |
6 | | * The implementation was written so as to conform with Netscapes SSL. |
7 | | * |
8 | | * This library is free for commercial and non-commercial use as long as |
9 | | * the following conditions are aheared to. The following conditions |
10 | | * apply to all code found in this distribution, be it the RC4, RSA, |
11 | | * lhash, DES, etc., code; not just the SSL code. The SSL documentation |
12 | | * included with this distribution is covered by the same copyright terms |
13 | | * except that the holder is Tim Hudson (tjh@cryptsoft.com). |
14 | | * |
15 | | * Copyright remains Eric Young's, and as such any Copyright notices in |
16 | | * the code are not to be removed. |
17 | | * If this package is used in a product, Eric Young should be given attribution |
18 | | * as the author of the parts of the library used. |
19 | | * This can be in the form of a textual message at program startup or |
20 | | * in documentation (online or textual) provided with the package. |
21 | | * |
22 | | * Redistribution and use in source and binary forms, with or without |
23 | | * modification, are permitted provided that the following conditions |
24 | | * are met: |
25 | | * 1. Redistributions of source code must retain the copyright |
26 | | * notice, this list of conditions and the following disclaimer. |
27 | | * 2. Redistributions in binary form must reproduce the above copyright |
28 | | * notice, this list of conditions and the following disclaimer in the |
29 | | * documentation and/or other materials provided with the distribution. |
30 | | * 3. All advertising materials mentioning features or use of this software |
31 | | * must display the following acknowledgement: |
32 | | * "This product includes cryptographic software written by |
33 | | * Eric Young (eay@cryptsoft.com)" |
34 | | * The word 'cryptographic' can be left out if the rouines from the library |
35 | | * being used are not cryptographic related :-). |
36 | | * 4. If you include any Windows specific code (or a derivative thereof) from |
37 | | * the apps directory (application code) you must include an acknowledgement: |
38 | | * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)" |
39 | | * |
40 | | * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND |
41 | | * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
42 | | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
43 | | * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE |
44 | | * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL |
45 | | * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS |
46 | | * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) |
47 | | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT |
48 | | * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY |
49 | | * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF |
50 | | * SUCH DAMAGE. |
51 | | * |
52 | | * The licence and distribution terms for any publically available version or |
53 | | * derivative of this code cannot be changed. i.e. this code cannot simply be |
54 | | * copied and put under another distribution licence |
55 | | * [including the GNU Public Licence.] |
56 | | */ |
57 | | /* ==================================================================== |
58 | | * Copyright (c) 1998-2006 The OpenSSL Project. All rights reserved. |
59 | | * |
60 | | * Redistribution and use in source and binary forms, with or without |
61 | | * modification, are permitted provided that the following conditions |
62 | | * are met: |
63 | | * |
64 | | * 1. Redistributions of source code must retain the above copyright |
65 | | * notice, this list of conditions and the following disclaimer. |
66 | | * |
67 | | * 2. Redistributions in binary form must reproduce the above copyright |
68 | | * notice, this list of conditions and the following disclaimer in |
69 | | * the documentation and/or other materials provided with the |
70 | | * distribution. |
71 | | * |
72 | | * 3. All advertising materials mentioning features or use of this |
73 | | * software must display the following acknowledgment: |
74 | | * "This product includes software developed by the OpenSSL Project |
75 | | * for use in the OpenSSL Toolkit. (http://www.openssl.org/)" |
76 | | * |
77 | | * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to |
78 | | * endorse or promote products derived from this software without |
79 | | * prior written permission. For written permission, please contact |
80 | | * openssl-core@openssl.org. |
81 | | * |
82 | | * 5. Products derived from this software may not be called "OpenSSL" |
83 | | * nor may "OpenSSL" appear in their names without prior written |
84 | | * permission of the OpenSSL Project. |
85 | | * |
86 | | * 6. Redistributions of any form whatsoever must retain the following |
87 | | * acknowledgment: |
88 | | * "This product includes software developed by the OpenSSL Project |
89 | | * for use in the OpenSSL Toolkit (http://www.openssl.org/)" |
90 | | * |
91 | | * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY |
92 | | * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
93 | | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR |
94 | | * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR |
95 | | * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, |
96 | | * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT |
97 | | * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; |
98 | | * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) |
99 | | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, |
100 | | * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) |
101 | | * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED |
102 | | * OF THE POSSIBILITY OF SUCH DAMAGE. |
103 | | * ==================================================================== |
104 | | * |
105 | | * This product includes cryptographic software written by Eric Young |
106 | | * (eay@cryptsoft.com). This product includes software written by Tim |
107 | | * Hudson (tjh@cryptsoft.com). |
108 | | * |
109 | | */ |
110 | | /* ==================================================================== |
111 | | * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED. |
112 | | * |
113 | | * Portions of the attached software ("Contribution") are developed by |
114 | | * SUN MICROSYSTEMS, INC., and are contributed to the OpenSSL project. |
115 | | * |
116 | | * The Contribution is licensed pursuant to the Eric Young open source |
117 | | * license provided above. |
118 | | * |
119 | | * The binary polynomial arithmetic software is originally written by |
120 | | * Sheueling Chang Shantz and Douglas Stebila of Sun Microsystems |
121 | | * Laboratories. */ |
122 | | |
123 | | #ifndef OPENSSL_HEADER_BN_H |
124 | | #define OPENSSL_HEADER_BN_H |
125 | | |
126 | | #include <openssl/base.h> |
127 | | #include <openssl/thread.h> |
128 | | |
129 | | #include <inttypes.h> // for PRIu64 and friends |
130 | | #include <stdio.h> // for FILE* |
131 | | |
132 | | #if defined(__cplusplus) |
133 | | extern "C" { |
134 | | #endif |
135 | | |
136 | | |
137 | | // BN provides support for working with arbitrary sized integers. For example, |
138 | | // although the largest integer supported by the compiler might be 64 bits, BN |
139 | | // will allow you to work with much larger numbers. |
140 | | // |
141 | | // This library is developed for use inside BoringSSL, and uses implementation |
142 | | // strategies that may not be ideal for other applications. Non-cryptographic |
143 | | // uses should use a more general-purpose integer library, especially if |
144 | | // performance-sensitive. |
145 | | // |
146 | | // Many functions in BN scale quadratically or higher in the bit length of their |
147 | | // input. Callers at this layer are assumed to have capped input sizes within |
148 | | // their performance tolerances. |
149 | | |
150 | | |
151 | | // BN_ULONG is the native word size when working with big integers. |
152 | | // |
153 | | // Note: on some platforms, inttypes.h does not define print format macros in |
154 | | // C++ unless |__STDC_FORMAT_MACROS| defined. This is due to text in C99 which |
155 | | // was never adopted in any C++ standard and explicitly overruled in C++11. As |
156 | | // this is a public header, bn.h does not define |__STDC_FORMAT_MACROS| itself. |
157 | | // Projects which use |BN_*_FMT*| with outdated C headers may need to define it |
158 | | // externally. |
159 | | #if defined(OPENSSL_64_BIT) |
160 | | typedef uint64_t BN_ULONG; |
161 | | #define BN_BITS2 64 |
162 | | #define BN_DEC_FMT1 "%" PRIu64 |
163 | | #define BN_HEX_FMT1 "%" PRIx64 |
164 | | #define BN_HEX_FMT2 "%016" PRIx64 |
165 | | #elif defined(OPENSSL_32_BIT) |
166 | | typedef uint32_t BN_ULONG; |
167 | | #define BN_BITS2 32 |
168 | | #define BN_DEC_FMT1 "%" PRIu32 |
169 | | #define BN_HEX_FMT1 "%" PRIx32 |
170 | | #define BN_HEX_FMT2 "%08" PRIx32 |
171 | | #else |
172 | | #error "Must define either OPENSSL_32_BIT or OPENSSL_64_BIT" |
173 | | #endif |
174 | | |
175 | | |
176 | | // Allocation and freeing. |
177 | | |
178 | | // BN_new creates a new, allocated BIGNUM and initialises it. |
179 | | OPENSSL_EXPORT BIGNUM *BN_new(void); |
180 | | |
181 | | // BN_init initialises a stack allocated |BIGNUM|. |
182 | | OPENSSL_EXPORT void BN_init(BIGNUM *bn); |
183 | | |
184 | | // BN_free frees the data referenced by |bn| and, if |bn| was originally |
185 | | // allocated on the heap, frees |bn| also. |
186 | | OPENSSL_EXPORT void BN_free(BIGNUM *bn); |
187 | | |
188 | | // BN_clear_free erases and frees the data referenced by |bn| and, if |bn| was |
189 | | // originally allocated on the heap, frees |bn| also. |
190 | | OPENSSL_EXPORT void BN_clear_free(BIGNUM *bn); |
191 | | |
192 | | // BN_dup allocates a new BIGNUM and sets it equal to |src|. It returns the |
193 | | // allocated BIGNUM on success or NULL otherwise. |
194 | | OPENSSL_EXPORT BIGNUM *BN_dup(const BIGNUM *src); |
195 | | |
196 | | // BN_copy sets |dest| equal to |src| and returns |dest| or NULL on allocation |
197 | | // failure. |
198 | | OPENSSL_EXPORT BIGNUM *BN_copy(BIGNUM *dest, const BIGNUM *src); |
199 | | |
200 | | // BN_clear sets |bn| to zero and erases the old data. |
201 | | OPENSSL_EXPORT void BN_clear(BIGNUM *bn); |
202 | | |
203 | | // BN_value_one returns a static BIGNUM with value 1. |
204 | | OPENSSL_EXPORT const BIGNUM *BN_value_one(void); |
205 | | |
206 | | |
207 | | // Basic functions. |
208 | | |
209 | | // BN_num_bits returns the minimum number of bits needed to represent the |
210 | | // absolute value of |bn|. |
211 | | OPENSSL_EXPORT unsigned BN_num_bits(const BIGNUM *bn); |
212 | | |
213 | | // BN_num_bytes returns the minimum number of bytes needed to represent the |
214 | | // absolute value of |bn|. |
215 | | // |
216 | | // While |size_t| is the preferred type for byte counts, callers can assume that |
217 | | // |BIGNUM|s are bounded such that this value, and its corresponding bit count, |
218 | | // will always fit in |int|. |
219 | | OPENSSL_EXPORT unsigned BN_num_bytes(const BIGNUM *bn); |
220 | | |
221 | | // BN_zero sets |bn| to zero. |
222 | | OPENSSL_EXPORT void BN_zero(BIGNUM *bn); |
223 | | |
224 | | // BN_one sets |bn| to one. It returns one on success or zero on allocation |
225 | | // failure. |
226 | | OPENSSL_EXPORT int BN_one(BIGNUM *bn); |
227 | | |
228 | | // BN_set_word sets |bn| to |value|. It returns one on success or zero on |
229 | | // allocation failure. |
230 | | OPENSSL_EXPORT int BN_set_word(BIGNUM *bn, BN_ULONG value); |
231 | | |
232 | | // BN_set_u64 sets |bn| to |value|. It returns one on success or zero on |
233 | | // allocation failure. |
234 | | OPENSSL_EXPORT int BN_set_u64(BIGNUM *bn, uint64_t value); |
235 | | |
236 | | // BN_set_negative sets the sign of |bn|. |
237 | | OPENSSL_EXPORT void BN_set_negative(BIGNUM *bn, int sign); |
238 | | |
239 | | // BN_is_negative returns one if |bn| is negative and zero otherwise. |
240 | | OPENSSL_EXPORT int BN_is_negative(const BIGNUM *bn); |
241 | | |
242 | | |
243 | | // Conversion functions. |
244 | | |
245 | | // BN_bin2bn sets |*ret| to the value of |len| bytes from |in|, interpreted as |
246 | | // a big-endian number, and returns |ret|. If |ret| is NULL then a fresh |
247 | | // |BIGNUM| is allocated and returned. It returns NULL on allocation |
248 | | // failure. |
249 | | OPENSSL_EXPORT BIGNUM *BN_bin2bn(const uint8_t *in, size_t len, BIGNUM *ret); |
250 | | |
251 | | // BN_bn2bin serialises the absolute value of |in| to |out| as a big-endian |
252 | | // integer, which must have |BN_num_bytes| of space available. It returns the |
253 | | // number of bytes written. Note this function leaks the magnitude of |in|. If |
254 | | // |in| is secret, use |BN_bn2bin_padded| instead. |
255 | | OPENSSL_EXPORT size_t BN_bn2bin(const BIGNUM *in, uint8_t *out); |
256 | | |
257 | | // BN_lebin2bn sets |*ret| to the value of |len| bytes from |in|, interpreted as |
258 | | // a little-endian number, and returns |ret|. If |ret| is NULL then a fresh |
259 | | // |BIGNUM| is allocated and returned. It returns NULL on allocation |
260 | | // failure. |
261 | | OPENSSL_EXPORT BIGNUM *BN_lebin2bn(const uint8_t *in, size_t len, BIGNUM *ret); |
262 | | |
263 | | // BN_bn2le_padded serialises the absolute value of |in| to |out| as a |
264 | | // little-endian integer, which must have |len| of space available, padding |
265 | | // out the remainder of out with zeros. If |len| is smaller than |BN_num_bytes|, |
266 | | // the function fails and returns 0. Otherwise, it returns 1. |
267 | | OPENSSL_EXPORT int BN_bn2le_padded(uint8_t *out, size_t len, const BIGNUM *in); |
268 | | |
269 | | // BN_bn2bin_padded serialises the absolute value of |in| to |out| as a |
270 | | // big-endian integer. The integer is padded with leading zeros up to size |
271 | | // |len|. If |len| is smaller than |BN_num_bytes|, the function fails and |
272 | | // returns 0. Otherwise, it returns 1. |
273 | | OPENSSL_EXPORT int BN_bn2bin_padded(uint8_t *out, size_t len, const BIGNUM *in); |
274 | | |
275 | | // BN_bn2cbb_padded behaves like |BN_bn2bin_padded| but writes to a |CBB|. |
276 | | OPENSSL_EXPORT int BN_bn2cbb_padded(CBB *out, size_t len, const BIGNUM *in); |
277 | | |
278 | | // BN_bn2hex returns an allocated string that contains a NUL-terminated, hex |
279 | | // representation of |bn|. If |bn| is negative, the first char in the resulting |
280 | | // string will be '-'. Returns NULL on allocation failure. |
281 | | OPENSSL_EXPORT char *BN_bn2hex(const BIGNUM *bn); |
282 | | |
283 | | // BN_hex2bn parses the leading hex number from |in|, which may be proceeded by |
284 | | // a '-' to indicate a negative number and may contain trailing, non-hex data. |
285 | | // If |outp| is not NULL, it constructs a BIGNUM equal to the hex number and |
286 | | // stores it in |*outp|. If |*outp| is NULL then it allocates a new BIGNUM and |
287 | | // updates |*outp|. It returns the number of bytes of |in| processed or zero on |
288 | | // error. |
289 | | OPENSSL_EXPORT int BN_hex2bn(BIGNUM **outp, const char *in); |
290 | | |
291 | | // BN_bn2dec returns an allocated string that contains a NUL-terminated, |
292 | | // decimal representation of |bn|. If |bn| is negative, the first char in the |
293 | | // resulting string will be '-'. Returns NULL on allocation failure. |
294 | | // |
295 | | // Converting an arbitrarily large integer to decimal is quadratic in the bit |
296 | | // length of |a|. This function assumes the caller has capped the input within |
297 | | // performance tolerances. |
298 | | OPENSSL_EXPORT char *BN_bn2dec(const BIGNUM *a); |
299 | | |
300 | | // BN_dec2bn parses the leading decimal number from |in|, which may be |
301 | | // proceeded by a '-' to indicate a negative number and may contain trailing, |
302 | | // non-decimal data. If |outp| is not NULL, it constructs a BIGNUM equal to the |
303 | | // decimal number and stores it in |*outp|. If |*outp| is NULL then it |
304 | | // allocates a new BIGNUM and updates |*outp|. It returns the number of bytes |
305 | | // of |in| processed or zero on error. |
306 | | // |
307 | | // Converting an arbitrarily large integer to decimal is quadratic in the bit |
308 | | // length of |a|. This function assumes the caller has capped the input within |
309 | | // performance tolerances. |
310 | | OPENSSL_EXPORT int BN_dec2bn(BIGNUM **outp, const char *in); |
311 | | |
312 | | // BN_asc2bn acts like |BN_dec2bn| or |BN_hex2bn| depending on whether |in| |
313 | | // begins with "0X" or "0x" (indicating hex) or not (indicating decimal). A |
314 | | // leading '-' is still permitted and comes before the optional 0X/0x. It |
315 | | // returns one on success or zero on error. |
316 | | OPENSSL_EXPORT int BN_asc2bn(BIGNUM **outp, const char *in); |
317 | | |
318 | | // BN_print writes a hex encoding of |a| to |bio|. It returns one on success |
319 | | // and zero on error. |
320 | | OPENSSL_EXPORT int BN_print(BIO *bio, const BIGNUM *a); |
321 | | |
322 | | // BN_print_fp acts like |BIO_print|, but wraps |fp| in a |BIO| first. |
323 | | OPENSSL_EXPORT int BN_print_fp(FILE *fp, const BIGNUM *a); |
324 | | |
325 | | // BN_get_word returns the absolute value of |bn| as a single word. If |bn| is |
326 | | // too large to be represented as a single word, the maximum possible value |
327 | | // will be returned. |
328 | | OPENSSL_EXPORT BN_ULONG BN_get_word(const BIGNUM *bn); |
329 | | |
330 | | // BN_get_u64 sets |*out| to the absolute value of |bn| as a |uint64_t| and |
331 | | // returns one. If |bn| is too large to be represented as a |uint64_t|, it |
332 | | // returns zero. |
333 | | OPENSSL_EXPORT int BN_get_u64(const BIGNUM *bn, uint64_t *out); |
334 | | |
335 | | |
336 | | // ASN.1 functions. |
337 | | |
338 | | // BN_parse_asn1_unsigned parses a non-negative DER INTEGER from |cbs| writes |
339 | | // the result to |ret|. It returns one on success and zero on failure. |
340 | | OPENSSL_EXPORT int BN_parse_asn1_unsigned(CBS *cbs, BIGNUM *ret); |
341 | | |
342 | | // BN_marshal_asn1 marshals |bn| as a non-negative DER INTEGER and appends the |
343 | | // result to |cbb|. It returns one on success and zero on failure. |
344 | | OPENSSL_EXPORT int BN_marshal_asn1(CBB *cbb, const BIGNUM *bn); |
345 | | |
346 | | |
347 | | // BIGNUM pools. |
348 | | // |
349 | | // Certain BIGNUM operations need to use many temporary variables and |
350 | | // allocating and freeing them can be quite slow. Thus such operations typically |
351 | | // take a |BN_CTX| parameter, which contains a pool of |BIGNUMs|. The |ctx| |
352 | | // argument to a public function may be NULL, in which case a local |BN_CTX| |
353 | | // will be created just for the lifetime of that call. |
354 | | // |
355 | | // A function must call |BN_CTX_start| first. Then, |BN_CTX_get| may be called |
356 | | // repeatedly to obtain temporary |BIGNUM|s. All |BN_CTX_get| calls must be made |
357 | | // before calling any other functions that use the |ctx| as an argument. |
358 | | // |
359 | | // Finally, |BN_CTX_end| must be called before returning from the function. |
360 | | // When |BN_CTX_end| is called, the |BIGNUM| pointers obtained from |
361 | | // |BN_CTX_get| become invalid. |
362 | | |
363 | | // BN_CTX_new returns a new, empty BN_CTX or NULL on allocation failure. |
364 | | OPENSSL_EXPORT BN_CTX *BN_CTX_new(void); |
365 | | |
366 | | // BN_CTX_free frees all BIGNUMs contained in |ctx| and then frees |ctx| |
367 | | // itself. |
368 | | OPENSSL_EXPORT void BN_CTX_free(BN_CTX *ctx); |
369 | | |
370 | | // BN_CTX_start "pushes" a new entry onto the |ctx| stack and allows future |
371 | | // calls to |BN_CTX_get|. |
372 | | OPENSSL_EXPORT void BN_CTX_start(BN_CTX *ctx); |
373 | | |
374 | | // BN_CTX_get returns a new |BIGNUM|, or NULL on allocation failure. Once |
375 | | // |BN_CTX_get| has returned NULL, all future calls will also return NULL until |
376 | | // |BN_CTX_end| is called. |
377 | | OPENSSL_EXPORT BIGNUM *BN_CTX_get(BN_CTX *ctx); |
378 | | |
379 | | // BN_CTX_end invalidates all |BIGNUM|s returned from |BN_CTX_get| since the |
380 | | // matching |BN_CTX_start| call. |
381 | | OPENSSL_EXPORT void BN_CTX_end(BN_CTX *ctx); |
382 | | |
383 | | |
384 | | // Simple arithmetic |
385 | | |
386 | | // BN_add sets |r| = |a| + |b|, where |r| may be the same pointer as either |a| |
387 | | // or |b|. It returns one on success and zero on allocation failure. |
388 | | OPENSSL_EXPORT int BN_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b); |
389 | | |
390 | | // BN_uadd sets |r| = |a| + |b|, considering only the absolute values of |a| and |
391 | | // |b|. |r| may be the same pointer as either |a| or |b|. It returns one on |
392 | | // success and zero on allocation failure. |
393 | | OPENSSL_EXPORT int BN_uadd(BIGNUM *r, const BIGNUM *a, const BIGNUM *b); |
394 | | |
395 | | // BN_add_word adds |w| to |a|. It returns one on success and zero otherwise. |
396 | | OPENSSL_EXPORT int BN_add_word(BIGNUM *a, BN_ULONG w); |
397 | | |
398 | | // BN_sub sets |r| = |a| - |b|, where |r| may be the same pointer as either |a| |
399 | | // or |b|. It returns one on success and zero on allocation failure. |
400 | | OPENSSL_EXPORT int BN_sub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b); |
401 | | |
402 | | // BN_usub sets |r| = |a| - |b|, considering only the absolute values of |a| and |
403 | | // |b|. The result must be non-negative, i.e. |b| <= |a|. |r| may be the same |
404 | | // pointer as either |a| or |b|. It returns one on success and zero on error. |
405 | | OPENSSL_EXPORT int BN_usub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b); |
406 | | |
407 | | // BN_sub_word subtracts |w| from |a|. It returns one on success and zero on |
408 | | // allocation failure. |
409 | | OPENSSL_EXPORT int BN_sub_word(BIGNUM *a, BN_ULONG w); |
410 | | |
411 | | // BN_mul sets |r| = |a| * |b|, where |r| may be the same pointer as |a| or |
412 | | // |b|. Returns one on success and zero otherwise. |
413 | | OPENSSL_EXPORT int BN_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, |
414 | | BN_CTX *ctx); |
415 | | |
416 | | // BN_mul_word sets |bn| = |bn| * |w|. It returns one on success or zero on |
417 | | // allocation failure. |
418 | | OPENSSL_EXPORT int BN_mul_word(BIGNUM *bn, BN_ULONG w); |
419 | | |
420 | | // BN_sqr sets |r| = |a|^2 (i.e. squares), where |r| may be the same pointer as |
421 | | // |a|. Returns one on success and zero otherwise. This is more efficient than |
422 | | // BN_mul(r, a, a, ctx). |
423 | | OPENSSL_EXPORT int BN_sqr(BIGNUM *r, const BIGNUM *a, BN_CTX *ctx); |
424 | | |
425 | | // BN_div divides |numerator| by |divisor| and places the result in |quotient| |
426 | | // and the remainder in |rem|. Either of |quotient| or |rem| may be NULL, in |
427 | | // which case the respective value is not returned. It returns one on success or |
428 | | // zero on error. It is an error condition if |divisor| is zero. |
429 | | // |
430 | | // The outputs will be such that |quotient| * |divisor| + |rem| = |numerator|, |
431 | | // with the quotient rounded towards zero. Thus, if |numerator| is negative, |
432 | | // |rem| will be zero or negative. If |divisor| is negative, the sign of |
433 | | // |quotient| will be flipped to compensate but otherwise rounding will be as if |
434 | | // |divisor| were its absolute value. |
435 | | OPENSSL_EXPORT int BN_div(BIGNUM *quotient, BIGNUM *rem, |
436 | | const BIGNUM *numerator, const BIGNUM *divisor, |
437 | | BN_CTX *ctx); |
438 | | |
439 | | // BN_div_word sets |numerator| = |numerator|/|divisor| and returns the |
440 | | // remainder or (BN_ULONG)-1 on error. |
441 | | OPENSSL_EXPORT BN_ULONG BN_div_word(BIGNUM *numerator, BN_ULONG divisor); |
442 | | |
443 | | // BN_sqrt sets |*out_sqrt| (which may be the same |BIGNUM| as |in|) to the |
444 | | // square root of |in|, using |ctx|. It returns one on success or zero on |
445 | | // error. Negative numbers and non-square numbers will result in an error with |
446 | | // appropriate errors on the error queue. |
447 | | OPENSSL_EXPORT int BN_sqrt(BIGNUM *out_sqrt, const BIGNUM *in, BN_CTX *ctx); |
448 | | |
449 | | |
450 | | // Comparison functions |
451 | | |
452 | | // BN_cmp returns a value less than, equal to or greater than zero if |a| is |
453 | | // less than, equal to or greater than |b|, respectively. |
454 | | OPENSSL_EXPORT int BN_cmp(const BIGNUM *a, const BIGNUM *b); |
455 | | |
456 | | // BN_cmp_word is like |BN_cmp| except it takes its second argument as a |
457 | | // |BN_ULONG| instead of a |BIGNUM|. |
458 | | OPENSSL_EXPORT int BN_cmp_word(const BIGNUM *a, BN_ULONG b); |
459 | | |
460 | | // BN_ucmp returns a value less than, equal to or greater than zero if the |
461 | | // absolute value of |a| is less than, equal to or greater than the absolute |
462 | | // value of |b|, respectively. |
463 | | OPENSSL_EXPORT int BN_ucmp(const BIGNUM *a, const BIGNUM *b); |
464 | | |
465 | | // BN_equal_consttime returns one if |a| is equal to |b|, and zero otherwise. |
466 | | // It takes an amount of time dependent on the sizes of |a| and |b|, but |
467 | | // independent of the contents (including the signs) of |a| and |b|. |
468 | | OPENSSL_EXPORT int BN_equal_consttime(const BIGNUM *a, const BIGNUM *b); |
469 | | |
470 | | // BN_abs_is_word returns one if the absolute value of |bn| equals |w| and zero |
471 | | // otherwise. |
472 | | OPENSSL_EXPORT int BN_abs_is_word(const BIGNUM *bn, BN_ULONG w); |
473 | | |
474 | | // BN_is_zero returns one if |bn| is zero and zero otherwise. |
475 | | OPENSSL_EXPORT int BN_is_zero(const BIGNUM *bn); |
476 | | |
477 | | // BN_is_one returns one if |bn| equals one and zero otherwise. |
478 | | OPENSSL_EXPORT int BN_is_one(const BIGNUM *bn); |
479 | | |
480 | | // BN_is_word returns one if |bn| is exactly |w| and zero otherwise. |
481 | | OPENSSL_EXPORT int BN_is_word(const BIGNUM *bn, BN_ULONG w); |
482 | | |
483 | | // BN_is_odd returns one if |bn| is odd and zero otherwise. |
484 | | OPENSSL_EXPORT int BN_is_odd(const BIGNUM *bn); |
485 | | |
486 | | // BN_is_pow2 returns 1 if |a| is a power of two, and 0 otherwise. |
487 | | OPENSSL_EXPORT int BN_is_pow2(const BIGNUM *a); |
488 | | |
489 | | |
490 | | // Bitwise operations. |
491 | | |
492 | | // BN_lshift sets |r| equal to |a| << n. The |a| and |r| arguments may be the |
493 | | // same |BIGNUM|. It returns one on success and zero on allocation failure. |
494 | | OPENSSL_EXPORT int BN_lshift(BIGNUM *r, const BIGNUM *a, int n); |
495 | | |
496 | | // BN_lshift1 sets |r| equal to |a| << 1, where |r| and |a| may be the same |
497 | | // pointer. It returns one on success and zero on allocation failure. |
498 | | OPENSSL_EXPORT int BN_lshift1(BIGNUM *r, const BIGNUM *a); |
499 | | |
500 | | // BN_rshift sets |r| equal to |a| >> n, where |r| and |a| may be the same |
501 | | // pointer. It returns one on success and zero on allocation failure. |
502 | | OPENSSL_EXPORT int BN_rshift(BIGNUM *r, const BIGNUM *a, int n); |
503 | | |
504 | | // BN_rshift1 sets |r| equal to |a| >> 1, where |r| and |a| may be the same |
505 | | // pointer. It returns one on success and zero on allocation failure. |
506 | | OPENSSL_EXPORT int BN_rshift1(BIGNUM *r, const BIGNUM *a); |
507 | | |
508 | | // BN_set_bit sets the |n|th, least-significant bit in |a|. For example, if |a| |
509 | | // is 2 then setting bit zero will make it 3. It returns one on success or zero |
510 | | // on allocation failure. |
511 | | OPENSSL_EXPORT int BN_set_bit(BIGNUM *a, int n); |
512 | | |
513 | | // BN_clear_bit clears the |n|th, least-significant bit in |a|. For example, if |
514 | | // |a| is 3, clearing bit zero will make it two. It returns one on success or |
515 | | // zero on allocation failure. |
516 | | OPENSSL_EXPORT int BN_clear_bit(BIGNUM *a, int n); |
517 | | |
518 | | // BN_is_bit_set returns one if the |n|th least-significant bit in |a| exists |
519 | | // and is set. Otherwise, it returns zero. |
520 | | OPENSSL_EXPORT int BN_is_bit_set(const BIGNUM *a, int n); |
521 | | |
522 | | // BN_mask_bits truncates |a| so that it is only |n| bits long. It returns one |
523 | | // on success or zero if |n| is negative. |
524 | | // |
525 | | // This differs from OpenSSL which additionally returns zero if |a|'s word |
526 | | // length is less than or equal to |n|, rounded down to a number of words. Note |
527 | | // word size is platform-dependent, so this behavior is also difficult to rely |
528 | | // on in OpenSSL and not very useful. |
529 | | OPENSSL_EXPORT int BN_mask_bits(BIGNUM *a, int n); |
530 | | |
531 | | // BN_count_low_zero_bits returns the number of low-order zero bits in |bn|, or |
532 | | // the number of factors of two which divide it. It returns zero if |bn| is |
533 | | // zero. |
534 | | OPENSSL_EXPORT int BN_count_low_zero_bits(const BIGNUM *bn); |
535 | | |
536 | | |
537 | | // Modulo arithmetic. |
538 | | |
539 | | // BN_mod_word returns |a| mod |w| or (BN_ULONG)-1 on error. |
540 | | OPENSSL_EXPORT BN_ULONG BN_mod_word(const BIGNUM *a, BN_ULONG w); |
541 | | |
542 | | // BN_mod_pow2 sets |r| = |a| mod 2^|e|. It returns 1 on success and |
543 | | // 0 on error. |
544 | | OPENSSL_EXPORT int BN_mod_pow2(BIGNUM *r, const BIGNUM *a, size_t e); |
545 | | |
546 | | // BN_nnmod_pow2 sets |r| = |a| mod 2^|e| where |r| is always positive. |
547 | | // It returns 1 on success and 0 on error. |
548 | | OPENSSL_EXPORT int BN_nnmod_pow2(BIGNUM *r, const BIGNUM *a, size_t e); |
549 | | |
550 | | // BN_mod is a helper macro that calls |BN_div| and discards the quotient. |
551 | | #define BN_mod(rem, numerator, divisor, ctx) \ |
552 | 57.6k | BN_div(NULL, (rem), (numerator), (divisor), (ctx)) |
553 | | |
554 | | // BN_nnmod is a non-negative modulo function. It acts like |BN_mod|, but 0 <= |
555 | | // |rem| < |divisor| is always true. It returns one on success and zero on |
556 | | // error. |
557 | | OPENSSL_EXPORT int BN_nnmod(BIGNUM *rem, const BIGNUM *numerator, |
558 | | const BIGNUM *divisor, BN_CTX *ctx); |
559 | | |
560 | | // BN_mod_add sets |r| = |a| + |b| mod |m|. It returns one on success and zero |
561 | | // on error. |
562 | | OPENSSL_EXPORT int BN_mod_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, |
563 | | const BIGNUM *m, BN_CTX *ctx); |
564 | | |
565 | | // BN_mod_add_quick acts like |BN_mod_add| but requires that |a| and |b| be |
566 | | // non-negative and less than |m|. |
567 | | OPENSSL_EXPORT int BN_mod_add_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, |
568 | | const BIGNUM *m); |
569 | | |
570 | | // BN_mod_sub sets |r| = |a| - |b| mod |m|. It returns one on success and zero |
571 | | // on error. |
572 | | OPENSSL_EXPORT int BN_mod_sub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, |
573 | | const BIGNUM *m, BN_CTX *ctx); |
574 | | |
575 | | // BN_mod_sub_quick acts like |BN_mod_sub| but requires that |a| and |b| be |
576 | | // non-negative and less than |m|. |
577 | | OPENSSL_EXPORT int BN_mod_sub_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, |
578 | | const BIGNUM *m); |
579 | | |
580 | | // BN_mod_mul sets |r| = |a|*|b| mod |m|. It returns one on success and zero |
581 | | // on error. |
582 | | OPENSSL_EXPORT int BN_mod_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, |
583 | | const BIGNUM *m, BN_CTX *ctx); |
584 | | |
585 | | // BN_mod_sqr sets |r| = |a|^2 mod |m|. It returns one on success and zero |
586 | | // on error. |
587 | | OPENSSL_EXPORT int BN_mod_sqr(BIGNUM *r, const BIGNUM *a, const BIGNUM *m, |
588 | | BN_CTX *ctx); |
589 | | |
590 | | // BN_mod_lshift sets |r| = (|a| << n) mod |m|, where |r| and |a| may be the |
591 | | // same pointer. It returns one on success and zero on error. |
592 | | OPENSSL_EXPORT int BN_mod_lshift(BIGNUM *r, const BIGNUM *a, int n, |
593 | | const BIGNUM *m, BN_CTX *ctx); |
594 | | |
595 | | // BN_mod_lshift_quick acts like |BN_mod_lshift| but requires that |a| be |
596 | | // non-negative and less than |m|. |
597 | | OPENSSL_EXPORT int BN_mod_lshift_quick(BIGNUM *r, const BIGNUM *a, int n, |
598 | | const BIGNUM *m); |
599 | | |
600 | | // BN_mod_lshift1 sets |r| = (|a| << 1) mod |m|, where |r| and |a| may be the |
601 | | // same pointer. It returns one on success and zero on error. |
602 | | OPENSSL_EXPORT int BN_mod_lshift1(BIGNUM *r, const BIGNUM *a, const BIGNUM *m, |
603 | | BN_CTX *ctx); |
604 | | |
605 | | // BN_mod_lshift1_quick acts like |BN_mod_lshift1| but requires that |a| be |
606 | | // non-negative and less than |m|. |
607 | | OPENSSL_EXPORT int BN_mod_lshift1_quick(BIGNUM *r, const BIGNUM *a, |
608 | | const BIGNUM *m); |
609 | | |
610 | | // BN_mod_sqrt returns a newly-allocated |BIGNUM|, r, such that |
611 | | // r^2 == a (mod p). It returns NULL on error or if |a| is not a square mod |p|. |
612 | | // In the latter case, it will add |BN_R_NOT_A_SQUARE| to the error queue. |
613 | | // If |a| is a square and |p| > 2, there are two possible square roots. This |
614 | | // function may return either and may even select one non-deterministically. |
615 | | // |
616 | | // This function only works if |p| is a prime. If |p| is composite, it may fail |
617 | | // or return an arbitrary value. Callers should not pass attacker-controlled |
618 | | // values of |p|. |
619 | | OPENSSL_EXPORT BIGNUM *BN_mod_sqrt(BIGNUM *in, const BIGNUM *a, const BIGNUM *p, |
620 | | BN_CTX *ctx); |
621 | | |
622 | | |
623 | | // Random and prime number generation. |
624 | | |
625 | | // The following are values for the |top| parameter of |BN_rand|. |
626 | 16 | #define BN_RAND_TOP_ANY (-1) |
627 | 16 | #define BN_RAND_TOP_ONE 0 |
628 | 8 | #define BN_RAND_TOP_TWO 1 |
629 | | |
630 | | // The following are values for the |bottom| parameter of |BN_rand|. |
631 | 0 | #define BN_RAND_BOTTOM_ANY 0 |
632 | 0 | #define BN_RAND_BOTTOM_ODD 1 |
633 | | |
634 | | // BN_rand sets |rnd| to a random number of length |bits|. It returns one on |
635 | | // success and zero otherwise. |
636 | | // |
637 | | // |top| must be one of the |BN_RAND_TOP_*| values. If |BN_RAND_TOP_ONE|, the |
638 | | // most-significant bit, if any, will be set. If |BN_RAND_TOP_TWO|, the two |
639 | | // most significant bits, if any, will be set. If |BN_RAND_TOP_ANY|, no extra |
640 | | // action will be taken and |BN_num_bits(rnd)| may not equal |bits| if the most |
641 | | // significant bits randomly ended up as zeros. |
642 | | // |
643 | | // |bottom| must be one of the |BN_RAND_BOTTOM_*| values. If |
644 | | // |BN_RAND_BOTTOM_ODD|, the least-significant bit, if any, will be set. If |
645 | | // |BN_RAND_BOTTOM_ANY|, no extra action will be taken. |
646 | | OPENSSL_EXPORT int BN_rand(BIGNUM *rnd, int bits, int top, int bottom); |
647 | | |
648 | | // BN_pseudo_rand is an alias for |BN_rand|. |
649 | | OPENSSL_EXPORT int BN_pseudo_rand(BIGNUM *rnd, int bits, int top, int bottom); |
650 | | |
651 | | // BN_rand_range is equivalent to |BN_rand_range_ex| with |min_inclusive| set |
652 | | // to zero and |max_exclusive| set to |range|. |
653 | | OPENSSL_EXPORT int BN_rand_range(BIGNUM *rnd, const BIGNUM *range); |
654 | | |
655 | | // BN_rand_range_ex sets |rnd| to a random value in |
656 | | // [min_inclusive..max_exclusive). It returns one on success and zero |
657 | | // otherwise. |
658 | | OPENSSL_EXPORT int BN_rand_range_ex(BIGNUM *r, BN_ULONG min_inclusive, |
659 | | const BIGNUM *max_exclusive); |
660 | | |
661 | | // BN_pseudo_rand_range is an alias for BN_rand_range. |
662 | | OPENSSL_EXPORT int BN_pseudo_rand_range(BIGNUM *rnd, const BIGNUM *range); |
663 | | |
664 | 2.54k | #define BN_GENCB_GENERATED 0 |
665 | 3.80k | #define BN_GENCB_PRIME_TEST 1 |
666 | | |
667 | | // bn_gencb_st, or |BN_GENCB|, holds a callback function that is used by |
668 | | // generation functions that can take a very long time to complete. Use |
669 | | // |BN_GENCB_set| to initialise a |BN_GENCB| structure. |
670 | | // |
671 | | // The callback receives the address of that |BN_GENCB| structure as its last |
672 | | // argument and the user is free to put an arbitrary pointer in |arg|. The other |
673 | | // arguments are set as follows: |
674 | | // - event=BN_GENCB_GENERATED, n=i: after generating the i'th possible prime |
675 | | // number. |
676 | | // - event=BN_GENCB_PRIME_TEST, n=-1: when finished trial division primality |
677 | | // checks. |
678 | | // - event=BN_GENCB_PRIME_TEST, n=i: when the i'th primality test has finished. |
679 | | // |
680 | | // The callback can return zero to abort the generation progress or one to |
681 | | // allow it to continue. |
682 | | // |
683 | | // When other code needs to call a BN generation function it will often take a |
684 | | // BN_GENCB argument and may call the function with other argument values. |
685 | | struct bn_gencb_st { |
686 | | void *arg; // callback-specific data |
687 | | int (*callback)(int event, int n, struct bn_gencb_st *); |
688 | | }; |
689 | | |
690 | | // BN_GENCB_new returns a newly-allocated |BN_GENCB| object, or NULL on |
691 | | // allocation failure. The result must be released with |BN_GENCB_free| when |
692 | | // done. |
693 | | OPENSSL_EXPORT BN_GENCB *BN_GENCB_new(void); |
694 | | |
695 | | // BN_GENCB_free releases memory associated with |callback|. |
696 | | OPENSSL_EXPORT void BN_GENCB_free(BN_GENCB *callback); |
697 | | |
698 | | // BN_GENCB_set configures |callback| to call |f| and sets |callout->arg| to |
699 | | // |arg|. |
700 | | OPENSSL_EXPORT void BN_GENCB_set(BN_GENCB *callback, |
701 | | int (*f)(int event, int n, BN_GENCB *), |
702 | | void *arg); |
703 | | |
704 | | // BN_GENCB_call calls |callback|, if not NULL, and returns the return value of |
705 | | // the callback, or 1 if |callback| is NULL. |
706 | | OPENSSL_EXPORT int BN_GENCB_call(BN_GENCB *callback, int event, int n); |
707 | | |
708 | | // BN_GENCB_get_arg returns |callback->arg|. |
709 | | OPENSSL_EXPORT void *BN_GENCB_get_arg(const BN_GENCB *callback); |
710 | | |
711 | | // BN_generate_prime_ex sets |ret| to a prime number of |bits| length. If safe |
712 | | // is non-zero then the prime will be such that (ret-1)/2 is also a prime. |
713 | | // (This is needed for Diffie-Hellman groups to ensure that the only subgroups |
714 | | // are of size 2 and (p-1)/2.). |
715 | | // |
716 | | // If |add| is not NULL, the prime will fulfill the condition |ret| % |add| == |
717 | | // |rem| in order to suit a given generator. (If |rem| is NULL then |ret| % |
718 | | // |add| == 1.) |
719 | | // |
720 | | // If |cb| is not NULL, it will be called during processing to give an |
721 | | // indication of progress. See the comments for |BN_GENCB|. It returns one on |
722 | | // success and zero otherwise. |
723 | | OPENSSL_EXPORT int BN_generate_prime_ex(BIGNUM *ret, int bits, int safe, |
724 | | const BIGNUM *add, const BIGNUM *rem, |
725 | | BN_GENCB *cb); |
726 | | |
727 | | // BN_prime_checks_for_validation can be used as the |checks| argument to the |
728 | | // primarily testing functions when validating an externally-supplied candidate |
729 | | // prime. It gives a false positive rate of at most 2^{-128}. (The worst case |
730 | | // false positive rate for a single iteration is 1/4 per |
731 | | // https://eprint.iacr.org/2018/749. (1/4)^64 = 2^{-128}.) |
732 | 0 | #define BN_prime_checks_for_validation 64 |
733 | | |
734 | | // BN_prime_checks_for_generation can be used as the |checks| argument to the |
735 | | // primality testing functions when generating random primes. It gives a false |
736 | | // positive rate at most the security level of the corresponding RSA key size. |
737 | | // |
738 | | // Note this value only performs enough checks if the candidate prime was |
739 | | // selected randomly. If validating an externally-supplied candidate, especially |
740 | | // one that may be selected adversarially, use |BN_prime_checks_for_validation| |
741 | | // instead. |
742 | 548 | #define BN_prime_checks_for_generation 0 |
743 | | |
744 | | // bn_primality_result_t enumerates the outcomes of primality-testing. |
745 | | enum bn_primality_result_t { |
746 | | bn_probably_prime, |
747 | | bn_composite, |
748 | | bn_non_prime_power_composite, |
749 | | }; |
750 | | |
751 | | // BN_enhanced_miller_rabin_primality_test tests whether |w| is probably a prime |
752 | | // number using the Enhanced Miller-Rabin Test (FIPS 186-4 C.3.2) with |
753 | | // |checks| iterations and returns the result in |out_result|. Enhanced |
754 | | // Miller-Rabin tests primality for odd integers greater than 3, returning |
755 | | // |bn_probably_prime| if the number is probably prime, |
756 | | // |bn_non_prime_power_composite| if the number is a composite that is not the |
757 | | // power of a single prime, and |bn_composite| otherwise. It returns one on |
758 | | // success and zero on failure. If |cb| is not NULL, then it is called during |
759 | | // each iteration of the primality test. |
760 | | // |
761 | | // See |BN_prime_checks_for_validation| and |BN_prime_checks_for_generation| for |
762 | | // recommended values of |checks|. |
763 | | OPENSSL_EXPORT int BN_enhanced_miller_rabin_primality_test( |
764 | | enum bn_primality_result_t *out_result, const BIGNUM *w, int checks, |
765 | | BN_CTX *ctx, BN_GENCB *cb); |
766 | | |
767 | | // BN_primality_test sets |*is_probably_prime| to one if |candidate| is |
768 | | // probably a prime number by the Miller-Rabin test or zero if it's certainly |
769 | | // not. |
770 | | // |
771 | | // If |do_trial_division| is non-zero then |candidate| will be tested against a |
772 | | // list of small primes before Miller-Rabin tests. The probability of this |
773 | | // function returning a false positive is at most 2^{2*checks}. See |
774 | | // |BN_prime_checks_for_validation| and |BN_prime_checks_for_generation| for |
775 | | // recommended values of |checks|. |
776 | | // |
777 | | // If |cb| is not NULL then it is called during the checking process. See the |
778 | | // comment above |BN_GENCB|. |
779 | | // |
780 | | // The function returns one on success and zero on error. |
781 | | OPENSSL_EXPORT int BN_primality_test(int *is_probably_prime, |
782 | | const BIGNUM *candidate, int checks, |
783 | | BN_CTX *ctx, int do_trial_division, |
784 | | BN_GENCB *cb); |
785 | | |
786 | | // BN_is_prime_fasttest_ex returns one if |candidate| is probably a prime |
787 | | // number by the Miller-Rabin test, zero if it's certainly not and -1 on error. |
788 | | // |
789 | | // If |do_trial_division| is non-zero then |candidate| will be tested against a |
790 | | // list of small primes before Miller-Rabin tests. The probability of this |
791 | | // function returning one when |candidate| is composite is at most 2^{2*checks}. |
792 | | // See |BN_prime_checks_for_validation| and |BN_prime_checks_for_generation| for |
793 | | // recommended values of |checks|. |
794 | | // |
795 | | // If |cb| is not NULL then it is called during the checking process. See the |
796 | | // comment above |BN_GENCB|. |
797 | | // |
798 | | // WARNING: deprecated. Use |BN_primality_test|. |
799 | | OPENSSL_EXPORT int BN_is_prime_fasttest_ex(const BIGNUM *candidate, int checks, |
800 | | BN_CTX *ctx, int do_trial_division, |
801 | | BN_GENCB *cb); |
802 | | |
803 | | // BN_is_prime_ex acts the same as |BN_is_prime_fasttest_ex| with |
804 | | // |do_trial_division| set to zero. |
805 | | // |
806 | | // WARNING: deprecated: Use |BN_primality_test|. |
807 | | OPENSSL_EXPORT int BN_is_prime_ex(const BIGNUM *candidate, int checks, |
808 | | BN_CTX *ctx, BN_GENCB *cb); |
809 | | |
810 | | |
811 | | // Number theory functions |
812 | | |
813 | | // BN_gcd sets |r| = gcd(|a|, |b|). It returns one on success and zero |
814 | | // otherwise. |
815 | | OPENSSL_EXPORT int BN_gcd(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, |
816 | | BN_CTX *ctx); |
817 | | |
818 | | // BN_mod_inverse sets |out| equal to |a|^-1, mod |n|. If |out| is NULL, a |
819 | | // fresh BIGNUM is allocated. It returns the result or NULL on error. |
820 | | // |
821 | | // If |n| is even then the operation is performed using an algorithm that avoids |
822 | | // some branches but which isn't constant-time. This function shouldn't be used |
823 | | // for secret values; use |BN_mod_inverse_blinded| instead. Or, if |n| is |
824 | | // guaranteed to be prime, use |
825 | | // |BN_mod_exp_mont_consttime(out, a, m_minus_2, m, ctx, m_mont)|, taking |
826 | | // advantage of Fermat's Little Theorem. |
827 | | OPENSSL_EXPORT BIGNUM *BN_mod_inverse(BIGNUM *out, const BIGNUM *a, |
828 | | const BIGNUM *n, BN_CTX *ctx); |
829 | | |
830 | | // BN_mod_inverse_blinded sets |out| equal to |a|^-1, mod |n|, where |n| is the |
831 | | // Montgomery modulus for |mont|. |a| must be non-negative and must be less |
832 | | // than |n|. |n| must be greater than 1. |a| is blinded (masked by a random |
833 | | // value) to protect it against side-channel attacks. On failure, if the failure |
834 | | // was caused by |a| having no inverse mod |n| then |*out_no_inverse| will be |
835 | | // set to one; otherwise it will be set to zero. |
836 | | // |
837 | | // Note this function may incorrectly report |a| has no inverse if the random |
838 | | // blinding value has no inverse. It should only be used when |n| has few |
839 | | // non-invertible elements, such as an RSA modulus. |
840 | | OPENSSL_EXPORT int BN_mod_inverse_blinded(BIGNUM *out, int *out_no_inverse, |
841 | | const BIGNUM *a, |
842 | | const BN_MONT_CTX *mont, BN_CTX *ctx); |
843 | | |
844 | | // BN_mod_inverse_odd sets |out| equal to |a|^-1, mod |n|. |a| must be |
845 | | // non-negative and must be less than |n|. |n| must be odd. This function |
846 | | // shouldn't be used for secret values; use |BN_mod_inverse_blinded| instead. |
847 | | // Or, if |n| is guaranteed to be prime, use |
848 | | // |BN_mod_exp_mont_consttime(out, a, m_minus_2, m, ctx, m_mont)|, taking |
849 | | // advantage of Fermat's Little Theorem. It returns one on success or zero on |
850 | | // failure. On failure, if the failure was caused by |a| having no inverse mod |
851 | | // |n| then |*out_no_inverse| will be set to one; otherwise it will be set to |
852 | | // zero. |
853 | | int BN_mod_inverse_odd(BIGNUM *out, int *out_no_inverse, const BIGNUM *a, |
854 | | const BIGNUM *n, BN_CTX *ctx); |
855 | | |
856 | | |
857 | | // Montgomery arithmetic. |
858 | | |
859 | | // BN_MONT_CTX contains the precomputed values needed to work in a specific |
860 | | // Montgomery domain. |
861 | | |
862 | | // BN_MONT_CTX_new_for_modulus returns a fresh |BN_MONT_CTX| given the modulus, |
863 | | // |mod| or NULL on error. Note this function assumes |mod| is public. |
864 | | OPENSSL_EXPORT BN_MONT_CTX *BN_MONT_CTX_new_for_modulus(const BIGNUM *mod, |
865 | | BN_CTX *ctx); |
866 | | |
867 | | // BN_MONT_CTX_new_consttime behaves like |BN_MONT_CTX_new_for_modulus| but |
868 | | // treats |mod| as secret. |
869 | | OPENSSL_EXPORT BN_MONT_CTX *BN_MONT_CTX_new_consttime(const BIGNUM *mod, |
870 | | BN_CTX *ctx); |
871 | | |
872 | | // BN_MONT_CTX_free frees memory associated with |mont|. |
873 | | OPENSSL_EXPORT void BN_MONT_CTX_free(BN_MONT_CTX *mont); |
874 | | |
875 | | // BN_MONT_CTX_copy sets |to| equal to |from|. It returns |to| on success or |
876 | | // NULL on error. |
877 | | OPENSSL_EXPORT BN_MONT_CTX *BN_MONT_CTX_copy(BN_MONT_CTX *to, |
878 | | const BN_MONT_CTX *from); |
879 | | |
880 | | // BN_to_montgomery sets |ret| equal to |a| in the Montgomery domain. |a| is |
881 | | // assumed to be in the range [0, n), where |n| is the Montgomery modulus. It |
882 | | // returns one on success or zero on error. |
883 | | OPENSSL_EXPORT int BN_to_montgomery(BIGNUM *ret, const BIGNUM *a, |
884 | | const BN_MONT_CTX *mont, BN_CTX *ctx); |
885 | | |
886 | | // BN_from_montgomery sets |ret| equal to |a| * R^-1, i.e. translates values out |
887 | | // of the Montgomery domain. |a| is assumed to be in the range [0, n*R), where |
888 | | // |n| is the Montgomery modulus. Note n < R, so inputs in the range [0, n*n) |
889 | | // are valid. This function returns one on success or zero on error. |
890 | | OPENSSL_EXPORT int BN_from_montgomery(BIGNUM *ret, const BIGNUM *a, |
891 | | const BN_MONT_CTX *mont, BN_CTX *ctx); |
892 | | |
893 | | // BN_mod_mul_montgomery set |r| equal to |a| * |b|, in the Montgomery domain. |
894 | | // Both |a| and |b| must already be in the Montgomery domain (by |
895 | | // |BN_to_montgomery|). In particular, |a| and |b| are assumed to be in the |
896 | | // range [0, n), where |n| is the Montgomery modulus. It returns one on success |
897 | | // or zero on error. |
898 | | OPENSSL_EXPORT int BN_mod_mul_montgomery(BIGNUM *r, const BIGNUM *a, |
899 | | const BIGNUM *b, |
900 | | const BN_MONT_CTX *mont, BN_CTX *ctx); |
901 | | |
902 | | |
903 | | // Exponentiation. |
904 | | |
905 | | // BN_exp sets |r| equal to |a|^{|p|}. It does so with a square-and-multiply |
906 | | // algorithm that leaks side-channel information. It returns one on success or |
907 | | // zero otherwise. |
908 | | OPENSSL_EXPORT int BN_exp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, |
909 | | BN_CTX *ctx); |
910 | | |
911 | | // BN_mod_exp sets |r| equal to |a|^{|p|} mod |m|. It does so with the best |
912 | | // algorithm for the values provided. It returns one on success or zero |
913 | | // otherwise. The |BN_mod_exp_mont_consttime| variant must be used if the |
914 | | // exponent is secret. |
915 | | OPENSSL_EXPORT int BN_mod_exp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, |
916 | | const BIGNUM *m, BN_CTX *ctx); |
917 | | |
918 | | // BN_mod_exp_mont behaves like |BN_mod_exp| but treats |a| as secret and |
919 | | // requires 0 <= |a| < |m|. |
920 | | OPENSSL_EXPORT int BN_mod_exp_mont(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, |
921 | | const BIGNUM *m, BN_CTX *ctx, |
922 | | const BN_MONT_CTX *mont); |
923 | | |
924 | | // BN_mod_exp_mont_consttime behaves like |BN_mod_exp| but treats |a|, |p|, and |
925 | | // |m| as secret and requires 0 <= |a| < |m|. |
926 | | OPENSSL_EXPORT int BN_mod_exp_mont_consttime(BIGNUM *rr, const BIGNUM *a, |
927 | | const BIGNUM *p, const BIGNUM *m, |
928 | | BN_CTX *ctx, |
929 | | const BN_MONT_CTX *mont); |
930 | | |
931 | | |
932 | | // Deprecated functions |
933 | | |
934 | | // BN_bn2mpi serialises the value of |in| to |out|, using a format that consists |
935 | | // of the number's length in bytes represented as a 4-byte big-endian number, |
936 | | // and the number itself in big-endian format, where the most significant bit |
937 | | // signals a negative number. (The representation of numbers with the MSB set is |
938 | | // prefixed with null byte). |out| must have sufficient space available; to |
939 | | // find the needed amount of space, call the function with |out| set to NULL. |
940 | | OPENSSL_EXPORT size_t BN_bn2mpi(const BIGNUM *in, uint8_t *out); |
941 | | |
942 | | // BN_mpi2bn parses |len| bytes from |in| and returns the resulting value. The |
943 | | // bytes at |in| are expected to be in the format emitted by |BN_bn2mpi|. |
944 | | // |
945 | | // If |out| is NULL then a fresh |BIGNUM| is allocated and returned, otherwise |
946 | | // |out| is reused and returned. On error, NULL is returned and the error queue |
947 | | // is updated. |
948 | | OPENSSL_EXPORT BIGNUM *BN_mpi2bn(const uint8_t *in, size_t len, BIGNUM *out); |
949 | | |
950 | | // BN_mod_exp_mont_word is like |BN_mod_exp_mont| except that the base |a| is |
951 | | // given as a |BN_ULONG| instead of a |BIGNUM *|. It returns one on success |
952 | | // or zero otherwise. |
953 | | OPENSSL_EXPORT int BN_mod_exp_mont_word(BIGNUM *r, BN_ULONG a, const BIGNUM *p, |
954 | | const BIGNUM *m, BN_CTX *ctx, |
955 | | const BN_MONT_CTX *mont); |
956 | | |
957 | | // BN_mod_exp2_mont calculates (a1^p1) * (a2^p2) mod m. It returns 1 on success |
958 | | // or zero otherwise. |
959 | | OPENSSL_EXPORT int BN_mod_exp2_mont(BIGNUM *r, const BIGNUM *a1, |
960 | | const BIGNUM *p1, const BIGNUM *a2, |
961 | | const BIGNUM *p2, const BIGNUM *m, |
962 | | BN_CTX *ctx, const BN_MONT_CTX *mont); |
963 | | |
964 | | // BN_MONT_CTX_new returns a fresh |BN_MONT_CTX| or NULL on allocation failure. |
965 | | // Use |BN_MONT_CTX_new_for_modulus| instead. |
966 | | OPENSSL_EXPORT BN_MONT_CTX *BN_MONT_CTX_new(void); |
967 | | |
968 | | // BN_MONT_CTX_set sets up a Montgomery context given the modulus, |mod|. It |
969 | | // returns one on success and zero on error. Use |BN_MONT_CTX_new_for_modulus| |
970 | | // instead. |
971 | | OPENSSL_EXPORT int BN_MONT_CTX_set(BN_MONT_CTX *mont, const BIGNUM *mod, |
972 | | BN_CTX *ctx); |
973 | | |
974 | | // BN_bn2binpad behaves like |BN_bn2bin_padded|, but it returns |len| on success |
975 | | // and -1 on error. |
976 | | // |
977 | | // Use |BN_bn2bin_padded| instead. It is |size_t|-clean. |
978 | | OPENSSL_EXPORT int BN_bn2binpad(const BIGNUM *in, uint8_t *out, int len); |
979 | | |
980 | | // BN_bn2lebinpad behaves like |BN_bn2le_padded|, but it returns |len| on |
981 | | // success and -1 on error. |
982 | | // |
983 | | // Use |BN_bn2le_padded| instead. It is |size_t|-clean. |
984 | | OPENSSL_EXPORT int BN_bn2lebinpad(const BIGNUM *in, uint8_t *out, int len); |
985 | | |
986 | | // BN_prime_checks is a deprecated alias for |BN_prime_checks_for_validation|. |
987 | | // Use |BN_prime_checks_for_generation| or |BN_prime_checks_for_validation| |
988 | | // instead. (This defaults to the |_for_validation| value in order to be |
989 | | // conservative.) |
990 | | #define BN_prime_checks BN_prime_checks_for_validation |
991 | | |
992 | | // BN_secure_new calls |BN_new|. |
993 | | OPENSSL_EXPORT BIGNUM *BN_secure_new(void); |
994 | | |
995 | | // BN_le2bn calls |BN_lebin2bn|. |
996 | | OPENSSL_EXPORT BIGNUM *BN_le2bn(const uint8_t *in, size_t len, BIGNUM *ret); |
997 | | |
998 | | |
999 | | // Private functions |
1000 | | |
1001 | | struct bignum_st { |
1002 | | // d is a pointer to an array of |width| |BN_BITS2|-bit chunks in |
1003 | | // little-endian order. This stores the absolute value of the number. |
1004 | | BN_ULONG *d; |
1005 | | // width is the number of elements of |d| which are valid. This value is not |
1006 | | // necessarily minimal; the most-significant words of |d| may be zero. |
1007 | | // |width| determines a potentially loose upper-bound on the absolute value |
1008 | | // of the |BIGNUM|. |
1009 | | // |
1010 | | // Functions taking |BIGNUM| inputs must compute the same answer for all |
1011 | | // possible widths. |bn_minimal_width|, |bn_set_minimal_width|, and other |
1012 | | // helpers may be used to recover the minimal width, provided it is not |
1013 | | // secret. If it is secret, use a different algorithm. Functions may output |
1014 | | // minimal or non-minimal |BIGNUM|s depending on secrecy requirements, but |
1015 | | // those which cause widths to unboundedly grow beyond the minimal value |
1016 | | // should be documented such. |
1017 | | // |
1018 | | // Note this is different from historical |BIGNUM| semantics. |
1019 | | int width; |
1020 | | // dmax is number of elements of |d| which are allocated. |
1021 | | int dmax; |
1022 | | // neg is one if the number if negative and zero otherwise. |
1023 | | int neg; |
1024 | | // flags is a bitmask of |BN_FLG_*| values |
1025 | | int flags; |
1026 | | }; |
1027 | | |
1028 | | struct bn_mont_ctx_st { |
1029 | | // RR is R^2, reduced modulo |N|. It is used to convert to Montgomery form. It |
1030 | | // is guaranteed to have the same width as |N|. |
1031 | | BIGNUM RR; |
1032 | | // N is the modulus. It is always stored in minimal form, so |N.width| |
1033 | | // determines R. |
1034 | | BIGNUM N; |
1035 | | BN_ULONG n0[2]; // least significant words of (R*Ri-1)/N |
1036 | | }; |
1037 | | |
1038 | | OPENSSL_EXPORT unsigned BN_num_bits_word(BN_ULONG l); |
1039 | | |
1040 | 345k | #define BN_FLG_MALLOCED 0x01 |
1041 | 276k | #define BN_FLG_STATIC_DATA 0x02 |
1042 | | // |BN_FLG_CONSTTIME| has been removed and intentionally omitted so code relying |
1043 | | // on it will not compile. Consumers outside BoringSSL should use the |
1044 | | // higher-level cryptographic algorithms exposed by other modules. Consumers |
1045 | | // within the library should call the appropriate timing-sensitive algorithm |
1046 | | // directly. |
1047 | | |
1048 | | |
1049 | | #if defined(__cplusplus) |
1050 | | } // extern C |
1051 | | |
1052 | | #if !defined(BORINGSSL_NO_CXX) |
1053 | | extern "C++" { |
1054 | | |
1055 | | BSSL_NAMESPACE_BEGIN |
1056 | | |
1057 | | BORINGSSL_MAKE_DELETER(BIGNUM, BN_free) |
1058 | | BORINGSSL_MAKE_DELETER(BN_CTX, BN_CTX_free) |
1059 | | BORINGSSL_MAKE_DELETER(BN_MONT_CTX, BN_MONT_CTX_free) |
1060 | | |
1061 | | class BN_CTXScope { |
1062 | | public: |
1063 | 0 | BN_CTXScope(BN_CTX *ctx) : ctx_(ctx) { BN_CTX_start(ctx_); } |
1064 | 0 | ~BN_CTXScope() { BN_CTX_end(ctx_); } |
1065 | | |
1066 | | private: |
1067 | | BN_CTX *ctx_; |
1068 | | |
1069 | | BN_CTXScope(BN_CTXScope &) = delete; |
1070 | | BN_CTXScope &operator=(BN_CTXScope &) = delete; |
1071 | | }; |
1072 | | |
1073 | | BSSL_NAMESPACE_END |
1074 | | |
1075 | | } // extern C++ |
1076 | | #endif |
1077 | | |
1078 | | #endif |
1079 | | |
1080 | | #define BN_R_ARG2_LT_ARG3 100 |
1081 | | #define BN_R_BAD_RECIPROCAL 101 |
1082 | | #define BN_R_BIGNUM_TOO_LONG 102 |
1083 | | #define BN_R_BITS_TOO_SMALL 103 |
1084 | | #define BN_R_CALLED_WITH_EVEN_MODULUS 104 |
1085 | | #define BN_R_DIV_BY_ZERO 105 |
1086 | | #define BN_R_EXPAND_ON_STATIC_BIGNUM_DATA 106 |
1087 | | #define BN_R_INPUT_NOT_REDUCED 107 |
1088 | | #define BN_R_INVALID_RANGE 108 |
1089 | | #define BN_R_NEGATIVE_NUMBER 109 |
1090 | 0 | #define BN_R_NOT_A_SQUARE 110 |
1091 | | #define BN_R_NOT_INITIALIZED 111 |
1092 | | #define BN_R_NO_INVERSE 112 |
1093 | | #define BN_R_PRIVATE_KEY_TOO_LARGE 113 |
1094 | | #define BN_R_P_IS_NOT_PRIME 114 |
1095 | | #define BN_R_TOO_MANY_ITERATIONS 115 |
1096 | | #define BN_R_TOO_MANY_TEMPORARY_VARIABLES 116 |
1097 | | #define BN_R_BAD_ENCODING 117 |
1098 | | #define BN_R_ENCODE_ERROR 118 |
1099 | | #define BN_R_INVALID_INPUT 119 |
1100 | | |
1101 | | #endif // OPENSSL_HEADER_BN_H |