summaryrefslogtreecommitdiff
path: root/src/lib/libcrypto/bn/bn_gcd.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/lib/libcrypto/bn/bn_gcd.c')
-rw-r--r--src/lib/libcrypto/bn/bn_gcd.c570
1 files changed, 296 insertions, 274 deletions
diff --git a/src/lib/libcrypto/bn/bn_gcd.c b/src/lib/libcrypto/bn/bn_gcd.c
index a808f53178..18f2812368 100644
--- a/src/lib/libcrypto/bn/bn_gcd.c
+++ b/src/lib/libcrypto/bn/bn_gcd.c
@@ -5,21 +5,21 @@
5 * This package is an SSL implementation written 5 * This package is an SSL implementation written
6 * by Eric Young (eay@cryptsoft.com). 6 * by Eric Young (eay@cryptsoft.com).
7 * The implementation was written so as to conform with Netscapes SSL. 7 * The implementation was written so as to conform with Netscapes SSL.
8 * 8 *
9 * This library is free for commercial and non-commercial use as long as 9 * This library is free for commercial and non-commercial use as long as
10 * the following conditions are aheared to. The following conditions 10 * the following conditions are aheared to. The following conditions
11 * apply to all code found in this distribution, be it the RC4, RSA, 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 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 13 * included with this distribution is covered by the same copyright terms
14 * except that the holder is Tim Hudson (tjh@cryptsoft.com). 14 * except that the holder is Tim Hudson (tjh@cryptsoft.com).
15 * 15 *
16 * Copyright remains Eric Young's, and as such any Copyright notices in 16 * Copyright remains Eric Young's, and as such any Copyright notices in
17 * the code are not to be removed. 17 * the code are not to be removed.
18 * If this package is used in a product, Eric Young should be given attribution 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. 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 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. 21 * in documentation (online or textual) provided with the package.
22 * 22 *
23 * Redistribution and use in source and binary forms, with or without 23 * Redistribution and use in source and binary forms, with or without
24 * modification, are permitted provided that the following conditions 24 * modification, are permitted provided that the following conditions
25 * are met: 25 * are met:
@@ -34,10 +34,10 @@
34 * Eric Young (eay@cryptsoft.com)" 34 * Eric Young (eay@cryptsoft.com)"
35 * The word 'cryptographic' can be left out if the rouines from the library 35 * The word 'cryptographic' can be left out if the rouines from the library
36 * being used are not cryptographic related :-). 36 * being used are not cryptographic related :-).
37 * 4. If you include any Windows specific code (or a derivative thereof) from 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: 38 * the apps directory (application code) you must include an acknowledgement:
39 * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)" 39 * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
40 * 40 *
41 * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND 41 * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
42 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 42 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
43 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 43 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
@@ -49,7 +49,7 @@
49 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 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 50 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
51 * SUCH DAMAGE. 51 * SUCH DAMAGE.
52 * 52 *
53 * The licence and distribution terms for any publically available version or 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 54 * derivative of this code cannot be changed. i.e. this code cannot simply be
55 * copied and put under another distribution licence 55 * copied and put under another distribution licence
@@ -63,7 +63,7 @@
63 * are met: 63 * are met:
64 * 64 *
65 * 1. Redistributions of source code must retain the above copyright 65 * 1. Redistributions of source code must retain the above copyright
66 * notice, this list of conditions and the following disclaimer. 66 * notice, this list of conditions and the following disclaimer.
67 * 67 *
68 * 2. Redistributions in binary form must reproduce the above copyright 68 * 2. Redistributions in binary form must reproduce the above copyright
69 * notice, this list of conditions and the following disclaimer in 69 * notice, this list of conditions and the following disclaimer in
@@ -114,10 +114,11 @@
114 114
115static BIGNUM *euclid(BIGNUM *a, BIGNUM *b); 115static BIGNUM *euclid(BIGNUM *a, BIGNUM *b);
116 116
117int BN_gcd(BIGNUM *r, const BIGNUM *in_a, const BIGNUM *in_b, BN_CTX *ctx) 117int
118 { 118BN_gcd(BIGNUM *r, const BIGNUM *in_a, const BIGNUM *in_b, BN_CTX *ctx)
119 BIGNUM *a,*b,*t; 119{
120 int ret=0; 120 BIGNUM *a, *b, *t;
121 int ret = 0;
121 122
122 bn_check_top(in_a); 123 bn_check_top(in_a);
123 bn_check_top(in_b); 124 bn_check_top(in_b);
@@ -125,98 +126,121 @@ int BN_gcd(BIGNUM *r, const BIGNUM *in_a, const BIGNUM *in_b, BN_CTX *ctx)
125 BN_CTX_start(ctx); 126 BN_CTX_start(ctx);
126 a = BN_CTX_get(ctx); 127 a = BN_CTX_get(ctx);
127 b = BN_CTX_get(ctx); 128 b = BN_CTX_get(ctx);
128 if (a == NULL || b == NULL) goto err; 129 if (a == NULL || b == NULL)
130 goto err;
129 131
130 if (BN_copy(a,in_a) == NULL) goto err; 132 if (BN_copy(a, in_a) == NULL)
131 if (BN_copy(b,in_b) == NULL) goto err; 133 goto err;
134 if (BN_copy(b, in_b) == NULL)
135 goto err;
132 a->neg = 0; 136 a->neg = 0;
133 b->neg = 0; 137 b->neg = 0;
134 138
135 if (BN_cmp(a,b) < 0) { t=a; a=b; b=t; } 139 if (BN_cmp(a, b) < 0) {
136 t=euclid(a,b); 140 t = a;
137 if (t == NULL) goto err; 141 a = b;
142 b = t;
143 }
144 t = euclid(a, b);
145 if (t == NULL)
146 goto err;
147
148 if (BN_copy(r, t) == NULL)
149 goto err;
150 ret = 1;
138 151
139 if (BN_copy(r,t) == NULL) goto err;
140 ret=1;
141err: 152err:
142 BN_CTX_end(ctx); 153 BN_CTX_end(ctx);
143 bn_check_top(r); 154 bn_check_top(r);
144 return(ret); 155 return (ret);
145 } 156}
146 157
147static BIGNUM *euclid(BIGNUM *a, BIGNUM *b) 158static BIGNUM *
148 { 159euclid(BIGNUM *a, BIGNUM *b)
160{
149 BIGNUM *t; 161 BIGNUM *t;
150 int shifts=0; 162 int shifts = 0;
151 163
152 bn_check_top(a); 164 bn_check_top(a);
153 bn_check_top(b); 165 bn_check_top(b);
154 166
155 /* 0 <= b <= a */ 167 /* 0 <= b <= a */
156 while (!BN_is_zero(b)) 168 while (!BN_is_zero(b)) {
157 {
158 /* 0 < b <= a */ 169 /* 0 < b <= a */
159 170
160 if (BN_is_odd(a)) 171 if (BN_is_odd(a)) {
161 { 172 if (BN_is_odd(b)) {
162 if (BN_is_odd(b)) 173 if (!BN_sub(a, a, b))
163 { 174 goto err;
164 if (!BN_sub(a,a,b)) goto err; 175 if (!BN_rshift1(a, a))
165 if (!BN_rshift1(a,a)) goto err; 176 goto err;
166 if (BN_cmp(a,b) < 0) 177 if (BN_cmp(a, b) < 0) {
167 { t=a; a=b; b=t; } 178 t = a;
179 a = b;
180 b = t;
168 } 181 }
182 }
169 else /* a odd - b even */ 183 else /* a odd - b even */
170 { 184 {
171 if (!BN_rshift1(b,b)) goto err; 185 if (!BN_rshift1(b, b))
172 if (BN_cmp(a,b) < 0) 186 goto err;
173 { t=a; a=b; b=t; } 187 if (BN_cmp(a, b) < 0) {
188 t = a;
189 a = b;
190 b = t;
174 } 191 }
175 } 192 }
193 }
176 else /* a is even */ 194 else /* a is even */
177 { 195 {
178 if (BN_is_odd(b)) 196 if (BN_is_odd(b)) {
179 { 197 if (!BN_rshift1(a, a))
180 if (!BN_rshift1(a,a)) goto err; 198 goto err;
181 if (BN_cmp(a,b) < 0) 199 if (BN_cmp(a, b) < 0) {
182 { t=a; a=b; b=t; } 200 t = a;
201 a = b;
202 b = t;
183 } 203 }
204 }
184 else /* a even - b even */ 205 else /* a even - b even */
185 { 206 {
186 if (!BN_rshift1(a,a)) goto err; 207 if (!BN_rshift1(a, a))
187 if (!BN_rshift1(b,b)) goto err; 208 goto err;
209 if (!BN_rshift1(b, b))
210 goto err;
188 shifts++; 211 shifts++;
189 }
190 } 212 }
191 /* 0 <= b <= a */
192 } 213 }
214 /* 0 <= b <= a */
215 }
193 216
194 if (shifts) 217 if (shifts) {
195 { 218 if (!BN_lshift(a, a, shifts))
196 if (!BN_lshift(a,a,shifts)) goto err; 219 goto err;
197 } 220 }
198 bn_check_top(a); 221 bn_check_top(a);
199 return(a); 222 return (a);
223
200err: 224err:
201 return(NULL); 225 return (NULL);
202 } 226}
203 227
204 228
205/* solves ax == 1 (mod n) */ 229/* solves ax == 1 (mod n) */
206static BIGNUM *BN_mod_inverse_no_branch(BIGNUM *in, 230static BIGNUM *BN_mod_inverse_no_branch(BIGNUM *in, const BIGNUM *a,
207 const BIGNUM *a, const BIGNUM *n, BN_CTX *ctx); 231 const BIGNUM *n, BN_CTX *ctx);
208 232
209BIGNUM *BN_mod_inverse(BIGNUM *in, 233BIGNUM *
210 const BIGNUM *a, const BIGNUM *n, BN_CTX *ctx) 234BN_mod_inverse(BIGNUM *in, const BIGNUM *a, const BIGNUM *n, BN_CTX *ctx)
211 { 235{
212 BIGNUM *A,*B,*X,*Y,*M,*D,*T,*R=NULL; 236 BIGNUM *A, *B, *X, *Y, *M, *D, *T, *R = NULL;
213 BIGNUM *ret=NULL; 237 BIGNUM *ret = NULL;
214 int sign; 238 int sign;
215 239
216 if ((BN_get_flags(a, BN_FLG_CONSTTIME) != 0) || (BN_get_flags(n, BN_FLG_CONSTTIME) != 0)) 240 if ((BN_get_flags(a, BN_FLG_CONSTTIME) != 0) ||
217 { 241 (BN_get_flags(n, BN_FLG_CONSTTIME) != 0)) {
218 return BN_mod_inverse_no_branch(in, a, n, ctx); 242 return BN_mod_inverse_no_branch(in, a, n, ctx);
219 } 243 }
220 244
221 bn_check_top(a); 245 bn_check_top(a);
222 bn_check_top(n); 246 bn_check_top(n);
@@ -229,23 +253,27 @@ BIGNUM *BN_mod_inverse(BIGNUM *in,
229 M = BN_CTX_get(ctx); 253 M = BN_CTX_get(ctx);
230 Y = BN_CTX_get(ctx); 254 Y = BN_CTX_get(ctx);
231 T = BN_CTX_get(ctx); 255 T = BN_CTX_get(ctx);
232 if (T == NULL) goto err; 256 if (T == NULL)
257 goto err;
233 258
234 if (in == NULL) 259 if (in == NULL)
235 R=BN_new(); 260 R = BN_new();
236 else 261 else
237 R=in; 262 R = in;
238 if (R == NULL) goto err; 263 if (R == NULL)
264 goto err;
239 265
240 BN_one(X); 266 BN_one(X);
241 BN_zero(Y); 267 BN_zero(Y);
242 if (BN_copy(B,a) == NULL) goto err; 268 if (BN_copy(B, a) == NULL)
243 if (BN_copy(A,n) == NULL) goto err; 269 goto err;
270 if (BN_copy(A, n) == NULL)
271 goto err;
244 A->neg = 0; 272 A->neg = 0;
245 if (B->neg || (BN_ucmp(B, A) >= 0)) 273 if (B->neg || (BN_ucmp(B, A) >= 0)) {
246 { 274 if (!BN_nnmod(B, B, A, ctx))
247 if (!BN_nnmod(B, B, A, ctx)) goto err; 275 goto err;
248 } 276 }
249 sign = -1; 277 sign = -1;
250 /* From B = a mod |n|, A = |n| it follows that 278 /* From B = a mod |n|, A = |n| it follows that
251 * 279 *
@@ -254,16 +282,14 @@ BIGNUM *BN_mod_inverse(BIGNUM *in,
254 * sign*Y*a == A (mod |n|). 282 * sign*Y*a == A (mod |n|).
255 */ 283 */
256 284
257 if (BN_is_odd(n) && (BN_num_bits(n) <= (BN_BITS <= 32 ? 450 : 2048))) 285 if (BN_is_odd(n) && (BN_num_bits(n) <= (BN_BITS <= 32 ? 450 : 2048))) {
258 {
259 /* Binary inversion algorithm; requires odd modulus. 286 /* Binary inversion algorithm; requires odd modulus.
260 * This is faster than the general algorithm if the modulus 287 * This is faster than the general algorithm if the modulus
261 * is sufficiently small (about 400 .. 500 bits on 32-bit 288 * is sufficiently small (about 400 .. 500 bits on 32-bit
262 * sytems, but much more on 64-bit systems) */ 289 * sytems, but much more on 64-bit systems) */
263 int shift; 290 int shift;
264 291
265 while (!BN_is_zero(B)) 292 while (!BN_is_zero(B)) {
266 {
267 /* 293 /*
268 * 0 < B < |n|, 294 * 0 < B < |n|,
269 * 0 < A <= |n|, 295 * 0 < A <= |n|,
@@ -276,41 +302,43 @@ BIGNUM *BN_mod_inverse(BIGNUM *in,
276 * When we're done, (1) still holds. */ 302 * When we're done, (1) still holds. */
277 shift = 0; 303 shift = 0;
278 while (!BN_is_bit_set(B, shift)) /* note that 0 < B */ 304 while (!BN_is_bit_set(B, shift)) /* note that 0 < B */
279 { 305 {
280 shift++; 306 shift++;
281 307
282 if (BN_is_odd(X)) 308 if (BN_is_odd(X)) {
283 { 309 if (!BN_uadd(X, X, n))
284 if (!BN_uadd(X, X, n)) goto err; 310 goto err;
285 }
286 /* now X is even, so we can easily divide it by two */
287 if (!BN_rshift1(X, X)) goto err;
288 }
289 if (shift > 0)
290 {
291 if (!BN_rshift(B, B, shift)) goto err;
292 } 311 }
312 /* now X is even, so we can easily divide it by two */
313 if (!BN_rshift1(X, X))
314 goto err;
315 }
316 if (shift > 0) {
317 if (!BN_rshift(B, B, shift))
318 goto err;
319 }
293 320
294 321
295 /* Same for A and Y. Afterwards, (2) still holds. */ 322 /* Same for A and Y. Afterwards, (2) still holds. */
296 shift = 0; 323 shift = 0;
297 while (!BN_is_bit_set(A, shift)) /* note that 0 < A */ 324 while (!BN_is_bit_set(A, shift)) /* note that 0 < A */
298 { 325 {
299 shift++; 326 shift++;
300 327
301 if (BN_is_odd(Y)) 328 if (BN_is_odd(Y)) {
302 { 329 if (!BN_uadd(Y, Y, n))
303 if (!BN_uadd(Y, Y, n)) goto err; 330 goto err;
304 }
305 /* now Y is even */
306 if (!BN_rshift1(Y, Y)) goto err;
307 }
308 if (shift > 0)
309 {
310 if (!BN_rshift(A, A, shift)) goto err;
311 } 331 }
332 /* now Y is even */
333 if (!BN_rshift1(Y, Y))
334 goto err;
335 }
336 if (shift > 0) {
337 if (!BN_rshift(A, A, shift))
338 goto err;
339 }
340
312 341
313
314 /* We still have (1) and (2). 342 /* We still have (1) and (2).
315 * Both A and B are odd. 343 * Both A and B are odd.
316 * The following computations ensure that 344 * The following computations ensure that
@@ -322,91 +350,87 @@ BIGNUM *BN_mod_inverse(BIGNUM *in,
322 * 350 *
323 * and that either A or B is even in the next iteration. 351 * and that either A or B is even in the next iteration.
324 */ 352 */
325 if (BN_ucmp(B, A) >= 0) 353 if (BN_ucmp(B, A) >= 0) {
326 {
327 /* -sign*(X + Y)*a == B - A (mod |n|) */ 354 /* -sign*(X + Y)*a == B - A (mod |n|) */
328 if (!BN_uadd(X, X, Y)) goto err; 355 if (!BN_uadd(X, X, Y))
356 goto err;
329 /* NB: we could use BN_mod_add_quick(X, X, Y, n), but that 357 /* NB: we could use BN_mod_add_quick(X, X, Y, n), but that
330 * actually makes the algorithm slower */ 358 * actually makes the algorithm slower */
331 if (!BN_usub(B, B, A)) goto err; 359 if (!BN_usub(B, B, A))
332 } 360 goto err;
333 else 361 } else {
334 {
335 /* sign*(X + Y)*a == A - B (mod |n|) */ 362 /* sign*(X + Y)*a == A - B (mod |n|) */
336 if (!BN_uadd(Y, Y, X)) goto err; 363 if (!BN_uadd(Y, Y, X))
364 goto err;
337 /* as above, BN_mod_add_quick(Y, Y, X, n) would slow things down */ 365 /* as above, BN_mod_add_quick(Y, Y, X, n) would slow things down */
338 if (!BN_usub(A, A, B)) goto err; 366 if (!BN_usub(A, A, B))
339 } 367 goto err;
340 } 368 }
341 } 369 }
342 else 370 } else {
343 {
344 /* general inversion algorithm */ 371 /* general inversion algorithm */
345 372
346 while (!BN_is_zero(B)) 373 while (!BN_is_zero(B)) {
347 {
348 BIGNUM *tmp; 374 BIGNUM *tmp;
349 375
350 /* 376 /*
351 * 0 < B < A, 377 * 0 < B < A,
352 * (*) -sign*X*a == B (mod |n|), 378 * (*) -sign*X*a == B (mod |n|),
353 * sign*Y*a == A (mod |n|) 379 * sign*Y*a == A (mod |n|)
354 */ 380 */
355 381
356 /* (D, M) := (A/B, A%B) ... */ 382 /* (D, M) := (A/B, A%B) ... */
357 if (BN_num_bits(A) == BN_num_bits(B)) 383 if (BN_num_bits(A) == BN_num_bits(B)) {
358 { 384 if (!BN_one(D))
359 if (!BN_one(D)) goto err; 385 goto err;
360 if (!BN_sub(M,A,B)) goto err; 386 if (!BN_sub(M, A, B))
361 } 387 goto err;
362 else if (BN_num_bits(A) == BN_num_bits(B) + 1) 388 } else if (BN_num_bits(A) == BN_num_bits(B) + 1) {
363 {
364 /* A/B is 1, 2, or 3 */ 389 /* A/B is 1, 2, or 3 */
365 if (!BN_lshift1(T,B)) goto err; 390 if (!BN_lshift1(T, B))
366 if (BN_ucmp(A,T) < 0) 391 goto err;
367 { 392 if (BN_ucmp(A, T) < 0) {
368 /* A < 2*B, so D=1 */ 393 /* A < 2*B, so D=1 */
369 if (!BN_one(D)) goto err; 394 if (!BN_one(D))
370 if (!BN_sub(M,A,B)) goto err; 395 goto err;
371 } 396 if (!BN_sub(M, A, B))
372 else 397 goto err;
373 { 398 } else {
374 /* A >= 2*B, so D=2 or D=3 */ 399 /* A >= 2*B, so D=2 or D=3 */
375 if (!BN_sub(M,A,T)) goto err; 400 if (!BN_sub(M, A, T))
401 goto err;
376 if (!BN_add(D,T,B)) goto err; /* use D (:= 3*B) as temp */ 402 if (!BN_add(D,T,B)) goto err; /* use D (:= 3*B) as temp */
377 if (BN_ucmp(A,D) < 0) 403 if (BN_ucmp(A, D) < 0) {
378 {
379 /* A < 3*B, so D=2 */ 404 /* A < 3*B, so D=2 */
380 if (!BN_set_word(D,2)) goto err; 405 if (!BN_set_word(D, 2))
406 goto err;
381 /* M (= A - 2*B) already has the correct value */ 407 /* M (= A - 2*B) already has the correct value */
382 } 408 } else {
383 else
384 {
385 /* only D=3 remains */ 409 /* only D=3 remains */
386 if (!BN_set_word(D,3)) goto err; 410 if (!BN_set_word(D, 3))
411 goto err;
387 /* currently M = A - 2*B, but we need M = A - 3*B */ 412 /* currently M = A - 2*B, but we need M = A - 3*B */
388 if (!BN_sub(M,M,B)) goto err; 413 if (!BN_sub(M, M, B))
389 } 414 goto err;
390 } 415 }
391 } 416 }
392 else 417 } else {
393 { 418 if (!BN_div(D, M, A, B, ctx))
394 if (!BN_div(D,M,A,B,ctx)) goto err; 419 goto err;
395 } 420 }
396 421
397 /* Now 422 /* Now
398 * A = D*B + M; 423 * A = D*B + M;
399 * thus we have 424 * thus we have
400 * (**) sign*Y*a == D*B + M (mod |n|). 425 * (**) sign*Y*a == D*B + M (mod |n|).
401 */ 426 */
402 427 tmp = A; /* keep the BIGNUM object, the value does not matter */
403 tmp=A; /* keep the BIGNUM object, the value does not matter */ 428
404
405 /* (A, B) := (B, A mod B) ... */ 429 /* (A, B) := (B, A mod B) ... */
406 A=B; 430 A = B;
407 B=M; 431 B = M;
408 /* ... so we have 0 <= B < A again */ 432 /* ... so we have 0 <= B < A again */
409 433
410 /* Since the former M is now B and the former B is now A, 434 /* Since the former M is now B and the former B is now A,
411 * (**) translates into 435 * (**) translates into
412 * sign*Y*a == D*A + B (mod |n|), 436 * sign*Y*a == D*A + B (mod |n|),
@@ -425,41 +449,38 @@ BIGNUM *BN_mod_inverse(BIGNUM *in,
425 * sign*Y*a == A (mod |n|). 449 * sign*Y*a == A (mod |n|).
426 * Note that X and Y stay non-negative all the time. 450 * Note that X and Y stay non-negative all the time.
427 */ 451 */
428 452
429 /* most of the time D is very small, so we can optimize tmp := D*X+Y */ 453 /* most of the time D is very small, so we can optimize tmp := D*X+Y */
430 if (BN_is_one(D)) 454 if (BN_is_one(D)) {
431 { 455 if (!BN_add(tmp, X, Y))
432 if (!BN_add(tmp,X,Y)) goto err; 456 goto err;
433 } 457 } else {
434 else 458 if (BN_is_word(D, 2)) {
435 { 459 if (!BN_lshift1(tmp, X))
436 if (BN_is_word(D,2)) 460 goto err;
437 { 461 } else if (BN_is_word(D, 4)) {
438 if (!BN_lshift1(tmp,X)) goto err; 462 if (!BN_lshift(tmp, X, 2))
439 } 463 goto err;
440 else if (BN_is_word(D,4)) 464 } else if (D->top == 1) {
441 { 465 if (!BN_copy(tmp, X))
442 if (!BN_lshift(tmp,X,2)) goto err; 466 goto err;
443 } 467 if (!BN_mul_word(tmp, D->d[0]))
444 else if (D->top == 1) 468 goto err;
445 { 469 } else {
446 if (!BN_copy(tmp,X)) goto err; 470 if (!BN_mul(tmp, D,X, ctx))
447 if (!BN_mul_word(tmp,D->d[0])) goto err; 471 goto err;
448 }
449 else
450 {
451 if (!BN_mul(tmp,D,X,ctx)) goto err;
452 }
453 if (!BN_add(tmp,tmp,Y)) goto err;
454 } 472 }
455 473 if (!BN_add(tmp, tmp, Y))
456 M=Y; /* keep the BIGNUM object, the value does not matter */ 474 goto err;
457 Y=X;
458 X=tmp;
459 sign = -sign;
460 } 475 }
476
477 M = Y; /* keep the BIGNUM object, the value does not matter */
478 Y = X;
479 X = tmp;
480 sign = -sign;
461 } 481 }
462 482 }
483
463 /* 484 /*
464 * The while loop (Euclid's algorithm) ends when 485 * The while loop (Euclid's algorithm) ends when
465 * A == gcd(a,n); 486 * A == gcd(a,n);
@@ -468,49 +489,47 @@ BIGNUM *BN_mod_inverse(BIGNUM *in,
468 * where Y is non-negative. 489 * where Y is non-negative.
469 */ 490 */
470 491
471 if (sign < 0) 492 if (sign < 0) {
472 { 493 if (!BN_sub(Y, n, Y))
473 if (!BN_sub(Y,n,Y)) goto err; 494 goto err;
474 } 495 }
475 /* Now Y*a == A (mod |n|). */ 496 /* Now Y*a == A (mod |n|). */
476
477 497
478 if (BN_is_one(A)) 498 if (BN_is_one(A)) {
479 {
480 /* Y*a == 1 (mod |n|) */ 499 /* Y*a == 1 (mod |n|) */
481 if (!Y->neg && BN_ucmp(Y,n) < 0) 500 if (!Y->neg && BN_ucmp(Y, n) < 0) {
482 { 501 if (!BN_copy(R, Y))
483 if (!BN_copy(R,Y)) goto err; 502 goto err;
484 } 503 } else {
485 else 504 if (!BN_nnmod(R, Y,n, ctx))
486 { 505 goto err;
487 if (!BN_nnmod(R,Y,n,ctx)) goto err;
488 }
489 } 506 }
490 else 507 } else {
491 { 508 BNerr(BN_F_BN_MOD_INVERSE, BN_R_NO_INVERSE);
492 BNerr(BN_F_BN_MOD_INVERSE,BN_R_NO_INVERSE);
493 goto err; 509 goto err;
494 } 510 }
495 ret=R; 511 ret = R;
512
496err: 513err:
497 if ((ret == NULL) && (in == NULL)) BN_free(R); 514 if ((ret == NULL) && (in == NULL))
515 BN_free(R);
498 BN_CTX_end(ctx); 516 BN_CTX_end(ctx);
499 bn_check_top(ret); 517 bn_check_top(ret);
500 return(ret); 518 return (ret);
501 } 519}
502 520
503 521
504/* BN_mod_inverse_no_branch is a special version of BN_mod_inverse. 522/* BN_mod_inverse_no_branch is a special version of BN_mod_inverse.
505 * It does not contain branches that may leak sensitive information. 523 * It does not contain branches that may leak sensitive information.
506 */ 524 */
507static BIGNUM *BN_mod_inverse_no_branch(BIGNUM *in, 525static BIGNUM *
508 const BIGNUM *a, const BIGNUM *n, BN_CTX *ctx) 526BN_mod_inverse_no_branch(BIGNUM *in, const BIGNUM *a, const BIGNUM *n,
509 { 527 BN_CTX *ctx)
510 BIGNUM *A,*B,*X,*Y,*M,*D,*T,*R=NULL; 528{
529 BIGNUM *A, *B, *X, *Y, *M, *D, *T, *R = NULL;
511 BIGNUM local_A, local_B; 530 BIGNUM local_A, local_B;
512 BIGNUM *pA, *pB; 531 BIGNUM *pA, *pB;
513 BIGNUM *ret=NULL; 532 BIGNUM *ret = NULL;
514 int sign; 533 int sign;
515 534
516 bn_check_top(a); 535 bn_check_top(a);
@@ -524,29 +543,33 @@ static BIGNUM *BN_mod_inverse_no_branch(BIGNUM *in,
524 M = BN_CTX_get(ctx); 543 M = BN_CTX_get(ctx);
525 Y = BN_CTX_get(ctx); 544 Y = BN_CTX_get(ctx);
526 T = BN_CTX_get(ctx); 545 T = BN_CTX_get(ctx);
527 if (T == NULL) goto err; 546 if (T == NULL)
547 goto err;
528 548
529 if (in == NULL) 549 if (in == NULL)
530 R=BN_new(); 550 R = BN_new();
531 else 551 else
532 R=in; 552 R = in;
533 if (R == NULL) goto err; 553 if (R == NULL)
554 goto err;
534 555
535 BN_one(X); 556 BN_one(X);
536 BN_zero(Y); 557 BN_zero(Y);
537 if (BN_copy(B,a) == NULL) goto err; 558 if (BN_copy(B, a) == NULL)
538 if (BN_copy(A,n) == NULL) goto err; 559 goto err;
560 if (BN_copy(A, n) == NULL)
561 goto err;
539 A->neg = 0; 562 A->neg = 0;
540 563
541 if (B->neg || (BN_ucmp(B, A) >= 0)) 564 if (B->neg || (BN_ucmp(B, A) >= 0)) {
542 {
543 /* Turn BN_FLG_CONSTTIME flag on, so that when BN_div is invoked, 565 /* Turn BN_FLG_CONSTTIME flag on, so that when BN_div is invoked,
544 * BN_div_no_branch will be called eventually. 566 * BN_div_no_branch will be called eventually.
545 */ 567 */
546 pB = &local_B; 568 pB = &local_B;
547 BN_with_flags(pB, B, BN_FLG_CONSTTIME); 569 BN_with_flags(pB, B, BN_FLG_CONSTTIME);
548 if (!BN_nnmod(B, pB, A, ctx)) goto err; 570 if (!BN_nnmod(B, pB, A, ctx))
549 } 571 goto err;
572 }
550 sign = -1; 573 sign = -1;
551 /* From B = a mod |n|, A = |n| it follows that 574 /* From B = a mod |n|, A = |n| it follows that
552 * 575 *
@@ -555,10 +578,9 @@ static BIGNUM *BN_mod_inverse_no_branch(BIGNUM *in,
555 * sign*Y*a == A (mod |n|). 578 * sign*Y*a == A (mod |n|).
556 */ 579 */
557 580
558 while (!BN_is_zero(B)) 581 while (!BN_is_zero(B)) {
559 {
560 BIGNUM *tmp; 582 BIGNUM *tmp;
561 583
562 /* 584 /*
563 * 0 < B < A, 585 * 0 < B < A,
564 * (*) -sign*X*a == B (mod |n|), 586 * (*) -sign*X*a == B (mod |n|),
@@ -569,24 +591,24 @@ static BIGNUM *BN_mod_inverse_no_branch(BIGNUM *in,
569 * BN_div_no_branch will be called eventually. 591 * BN_div_no_branch will be called eventually.
570 */ 592 */
571 pA = &local_A; 593 pA = &local_A;
572 BN_with_flags(pA, A, BN_FLG_CONSTTIME); 594 BN_with_flags(pA, A, BN_FLG_CONSTTIME);
573 595
574 /* (D, M) := (A/B, A%B) ... */ 596 /* (D, M) := (A/B, A%B) ... */
575 if (!BN_div(D,M,pA,B,ctx)) goto err; 597 if (!BN_div(D, M, pA, B, ctx))
576 598 goto err;
599
577 /* Now 600 /* Now
578 * A = D*B + M; 601 * A = D*B + M;
579 * thus we have 602 * thus we have
580 * (**) sign*Y*a == D*B + M (mod |n|). 603 * (**) sign*Y*a == D*B + M (mod |n|).
581 */ 604 */
582 605 tmp = A; /* keep the BIGNUM object, the value does not matter */
583 tmp=A; /* keep the BIGNUM object, the value does not matter */ 606
584
585 /* (A, B) := (B, A mod B) ... */ 607 /* (A, B) := (B, A mod B) ... */
586 A=B; 608 A = B;
587 B=M; 609 B = M;
588 /* ... so we have 0 <= B < A again */ 610 /* ... so we have 0 <= B < A again */
589 611
590 /* Since the former M is now B and the former B is now A, 612 /* Since the former M is now B and the former B is now A,
591 * (**) translates into 613 * (**) translates into
592 * sign*Y*a == D*A + B (mod |n|), 614 * sign*Y*a == D*A + B (mod |n|),
@@ -605,16 +627,18 @@ static BIGNUM *BN_mod_inverse_no_branch(BIGNUM *in,
605 * sign*Y*a == A (mod |n|). 627 * sign*Y*a == A (mod |n|).
606 * Note that X and Y stay non-negative all the time. 628 * Note that X and Y stay non-negative all the time.
607 */ 629 */
608
609 if (!BN_mul(tmp,D,X,ctx)) goto err;
610 if (!BN_add(tmp,tmp,Y)) goto err;
611 630
612 M=Y; /* keep the BIGNUM object, the value does not matter */ 631 if (!BN_mul(tmp, D, X, ctx))
613 Y=X; 632 goto err;
614 X=tmp; 633 if (!BN_add(tmp, tmp, Y))
634 goto err;
635
636 M = Y; /* keep the BIGNUM object, the value does not matter */
637 Y = X;
638 X = tmp;
615 sign = -sign; 639 sign = -sign;
616 } 640 }
617 641
618 /* 642 /*
619 * The while loop (Euclid's algorithm) ends when 643 * The while loop (Euclid's algorithm) ends when
620 * A == gcd(a,n); 644 * A == gcd(a,n);
@@ -623,33 +647,31 @@ static BIGNUM *BN_mod_inverse_no_branch(BIGNUM *in,
623 * where Y is non-negative. 647 * where Y is non-negative.
624 */ 648 */
625 649
626 if (sign < 0) 650 if (sign < 0) {
627 { 651 if (!BN_sub(Y, n, Y))
628 if (!BN_sub(Y,n,Y)) goto err; 652 goto err;
629 } 653 }
630 /* Now Y*a == A (mod |n|). */ 654 /* Now Y*a == A (mod |n|). */
631 655
632 if (BN_is_one(A)) 656 if (BN_is_one(A)) {
633 {
634 /* Y*a == 1 (mod |n|) */ 657 /* Y*a == 1 (mod |n|) */
635 if (!Y->neg && BN_ucmp(Y,n) < 0) 658 if (!Y->neg && BN_ucmp(Y, n) < 0) {
636 { 659 if (!BN_copy(R, Y))
637 if (!BN_copy(R,Y)) goto err; 660 goto err;
638 } 661 } else {
639 else 662 if (!BN_nnmod(R, Y, n, ctx))
640 { 663 goto err;
641 if (!BN_nnmod(R,Y,n,ctx)) goto err;
642 }
643 } 664 }
644 else 665 } else {
645 { 666 BNerr(BN_F_BN_MOD_INVERSE_NO_BRANCH, BN_R_NO_INVERSE);
646 BNerr(BN_F_BN_MOD_INVERSE_NO_BRANCH,BN_R_NO_INVERSE);
647 goto err; 667 goto err;
648 } 668 }
649 ret=R; 669 ret = R;
670
650err: 671err:
651 if ((ret == NULL) && (in == NULL)) BN_free(R); 672 if ((ret == NULL) && (in == NULL))
673 BN_free(R);
652 BN_CTX_end(ctx); 674 BN_CTX_end(ctx);
653 bn_check_top(ret); 675 bn_check_top(ret);
654 return(ret); 676 return (ret);
655 } 677}
generated by cgit v1.2.3-55-g6feb (git 2.39.1) at 2025-08-15 05:05:21 +0000