175145e7b757901cd1211efd26d19ddc12fceb81
[openssl.git] / crypto / bn / bn_mont.c
1 /* crypto/bn/bn_mont.c */
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 "cryptlib.h"
120 #include "bn_lcl.h"
121
122 #define MONT_WORD               /* use the faster word-based algorithm */
123
124 #ifdef MONT_WORD
125 static int BN_from_montgomery_word(BIGNUM *ret, BIGNUM *r, BN_MONT_CTX *mont);
126 #endif
127
128 int BN_mod_mul_montgomery(BIGNUM *r, const BIGNUM *a, const BIGNUM *b,
129                           BN_MONT_CTX *mont, BN_CTX *ctx)
130 {
131     BIGNUM *tmp;
132     int ret = 0;
133 #if defined(OPENSSL_BN_ASM_MONT) && defined(MONT_WORD)
134     int num = mont->N.top;
135
136     if (num > 1 && a->top == num && b->top == num) {
137         if (bn_wexpand(r, num) == NULL)
138             return (0);
139         if (bn_mul_mont(r->d, a->d, b->d, mont->N.d, mont->n0, num)) {
140             r->neg = a->neg ^ b->neg;
141             r->top = num;
142             bn_correct_top(r);
143             return (1);
144         }
145     }
146 #endif
147
148     BN_CTX_start(ctx);
149     tmp = BN_CTX_get(ctx);
150     if (tmp == NULL)
151         goto err;
152
153     bn_check_top(tmp);
154     if (a == b) {
155         if (!BN_sqr(tmp, a, ctx))
156             goto err;
157     } else {
158         if (!BN_mul(tmp, a, b, ctx))
159             goto err;
160     }
161     /* reduce from aRR to aR */
162 #ifdef MONT_WORD
163     if (!BN_from_montgomery_word(r, tmp, mont))
164         goto err;
165 #else
166     if (!BN_from_montgomery(r, tmp, mont, ctx))
167         goto err;
168 #endif
169     bn_check_top(r);
170     ret = 1;
171  err:
172     BN_CTX_end(ctx);
173     return (ret);
174 }
175
176 #ifdef MONT_WORD
177 static int BN_from_montgomery_word(BIGNUM *ret, BIGNUM *r, BN_MONT_CTX *mont)
178 {
179     BIGNUM *n;
180     BN_ULONG *ap, *np, *rp, n0, v, carry;
181     int nl, max, i;
182
183     n = &(mont->N);
184     nl = n->top;
185     if (nl == 0) {
186         ret->top = 0;
187         return (1);
188     }
189
190     max = (2 * nl);             /* carry is stored separately */
191     if (bn_wexpand(r, max) == NULL)
192         return (0);
193
194     r->neg ^= n->neg;
195     np = n->d;
196     rp = r->d;
197
198     /* clear the top words of T */
199 # if 1
200     for (i = r->top; i < max; i++) /* memset? XXX */
201         rp[i] = 0;
202 # else
203     memset(&(rp[r->top]), 0, (max - r->top) * sizeof(BN_ULONG));
204 # endif
205
206     r->top = max;
207     n0 = mont->n0[0];
208
209     for (carry = 0, i = 0; i < nl; i++, rp++) {
210         v = bn_mul_add_words(rp, np, nl, (rp[0] * n0) & BN_MASK2);
211         v = (v + carry + rp[nl]) & BN_MASK2;
212         carry |= (v != rp[nl]);
213         carry &= (v <= rp[nl]);
214         rp[nl] = v;
215     }
216
217     if (bn_wexpand(ret, nl) == NULL)
218         return (0);
219     ret->top = nl;
220     ret->neg = r->neg;
221
222     rp = ret->d;
223     ap = &(r->d[nl]);
224
225 # define BRANCH_FREE 1
226 # if BRANCH_FREE
227     {
228         BN_ULONG *nrp;
229         size_t m;
230
231         v = bn_sub_words(rp, ap, np, nl) - carry;
232         /*
233          * if subtraction result is real, then trick unconditional memcpy
234          * below to perform in-place "refresh" instead of actual copy.
235          */
236         m = (0 - (size_t)v);
237         nrp =
238             (BN_ULONG *)(((PTR_SIZE_INT) rp & ~m) | ((PTR_SIZE_INT) ap & m));
239
240         for (i = 0, nl -= 4; i < nl; i += 4) {
241             BN_ULONG t1, t2, t3, t4;
242
243             t1 = nrp[i + 0];
244             t2 = nrp[i + 1];
245             t3 = nrp[i + 2];
246             ap[i + 0] = 0;
247             t4 = nrp[i + 3];
248             ap[i + 1] = 0;
249             rp[i + 0] = t1;
250             ap[i + 2] = 0;
251             rp[i + 1] = t2;
252             ap[i + 3] = 0;
253             rp[i + 2] = t3;
254             rp[i + 3] = t4;
255         }
256         for (nl += 4; i < nl; i++)
257             rp[i] = nrp[i], ap[i] = 0;
258     }
259 # else
260     if (bn_sub_words(rp, ap, np, nl) - carry)
261         memcpy(rp, ap, nl * sizeof(BN_ULONG));
262 # endif
263     bn_correct_top(r);
264     bn_correct_top(ret);
265     bn_check_top(ret);
266
267     return (1);
268 }
269 #endif                          /* MONT_WORD */
270
271 int BN_from_montgomery(BIGNUM *ret, const BIGNUM *a, BN_MONT_CTX *mont,
272                        BN_CTX *ctx)
273 {
274     int retn = 0;
275 #ifdef MONT_WORD
276     BIGNUM *t;
277
278     BN_CTX_start(ctx);
279     if ((t = BN_CTX_get(ctx)) && BN_copy(t, a))
280         retn = BN_from_montgomery_word(ret, t, mont);
281     BN_CTX_end(ctx);
282 #else                           /* !MONT_WORD */
283     BIGNUM *t1, *t2;
284
285     BN_CTX_start(ctx);
286     t1 = BN_CTX_get(ctx);
287     t2 = BN_CTX_get(ctx);
288     if (t1 == NULL || t2 == NULL)
289         goto err;
290
291     if (!BN_copy(t1, a))
292         goto err;
293     BN_mask_bits(t1, mont->ri);
294
295     if (!BN_mul(t2, t1, &mont->Ni, ctx))
296         goto err;
297     BN_mask_bits(t2, mont->ri);
298
299     if (!BN_mul(t1, t2, &mont->N, ctx))
300         goto err;
301     if (!BN_add(t2, a, t1))
302         goto err;
303     if (!BN_rshift(ret, t2, mont->ri))
304         goto err;
305
306     if (BN_ucmp(ret, &(mont->N)) >= 0) {
307         if (!BN_usub(ret, ret, &(mont->N)))
308             goto err;
309     }
310     retn = 1;
311     bn_check_top(ret);
312  err:
313     BN_CTX_end(ctx);
314 #endif                          /* MONT_WORD */
315     return (retn);
316 }
317
318 BN_MONT_CTX *BN_MONT_CTX_new(void)
319 {
320     BN_MONT_CTX *ret;
321
322     if ((ret = (BN_MONT_CTX *)OPENSSL_malloc(sizeof(BN_MONT_CTX))) == NULL)
323         return (NULL);
324
325     BN_MONT_CTX_init(ret);
326     ret->flags = BN_FLG_MALLOCED;
327     return (ret);
328 }
329
330 void BN_MONT_CTX_init(BN_MONT_CTX *ctx)
331 {
332     ctx->ri = 0;
333     BN_init(&(ctx->RR));
334     BN_init(&(ctx->N));
335     BN_init(&(ctx->Ni));
336     ctx->n0[0] = ctx->n0[1] = 0;
337     ctx->flags = 0;
338 }
339
340 void BN_MONT_CTX_free(BN_MONT_CTX *mont)
341 {
342     if (mont == NULL)
343         return;
344
345     BN_free(&(mont->RR));
346     BN_free(&(mont->N));
347     BN_free(&(mont->Ni));
348     if (mont->flags & BN_FLG_MALLOCED)
349         OPENSSL_free(mont);
350 }
351
352 int BN_MONT_CTX_set(BN_MONT_CTX *mont, const BIGNUM *mod, BN_CTX *ctx)
353 {
354     int ret = 0;
355     BIGNUM *Ri, *R;
356
357     BN_CTX_start(ctx);
358     if ((Ri = BN_CTX_get(ctx)) == NULL)
359         goto err;
360     R = &(mont->RR);            /* grab RR as a temp */
361     if (!BN_copy(&(mont->N), mod))
362         goto err;               /* Set N */
363     mont->N.neg = 0;
364
365 #ifdef MONT_WORD
366     {
367         BIGNUM tmod;
368         BN_ULONG buf[2];
369
370         BN_init(&tmod);
371         tmod.d = buf;
372         tmod.dmax = 2;
373         tmod.neg = 0;
374
375         mont->ri = (BN_num_bits(mod) + (BN_BITS2 - 1)) / BN_BITS2 * BN_BITS2;
376
377 # if defined(OPENSSL_BN_ASM_MONT) && (BN_BITS2<=32)
378         /*
379          * Only certain BN_BITS2<=32 platforms actually make use of n0[1],
380          * and we could use the #else case (with a shorter R value) for the
381          * others.  However, currently only the assembler files do know which
382          * is which.
383          */
384
385         BN_zero(R);
386         if (!(BN_set_bit(R, 2 * BN_BITS2)))
387             goto err;
388
389         tmod.top = 0;
390         if ((buf[0] = mod->d[0]))
391             tmod.top = 1;
392         if ((buf[1] = mod->top > 1 ? mod->d[1] : 0))
393             tmod.top = 2;
394
395         if ((BN_mod_inverse(Ri, R, &tmod, ctx)) == NULL)
396             goto err;
397         if (!BN_lshift(Ri, Ri, 2 * BN_BITS2))
398             goto err;           /* R*Ri */
399         if (!BN_is_zero(Ri)) {
400             if (!BN_sub_word(Ri, 1))
401                 goto err;
402         } else {                /* if N mod word size == 1 */
403
404             if (bn_expand(Ri, (int)sizeof(BN_ULONG) * 2) == NULL)
405                 goto err;
406             /* Ri-- (mod double word size) */
407             Ri->neg = 0;
408             Ri->d[0] = BN_MASK2;
409             Ri->d[1] = BN_MASK2;
410             Ri->top = 2;
411         }
412         if (!BN_div(Ri, NULL, Ri, &tmod, ctx))
413             goto err;
414         /*
415          * Ni = (R*Ri-1)/N, keep only couple of least significant words:
416          */
417         mont->n0[0] = (Ri->top > 0) ? Ri->d[0] : 0;
418         mont->n0[1] = (Ri->top > 1) ? Ri->d[1] : 0;
419 # else
420         BN_zero(R);
421         if (!(BN_set_bit(R, BN_BITS2)))
422             goto err;           /* R */
423
424         buf[0] = mod->d[0];     /* tmod = N mod word size */
425         buf[1] = 0;
426         tmod.top = buf[0] != 0 ? 1 : 0;
427         /* Ri = R^-1 mod N */
428         if ((BN_mod_inverse(Ri, R, &tmod, ctx)) == NULL)
429             goto err;
430         if (!BN_lshift(Ri, Ri, BN_BITS2))
431             goto err;           /* R*Ri */
432         if (!BN_is_zero(Ri)) {
433             if (!BN_sub_word(Ri, 1))
434                 goto err;
435         } else {                /* if N mod word size == 1 */
436
437             if (!BN_set_word(Ri, BN_MASK2))
438                 goto err;       /* Ri-- (mod word size) */
439         }
440         if (!BN_div(Ri, NULL, Ri, &tmod, ctx))
441             goto err;
442         /*
443          * Ni = (R*Ri-1)/N, keep only least significant word:
444          */
445         mont->n0[0] = (Ri->top > 0) ? Ri->d[0] : 0;
446         mont->n0[1] = 0;
447 # endif
448     }
449 #else                           /* !MONT_WORD */
450     {                           /* bignum version */
451         mont->ri = BN_num_bits(&mont->N);
452         BN_zero(R);
453         if (!BN_set_bit(R, mont->ri))
454             goto err;           /* R = 2^ri */
455         /* Ri = R^-1 mod N */
456         if ((BN_mod_inverse(Ri, R, &mont->N, ctx)) == NULL)
457             goto err;
458         if (!BN_lshift(Ri, Ri, mont->ri))
459             goto err;           /* R*Ri */
460         if (!BN_sub_word(Ri, 1))
461             goto err;
462         /*
463          * Ni = (R*Ri-1) / N
464          */
465         if (!BN_div(&(mont->Ni), NULL, Ri, &mont->N, ctx))
466             goto err;
467     }
468 #endif
469
470     /* setup RR for conversions */
471     BN_zero(&(mont->RR));
472     if (!BN_set_bit(&(mont->RR), mont->ri * 2))
473         goto err;
474     if (!BN_mod(&(mont->RR), &(mont->RR), &(mont->N), ctx))
475         goto err;
476
477     ret = 1;
478  err:
479     BN_CTX_end(ctx);
480     return ret;
481 }
482
483 BN_MONT_CTX *BN_MONT_CTX_copy(BN_MONT_CTX *to, BN_MONT_CTX *from)
484 {
485     if (to == from)
486         return (to);
487
488     if (!BN_copy(&(to->RR), &(from->RR)))
489         return NULL;
490     if (!BN_copy(&(to->N), &(from->N)))
491         return NULL;
492     if (!BN_copy(&(to->Ni), &(from->Ni)))
493         return NULL;
494     to->ri = from->ri;
495     to->n0[0] = from->n0[0];
496     to->n0[1] = from->n0[1];
497     return (to);
498 }
499
500 BN_MONT_CTX *BN_MONT_CTX_set_locked(BN_MONT_CTX **pmont, int lock,
501                                     const BIGNUM *mod, BN_CTX *ctx)
502 {
503     BN_MONT_CTX *ret;
504
505     CRYPTO_r_lock(lock);
506     ret = *pmont;
507     CRYPTO_r_unlock(lock);
508     if (ret)
509         return ret;
510
511     /*
512      * We don't want to serialise globally while doing our lazy-init math in
513      * BN_MONT_CTX_set. That punishes threads that are doing independent
514      * things. Instead, punish the case where more than one thread tries to
515      * lazy-init the same 'pmont', by having each do the lazy-init math work
516      * independently and only use the one from the thread that wins the race
517      * (the losers throw away the work they've done).
518      */
519     ret = BN_MONT_CTX_new();
520     if (!ret)
521         return NULL;
522     if (!BN_MONT_CTX_set(ret, mod, ctx)) {
523         BN_MONT_CTX_free(ret);
524         return NULL;
525     }
526
527     /* The locked compare-and-set, after the local work is done. */
528     CRYPTO_w_lock(lock);
529     if (*pmont) {
530         BN_MONT_CTX_free(ret);
531         ret = *pmont;
532     } else
533         *pmont = ret;
534     CRYPTO_w_unlock(lock);
535     return ret;
536 }