Don't free the BIGNUM passed to BN_mpi2bn
[openssl.git] / crypto / bn / bn_mont.c
1 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
2  * All rights reserved.
3  *
4  * This package is an SSL implementation written
5  * by Eric Young (eay@cryptsoft.com).
6  * The implementation was written so as to conform with Netscapes SSL.
7  *
8  * This library is free for commercial and non-commercial use as long as
9  * the following conditions are aheared to.  The following conditions
10  * apply to all code found in this distribution, be it the RC4, RSA,
11  * lhash, DES, etc., code; not just the SSL code.  The SSL documentation
12  * included with this distribution is covered by the same copyright terms
13  * except that the holder is Tim Hudson (tjh@cryptsoft.com).
14  *
15  * Copyright remains Eric Young's, and as such any Copyright notices in
16  * the code are not to be removed.
17  * If this package is used in a product, Eric Young should be given attribution
18  * as the author of the parts of the library used.
19  * This can be in the form of a textual message at program startup or
20  * in documentation (online or textual) provided with the package.
21  *
22  * Redistribution and use in source and binary forms, with or without
23  * modification, are permitted provided that the following conditions
24  * are met:
25  * 1. Redistributions of source code must retain the copyright
26  *    notice, this list of conditions and the following disclaimer.
27  * 2. Redistributions in binary form must reproduce the above copyright
28  *    notice, this list of conditions and the following disclaimer in the
29  *    documentation and/or other materials provided with the distribution.
30  * 3. All advertising materials mentioning features or use of this software
31  *    must display the following acknowledgement:
32  *    "This product includes cryptographic software written by
33  *     Eric Young (eay@cryptsoft.com)"
34  *    The word 'cryptographic' can be left out if the rouines from the library
35  *    being used are not cryptographic related :-).
36  * 4. If you include any Windows specific code (or a derivative thereof) from
37  *    the apps directory (application code) you must include an acknowledgement:
38  *    "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
39  *
40  * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
41  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
42  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
43  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
44  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
45  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
46  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
47  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
48  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
49  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
50  * SUCH DAMAGE.
51  *
52  * The licence and distribution terms for any publically available version or
53  * derivative of this code cannot be changed.  i.e. this code cannot simply be
54  * copied and put under another distribution licence
55  * [including the GNU Public Licence.]
56  */
57 /* ====================================================================
58  * Copyright (c) 1998-2006 The OpenSSL Project.  All rights reserved.
59  *
60  * Redistribution and use in source and binary forms, with or without
61  * modification, are permitted provided that the following conditions
62  * are met:
63  *
64  * 1. Redistributions of source code must retain the above copyright
65  *    notice, this list of conditions and the following disclaimer.
66  *
67  * 2. Redistributions in binary form must reproduce the above copyright
68  *    notice, this list of conditions and the following disclaimer in
69  *    the documentation and/or other materials provided with the
70  *    distribution.
71  *
72  * 3. All advertising materials mentioning features or use of this
73  *    software must display the following acknowledgment:
74  *    "This product includes software developed by the OpenSSL Project
75  *    for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
76  *
77  * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
78  *    endorse or promote products derived from this software without
79  *    prior written permission. For written permission, please contact
80  *    openssl-core@openssl.org.
81  *
82  * 5. Products derived from this software may not be called "OpenSSL"
83  *    nor may "OpenSSL" appear in their names without prior written
84  *    permission of the OpenSSL Project.
85  *
86  * 6. Redistributions of any form whatsoever must retain the following
87  *    acknowledgment:
88  *    "This product includes software developed by the OpenSSL Project
89  *    for use in the OpenSSL Toolkit (http://www.openssl.org/)"
90  *
91  * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
92  * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
93  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
94  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE OpenSSL PROJECT OR
95  * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
96  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
97  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
98  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
99  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
100  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
101  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
102  * OF THE POSSIBILITY OF SUCH DAMAGE.
103  * ====================================================================
104  *
105  * This product includes cryptographic software written by Eric Young
106  * (eay@cryptsoft.com).  This product includes software written by Tim
107  * Hudson (tjh@cryptsoft.com).
108  *
109  */
110
111 /*
112  * Details about Montgomery multiplication algorithms can be found at
113  * http://security.ece.orst.edu/publications.html, e.g.
114  * http://security.ece.orst.edu/koc/papers/j37acmon.pdf and
115  * sections 3.8 and 4.2 in http://security.ece.orst.edu/koc/papers/r01rsasw.pdf
116  */
117
118 #include "internal/cryptlib.h"
119 #include "bn_lcl.h"
120
121 #define MONT_WORD               /* use the faster word-based algorithm */
122
123 #ifdef MONT_WORD
124 static int BN_from_montgomery_word(BIGNUM *ret, BIGNUM *r, BN_MONT_CTX *mont);
125 #endif
126
127 int BN_mod_mul_montgomery(BIGNUM *r, const BIGNUM *a, const BIGNUM *b,
128                           BN_MONT_CTX *mont, BN_CTX *ctx)
129 {
130     BIGNUM *tmp;
131     int ret = 0;
132 #if defined(OPENSSL_BN_ASM_MONT) && defined(MONT_WORD)
133     int num = mont->N.top;
134
135     if (num > 1 && a->top == num && b->top == num) {
136         if (bn_wexpand(r, num) == NULL)
137             return (0);
138         if (bn_mul_mont(r->d, a->d, b->d, mont->N.d, mont->n0, num)) {
139             r->neg = a->neg ^ b->neg;
140             r->top = num;
141             bn_correct_top(r);
142             return (1);
143         }
144     }
145 #endif
146
147     BN_CTX_start(ctx);
148     tmp = BN_CTX_get(ctx);
149     if (tmp == NULL)
150         goto err;
151
152     bn_check_top(tmp);
153     if (a == b) {
154         if (!BN_sqr(tmp, a, ctx))
155             goto err;
156     } else {
157         if (!BN_mul(tmp, a, b, ctx))
158             goto err;
159     }
160     /* reduce from aRR to aR */
161 #ifdef MONT_WORD
162     if (!BN_from_montgomery_word(r, tmp, mont))
163         goto err;
164 #else
165     if (!BN_from_montgomery(r, tmp, mont, ctx))
166         goto err;
167 #endif
168     bn_check_top(r);
169     ret = 1;
170  err:
171     BN_CTX_end(ctx);
172     return (ret);
173 }
174
175 #ifdef MONT_WORD
176 static int BN_from_montgomery_word(BIGNUM *ret, BIGNUM *r, BN_MONT_CTX *mont)
177 {
178     BIGNUM *n;
179     BN_ULONG *ap, *np, *rp, n0, v, carry;
180     int nl, max, i;
181
182     n = &(mont->N);
183     nl = n->top;
184     if (nl == 0) {
185         ret->top = 0;
186         return (1);
187     }
188
189     max = (2 * nl);             /* carry is stored separately */
190     if (bn_wexpand(r, max) == NULL)
191         return (0);
192
193     r->neg ^= n->neg;
194     np = n->d;
195     rp = r->d;
196
197     /* clear the top words of T */
198     i = max - r->top;
199     if (i)
200         memset(&rp[r->top], 0, sizeof(*rp) * i);
201
202     r->top = max;
203     n0 = mont->n0[0];
204
205     for (carry = 0, i = 0; i < nl; i++, rp++) {
206         v = bn_mul_add_words(rp, np, nl, (rp[0] * n0) & BN_MASK2);
207         v = (v + carry + rp[nl]) & BN_MASK2;
208         carry |= (v != rp[nl]);
209         carry &= (v <= rp[nl]);
210         rp[nl] = v;
211     }
212
213     if (bn_wexpand(ret, nl) == NULL)
214         return (0);
215     ret->top = nl;
216     ret->neg = r->neg;
217
218     rp = ret->d;
219     ap = &(r->d[nl]);
220
221 # define BRANCH_FREE 1
222 # if BRANCH_FREE
223     {
224         BN_ULONG *nrp;
225         size_t m;
226
227         v = bn_sub_words(rp, ap, np, nl) - carry;
228         /*
229          * if subtraction result is real, then trick unconditional memcpy
230          * below to perform in-place "refresh" instead of actual copy.
231          */
232         m = (0 - (size_t)v);
233         nrp =
234             (BN_ULONG *)(((PTR_SIZE_INT) rp & ~m) | ((PTR_SIZE_INT) ap & m));
235
236         for (i = 0, nl -= 4; i < nl; i += 4) {
237             BN_ULONG t1, t2, t3, t4;
238
239             t1 = nrp[i + 0];
240             t2 = nrp[i + 1];
241             t3 = nrp[i + 2];
242             ap[i + 0] = 0;
243             t4 = nrp[i + 3];
244             ap[i + 1] = 0;
245             rp[i + 0] = t1;
246             ap[i + 2] = 0;
247             rp[i + 1] = t2;
248             ap[i + 3] = 0;
249             rp[i + 2] = t3;
250             rp[i + 3] = t4;
251         }
252         for (nl += 4; i < nl; i++)
253             rp[i] = nrp[i], ap[i] = 0;
254     }
255 # else
256     if (bn_sub_words(rp, ap, np, nl) - carry)
257         memcpy(rp, ap, nl * sizeof(BN_ULONG));
258 # endif
259     bn_correct_top(r);
260     bn_correct_top(ret);
261     bn_check_top(ret);
262
263     return (1);
264 }
265 #endif                          /* MONT_WORD */
266
267 int BN_from_montgomery(BIGNUM *ret, const BIGNUM *a, BN_MONT_CTX *mont,
268                        BN_CTX *ctx)
269 {
270     int retn = 0;
271 #ifdef MONT_WORD
272     BIGNUM *t;
273
274     BN_CTX_start(ctx);
275     if ((t = BN_CTX_get(ctx)) && BN_copy(t, a))
276         retn = BN_from_montgomery_word(ret, t, mont);
277     BN_CTX_end(ctx);
278 #else                           /* !MONT_WORD */
279     BIGNUM *t1, *t2;
280
281     BN_CTX_start(ctx);
282     t1 = BN_CTX_get(ctx);
283     t2 = BN_CTX_get(ctx);
284     if (t1 == NULL || t2 == NULL)
285         goto err;
286
287     if (!BN_copy(t1, a))
288         goto err;
289     BN_mask_bits(t1, mont->ri);
290
291     if (!BN_mul(t2, t1, &mont->Ni, ctx))
292         goto err;
293     BN_mask_bits(t2, mont->ri);
294
295     if (!BN_mul(t1, t2, &mont->N, ctx))
296         goto err;
297     if (!BN_add(t2, a, t1))
298         goto err;
299     if (!BN_rshift(ret, t2, mont->ri))
300         goto err;
301
302     if (BN_ucmp(ret, &(mont->N)) >= 0) {
303         if (!BN_usub(ret, ret, &(mont->N)))
304             goto err;
305     }
306     retn = 1;
307     bn_check_top(ret);
308  err:
309     BN_CTX_end(ctx);
310 #endif                          /* MONT_WORD */
311     return (retn);
312 }
313
314 BN_MONT_CTX *BN_MONT_CTX_new(void)
315 {
316     BN_MONT_CTX *ret;
317
318     if ((ret = OPENSSL_malloc(sizeof(*ret))) == NULL)
319         return (NULL);
320
321     BN_MONT_CTX_init(ret);
322     ret->flags = BN_FLG_MALLOCED;
323     return (ret);
324 }
325
326 void BN_MONT_CTX_init(BN_MONT_CTX *ctx)
327 {
328     ctx->ri = 0;
329     bn_init(&(ctx->RR));
330     bn_init(&(ctx->N));
331     bn_init(&(ctx->Ni));
332     ctx->n0[0] = ctx->n0[1] = 0;
333     ctx->flags = 0;
334 }
335
336 void BN_MONT_CTX_free(BN_MONT_CTX *mont)
337 {
338     if (mont == NULL)
339         return;
340
341     BN_clear_free(&(mont->RR));
342     BN_clear_free(&(mont->N));
343     BN_clear_free(&(mont->Ni));
344     if (mont->flags & BN_FLG_MALLOCED)
345         OPENSSL_free(mont);
346 }
347
348 int BN_MONT_CTX_set(BN_MONT_CTX *mont, const BIGNUM *mod, BN_CTX *ctx)
349 {
350     int ret = 0;
351     BIGNUM *Ri, *R;
352
353     if (BN_is_zero(mod))
354         return 0;
355
356     BN_CTX_start(ctx);
357     if ((Ri = BN_CTX_get(ctx)) == NULL)
358         goto err;
359     R = &(mont->RR);            /* grab RR as a temp */
360     if (!BN_copy(&(mont->N), mod))
361         goto err;               /* Set N */
362     mont->N.neg = 0;
363
364 #ifdef MONT_WORD
365     {
366         BIGNUM tmod;
367         BN_ULONG buf[2];
368
369         bn_init(&tmod);
370         tmod.d = buf;
371         tmod.dmax = 2;
372         tmod.neg = 0;
373
374         mont->ri = (BN_num_bits(mod) + (BN_BITS2 - 1)) / BN_BITS2 * BN_BITS2;
375
376 # if defined(OPENSSL_BN_ASM_MONT) && (BN_BITS2<=32)
377         /*
378          * Only certain BN_BITS2<=32 platforms actually make use of n0[1],
379          * and we could use the #else case (with a shorter R value) for the
380          * others.  However, currently only the assembler files do know which
381          * is which.
382          */
383
384         BN_zero(R);
385         if (!(BN_set_bit(R, 2 * BN_BITS2)))
386             goto err;
387
388         tmod.top = 0;
389         if ((buf[0] = mod->d[0]))
390             tmod.top = 1;
391         if ((buf[1] = mod->top > 1 ? mod->d[1] : 0))
392             tmod.top = 2;
393
394         if ((BN_mod_inverse(Ri, R, &tmod, ctx)) == NULL)
395             goto err;
396         if (!BN_lshift(Ri, Ri, 2 * BN_BITS2))
397             goto err;           /* R*Ri */
398         if (!BN_is_zero(Ri)) {
399             if (!BN_sub_word(Ri, 1))
400                 goto err;
401         } else {                /* if N mod word size == 1 */
402
403             if (bn_expand(Ri, (int)sizeof(BN_ULONG) * 2) == NULL)
404                 goto err;
405             /* Ri-- (mod double word size) */
406             Ri->neg = 0;
407             Ri->d[0] = BN_MASK2;
408             Ri->d[1] = BN_MASK2;
409             Ri->top = 2;
410         }
411         if (!BN_div(Ri, NULL, Ri, &tmod, ctx))
412             goto err;
413         /*
414          * Ni = (R*Ri-1)/N, keep only couple of least significant words:
415          */
416         mont->n0[0] = (Ri->top > 0) ? Ri->d[0] : 0;
417         mont->n0[1] = (Ri->top > 1) ? Ri->d[1] : 0;
418 # else
419         BN_zero(R);
420         if (!(BN_set_bit(R, BN_BITS2)))
421             goto err;           /* R */
422
423         buf[0] = mod->d[0];     /* tmod = N mod word size */
424         buf[1] = 0;
425         tmod.top = buf[0] != 0 ? 1 : 0;
426         /* Ri = R^-1 mod N */
427         if ((BN_mod_inverse(Ri, R, &tmod, ctx)) == NULL)
428             goto err;
429         if (!BN_lshift(Ri, Ri, BN_BITS2))
430             goto err;           /* R*Ri */
431         if (!BN_is_zero(Ri)) {
432             if (!BN_sub_word(Ri, 1))
433                 goto err;
434         } else {                /* if N mod word size == 1 */
435
436             if (!BN_set_word(Ri, BN_MASK2))
437                 goto err;       /* Ri-- (mod word size) */
438         }
439         if (!BN_div(Ri, NULL, Ri, &tmod, ctx))
440             goto err;
441         /*
442          * Ni = (R*Ri-1)/N, keep only least significant word:
443          */
444         mont->n0[0] = (Ri->top > 0) ? Ri->d[0] : 0;
445         mont->n0[1] = 0;
446 # endif
447     }
448 #else                           /* !MONT_WORD */
449     {                           /* bignum version */
450         mont->ri = BN_num_bits(&mont->N);
451         BN_zero(R);
452         if (!BN_set_bit(R, mont->ri))
453             goto err;           /* R = 2^ri */
454         /* Ri = R^-1 mod N */
455         if ((BN_mod_inverse(Ri, R, &mont->N, ctx)) == NULL)
456             goto err;
457         if (!BN_lshift(Ri, Ri, mont->ri))
458             goto err;           /* R*Ri */
459         if (!BN_sub_word(Ri, 1))
460             goto err;
461         /*
462          * Ni = (R*Ri-1) / N
463          */
464         if (!BN_div(&(mont->Ni), NULL, Ri, &mont->N, ctx))
465             goto err;
466     }
467 #endif
468
469     /* setup RR for conversions */
470     BN_zero(&(mont->RR));
471     if (!BN_set_bit(&(mont->RR), mont->ri * 2))
472         goto err;
473     if (!BN_mod(&(mont->RR), &(mont->RR), &(mont->N), ctx))
474         goto err;
475
476     ret = 1;
477  err:
478     BN_CTX_end(ctx);
479     return ret;
480 }
481
482 BN_MONT_CTX *BN_MONT_CTX_copy(BN_MONT_CTX *to, BN_MONT_CTX *from)
483 {
484     if (to == from)
485         return (to);
486
487     if (!BN_copy(&(to->RR), &(from->RR)))
488         return NULL;
489     if (!BN_copy(&(to->N), &(from->N)))
490         return NULL;
491     if (!BN_copy(&(to->Ni), &(from->Ni)))
492         return NULL;
493     to->ri = from->ri;
494     to->n0[0] = from->n0[0];
495     to->n0[1] = from->n0[1];
496     return (to);
497 }
498
499 BN_MONT_CTX *BN_MONT_CTX_set_locked(BN_MONT_CTX **pmont, CRYPTO_RWLOCK *lock,
500                                     const BIGNUM *mod, BN_CTX *ctx)
501 {
502     BN_MONT_CTX *ret;
503
504     CRYPTO_THREAD_read_lock(lock);
505     ret = *pmont;
506     CRYPTO_THREAD_unlock(lock);
507     if (ret)
508         return ret;
509
510     /*
511      * We don't want to serialise globally while doing our lazy-init math in
512      * BN_MONT_CTX_set. That punishes threads that are doing independent
513      * things. Instead, punish the case where more than one thread tries to
514      * lazy-init the same 'pmont', by having each do the lazy-init math work
515      * independently and only use the one from the thread that wins the race
516      * (the losers throw away the work they've done).
517      */
518     ret = BN_MONT_CTX_new();
519     if (ret == NULL)
520         return NULL;
521     if (!BN_MONT_CTX_set(ret, mod, ctx)) {
522         BN_MONT_CTX_free(ret);
523         return NULL;
524     }
525
526     /* The locked compare-and-set, after the local work is done. */
527     CRYPTO_THREAD_write_lock(lock);
528     if (*pmont) {
529         BN_MONT_CTX_free(ret);
530         ret = *pmont;
531     } else
532         *pmont = ret;
533     CRYPTO_THREAD_unlock(lock);
534     return ret;
535 }