Absolute File Name: | /home/opencoverage/opencoverage/guest-scripts/libressl/src/crypto/bn/bn_prime.c |
Source code | Switch to Preprocessed file |
Line | Source | Count | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
1 | /* $OpenBSD: bn_prime.c,v 1.18 2017/01/29 17:49:22 beck Exp $ */ | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
2 | /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
3 | * All rights reserved. | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
4 | * | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
5 | * This package is an SSL implementation written | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
6 | * by Eric Young (eay@cryptsoft.com). | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
7 | * The implementation was written so as to conform with Netscapes SSL. | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
8 | * | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
9 | * This library is free for commercial and non-commercial use as long as | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
10 | * the following conditions are aheared to. The following conditions | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
11 | * apply to all code found in this distribution, be it the RC4, RSA, | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
12 | * lhash, DES, etc., code; not just the SSL code. The SSL documentation | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
13 | * included with this distribution is covered by the same copyright terms | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
14 | * except that the holder is Tim Hudson (tjh@cryptsoft.com). | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
15 | * | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
16 | * Copyright remains Eric Young's, and as such any Copyright notices in | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
17 | * the code are not to be removed. | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
18 | * If this package is used in a product, Eric Young should be given attribution | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
19 | * as the author of the parts of the library used. | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
20 | * This can be in the form of a textual message at program startup or | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
21 | * in documentation (online or textual) provided with the package. | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
22 | * | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
23 | * Redistribution and use in source and binary forms, with or without | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
24 | * modification, are permitted provided that the following conditions | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
25 | * are met: | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
26 | * 1. Redistributions of source code must retain the copyright | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
27 | * notice, this list of conditions and the following disclaimer. | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
28 | * 2. Redistributions in binary form must reproduce the above copyright | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
29 | * notice, this list of conditions and the following disclaimer in the | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
30 | * documentation and/or other materials provided with the distribution. | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
31 | * 3. All advertising materials mentioning features or use of this software | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
32 | * must display the following acknowledgement: | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
33 | * "This product includes cryptographic software written by | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
34 | * Eric Young (eay@cryptsoft.com)" | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
35 | * The word 'cryptographic' can be left out if the rouines from the library | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
36 | * being used are not cryptographic related :-). | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
37 | * 4. If you include any Windows specific code (or a derivative thereof) from | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
38 | * the apps directory (application code) you must include an acknowledgement: | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
39 | * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)" | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
40 | * | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
41 | * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
42 | * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
43 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
44 | * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
45 | * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
46 | * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
47 | * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
48 | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
49 | * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
50 | * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
51 | * SUCH DAMAGE. | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
52 | * | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
53 | * The licence and distribution terms for any publically available version or | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
54 | * derivative of this code cannot be changed. i.e. this code cannot simply be | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
55 | * copied and put under another distribution licence | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
56 | * [including the GNU Public Licence.] | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
57 | */ | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
58 | /* ==================================================================== | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
59 | * Copyright (c) 1998-2001 The OpenSSL Project. All rights reserved. | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
60 | * | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
61 | * Redistribution and use in source and binary forms, with or without | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
62 | * modification, are permitted provided that the following conditions | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
63 | * are met: | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
64 | * | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
65 | * 1. Redistributions of source code must retain the above copyright | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
66 | * notice, this list of conditions and the following disclaimer. | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
67 | * | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
68 | * 2. Redistributions in binary form must reproduce the above copyright | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
69 | * notice, this list of conditions and the following disclaimer in | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
70 | * the documentation and/or other materials provided with the | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
71 | * distribution. | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
72 | * | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
73 | * 3. All advertising materials mentioning features or use of this | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
74 | * software must display the following acknowledgment: | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
75 | * "This product includes software developed by the OpenSSL Project | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
76 | * for use in the OpenSSL Toolkit. (http://www.openssl.org/)" | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
77 | * | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
78 | * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
79 | * endorse or promote products derived from this software without | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
80 | * prior written permission. For written permission, please contact | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
81 | * openssl-core@openssl.org. | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
82 | * | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
83 | * 5. Products derived from this software may not be called "OpenSSL" | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
84 | * nor may "OpenSSL" appear in their names without prior written | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
85 | * permission of the OpenSSL Project. | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
86 | * | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
87 | * 6. Redistributions of any form whatsoever must retain the following | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
88 | * acknowledgment: | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
89 | * "This product includes software developed by the OpenSSL Project | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
90 | * for use in the OpenSSL Toolkit (http://www.openssl.org/)" | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
91 | * | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
92 | * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
93 | * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
94 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
95 | * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
96 | * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
97 | * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
98 | * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
99 | * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
100 | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
101 | * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
102 | * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
103 | * OF THE POSSIBILITY OF SUCH DAMAGE. | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
104 | * ==================================================================== | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
105 | * | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
106 | * This product includes cryptographic software written by Eric Young | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
107 | * (eay@cryptsoft.com). This product includes software written by Tim | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
108 | * Hudson (tjh@cryptsoft.com). | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
109 | * | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
110 | */ | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
111 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
112 | #include <stdio.h> | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
113 | #include <time.h> | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
114 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
115 | #include <openssl/err.h> | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
116 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
117 | #include "bn_lcl.h" | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
118 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
119 | /* NB: these functions have been "upgraded", the deprecated versions (which are | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
120 | * compatibility wrappers using these functions) are in bn_depr.c. | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
121 | * - Geoff | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
122 | */ | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
123 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
124 | /* The quick sieve algorithm approach to weeding out primes is | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
125 | * Philip Zimmermann's, as implemented in PGP. I have had a read of | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
126 | * his comments and implemented my own version. | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
127 | */ | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
128 | #include "bn_prime.h" | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
129 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
130 | static int witness(BIGNUM *w, const BIGNUM *a, const BIGNUM *a1, | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
131 | const BIGNUM *a1_odd, int k, BN_CTX *ctx, BN_MONT_CTX *mont); | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
132 | static int probable_prime(BIGNUM *rnd, int bits); | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
133 | static int probable_prime_dh(BIGNUM *rnd, int bits, | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
134 | const BIGNUM *add, const BIGNUM *rem, BN_CTX *ctx); | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
135 | static int probable_prime_dh_safe(BIGNUM *rnd, int bits, | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
136 | const BIGNUM *add, const BIGNUM *rem, BN_CTX *ctx); | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
137 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
138 | int | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
139 | BN_GENCB_call(BN_GENCB *cb, int a, int b) | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
140 | { | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
141 | /* No callback means continue */ | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
142 | if (!cb)
| 983-1587 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
143 | return 1; executed 1587 times by 4 tests: return 1; Executed by:
| 1587 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
144 | switch (cb->ver) { | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
145 | case 1: never executed: case 1: | 0 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
146 | /* Deprecated-style callbacks */ | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
147 | if (!cb->cb.cb_1)
| 0 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
148 | return 1; never executed: return 1; | 0 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
149 | cb->cb.cb_1(a, b, cb->arg); | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
150 | return 1; never executed: return 1; | 0 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
151 | case 2: executed 983 times by 4 tests: case 2: Executed by:
| 983 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
152 | /* New-style callbacks */ | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
153 | return cb->cb.cb_2(a, b, cb); executed 983 times by 4 tests: return cb->cb.cb_2(a, b, cb); Executed by:
| 983 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
154 | default: never executed: default: | 0 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
155 | break; never executed: break; | 0 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
156 | } | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
157 | /* Unrecognised callback type */ | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
158 | return 0; never executed: return 0; | 0 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
159 | } | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
160 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
161 | int | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
162 | BN_generate_prime_ex(BIGNUM *ret, int bits, int safe, const BIGNUM *add, | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
163 | const BIGNUM *rem, BN_GENCB *cb) | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
164 | { | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
165 | BIGNUM *t; | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
166 | int found = 0; | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
167 | int i, j, c1 = 0; | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
168 | BN_CTX *ctx; | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
169 | int checks; | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
170 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
171 | if (bits < 2 || (bits == 2 && safe)) {
| 0-30 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
172 | /* | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
173 | * There are no prime numbers smaller than 2, and the smallest | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
174 | * safe prime (7) spans three bits. | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
175 | */ | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
176 | BNerror(BN_R_BITS_TOO_SMALL); | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
177 | return 0; never executed: return 0; | 0 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
178 | } | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
179 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
180 | ctx = BN_CTX_new(); | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
181 | if (ctx == NULL)
| 0-30 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
182 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
183 | BN_CTX_start(ctx); | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
184 | if ((t = BN_CTX_get(ctx)) == NULL)
| 0-30 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
185 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
186 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
187 | checks = BN_prime_checks_for_size(bits);
| 0-30 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
188 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
189 | loop: code before this statement executed 30 times by 4 tests: loop: Executed by:
| 30 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
190 | /* make a random number and set the top and bottom bits */ | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
191 | if (add == NULL) {
| 24-94 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
192 | if (!probable_prime(ret, bits))
| 0-24 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
193 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
194 | } else { executed 24 times by 2 tests: end of block Executed by:
| 24 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
195 | if (safe) {
| 42-52 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
196 | if (!probable_prime_dh_safe(ret, bits, add, rem, ctx))
| 0-42 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
197 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
198 | } else { executed 42 times by 2 tests: end of block Executed by:
| 42 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
199 | if (!probable_prime_dh(ret, bits, add, rem, ctx))
| 0-52 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
200 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
201 | } executed 52 times by 1 test: end of block Executed by:
| 52 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
202 | } | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
203 | /* if (BN_mod_word(ret,(BN_ULONG)3) == 1) goto loop; */ | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
204 | if (!BN_GENCB_call(cb, 0, c1++))
| 0-118 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
205 | /* aborted */ | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
206 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
207 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
208 | if (!safe) {
| 42-76 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
209 | i = BN_is_prime_fasttest_ex(ret, checks, ctx, 0, cb); | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
210 | if (i == -1)
| 0-76 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
211 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
212 | if (i == 0)
| 12-64 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
213 | goto loop; executed 64 times by 2 tests: goto loop; Executed by:
| 64 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
214 | } else { executed 12 times by 2 tests: end of block Executed by:
| 12 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
215 | /* for "safe prime" generation, | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
216 | * check that (p-1)/2 is prime. | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
217 | * Since a prime is odd, We just | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
218 | * need to divide by 2 */ | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
219 | if (!BN_rshift1(t, ret))
| 0-42 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
220 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
221 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
222 | for (i = 0; i < checks; i++) {
| 18-510 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
223 | j = BN_is_prime_fasttest_ex(ret, 1, ctx, 0, cb); | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
224 | if (j == -1)
| 0-510 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
225 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
226 | if (j == 0)
| 17-493 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
227 | goto loop; executed 17 times by 2 tests: goto loop; Executed by:
| 17 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
228 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
229 | j = BN_is_prime_fasttest_ex(t, 1, ctx, 0, cb); | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
230 | if (j == -1)
| 0-493 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
231 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
232 | if (j == 0)
| 7-486 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
233 | goto loop; executed 7 times by 2 tests: goto loop; Executed by:
| 7 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
234 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
235 | if (!BN_GENCB_call(cb, 2, c1 - 1))
| 0-486 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
236 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
237 | /* We have a safe prime test pass */ | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
238 | } executed 486 times by 2 tests: end of block Executed by:
| 486 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
239 | } executed 18 times by 2 tests: end of block Executed by:
| 18 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
240 | /* we have a prime :-) */ | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
241 | found = 1; | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
242 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
243 | err: code before this statement executed 30 times by 4 tests: err: Executed by:
| 30 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
244 | if (ctx != NULL) {
| 0-30 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
245 | BN_CTX_end(ctx); | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
246 | BN_CTX_free(ctx); | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
247 | } executed 30 times by 4 tests: end of block Executed by:
| 30 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
248 | bn_check_top(ret); | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
249 | return found; executed 30 times by 4 tests: return found; Executed by:
| 30 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
250 | } | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
251 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
252 | int | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
253 | BN_is_prime_ex(const BIGNUM *a, int checks, BN_CTX *ctx_passed, BN_GENCB *cb) | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
254 | { | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
255 | return BN_is_prime_fasttest_ex(a, checks, ctx_passed, 0, cb); executed 8 times by 2 tests: return BN_is_prime_fasttest_ex(a, checks, ctx_passed, 0, cb); Executed by:
| 8 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
256 | } | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
257 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
258 | int | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
259 | BN_is_prime_fasttest_ex(const BIGNUM *a, int checks, BN_CTX *ctx_passed, | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
260 | int do_trial_division, BN_GENCB *cb) | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
261 | { | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
262 | int i, j, ret = -1; | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
263 | int k; | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
264 | BN_CTX *ctx = NULL; | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
265 | BIGNUM *A1, *A1_odd, *check; /* taken from ctx */ | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
266 | BN_MONT_CTX *mont = NULL; | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
267 | const BIGNUM *A = NULL; | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
268 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
269 | if (BN_cmp(a, BN_value_one()) <= 0)
| 0-1536 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
270 | return 0; never executed: return 0; | 0 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
271 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
272 | if (checks == BN_prime_checks)
| 8-1528 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
273 | checks = BN_prime_checks_for_size(BN_num_bits(a)); executed 8 times by 2 tests: checks = ((BN_num_bits(a)) >= 1300 ? 2 : (BN_num_bits(a)) >= 850 ? 3 : (BN_num_bits(a)) >= 650 ? 4 : (BN_num_bits(a)) >= 550 ? 5 : (BN_num_bits(a)) >= 450 ? 6 : (BN_num_bits(a)) >= 400 ? 7 : (BN_num_bits(a)) >= 350 ? 8 : (BN_num_bits(a)) >= 300 ? 9 : (BN_num_bits(a)) >= 250 ? 12 : (BN_num_bits(a)) >= 200 ? 15 : (BN_num_bits(a)) >= 150 ? 18 : 27); Executed by:
| 0-8 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
274 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
275 | /* first look for small factors */ | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
276 | if (!BN_is_odd(a))
| 0-1536 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
277 | /* a is even => a is prime if and only if a == 2 */ | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
278 | return BN_is_word(a, 2); executed 4 times by 1 test: return ((((((a))->top == 1) && (((a))->d[0] == (unsigned long)((2)))) || ((((2)) == 0) && (((a))->top == 0))) && (!(2) || !(a)->neg)); Executed by:
| 0-4 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
279 | if (do_trial_division) {
| 448-1084 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
280 | for (i = 1; i < NUMPRIMES; i++) {
| 46-112372 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
281 | BN_ULONG mod = BN_mod_word(a, primes[i]); | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
282 | if (mod == (BN_ULONG)-1)
| 0-112372 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
283 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
284 | if (mod == 0)
| 402-111970 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
285 | return 0; executed 402 times by 2 tests: return 0; Executed by:
| 402 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
286 | } executed 111970 times by 2 tests: end of block Executed by:
| 111970 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
287 | if (!BN_GENCB_call(cb, 1, -1))
| 0-46 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
288 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
289 | } executed 46 times by 2 tests: end of block Executed by:
| 46 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
290 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
291 | if (ctx_passed != NULL)
| 0-1130 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
292 | ctx = ctx_passed; executed 1130 times by 6 tests: ctx = ctx_passed; Executed by:
| 1130 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
293 | else if ((ctx = BN_CTX_new()) == NULL)
| 0 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
294 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
295 | BN_CTX_start(ctx); | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
296 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
297 | /* A := abs(a) */ | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
298 | if (a->neg) {
| 0-1130 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
299 | BIGNUM *t; | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
300 | if ((t = BN_CTX_get(ctx)) == NULL)
| 0 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
301 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
302 | BN_copy(t, a); | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
303 | t->neg = 0; | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
304 | A = t; | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
305 | } else never executed: end of block | 0 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
306 | A = a; executed 1130 times by 6 tests: A = a; Executed by:
| 1130 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
307 | if ((A1 = BN_CTX_get(ctx)) == NULL)
| 0-1130 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
308 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
309 | if ((A1_odd = BN_CTX_get(ctx)) == NULL)
| 0-1130 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
310 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
311 | if ((check = BN_CTX_get(ctx)) == NULL)
| 0-1130 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
312 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
313 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
314 | /* compute A1 := A - 1 */ | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
315 | if (!BN_copy(A1, A))
| 0-1130 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
316 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
317 | if (!BN_sub_word(A1, 1))
| 0-1130 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
318 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
319 | if (BN_is_zero(A1)) {
| 0-1130 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
320 | ret = 0; | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
321 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
322 | } | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
323 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
324 | /* write A1 as A1_odd * 2^k */ | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
325 | k = 1; | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
326 | while (!BN_is_bit_set(A1, k))
| 1130-1394 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
327 | k++; executed 1394 times by 6 tests: k++; Executed by:
| 1394 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
328 | if (!BN_rshift(A1_odd, A1, k))
| 0-1130 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
329 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
330 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
331 | /* Montgomery setup for computations mod A */ | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
332 | mont = BN_MONT_CTX_new(); | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
333 | if (mont == NULL)
| 0-1130 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
334 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
335 | if (!BN_MONT_CTX_set(mont, A, ctx))
| 0-1130 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
336 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
337 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
338 | for (i = 0; i < checks; i++) {
| 1003-1572 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
339 | if (!BN_pseudo_rand_range(check, A1))
| 0-1572 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
340 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
341 | if (!BN_add_word(check, 1))
| 0-1572 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
342 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
343 | /* now 1 <= check < A */ | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
344 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
345 | j = witness(check, A, A1, A1_odd, k, ctx, mont); | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
346 | if (j == -1)
| 0-1572 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
347 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
348 | if (j) {
| 127-1445 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
349 | ret = 0; | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
350 | goto err; executed 127 times by 5 tests: goto err; Executed by:
| 127 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
351 | } | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
352 | if (!BN_GENCB_call(cb, 1, i))
| 0-1445 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
353 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
354 | } executed 1445 times by 6 tests: end of block Executed by:
| 1445 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
355 | ret = 1; | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
356 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
357 | err: code before this statement executed 1003 times by 6 tests: err: Executed by:
| 1003 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
358 | if (ctx != NULL) {
| 0-1130 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
359 | BN_CTX_end(ctx); | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
360 | if (ctx_passed == NULL)
| 0-1130 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
361 | BN_CTX_free(ctx); never executed: BN_CTX_free(ctx); | 0 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
362 | } executed 1130 times by 6 tests: end of block Executed by:
| 1130 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
363 | BN_MONT_CTX_free(mont); | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
364 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
365 | return (ret); executed 1130 times by 6 tests: return (ret); Executed by:
| 1130 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
366 | } | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
367 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
368 | static int | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
369 | witness(BIGNUM *w, const BIGNUM *a, const BIGNUM *a1, const BIGNUM *a1_odd, | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
370 | int k, BN_CTX *ctx, BN_MONT_CTX *mont) | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
371 | { | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
372 | if (!BN_mod_exp_mont_ct(w, w, a1_odd, a, ctx, mont))
| 0-1572 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
373 | /* w := w^a1_odd mod a */ | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
374 | return -1; never executed: return -1; | 0 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
375 | if (BN_is_one(w))
| 0-1243 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
376 | return 0; /* probably prime */ executed 512 times by 6 tests: return 0; Executed by:
| 512 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
377 | if (BN_cmp(w, a1) == 0)
| 493-567 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
378 | return 0; /* w == -1 (mod a), 'a' is probably prime */ executed 493 times by 6 tests: return 0; Executed by:
| 493 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
379 | while (--k) {
| 127-2670 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
380 | if (!BN_mod_mul(w, w, w, a, ctx)) /* w := w^2 mod a */
| 0-2670 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
381 | return -1; never executed: return -1; | 0 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
382 | if (BN_is_one(w))
| 0-2670 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
383 | return 1; /* 'a' is composite, otherwise a previous 'w' would never executed: return 1; | 0 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
384 | * have been == -1 (mod 'a') */ | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
385 | if (BN_cmp(w, a1) == 0)
| 440-2230 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
386 | return 0; /* w == -1 (mod a), 'a' is probably prime */ executed 440 times by 5 tests: return 0; Executed by:
| 440 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
387 | } executed 2230 times by 6 tests: end of block Executed by:
| 2230 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
388 | /* If we get here, 'w' is the (a-1)/2-th power of the original 'w', | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
389 | * and it is neither -1 nor +1 -- so 'a' cannot be prime */ | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
390 | bn_check_top(w); | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
391 | return 1; executed 127 times by 5 tests: return 1; Executed by:
| 127 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
392 | } | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
393 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
394 | static int | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
395 | probable_prime(BIGNUM *rnd, int bits) | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
396 | { | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
397 | int i; | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
398 | prime_t mods[NUMPRIMES]; | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
399 | BN_ULONG delta, maxdelta; | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
400 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
401 | again: code before this statement executed 24 times by 2 tests: again: Executed by:
| 24 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
402 | if (!BN_rand(rnd, bits, 1, 1))
| 0-24 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
403 | return (0); never executed: return (0); | 0 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
404 | /* we now have a random number 'rand' to test. */ | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
405 | for (i = 1; i < NUMPRIMES; i++) {
| 24-49128 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
406 | BN_ULONG mod = BN_mod_word(rnd, (BN_ULONG)primes[i]); | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
407 | if (mod == (BN_ULONG)-1)
| 0-49128 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
408 | return (0); never executed: return (0); | 0 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
409 | mods[i] = (prime_t)mod; | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
410 | } executed 49128 times by 2 tests: end of block Executed by:
| 49128 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
411 | maxdelta = BN_MASK2 - primes[NUMPRIMES - 1]; | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
412 | delta = 0; | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
413 | loop: code before this statement executed 24 times by 2 tests: loop: Executed by:
| 24 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
414 | for (i = 1; i < NUMPRIMES; i++) {
| 24-76031 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
415 | /* check that rnd is not a prime and also | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
416 | * that gcd(rnd-1,primes) == 1 (except for 2) */ | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
417 | if (((mods[i] + delta) % primes[i]) <= 1) {
| 2686-73345 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
418 | delta += 2; | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
419 | if (delta > maxdelta)
| 0-2686 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
420 | goto again; never executed: goto again; | 0 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
421 | goto loop; executed 2686 times by 2 tests: goto loop; Executed by:
| 2686 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
422 | } | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
423 | } executed 73345 times by 2 tests: end of block Executed by:
| 73345 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
424 | if (!BN_add_word(rnd, delta))
| 0-24 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
425 | return (0); never executed: return (0); | 0 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
426 | bn_check_top(rnd); | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
427 | return (1); executed 24 times by 2 tests: return (1); Executed by:
| 24 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
428 | } | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
429 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
430 | static int | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
431 | probable_prime_dh(BIGNUM *rnd, int bits, const BIGNUM *add, const BIGNUM *rem, | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
432 | BN_CTX *ctx) | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
433 | { | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
434 | int i, ret = 0; | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
435 | BIGNUM *t1; | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
436 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
437 | BN_CTX_start(ctx); | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
438 | if ((t1 = BN_CTX_get(ctx)) == NULL)
| 0-52 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
439 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
440 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
441 | if (!BN_rand(rnd, bits, 0, 1))
| 0-52 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
442 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
443 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
444 | /* we need ((rnd-rem) % add) == 0 */ | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
445 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
446 | if (!BN_mod_ct(t1, rnd, add, ctx))
| 0-52 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
447 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
448 | if (!BN_sub(rnd, rnd, t1))
| 0-52 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
449 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
450 | if (rem == NULL) {
| 0-52 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
451 | if (!BN_add_word(rnd, 1))
| 0 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
452 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
453 | } else { never executed: end of block | 0 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
454 | if (!BN_add(rnd, rnd, rem))
| 0-52 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
455 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
456 | } executed 52 times by 1 test: end of block Executed by:
| 52 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
457 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
458 | /* we now have a random number 'rand' to test. */ | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
459 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
460 | loop: code before this statement executed 52 times by 1 test: loop: Executed by:
| 52 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
461 | for (i = 1; i < NUMPRIMES; i++) {
| 52-150158 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
462 | /* check that rnd is a prime */ | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
463 | BN_LONG mod = BN_mod_word(rnd, (BN_ULONG)primes[i]); | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
464 | if (mod == (BN_ULONG)-1)
| 0-150158 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
465 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
466 | if (mod <= 1) {
| 5364-144794 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
467 | if (!BN_add(rnd, rnd, add))
| 0-5364 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
468 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
469 | goto loop; executed 5364 times by 1 test: goto loop; Executed by:
| 5364 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
470 | } | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
471 | } executed 144794 times by 1 test: end of block Executed by:
| 144794 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
472 | ret = 1; | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
473 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
474 | err: code before this statement executed 52 times by 1 test: err: Executed by:
| 52 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
475 | BN_CTX_end(ctx); | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
476 | bn_check_top(rnd); | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
477 | return (ret); executed 52 times by 1 test: return (ret); Executed by:
| 52 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
478 | } | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
479 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
480 | static int | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
481 | probable_prime_dh_safe(BIGNUM *p, int bits, const BIGNUM *padd, | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
482 | const BIGNUM *rem, BN_CTX *ctx) | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
483 | { | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
484 | int i, ret = 0; | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
485 | BIGNUM *t1, *qadd, *q; | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
486 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
487 | bits--; | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
488 | BN_CTX_start(ctx); | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
489 | if ((t1 = BN_CTX_get(ctx)) == NULL)
| 0-42 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
490 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
491 | if ((q = BN_CTX_get(ctx)) == NULL)
| 0-42 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
492 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
493 | if ((qadd = BN_CTX_get(ctx)) == NULL)
| 0-42 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
494 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
495 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
496 | if (!BN_rshift1(qadd, padd))
| 0-42 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
497 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
498 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
499 | if (!BN_rand(q, bits, 0, 1))
| 0-42 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
500 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
501 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
502 | /* we need ((rnd-rem) % add) == 0 */ | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
503 | if (!BN_mod_ct(t1, q,qadd, ctx))
| 0-42 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
504 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
505 | if (!BN_sub(q, q, t1))
| 0-42 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
506 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
507 | if (rem == NULL) {
| 0-42 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
508 | if (!BN_add_word(q, 1))
| 0 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
509 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
510 | } else { never executed: end of block | 0 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
511 | if (!BN_rshift1(t1, rem))
| 0-42 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
512 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
513 | if (!BN_add(q, q, t1))
| 0-42 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
514 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
515 | } executed 42 times by 2 tests: end of block Executed by:
| 42 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
516 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
517 | /* we now have a random number 'rand' to test. */ | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
518 | if (!BN_lshift1(p, q))
| 0-42 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
519 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
520 | if (!BN_add_word(p, 1))
| 0-42 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
521 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
522 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
523 | loop: code before this statement executed 42 times by 2 tests: loop: Executed by:
| 42 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
524 | for (i = 1; i < NUMPRIMES; i++) {
| 42-122532 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
525 | /* check that p and q are prime */ | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
526 | /* check that for p and q | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
527 | * gcd(p-1,primes) == 1 (except for 2) */ | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
528 | BN_ULONG pmod = BN_mod_word(p, (BN_ULONG)primes[i]); | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
529 | BN_ULONG qmod = BN_mod_word(q, (BN_ULONG)primes[i]); | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
530 | if (pmod == (BN_ULONG)-1 || qmod == (BN_ULONG)-1)
| 0-122532 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
531 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
532 | if (pmod == 0 || qmod == 0) {
| 787-121735 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
533 | if (!BN_add(p, p, padd))
| 0-1584 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
534 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
535 | if (!BN_add(q, q, qadd))
| 0-1584 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
536 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
537 | goto loop; executed 1584 times by 2 tests: goto loop; Executed by:
| 1584 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
538 | } | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
539 | } executed 120948 times by 2 tests: end of block Executed by:
| 120948 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
540 | ret = 1; | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
541 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
542 | err: code before this statement executed 42 times by 2 tests: err: Executed by:
| 42 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
543 | BN_CTX_end(ctx); | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
544 | bn_check_top(p); | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
545 | return (ret); executed 42 times by 2 tests: return (ret); Executed by:
| 42 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
546 | } | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Source code | Switch to Preprocessed file |