summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/lib/libcrypto/bn/bn_mont.c442
1 files changed, 221 insertions, 221 deletions
diff --git a/src/lib/libcrypto/bn/bn_mont.c b/src/lib/libcrypto/bn/bn_mont.c
index 8b364ff716..4ddf7285c7 100644
--- a/src/lib/libcrypto/bn/bn_mont.c
+++ b/src/lib/libcrypto/bn/bn_mont.c
@@ -1,4 +1,4 @@
1/* $OpenBSD: bn_mont.c,v 1.34 2023/01/28 17:07:02 jsing Exp $ */ 1/* $OpenBSD: bn_mont.c,v 1.35 2023/02/01 04:48:08 jsing Exp $ */
2/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) 2/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
3 * All rights reserved. 3 * All rights reserved.
4 * 4 *
@@ -121,6 +121,226 @@
121 121
122#include "bn_local.h" 122#include "bn_local.h"
123 123
124BN_MONT_CTX *
125BN_MONT_CTX_new(void)
126{
127 BN_MONT_CTX *ret;
128
129 if ((ret = malloc(sizeof(BN_MONT_CTX))) == NULL)
130 return (NULL);
131
132 BN_MONT_CTX_init(ret);
133 ret->flags = BN_FLG_MALLOCED;
134 return (ret);
135}
136
137void
138BN_MONT_CTX_init(BN_MONT_CTX *ctx)
139{
140 ctx->ri = 0;
141 BN_init(&(ctx->RR));
142 BN_init(&(ctx->N));
143 BN_init(&(ctx->Ni));
144 ctx->n0[0] = ctx->n0[1] = 0;
145 ctx->flags = 0;
146}
147
148void
149BN_MONT_CTX_free(BN_MONT_CTX *mont)
150{
151 if (mont == NULL)
152 return;
153
154 BN_clear_free(&(mont->RR));
155 BN_clear_free(&(mont->N));
156 BN_clear_free(&(mont->Ni));
157 if (mont->flags & BN_FLG_MALLOCED)
158 free(mont);
159}
160
161int
162BN_MONT_CTX_set(BN_MONT_CTX *mont, const BIGNUM *mod, BN_CTX *ctx)
163{
164 int ret = 0;
165 BIGNUM *Ri, *R;
166
167 if (BN_is_zero(mod))
168 return 0;
169
170 BN_CTX_start(ctx);
171 if ((Ri = BN_CTX_get(ctx)) == NULL)
172 goto err;
173 R = &(mont->RR); /* grab RR as a temp */
174 if (!BN_copy(&(mont->N), mod))
175 goto err; /* Set N */
176 mont->N.neg = 0;
177
178#ifdef MONT_WORD
179 {
180 BIGNUM tmod;
181 BN_ULONG buf[2];
182
183 BN_init(&tmod);
184 tmod.d = buf;
185 tmod.dmax = 2;
186 tmod.neg = 0;
187
188 mont->ri = (BN_num_bits(mod) +
189 (BN_BITS2 - 1)) / BN_BITS2 * BN_BITS2;
190
191#if defined(OPENSSL_BN_ASM_MONT) && (BN_BITS2<=32)
192 /* Only certain BN_BITS2<=32 platforms actually make use of
193 * n0[1], and we could use the #else case (with a shorter R
194 * value) for the others. However, currently only the assembler
195 * files do know which is which. */
196
197 BN_zero(R);
198 if (!(BN_set_bit(R, 2 * BN_BITS2)))
199 goto err;
200
201 tmod.top = 0;
202 if ((buf[0] = mod->d[0]))
203 tmod.top = 1;
204 if ((buf[1] = mod->top > 1 ? mod->d[1] : 0))
205 tmod.top = 2;
206
207 if ((BN_mod_inverse_ct(Ri, R, &tmod, ctx)) == NULL)
208 goto err;
209 if (!BN_lshift(Ri, Ri, 2 * BN_BITS2))
210 goto err; /* R*Ri */
211 if (!BN_is_zero(Ri)) {
212 if (!BN_sub_word(Ri, 1))
213 goto err;
214 }
215 else /* if N mod word size == 1 */
216 {
217 if (!bn_wexpand(Ri, 2))
218 goto err;
219 /* Ri-- (mod double word size) */
220 Ri->neg = 0;
221 Ri->d[0] = BN_MASK2;
222 Ri->d[1] = BN_MASK2;
223 Ri->top = 2;
224 }
225 if (!BN_div_ct(Ri, NULL, Ri, &tmod, ctx))
226 goto err;
227 /* Ni = (R*Ri-1)/N,
228 * keep only couple of least significant words: */
229 mont->n0[0] = (Ri->top > 0) ? Ri->d[0] : 0;
230 mont->n0[1] = (Ri->top > 1) ? Ri->d[1] : 0;
231#else
232 BN_zero(R);
233 if (!(BN_set_bit(R, BN_BITS2)))
234 goto err; /* R */
235
236 buf[0] = mod->d[0]; /* tmod = N mod word size */
237 buf[1] = 0;
238 tmod.top = buf[0] != 0 ? 1 : 0;
239 /* Ri = R^-1 mod N*/
240 if ((BN_mod_inverse_ct(Ri, R, &tmod, ctx)) == NULL)
241 goto err;
242 if (!BN_lshift(Ri, Ri, BN_BITS2))
243 goto err; /* R*Ri */
244 if (!BN_is_zero(Ri)) {
245 if (!BN_sub_word(Ri, 1))
246 goto err;
247 }
248 else /* if N mod word size == 1 */
249 {
250 if (!BN_set_word(Ri, BN_MASK2))
251 goto err; /* Ri-- (mod word size) */
252 }
253 if (!BN_div_ct(Ri, NULL, Ri, &tmod, ctx))
254 goto err;
255 /* Ni = (R*Ri-1)/N,
256 * keep only least significant word: */
257 mont->n0[0] = (Ri->top > 0) ? Ri->d[0] : 0;
258 mont->n0[1] = 0;
259#endif
260 }
261#else /* !MONT_WORD */
262 { /* bignum version */
263 mont->ri = BN_num_bits(&mont->N);
264 BN_zero(R);
265 if (!BN_set_bit(R, mont->ri))
266 goto err; /* R = 2^ri */
267 /* Ri = R^-1 mod N*/
268 if ((BN_mod_inverse_ct(Ri, R, &mont->N, ctx)) == NULL)
269 goto err;
270 if (!BN_lshift(Ri, Ri, mont->ri))
271 goto err; /* R*Ri */
272 if (!BN_sub_word(Ri, 1))
273 goto err;
274 /* Ni = (R*Ri-1) / N */
275 if (!BN_div_ct(&(mont->Ni), NULL, Ri, &mont->N, ctx))
276 goto err;
277 }
278#endif
279
280 /* setup RR for conversions */
281 BN_zero(&(mont->RR));
282 if (!BN_set_bit(&(mont->RR), mont->ri*2))
283 goto err;
284 if (!BN_mod_ct(&(mont->RR), &(mont->RR), &(mont->N), ctx))
285 goto err;
286
287 ret = 1;
288
289err:
290 BN_CTX_end(ctx);
291 return ret;
292}
293
294BN_MONT_CTX *
295BN_MONT_CTX_copy(BN_MONT_CTX *to, BN_MONT_CTX *from)
296{
297 if (to == from)
298 return (to);
299
300 if (!BN_copy(&(to->RR), &(from->RR)))
301 return NULL;
302 if (!BN_copy(&(to->N), &(from->N)))
303 return NULL;
304 if (!BN_copy(&(to->Ni), &(from->Ni)))
305 return NULL;
306 to->ri = from->ri;
307 to->n0[0] = from->n0[0];
308 to->n0[1] = from->n0[1];
309 return (to);
310}
311
312BN_MONT_CTX *
313BN_MONT_CTX_set_locked(BN_MONT_CTX **pmont, int lock, const BIGNUM *mod,
314 BN_CTX *ctx)
315{
316 int got_write_lock = 0;
317 BN_MONT_CTX *ret;
318
319 CRYPTO_r_lock(lock);
320 if (!*pmont) {
321 CRYPTO_r_unlock(lock);
322 CRYPTO_w_lock(lock);
323 got_write_lock = 1;
324
325 if (!*pmont) {
326 ret = BN_MONT_CTX_new();
327 if (ret && !BN_MONT_CTX_set(ret, mod, ctx))
328 BN_MONT_CTX_free(ret);
329 else
330 *pmont = ret;
331 }
332 }
333
334 ret = *pmont;
335
336 if (got_write_lock)
337 CRYPTO_w_unlock(lock);
338 else
339 CRYPTO_r_unlock(lock);
340
341 return ret;
342}
343
124#ifdef OPENSSL_NO_ASM 344#ifdef OPENSSL_NO_ASM
125#ifdef OPENSSL_BN_ASM_MONT 345#ifdef OPENSSL_BN_ASM_MONT
126int 346int
@@ -371,223 +591,3 @@ err:
371#endif /* MONT_WORD */ 591#endif /* MONT_WORD */
372 return (retn); 592 return (retn);
373} 593}
374
375BN_MONT_CTX *
376BN_MONT_CTX_new(void)
377{
378 BN_MONT_CTX *ret;
379
380 if ((ret = malloc(sizeof(BN_MONT_CTX))) == NULL)
381 return (NULL);
382
383 BN_MONT_CTX_init(ret);
384 ret->flags = BN_FLG_MALLOCED;
385 return (ret);
386}
387
388void
389BN_MONT_CTX_init(BN_MONT_CTX *ctx)
390{
391 ctx->ri = 0;
392 BN_init(&(ctx->RR));
393 BN_init(&(ctx->N));
394 BN_init(&(ctx->Ni));
395 ctx->n0[0] = ctx->n0[1] = 0;
396 ctx->flags = 0;
397}
398
399void
400BN_MONT_CTX_free(BN_MONT_CTX *mont)
401{
402 if (mont == NULL)
403 return;
404
405 BN_clear_free(&(mont->RR));
406 BN_clear_free(&(mont->N));
407 BN_clear_free(&(mont->Ni));
408 if (mont->flags & BN_FLG_MALLOCED)
409 free(mont);
410}
411
412int
413BN_MONT_CTX_set(BN_MONT_CTX *mont, const BIGNUM *mod, BN_CTX *ctx)
414{
415 int ret = 0;
416 BIGNUM *Ri, *R;
417
418 if (BN_is_zero(mod))
419 return 0;
420
421 BN_CTX_start(ctx);
422 if ((Ri = BN_CTX_get(ctx)) == NULL)
423 goto err;
424 R = &(mont->RR); /* grab RR as a temp */
425 if (!BN_copy(&(mont->N), mod))
426 goto err; /* Set N */
427 mont->N.neg = 0;
428
429#ifdef MONT_WORD
430 {
431 BIGNUM tmod;
432 BN_ULONG buf[2];
433
434 BN_init(&tmod);
435 tmod.d = buf;
436 tmod.dmax = 2;
437 tmod.neg = 0;
438
439 mont->ri = (BN_num_bits(mod) +
440 (BN_BITS2 - 1)) / BN_BITS2 * BN_BITS2;
441
442#if defined(OPENSSL_BN_ASM_MONT) && (BN_BITS2<=32)
443 /* Only certain BN_BITS2<=32 platforms actually make use of
444 * n0[1], and we could use the #else case (with a shorter R
445 * value) for the others. However, currently only the assembler
446 * files do know which is which. */
447
448 BN_zero(R);
449 if (!(BN_set_bit(R, 2 * BN_BITS2)))
450 goto err;
451
452 tmod.top = 0;
453 if ((buf[0] = mod->d[0]))
454 tmod.top = 1;
455 if ((buf[1] = mod->top > 1 ? mod->d[1] : 0))
456 tmod.top = 2;
457
458 if ((BN_mod_inverse_ct(Ri, R, &tmod, ctx)) == NULL)
459 goto err;
460 if (!BN_lshift(Ri, Ri, 2 * BN_BITS2))
461 goto err; /* R*Ri */
462 if (!BN_is_zero(Ri)) {
463 if (!BN_sub_word(Ri, 1))
464 goto err;
465 }
466 else /* if N mod word size == 1 */
467 {
468 if (!bn_wexpand(Ri, 2))
469 goto err;
470 /* Ri-- (mod double word size) */
471 Ri->neg = 0;
472 Ri->d[0] = BN_MASK2;
473 Ri->d[1] = BN_MASK2;
474 Ri->top = 2;
475 }
476 if (!BN_div_ct(Ri, NULL, Ri, &tmod, ctx))
477 goto err;
478 /* Ni = (R*Ri-1)/N,
479 * keep only couple of least significant words: */
480 mont->n0[0] = (Ri->top > 0) ? Ri->d[0] : 0;
481 mont->n0[1] = (Ri->top > 1) ? Ri->d[1] : 0;
482#else
483 BN_zero(R);
484 if (!(BN_set_bit(R, BN_BITS2)))
485 goto err; /* R */
486
487 buf[0] = mod->d[0]; /* tmod = N mod word size */
488 buf[1] = 0;
489 tmod.top = buf[0] != 0 ? 1 : 0;
490 /* Ri = R^-1 mod N*/
491 if ((BN_mod_inverse_ct(Ri, R, &tmod, ctx)) == NULL)
492 goto err;
493 if (!BN_lshift(Ri, Ri, BN_BITS2))
494 goto err; /* R*Ri */
495 if (!BN_is_zero(Ri)) {
496 if (!BN_sub_word(Ri, 1))
497 goto err;
498 }
499 else /* if N mod word size == 1 */
500 {
501 if (!BN_set_word(Ri, BN_MASK2))
502 goto err; /* Ri-- (mod word size) */
503 }
504 if (!BN_div_ct(Ri, NULL, Ri, &tmod, ctx))
505 goto err;
506 /* Ni = (R*Ri-1)/N,
507 * keep only least significant word: */
508 mont->n0[0] = (Ri->top > 0) ? Ri->d[0] : 0;
509 mont->n0[1] = 0;
510#endif
511 }
512#else /* !MONT_WORD */
513 { /* bignum version */
514 mont->ri = BN_num_bits(&mont->N);
515 BN_zero(R);
516 if (!BN_set_bit(R, mont->ri))
517 goto err; /* R = 2^ri */
518 /* Ri = R^-1 mod N*/
519 if ((BN_mod_inverse_ct(Ri, R, &mont->N, ctx)) == NULL)
520 goto err;
521 if (!BN_lshift(Ri, Ri, mont->ri))
522 goto err; /* R*Ri */
523 if (!BN_sub_word(Ri, 1))
524 goto err;
525 /* Ni = (R*Ri-1) / N */
526 if (!BN_div_ct(&(mont->Ni), NULL, Ri, &mont->N, ctx))
527 goto err;
528 }
529#endif
530
531 /* setup RR for conversions */
532 BN_zero(&(mont->RR));
533 if (!BN_set_bit(&(mont->RR), mont->ri*2))
534 goto err;
535 if (!BN_mod_ct(&(mont->RR), &(mont->RR), &(mont->N), ctx))
536 goto err;
537
538 ret = 1;
539
540err:
541 BN_CTX_end(ctx);
542 return ret;
543}
544
545BN_MONT_CTX *
546BN_MONT_CTX_copy(BN_MONT_CTX *to, BN_MONT_CTX *from)
547{
548 if (to == from)
549 return (to);
550
551 if (!BN_copy(&(to->RR), &(from->RR)))
552 return NULL;
553 if (!BN_copy(&(to->N), &(from->N)))
554 return NULL;
555 if (!BN_copy(&(to->Ni), &(from->Ni)))
556 return NULL;
557 to->ri = from->ri;
558 to->n0[0] = from->n0[0];
559 to->n0[1] = from->n0[1];
560 return (to);
561}
562
563BN_MONT_CTX *
564BN_MONT_CTX_set_locked(BN_MONT_CTX **pmont, int lock, const BIGNUM *mod,
565 BN_CTX *ctx)
566{
567 int got_write_lock = 0;
568 BN_MONT_CTX *ret;
569
570 CRYPTO_r_lock(lock);
571 if (!*pmont) {
572 CRYPTO_r_unlock(lock);
573 CRYPTO_w_lock(lock);
574 got_write_lock = 1;
575
576 if (!*pmont) {
577 ret = BN_MONT_CTX_new();
578 if (ret && !BN_MONT_CTX_set(ret, mod, ctx))
579 BN_MONT_CTX_free(ret);
580 else
581 *pmont = ret;
582 }
583 }
584
585 ret = *pmont;
586
587 if (got_write_lock)
588 CRYPTO_w_unlock(lock);
589 else
590 CRYPTO_r_unlock(lock);
591
592 return ret;
593}
generated by cgit v1.2.3-55-g6feb (git 2.39.1) at 2025-03-21 19:49:59 +0000