Import OpenSSL 0.9.8h.
[dragonfly.git] / crypto / openssl-0.9 / 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 <stdio.h>
120 #include "cryptlib.h"
121 #include "bn_lcl.h"
122
123 #define MONT_WORD /* use the faster word-based algorithm */
124
125 #if defined(MONT_WORD) && defined(OPENSSL_BN_ASM_MONT) && (BN_BITS2<=32)
126 /* This condition means we have a specific non-default build:
127  * In the 0.9.8 branch, OPENSSL_BN_ASM_MONT is normally not set for any
128  * BN_BITS2<=32 platform; an explicit "enable-montasm" is required.
129  * I.e., if we are here, the user intentionally deviates from the
130  * normal stable build to get better Montgomery performance from
131  * the 0.9.9-dev backport.
132  *
133  * In this case only, we also enable BN_from_montgomery_word()
134  * (another non-stable feature from 0.9.9-dev).
135  */
136 #define MONT_FROM_WORD___NON_DEFAULT_0_9_8_BUILD
137 #endif
138
139 #ifdef MONT_FROM_WORD___NON_DEFAULT_0_9_8_BUILD
140 static int BN_from_montgomery_word(BIGNUM *ret, BIGNUM *r, BN_MONT_CTX *mont);
141 #endif
142
143
144
145 int BN_mod_mul_montgomery(BIGNUM *r, const BIGNUM *a, const BIGNUM *b,
146                           BN_MONT_CTX *mont, BN_CTX *ctx)
147         {
148         BIGNUM *tmp;
149         int ret=0;
150 #if defined(OPENSSL_BN_ASM_MONT) && defined(MONT_WORD)
151         int num = mont->N.top;
152
153         if (num>1 && a->top==num && b->top==num)
154                 {
155                 if (bn_wexpand(r,num) == NULL) return(0);
156 #if 0 /* for OpenSSL 0.9.9 mont->n0 */
157                 if (bn_mul_mont(r->d,a->d,b->d,mont->N.d,mont->n0,num))
158 #else
159                 if (bn_mul_mont(r->d,a->d,b->d,mont->N.d,&mont->n0,num))
160 #endif
161                         {
162                         r->neg = a->neg^b->neg;
163                         r->top = num;
164                         bn_correct_top(r);
165                         return(1);
166                         }
167                 }
168 #endif
169
170         BN_CTX_start(ctx);
171         tmp = BN_CTX_get(ctx);
172         if (tmp == NULL) goto err;
173
174         bn_check_top(tmp);
175         if (a == b)
176                 {
177                 if (!BN_sqr(tmp,a,ctx)) goto err;
178                 }
179         else
180                 {
181                 if (!BN_mul(tmp,a,b,ctx)) goto err;
182                 }
183         /* reduce from aRR to aR */
184 #ifdef MONT_FROM_WORD___NON_DEFAULT_0_9_8_BUILD
185         if (!BN_from_montgomery_word(r,tmp,mont)) goto err;
186 #else
187         if (!BN_from_montgomery(r,tmp,mont,ctx)) goto err;
188 #endif
189         bn_check_top(r);
190         ret=1;
191 err:
192         BN_CTX_end(ctx);
193         return(ret);
194         }
195
196 #ifdef MONT_FROM_WORD___NON_DEFAULT_0_9_8_BUILD
197 static int BN_from_montgomery_word(BIGNUM *ret, BIGNUM *r, BN_MONT_CTX *mont)
198         {
199         BIGNUM *n;
200         BN_ULONG *ap,*np,*rp,n0,v,*nrp;
201         int al,nl,max,i,x,ri;
202
203         n= &(mont->N);
204         /* mont->ri is the size of mont->N in bits (rounded up
205            to the word size) */
206         al=ri=mont->ri/BN_BITS2;
207
208         nl=n->top;
209         if ((al == 0) || (nl == 0)) { ret->top=0; return(1); }
210
211         max=(nl+al+1); /* allow for overflow (no?) XXX */
212         if (bn_wexpand(r,max) == NULL) return(0);
213
214         r->neg^=n->neg;
215         np=n->d;
216         rp=r->d;
217         nrp= &(r->d[nl]);
218
219         /* clear the top words of T */
220         for (i=r->top; i<max; i++) /* memset? XXX */
221                 r->d[i]=0;
222
223         r->top=max;
224 #if 0 /* for OpenSSL 0.9.9 mont->n0 */
225         n0=mont->n0[0];
226 #else
227         n0=mont->n0;
228 #endif
229
230 #ifdef BN_COUNT
231         fprintf(stderr,"word BN_from_montgomery_word %d * %d\n",nl,nl);
232 #endif
233         for (i=0; i<nl; i++)
234                 {
235 #ifdef __TANDEM
236                 {
237                    long long t1;
238                    long long t2;
239                    long long t3;
240                    t1 = rp[0] * (n0 & 0177777);
241                    t2 = 037777600000l;
242                    t2 = n0 & t2;
243                    t3 = rp[0] & 0177777;
244                    t2 = (t3 * t2) & BN_MASK2;
245                    t1 = t1 + t2;
246                    v=bn_mul_add_words(rp,np,nl,(BN_ULONG) t1);
247                 }
248 #else
249                 v=bn_mul_add_words(rp,np,nl,(rp[0]*n0)&BN_MASK2);
250 #endif
251                 nrp++;
252                 rp++;
253                 if (((nrp[-1]+=v)&BN_MASK2) >= v)
254                         continue;
255                 else
256                         {
257                         if (((++nrp[0])&BN_MASK2) != 0) continue;
258                         if (((++nrp[1])&BN_MASK2) != 0) continue;
259                         for (x=2; (((++nrp[x])&BN_MASK2) == 0); x++) ;
260                         }
261                 }
262         bn_correct_top(r);
263
264         /* mont->ri will be a multiple of the word size and below code
265          * is kind of BN_rshift(ret,r,mont->ri) equivalent */
266         if (r->top <= ri)
267                 {
268                 ret->top=0;
269                 return(1);
270                 }
271         al=r->top-ri;
272
273         if (bn_wexpand(ret,ri) == NULL) return(0);
274         x=0-(((al-ri)>>(sizeof(al)*8-1))&1);
275         ret->top=x=(ri&~x)|(al&x);      /* min(ri,al) */
276         ret->neg=r->neg;
277
278         rp=ret->d;
279         ap=&(r->d[ri]);
280
281         {
282         size_t m1,m2;
283
284         v=bn_sub_words(rp,ap,np,ri);
285         /* this ----------------^^ works even in al<ri case
286          * thanks to zealous zeroing of top of the vector in the
287          * beginning. */
288
289         /* if (al==ri && !v) || al>ri) nrp=rp; else nrp=ap; */
290         /* in other words if subtraction result is real, then
291          * trick unconditional memcpy below to perform in-place
292          * "refresh" instead of actual copy. */
293         m1=0-(size_t)(((al-ri)>>(sizeof(al)*8-1))&1);   /* al<ri */
294         m2=0-(size_t)(((ri-al)>>(sizeof(al)*8-1))&1);   /* al>ri */
295         m1|=m2;                 /* (al!=ri) */
296         m1|=(0-(size_t)v);      /* (al!=ri || v) */
297         m1&=~m2;                /* (al!=ri || v) && !al>ri */
298         nrp=(BN_ULONG *)(((size_t)rp&~m1)|((size_t)ap&m1));
299         }
300
301         /* 'i<ri' is chosen to eliminate dependency on input data, even
302          * though it results in redundant copy in al<ri case. */
303         for (i=0,ri-=4; i<ri; i+=4)
304                 {
305                 BN_ULONG t1,t2,t3,t4;
306                 
307                 t1=nrp[i+0];
308                 t2=nrp[i+1];
309                 t3=nrp[i+2];    ap[i+0]=0;
310                 t4=nrp[i+3];    ap[i+1]=0;
311                 rp[i+0]=t1;     ap[i+2]=0;
312                 rp[i+1]=t2;     ap[i+3]=0;
313                 rp[i+2]=t3;
314                 rp[i+3]=t4;
315                 }
316         for (ri+=4; i<ri; i++)
317                 rp[i]=nrp[i], ap[i]=0;
318         bn_correct_top(r);
319         bn_correct_top(ret);
320         bn_check_top(ret);
321
322         return(1);
323         }
324
325 int BN_from_montgomery(BIGNUM *ret, const BIGNUM *a, BN_MONT_CTX *mont,
326              BN_CTX *ctx)
327         {
328         int retn=0;
329         BIGNUM *t;
330
331         BN_CTX_start(ctx);
332         if ((t = BN_CTX_get(ctx)) && BN_copy(t,a))
333                 retn = BN_from_montgomery_word(ret,t,mont);
334         BN_CTX_end(ctx);
335         return retn;
336         }
337
338 #else /* !MONT_FROM_WORD___NON_DEFAULT_0_9_8_BUILD */
339
340 int BN_from_montgomery(BIGNUM *ret, const BIGNUM *a, BN_MONT_CTX *mont,
341              BN_CTX *ctx)
342         {
343         int retn=0;
344
345 #ifdef MONT_WORD
346         BIGNUM *n,*r;
347         BN_ULONG *ap,*np,*rp,n0,v,*nrp;
348         int al,nl,max,i,x,ri;
349
350         BN_CTX_start(ctx);
351         if ((r = BN_CTX_get(ctx)) == NULL) goto err;
352
353         if (!BN_copy(r,a)) goto err;
354         n= &(mont->N);
355
356         ap=a->d;
357         /* mont->ri is the size of mont->N in bits (rounded up
358            to the word size) */
359         al=ri=mont->ri/BN_BITS2;
360         
361         nl=n->top;
362         if ((al == 0) || (nl == 0)) { r->top=0; return(1); }
363
364         max=(nl+al+1); /* allow for overflow (no?) XXX */
365         if (bn_wexpand(r,max) == NULL) goto err;
366
367         r->neg=a->neg^n->neg;
368         np=n->d;
369         rp=r->d;
370         nrp= &(r->d[nl]);
371
372         /* clear the top words of T */
373 #if 1
374         for (i=r->top; i<max; i++) /* memset? XXX */
375                 r->d[i]=0;
376 #else
377         memset(&(r->d[r->top]),0,(max-r->top)*sizeof(BN_ULONG)); 
378 #endif
379
380         r->top=max;
381         n0=mont->n0;
382
383 #ifdef BN_COUNT
384         fprintf(stderr,"word BN_from_montgomery %d * %d\n",nl,nl);
385 #endif
386         for (i=0; i<nl; i++)
387                 {
388 #ifdef __TANDEM
389                 {
390                    long long t1;
391                    long long t2;
392                    long long t3;
393                    t1 = rp[0] * (n0 & 0177777);
394                    t2 = 037777600000l;
395                    t2 = n0 & t2;
396                    t3 = rp[0] & 0177777;
397                    t2 = (t3 * t2) & BN_MASK2;
398                    t1 = t1 + t2;
399                    v=bn_mul_add_words(rp,np,nl,(BN_ULONG) t1);
400                 }
401 #else
402                 v=bn_mul_add_words(rp,np,nl,(rp[0]*n0)&BN_MASK2);
403 #endif
404                 nrp++;
405                 rp++;
406                 if (((nrp[-1]+=v)&BN_MASK2) >= v)
407                         continue;
408                 else
409                         {
410                         if (((++nrp[0])&BN_MASK2) != 0) continue;
411                         if (((++nrp[1])&BN_MASK2) != 0) continue;
412                         for (x=2; (((++nrp[x])&BN_MASK2) == 0); x++) ;
413                         }
414                 }
415         bn_correct_top(r);
416         
417         /* mont->ri will be a multiple of the word size and below code
418          * is kind of BN_rshift(ret,r,mont->ri) equivalent */
419         if (r->top <= ri)
420                 {
421                 ret->top=0;
422                 retn=1;
423                 goto err;
424                 }
425         al=r->top-ri;
426
427 # define BRANCH_FREE 1
428 # if BRANCH_FREE
429         if (bn_wexpand(ret,ri) == NULL) goto err;
430         x=0-(((al-ri)>>(sizeof(al)*8-1))&1);
431         ret->top=x=(ri&~x)|(al&x);      /* min(ri,al) */
432         ret->neg=r->neg;
433
434         rp=ret->d;
435         ap=&(r->d[ri]);
436
437         {
438         size_t m1,m2;
439
440         v=bn_sub_words(rp,ap,np,ri);
441         /* this ----------------^^ works even in al<ri case
442          * thanks to zealous zeroing of top of the vector in the
443          * beginning. */
444
445         /* if (al==ri && !v) || al>ri) nrp=rp; else nrp=ap; */
446         /* in other words if subtraction result is real, then
447          * trick unconditional memcpy below to perform in-place
448          * "refresh" instead of actual copy. */
449         m1=0-(size_t)(((al-ri)>>(sizeof(al)*8-1))&1);   /* al<ri */
450         m2=0-(size_t)(((ri-al)>>(sizeof(al)*8-1))&1);   /* al>ri */
451         m1|=m2;                 /* (al!=ri) */
452         m1|=(0-(size_t)v);      /* (al!=ri || v) */
453         m1&=~m2;                /* (al!=ri || v) && !al>ri */
454         nrp=(BN_ULONG *)(((size_t)rp&~m1)|((size_t)ap&m1));
455         }
456
457         /* 'i<ri' is chosen to eliminate dependency on input data, even
458          * though it results in redundant copy in al<ri case. */
459         for (i=0,ri-=4; i<ri; i+=4)
460                 {
461                 BN_ULONG t1,t2,t3,t4;
462                 
463                 t1=nrp[i+0];
464                 t2=nrp[i+1];
465                 t3=nrp[i+2];    ap[i+0]=0;
466                 t4=nrp[i+3];    ap[i+1]=0;
467                 rp[i+0]=t1;     ap[i+2]=0;
468                 rp[i+1]=t2;     ap[i+3]=0;
469                 rp[i+2]=t3;
470                 rp[i+3]=t4;
471                 }
472         for (ri+=4; i<ri; i++)
473                 rp[i]=nrp[i], ap[i]=0;
474         bn_correct_top(r);
475         bn_correct_top(ret);
476 # else
477         if (bn_wexpand(ret,al) == NULL) goto err;
478         ret->top=al;
479         ret->neg=r->neg;
480
481         rp=ret->d;
482         ap=&(r->d[ri]);
483         al-=4;
484         for (i=0; i<al; i+=4)
485                 {
486                 BN_ULONG t1,t2,t3,t4;
487                 
488                 t1=ap[i+0];
489                 t2=ap[i+1];
490                 t3=ap[i+2];
491                 t4=ap[i+3];
492                 rp[i+0]=t1;
493                 rp[i+1]=t2;
494                 rp[i+2]=t3;
495                 rp[i+3]=t4;
496                 }
497         al+=4;
498         for (; i<al; i++)
499                 rp[i]=ap[i];
500 # endif
501 #else /* !MONT_WORD */ 
502         BIGNUM *t1,*t2;
503
504         BN_CTX_start(ctx);
505         t1 = BN_CTX_get(ctx);
506         t2 = BN_CTX_get(ctx);
507         if (t1 == NULL || t2 == NULL) goto err;
508         
509         if (!BN_copy(t1,a)) goto err;
510         BN_mask_bits(t1,mont->ri);
511
512         if (!BN_mul(t2,t1,&mont->Ni,ctx)) goto err;
513         BN_mask_bits(t2,mont->ri);
514
515         if (!BN_mul(t1,t2,&mont->N,ctx)) goto err;
516         if (!BN_add(t2,a,t1)) goto err;
517         if (!BN_rshift(ret,t2,mont->ri)) goto err;
518 #endif /* MONT_WORD */
519
520 #if !defined(BRANCH_FREE) || BRANCH_FREE==0
521         if (BN_ucmp(ret, &(mont->N)) >= 0)
522                 {
523                 if (!BN_usub(ret,ret,&(mont->N))) goto err;
524                 }
525 #endif
526         retn=1;
527         bn_check_top(ret);
528  err:
529         BN_CTX_end(ctx);
530         return(retn);
531         }
532 #endif /* MONT_FROM_WORD___NON_DEFAULT_0_9_8_BUILD */
533
534 BN_MONT_CTX *BN_MONT_CTX_new(void)
535         {
536         BN_MONT_CTX *ret;
537
538         if ((ret=(BN_MONT_CTX *)OPENSSL_malloc(sizeof(BN_MONT_CTX))) == NULL)
539                 return(NULL);
540
541         BN_MONT_CTX_init(ret);
542         ret->flags=BN_FLG_MALLOCED;
543         return(ret);
544         }
545
546 void BN_MONT_CTX_init(BN_MONT_CTX *ctx)
547         {
548         ctx->ri=0;
549         BN_init(&(ctx->RR));
550         BN_init(&(ctx->N));
551         BN_init(&(ctx->Ni));
552 #if 0 /* for OpenSSL 0.9.9 mont->n0 */
553         ctx->n0[0] = ctx->n0[1] = 0;
554 #else
555         ctx->n0 = 0;
556 #endif
557         ctx->flags=0;
558         }
559
560 void BN_MONT_CTX_free(BN_MONT_CTX *mont)
561         {
562         if(mont == NULL)
563             return;
564
565         BN_free(&(mont->RR));
566         BN_free(&(mont->N));
567         BN_free(&(mont->Ni));
568         if (mont->flags & BN_FLG_MALLOCED)
569                 OPENSSL_free(mont);
570         }
571
572 int BN_MONT_CTX_set(BN_MONT_CTX *mont, const BIGNUM *mod, BN_CTX *ctx)
573         {
574         int ret = 0;
575         BIGNUM *Ri,*R;
576
577         BN_CTX_start(ctx);
578         if((Ri = BN_CTX_get(ctx)) == NULL) goto err;
579         R= &(mont->RR);                                 /* grab RR as a temp */
580         if (!BN_copy(&(mont->N),mod)) goto err;         /* Set N */
581         mont->N.neg = 0;
582
583 #ifdef MONT_WORD
584                 {
585                 BIGNUM tmod;
586                 BN_ULONG buf[2];
587
588                 mont->ri=(BN_num_bits(mod)+(BN_BITS2-1))/BN_BITS2*BN_BITS2;
589                 BN_zero(R);
590 #if 0 /* for OpenSSL 0.9.9 mont->n0, would be "#if defined(OPENSSL_BN_ASM_MONT) && (BN_BITS2<=32)",
591          only certain BN_BITS2<=32 platforms actually need this */
592                 if (!(BN_set_bit(R,2*BN_BITS2))) goto err;      /* R */
593 #else
594                 if (!(BN_set_bit(R,BN_BITS2))) goto err;        /* R */
595 #endif
596
597                 buf[0]=mod->d[0]; /* tmod = N mod word size */
598                 buf[1]=0;
599
600                 BN_init(&tmod);
601                 tmod.d=buf;
602                 tmod.top = buf[0] != 0 ? 1 : 0;
603                 tmod.dmax=2;
604                 tmod.neg=0;
605
606 #if 0 /* for OpenSSL 0.9.9 mont->n0, would be "#if defined(OPENSSL_BN_ASM_MONT) && (BN_BITS2<=32)";
607          only certain BN_BITS2<=32 platforms actually need this */
608                                                                 tmod.top=0;
609                 if ((buf[0] = mod->d[0]))                       tmod.top=1;
610                 if ((buf[1] = mod->top>1 ? mod->d[1] : 0))      tmod.top=2;
611
612                 if ((BN_mod_inverse(Ri,R,&tmod,ctx)) == NULL)
613                         goto err;
614                 if (!BN_lshift(Ri,Ri,2*BN_BITS2)) goto err; /* R*Ri */
615                 if (!BN_is_zero(Ri))
616                         {
617                         if (!BN_sub_word(Ri,1)) goto err;
618                         }
619                 else /* if N mod word size == 1 */
620                         {
621                         if (bn_expand(Ri,(int)sizeof(BN_ULONG)*2) == NULL)
622                                 goto err;
623                         /* Ri-- (mod double word size) */
624                         Ri->neg=0;
625                         Ri->d[0]=BN_MASK2;
626                         Ri->d[1]=BN_MASK2;
627                         Ri->top=2;
628                         }
629                 if (!BN_div(Ri,NULL,Ri,&tmod,ctx)) goto err;
630                 /* Ni = (R*Ri-1)/N,
631                  * keep only couple of least significant words: */
632                 mont->n0[0] = (Ri->top > 0) ? Ri->d[0] : 0;
633                 mont->n0[1] = (Ri->top > 1) ? Ri->d[1] : 0;
634 #else
635                                                         /* Ri = R^-1 mod N*/
636                 if ((BN_mod_inverse(Ri,R,&tmod,ctx)) == NULL)
637                         goto err;
638                 if (!BN_lshift(Ri,Ri,BN_BITS2)) goto err; /* R*Ri */
639                 if (!BN_is_zero(Ri))
640                         {
641                         if (!BN_sub_word(Ri,1)) goto err;
642                         }
643                 else /* if N mod word size == 1 */
644                         {
645                         if (!BN_set_word(Ri,BN_MASK2)) goto err;  /* Ri-- (mod word size) */
646                         }
647                 if (!BN_div(Ri,NULL,Ri,&tmod,ctx)) goto err;
648                 /* Ni = (R*Ri-1)/N,
649                  * keep only least significant word: */
650 # if 0 /* for OpenSSL 0.9.9 mont->n0 */
651                 mont->n0[0] = (Ri->top > 0) ? Ri->d[0] : 0;
652                 mont->n0[1] = 0;
653 # else
654                 mont->n0 = (Ri->top > 0) ? Ri->d[0] : 0;
655 # endif
656 #endif
657                 }
658 #else /* !MONT_WORD */
659                 { /* bignum version */
660                 mont->ri=BN_num_bits(&mont->N);
661                 BN_zero(R);
662                 if (!BN_set_bit(R,mont->ri)) goto err;  /* R = 2^ri */
663                                                         /* Ri = R^-1 mod N*/
664                 if ((BN_mod_inverse(Ri,R,&mont->N,ctx)) == NULL)
665                         goto err;
666                 if (!BN_lshift(Ri,Ri,mont->ri)) goto err; /* R*Ri */
667                 if (!BN_sub_word(Ri,1)) goto err;
668                                                         /* Ni = (R*Ri-1) / N */
669                 if (!BN_div(&(mont->Ni),NULL,Ri,&mont->N,ctx)) goto err;
670                 }
671 #endif
672
673         /* setup RR for conversions */
674         BN_zero(&(mont->RR));
675         if (!BN_set_bit(&(mont->RR),mont->ri*2)) goto err;
676         if (!BN_mod(&(mont->RR),&(mont->RR),&(mont->N),ctx)) goto err;
677
678         ret = 1;
679 err:
680         BN_CTX_end(ctx);
681         return ret;
682         }
683
684 BN_MONT_CTX *BN_MONT_CTX_copy(BN_MONT_CTX *to, BN_MONT_CTX *from)
685         {
686         if (to == from) return(to);
687
688         if (!BN_copy(&(to->RR),&(from->RR))) return NULL;
689         if (!BN_copy(&(to->N),&(from->N))) return NULL;
690         if (!BN_copy(&(to->Ni),&(from->Ni))) return NULL;
691         to->ri=from->ri;
692 #if 0 /* for OpenSSL 0.9.9 mont->n0 */
693         to->n0[0]=from->n0[0];
694         to->n0[1]=from->n0[1];
695 #else
696         to->n0=from->n0;
697 #endif
698         return(to);
699         }
700
701 BN_MONT_CTX *BN_MONT_CTX_set_locked(BN_MONT_CTX **pmont, int lock,
702                                         const BIGNUM *mod, BN_CTX *ctx)
703         {
704         int got_write_lock = 0;
705         BN_MONT_CTX *ret;
706
707         CRYPTO_r_lock(lock);
708         if (!*pmont)
709                 {
710                 CRYPTO_r_unlock(lock);
711                 CRYPTO_w_lock(lock);
712                 got_write_lock = 1;
713
714                 if (!*pmont)
715                         {
716                         ret = BN_MONT_CTX_new();
717                         if (ret && !BN_MONT_CTX_set(ret, mod, ctx))
718                                 BN_MONT_CTX_free(ret);
719                         else
720                                 *pmont = ret;
721                         }
722                 }
723         
724         ret = *pmont;
725         
726         if (got_write_lock)
727                 CRYPTO_w_unlock(lock);
728         else
729                 CRYPTO_r_unlock(lock);
730                 
731         return ret;
732         }