1 /* $OpenBSD: bn_mont.c,v 1.63 2024/03/26 04:23:04 jsing 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-2006 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 /*
113 * Details about Montgomery multiplication algorithms can be found at
114 * http://security.ece.orst.edu/publications.html, e.g.
115 * http://security.ece.orst.edu/koc/papers/j37acmon.pdf and
116 * sections 3.8 and 4.2 in http://security.ece.orst.edu/koc/papers/r01rsasw.pdf
117 */
118
119 #include <stdio.h>
120 #include <stdint.h>
121 #include <string.h>
122
123 #include "bn_internal.h"
124 #include "bn_local.h"
125
126 BN_MONT_CTX *
BN_MONT_CTX_new(void)127 BN_MONT_CTX_new(void)
128 {
129 BN_MONT_CTX *mctx;
130
131 if ((mctx = calloc(1, sizeof(BN_MONT_CTX))) == NULL)
132 return NULL;
133 mctx->flags = BN_FLG_MALLOCED;
134
135 BN_init(&mctx->RR);
136 BN_init(&mctx->N);
137
138 return mctx;
139 }
140 LCRYPTO_ALIAS(BN_MONT_CTX_new);
141
142 void
BN_MONT_CTX_free(BN_MONT_CTX * mctx)143 BN_MONT_CTX_free(BN_MONT_CTX *mctx)
144 {
145 if (mctx == NULL)
146 return;
147
148 BN_free(&mctx->RR);
149 BN_free(&mctx->N);
150
151 if (mctx->flags & BN_FLG_MALLOCED)
152 free(mctx);
153 }
154 LCRYPTO_ALIAS(BN_MONT_CTX_free);
155
156 BN_MONT_CTX *
BN_MONT_CTX_copy(BN_MONT_CTX * dst,BN_MONT_CTX * src)157 BN_MONT_CTX_copy(BN_MONT_CTX *dst, BN_MONT_CTX *src)
158 {
159 if (dst == src)
160 return dst;
161
162 if (!bn_copy(&dst->RR, &src->RR))
163 return NULL;
164 if (!bn_copy(&dst->N, &src->N))
165 return NULL;
166
167 dst->ri = src->ri;
168 dst->n0[0] = src->n0[0];
169 dst->n0[1] = src->n0[1];
170
171 return dst;
172 }
173 LCRYPTO_ALIAS(BN_MONT_CTX_copy);
174
175 int
BN_MONT_CTX_set(BN_MONT_CTX * mont,const BIGNUM * mod,BN_CTX * ctx)176 BN_MONT_CTX_set(BN_MONT_CTX *mont, const BIGNUM *mod, BN_CTX *ctx)
177 {
178 BIGNUM *N, *Ninv, *Rinv, *R;
179 int ret = 0;
180
181 BN_CTX_start(ctx);
182
183 if ((N = BN_CTX_get(ctx)) == NULL)
184 goto err;
185 if ((Ninv = BN_CTX_get(ctx)) == NULL)
186 goto err;
187 if ((R = BN_CTX_get(ctx)) == NULL)
188 goto err;
189 if ((Rinv = BN_CTX_get(ctx)) == NULL)
190 goto err;
191
192 /* Save modulus and determine length of R. */
193 if (BN_is_zero(mod))
194 goto err;
195 if (!bn_copy(&mont->N, mod))
196 goto err;
197 mont->N.neg = 0;
198 mont->ri = ((BN_num_bits(mod) + BN_BITS2 - 1) / BN_BITS2) * BN_BITS2;
199 if (mont->ri * 2 < mont->ri)
200 goto err;
201
202 /*
203 * Compute Ninv = (R * Rinv - 1)/N mod R, for R = 2^64. This provides
204 * a single or double word result (dependent on BN word size), that is
205 * later used to implement Montgomery reduction.
206 */
207 BN_zero(R);
208 if (!BN_set_bit(R, 64))
209 goto err;
210
211 /* N = N mod R. */
212 if (!bn_wexpand(N, 2))
213 goto err;
214 if (!BN_set_word(N, mod->d[0]))
215 goto err;
216 #if BN_BITS2 == 32
217 if (mod->top > 1) {
218 N->d[1] = mod->d[1];
219 N->top += bn_ct_ne_zero(N->d[1]);
220 }
221 #endif
222
223 /* Rinv = R^-1 mod N */
224 if ((BN_mod_inverse_ct(Rinv, R, N, ctx)) == NULL)
225 goto err;
226
227 /* Ninv = (R * Rinv - 1) / N */
228 if (!BN_lshift(Ninv, Rinv, 64))
229 goto err;
230 if (BN_is_zero(Ninv)) {
231 /* R * Rinv == 0, set to R so that R * Rinv - 1 is mod R. */
232 if (!BN_set_bit(Ninv, 64))
233 goto err;
234 }
235 if (!BN_sub_word(Ninv, 1))
236 goto err;
237 if (!BN_div_ct(Ninv, NULL, Ninv, N, ctx))
238 goto err;
239
240 /* Store least significant word(s) of Ninv. */
241 mont->n0[0] = mont->n0[1] = 0;
242 if (Ninv->top > 0)
243 mont->n0[0] = Ninv->d[0];
244 #if BN_BITS2 == 32
245 /* Some BN_BITS2 == 32 platforms (namely parisc) use two words of Ninv. */
246 if (Ninv->top > 1)
247 mont->n0[1] = Ninv->d[1];
248 #endif
249
250 /* Compute RR = R * R mod N, for use when converting to Montgomery form. */
251 BN_zero(&mont->RR);
252 if (!BN_set_bit(&mont->RR, mont->ri * 2))
253 goto err;
254 if (!BN_mod_ct(&mont->RR, &mont->RR, &mont->N, ctx))
255 goto err;
256
257 ret = 1;
258 err:
259 BN_CTX_end(ctx);
260
261 return ret;
262 }
263 LCRYPTO_ALIAS(BN_MONT_CTX_set);
264
265 BN_MONT_CTX *
BN_MONT_CTX_set_locked(BN_MONT_CTX ** pmctx,int lock,const BIGNUM * mod,BN_CTX * ctx)266 BN_MONT_CTX_set_locked(BN_MONT_CTX **pmctx, int lock, const BIGNUM *mod,
267 BN_CTX *ctx)
268 {
269 BN_MONT_CTX *mctx = NULL;
270
271 CRYPTO_r_lock(lock);
272 mctx = *pmctx;
273 CRYPTO_r_unlock(lock);
274
275 if (mctx != NULL)
276 goto done;
277
278 if ((mctx = BN_MONT_CTX_new()) == NULL)
279 goto err;
280 if (!BN_MONT_CTX_set(mctx, mod, ctx))
281 goto err;
282
283 CRYPTO_w_lock(lock);
284 if (*pmctx != NULL) {
285 /* Someone else raced us... */
286 BN_MONT_CTX_free(mctx);
287 mctx = *pmctx;
288 } else {
289 *pmctx = mctx;
290 }
291 CRYPTO_w_unlock(lock);
292
293 goto done;
294 err:
295 BN_MONT_CTX_free(mctx);
296 mctx = NULL;
297 done:
298 return mctx;
299 }
300 LCRYPTO_ALIAS(BN_MONT_CTX_set_locked);
301
302 /*
303 * bn_montgomery_reduce() performs Montgomery reduction, reducing the input
304 * from its Montgomery form aR to a, returning the result in r. Note that the
305 * input is mutated in the process of performing the reduction, destroying its
306 * original value.
307 */
308 static int
bn_montgomery_reduce(BIGNUM * r,BIGNUM * a,BN_MONT_CTX * mctx)309 bn_montgomery_reduce(BIGNUM *r, BIGNUM *a, BN_MONT_CTX *mctx)
310 {
311 BIGNUM *n;
312 BN_ULONG *ap, *rp, n0, v, carry, mask;
313 int i, max, n_len;
314
315 n = &mctx->N;
316 n_len = mctx->N.top;
317
318 if (n_len == 0) {
319 BN_zero(r);
320 return 1;
321 }
322
323 if (!bn_wexpand(r, n_len))
324 return 0;
325
326 /*
327 * Expand a to twice the length of the modulus, zero if necessary.
328 * XXX - make this a requirement of the caller.
329 */
330 if ((max = 2 * n_len) < n_len)
331 return 0;
332 if (!bn_wexpand(a, max))
333 return 0;
334 for (i = a->top; i < max; i++)
335 a->d[i] = 0;
336
337 carry = 0;
338 n0 = mctx->n0[0];
339
340 /* Add multiples of the modulus, so that it becomes divisible by R. */
341 for (i = 0; i < n_len; i++) {
342 v = bn_mul_add_words(&a->d[i], n->d, n_len, a->d[i] * n0);
343 bn_addw_addw(v, a->d[i + n_len], carry, &carry,
344 &a->d[i + n_len]);
345 }
346
347 /* Divide by R (this is the equivalent of right shifting by n_len). */
348 ap = &a->d[n_len];
349
350 /*
351 * The output is now in the range of [0, 2N). Attempt to reduce once by
352 * subtracting the modulus. If the reduction was necessary then the
353 * result is already in r, otherwise copy the value prior to reduction
354 * from the top half of a.
355 */
356 mask = carry - bn_sub_words(r->d, ap, n->d, n_len);
357
358 rp = r->d;
359 for (i = 0; i < n_len; i++) {
360 *rp = (*rp & ~mask) | (*ap & mask);
361 rp++;
362 ap++;
363 }
364 r->top = n_len;
365
366 bn_correct_top(r);
367
368 BN_set_negative(r, a->neg ^ n->neg);
369
370 return 1;
371 }
372
373 static int
bn_mod_mul_montgomery_simple(BIGNUM * r,const BIGNUM * a,const BIGNUM * b,BN_MONT_CTX * mctx,BN_CTX * ctx)374 bn_mod_mul_montgomery_simple(BIGNUM *r, const BIGNUM *a, const BIGNUM *b,
375 BN_MONT_CTX *mctx, BN_CTX *ctx)
376 {
377 BIGNUM *tmp;
378 int ret = 0;
379
380 BN_CTX_start(ctx);
381
382 if ((tmp = BN_CTX_get(ctx)) == NULL)
383 goto err;
384
385 if (a == b) {
386 if (!BN_sqr(tmp, a, ctx))
387 goto err;
388 } else {
389 if (!BN_mul(tmp, a, b, ctx))
390 goto err;
391 }
392
393 /* Reduce from aRR to aR. */
394 if (!bn_montgomery_reduce(r, tmp, mctx))
395 goto err;
396
397 ret = 1;
398 err:
399 BN_CTX_end(ctx);
400
401 return ret;
402 }
403
404 static void
bn_montgomery_multiply_word(const BN_ULONG * ap,BN_ULONG b,const BN_ULONG * np,BN_ULONG * tp,BN_ULONG w,BN_ULONG * carry_a,BN_ULONG * carry_n,int n_len)405 bn_montgomery_multiply_word(const BN_ULONG *ap, BN_ULONG b, const BN_ULONG *np,
406 BN_ULONG *tp, BN_ULONG w, BN_ULONG *carry_a, BN_ULONG *carry_n, int n_len)
407 {
408 BN_ULONG x3, x2, x1, x0;
409
410 *carry_a = *carry_n = 0;
411
412 while (n_len & ~3) {
413 bn_qwmulw_addqw_addw(ap[3], ap[2], ap[1], ap[0], b,
414 tp[3], tp[2], tp[1], tp[0], *carry_a, carry_a,
415 &x3, &x2, &x1, &x0);
416 bn_qwmulw_addqw_addw(np[3], np[2], np[1], np[0], w,
417 x3, x2, x1, x0, *carry_n, carry_n,
418 &tp[3], &tp[2], &tp[1], &tp[0]);
419 ap += 4;
420 np += 4;
421 tp += 4;
422 n_len -= 4;
423 }
424 while (n_len > 0) {
425 bn_mulw_addw_addw(ap[0], b, tp[0], *carry_a, carry_a, &x0);
426 bn_mulw_addw_addw(np[0], w, x0, *carry_n, carry_n, &tp[0]);
427 ap++;
428 np++;
429 tp++;
430 n_len--;
431 }
432 }
433
434 /*
435 * bn_montgomery_multiply_words() computes r = aR * bR * R^-1 = abR for the
436 * given word arrays. The caller must ensure that rp, ap, bp and np are all
437 * n_len words in length, while tp must be n_len * 2 + 2 words in length.
438 */
439 static void
bn_montgomery_multiply_words(BN_ULONG * rp,const BN_ULONG * ap,const BN_ULONG * bp,const BN_ULONG * np,BN_ULONG * tp,BN_ULONG n0,int n_len)440 bn_montgomery_multiply_words(BN_ULONG *rp, const BN_ULONG *ap, const BN_ULONG *bp,
441 const BN_ULONG *np, BN_ULONG *tp, BN_ULONG n0, int n_len)
442 {
443 BN_ULONG a0, b, carry_a, carry_n, carry, mask, w;
444 int i;
445
446 carry = 0;
447
448 for (i = 0; i < n_len; i++)
449 tp[i] = 0;
450
451 a0 = ap[0];
452
453 for (i = 0; i < n_len; i++) {
454 b = bp[i];
455
456 /* Compute new t[0] * n0, as we need it for this iteration. */
457 w = (a0 * b + tp[0]) * n0;
458
459 bn_montgomery_multiply_word(ap, b, np, tp, w, &carry_a,
460 &carry_n, n_len);
461 bn_addw_addw(carry_a, carry_n, carry, &carry, &tp[n_len]);
462
463 tp++;
464 }
465 tp[n_len] = carry;
466
467 /*
468 * The output is now in the range of [0, 2N). Attempt to reduce once by
469 * subtracting the modulus. If the reduction was necessary then the
470 * result is already in r, otherwise copy the value prior to reduction
471 * from tp.
472 */
473 mask = bn_ct_ne_zero(tp[n_len]) - bn_sub_words(rp, tp, np, n_len);
474
475 for (i = 0; i < n_len; i++) {
476 *rp = (*rp & ~mask) | (*tp & mask);
477 rp++;
478 tp++;
479 }
480 }
481
482 /*
483 * bn_montgomery_multiply() computes r = aR * bR * R^-1 = abR for the given
484 * BIGNUMs. The caller must ensure that the modulus is two or more words in
485 * length and that a and b have the same number of words as the modulus.
486 */
487 static int
bn_montgomery_multiply(BIGNUM * r,const BIGNUM * a,const BIGNUM * b,BN_MONT_CTX * mctx,BN_CTX * ctx)488 bn_montgomery_multiply(BIGNUM *r, const BIGNUM *a, const BIGNUM *b,
489 BN_MONT_CTX *mctx, BN_CTX *ctx)
490 {
491 BIGNUM *t;
492 int ret = 0;
493
494 BN_CTX_start(ctx);
495
496 if (mctx->N.top <= 1 || a->top != mctx->N.top || b->top != mctx->N.top)
497 goto err;
498 if (!bn_wexpand(r, mctx->N.top))
499 goto err;
500
501 if ((t = BN_CTX_get(ctx)) == NULL)
502 goto err;
503 if (!bn_wexpand(t, mctx->N.top * 2 + 2))
504 goto err;
505
506 bn_montgomery_multiply_words(r->d, a->d, b->d, mctx->N.d, t->d,
507 mctx->n0[0], mctx->N.top);
508
509 r->top = mctx->N.top;
510 bn_correct_top(r);
511
512 BN_set_negative(r, a->neg ^ b->neg);
513
514 ret = 1;
515 err:
516 BN_CTX_end(ctx);
517
518 return ret;
519 }
520
521 #ifndef OPENSSL_BN_ASM_MONT
522 static int
bn_mod_mul_montgomery(BIGNUM * r,const BIGNUM * a,const BIGNUM * b,BN_MONT_CTX * mctx,BN_CTX * ctx)523 bn_mod_mul_montgomery(BIGNUM *r, const BIGNUM *a, const BIGNUM *b,
524 BN_MONT_CTX *mctx, BN_CTX *ctx)
525 {
526 if (mctx->N.top <= 1 || a->top != mctx->N.top || b->top != mctx->N.top)
527 return bn_mod_mul_montgomery_simple(r, a, b, mctx, ctx);
528
529 return bn_montgomery_multiply(r, a, b, mctx, ctx);
530 }
531 #else
532
533 static int
bn_mod_mul_montgomery(BIGNUM * r,const BIGNUM * a,const BIGNUM * b,BN_MONT_CTX * mctx,BN_CTX * ctx)534 bn_mod_mul_montgomery(BIGNUM *r, const BIGNUM *a, const BIGNUM *b,
535 BN_MONT_CTX *mctx, BN_CTX *ctx)
536 {
537 if (mctx->N.top <= 1 || a->top != mctx->N.top || b->top != mctx->N.top)
538 return bn_mod_mul_montgomery_simple(r, a, b, mctx, ctx);
539
540 /*
541 * Legacy bn_mul_mont() performs stack based allocation, without
542 * size limitation. Allowing a large size results in the stack
543 * being blown.
544 */
545 if (mctx->N.top > (8 * 1024 / sizeof(BN_ULONG)))
546 return bn_montgomery_multiply(r, a, b, mctx, ctx);
547
548 if (!bn_wexpand(r, mctx->N.top))
549 return 0;
550
551 /*
552 * Legacy bn_mul_mont() can indicate that we should "fallback" to
553 * another implementation.
554 */
555 if (!bn_mul_mont(r->d, a->d, b->d, mctx->N.d, mctx->n0, mctx->N.top))
556 return bn_montgomery_multiply(r, a, b, mctx, ctx);
557
558 r->top = mctx->N.top;
559 bn_correct_top(r);
560
561 BN_set_negative(r, a->neg ^ b->neg);
562
563 return (1);
564 }
565 #endif
566
567 int
BN_mod_mul_montgomery(BIGNUM * r,const BIGNUM * a,const BIGNUM * b,BN_MONT_CTX * mctx,BN_CTX * ctx)568 BN_mod_mul_montgomery(BIGNUM *r, const BIGNUM *a, const BIGNUM *b,
569 BN_MONT_CTX *mctx, BN_CTX *ctx)
570 {
571 /* Compute r = aR * bR * R^-1 mod N = abR mod N */
572 return bn_mod_mul_montgomery(r, a, b, mctx, ctx);
573 }
574 LCRYPTO_ALIAS(BN_mod_mul_montgomery);
575
576 int
BN_to_montgomery(BIGNUM * r,const BIGNUM * a,BN_MONT_CTX * mctx,BN_CTX * ctx)577 BN_to_montgomery(BIGNUM *r, const BIGNUM *a, BN_MONT_CTX *mctx, BN_CTX *ctx)
578 {
579 /* Compute r = a * R * R * R^-1 mod N = aR mod N */
580 return bn_mod_mul_montgomery(r, a, &mctx->RR, mctx, ctx);
581 }
582 LCRYPTO_ALIAS(BN_to_montgomery);
583
584 int
BN_from_montgomery(BIGNUM * r,const BIGNUM * a,BN_MONT_CTX * mctx,BN_CTX * ctx)585 BN_from_montgomery(BIGNUM *r, const BIGNUM *a, BN_MONT_CTX *mctx, BN_CTX *ctx)
586 {
587 BIGNUM *tmp;
588 int ret = 0;
589
590 BN_CTX_start(ctx);
591
592 if ((tmp = BN_CTX_get(ctx)) == NULL)
593 goto err;
594 if (!bn_copy(tmp, a))
595 goto err;
596 if (!bn_montgomery_reduce(r, tmp, mctx))
597 goto err;
598
599 ret = 1;
600 err:
601 BN_CTX_end(ctx);
602
603 return ret;
604 }
605 LCRYPTO_ALIAS(BN_from_montgomery);
606