ce31ad0a58a61f74f33fbe12118fedb188ecea3c
[openssl.git] / crypto / bn / bn_exp.c
1 /* crypto/bn/bn_exp.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-2005 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 #define OPENSSL_FIPSAPI
113
114 #include "cryptlib.h"
115 #include "bn_lcl.h"
116
117 /* maximum precomputation table size for *variable* sliding windows */
118 #define TABLE_SIZE      32
119
120 /* this one works - simple but works */
121 int BN_exp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx)
122         {
123         int i,bits,ret=0;
124         BIGNUM *v,*rr;
125
126         if (BN_get_flags(p, BN_FLG_CONSTTIME) != 0)
127                 {
128                 /* BN_FLG_CONSTTIME only supported by BN_mod_exp_mont() */
129                 BNerr(BN_F_BN_EXP,ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
130                 return -1;
131                 }
132
133         BN_CTX_start(ctx);
134         if ((r == a) || (r == p))
135                 rr = BN_CTX_get(ctx);
136         else
137                 rr = r;
138         v = BN_CTX_get(ctx);
139         if (rr == NULL || v == NULL) goto err;
140
141         if (BN_copy(v,a) == NULL) goto err;
142         bits=BN_num_bits(p);
143
144         if (BN_is_odd(p))
145                 { if (BN_copy(rr,a) == NULL) goto err; }
146         else    { if (!BN_one(rr)) goto err; }
147
148         for (i=1; i<bits; i++)
149                 {
150                 if (!BN_sqr(v,v,ctx)) goto err;
151                 if (BN_is_bit_set(p,i))
152                         {
153                         if (!BN_mul(rr,rr,v,ctx)) goto err;
154                         }
155                 }
156         ret=1;
157 err:
158         if (r != rr) BN_copy(r,rr);
159         BN_CTX_end(ctx);
160         bn_check_top(r);
161         return(ret);
162         }
163
164
165 int BN_mod_exp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, const BIGNUM *m,
166                BN_CTX *ctx)
167         {
168         int ret;
169
170         bn_check_top(a);
171         bn_check_top(p);
172         bn_check_top(m);
173
174         /* For even modulus  m = 2^k*m_odd,  it might make sense to compute
175          * a^p mod m_odd  and  a^p mod 2^k  separately (with Montgomery
176          * exponentiation for the odd part), using appropriate exponent
177          * reductions, and combine the results using the CRT.
178          *
179          * For now, we use Montgomery only if the modulus is odd; otherwise,
180          * exponentiation using the reciprocal-based quick remaindering
181          * algorithm is used.
182          *
183          * (Timing obtained with expspeed.c [computations  a^p mod m
184          * where  a, p, m  are of the same length: 256, 512, 1024, 2048,
185          * 4096, 8192 bits], compared to the running time of the
186          * standard algorithm:
187          *
188          *   BN_mod_exp_mont   33 .. 40 %  [AMD K6-2, Linux, debug configuration]
189          *                     55 .. 77 %  [UltraSparc processor, but
190          *                                  debug-solaris-sparcv8-gcc conf.]
191          * 
192          *   BN_mod_exp_recp   50 .. 70 %  [AMD K6-2, Linux, debug configuration]
193          *                     62 .. 118 % [UltraSparc, debug-solaris-sparcv8-gcc]
194          *
195          * On the Sparc, BN_mod_exp_recp was faster than BN_mod_exp_mont
196          * at 2048 and more bits, but at 512 and 1024 bits, it was
197          * slower even than the standard algorithm!
198          *
199          * "Real" timings [linux-elf, solaris-sparcv9-gcc configurations]
200          * should be obtained when the new Montgomery reduction code
201          * has been integrated into OpenSSL.)
202          */
203
204 #define MONT_MUL_MOD
205 #define MONT_EXP_WORD
206 #define RECP_MUL_MOD
207
208 #ifdef MONT_MUL_MOD
209         /* I have finally been able to take out this pre-condition of
210          * the top bit being set.  It was caused by an error in BN_div
211          * with negatives.  There was also another problem when for a^b%m
212          * a >= m.  eay 07-May-97 */
213 /*      if ((m->d[m->top-1]&BN_TBIT) && BN_is_odd(m)) */
214
215         if (BN_is_odd(m))
216                 {
217 #  ifdef MONT_EXP_WORD
218                 if (a->top == 1 && !a->neg && (BN_get_flags(p, BN_FLG_CONSTTIME) == 0))
219                         {
220                         BN_ULONG A = a->d[0];
221                         ret=BN_mod_exp_mont_word(r,A,p,m,ctx,NULL);
222                         }
223                 else
224 #  endif
225                         ret=BN_mod_exp_mont(r,a,p,m,ctx,NULL);
226                 }
227         else
228 #endif
229 #ifdef RECP_MUL_MOD
230                 { ret=BN_mod_exp_recp(r,a,p,m,ctx); }
231 #else
232                 { ret=BN_mod_exp_simple(r,a,p,m,ctx); }
233 #endif
234
235         bn_check_top(r);
236         return(ret);
237         }
238
239
240 int BN_mod_exp_recp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p,
241                     const BIGNUM *m, BN_CTX *ctx)
242         {
243         int i,j,bits,ret=0,wstart,wend,window,wvalue;
244         int start=1;
245         BIGNUM *aa;
246         /* Table of variables obtained from 'ctx' */
247         BIGNUM *val[TABLE_SIZE];
248         BN_RECP_CTX recp;
249
250         if (BN_get_flags(p, BN_FLG_CONSTTIME) != 0)
251                 {
252                 /* BN_FLG_CONSTTIME only supported by BN_mod_exp_mont() */
253                 BNerr(BN_F_BN_MOD_EXP_RECP,ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
254                 return -1;
255                 }
256
257         bits=BN_num_bits(p);
258
259         if (bits == 0)
260                 {
261                 ret = BN_one(r);
262                 return ret;
263                 }
264
265         BN_CTX_start(ctx);
266         aa = BN_CTX_get(ctx);
267         val[0] = BN_CTX_get(ctx);
268         if(!aa || !val[0]) goto err;
269
270         BN_RECP_CTX_init(&recp);
271         if (m->neg)
272                 {
273                 /* ignore sign of 'm' */
274                 if (!BN_copy(aa, m)) goto err;
275                 aa->neg = 0;
276                 if (BN_RECP_CTX_set(&recp,aa,ctx) <= 0) goto err;
277                 }
278         else
279                 {
280                 if (BN_RECP_CTX_set(&recp,m,ctx) <= 0) goto err;
281                 }
282
283         if (!BN_nnmod(val[0],a,m,ctx)) goto err;                /* 1 */
284         if (BN_is_zero(val[0]))
285                 {
286                 BN_zero(r);
287                 ret = 1;
288                 goto err;
289                 }
290
291         window = BN_window_bits_for_exponent_size(bits);
292         if (window > 1)
293                 {
294                 if (!BN_mod_mul_reciprocal(aa,val[0],val[0],&recp,ctx))
295                         goto err;                               /* 2 */
296                 j=1<<(window-1);
297                 for (i=1; i<j; i++)
298                         {
299                         if(((val[i] = BN_CTX_get(ctx)) == NULL) ||
300                                         !BN_mod_mul_reciprocal(val[i],val[i-1],
301                                                 aa,&recp,ctx))
302                                 goto err;
303                         }
304                 }
305                 
306         start=1;        /* This is used to avoid multiplication etc
307                          * when there is only the value '1' in the
308                          * buffer. */
309         wvalue=0;       /* The 'value' of the window */
310         wstart=bits-1;  /* The top bit of the window */
311         wend=0;         /* The bottom bit of the window */
312
313         if (!BN_one(r)) goto err;
314
315         for (;;)
316                 {
317                 if (BN_is_bit_set(p,wstart) == 0)
318                         {
319                         if (!start)
320                                 if (!BN_mod_mul_reciprocal(r,r,r,&recp,ctx))
321                                 goto err;
322                         if (wstart == 0) break;
323                         wstart--;
324                         continue;
325                         }
326                 /* We now have wstart on a 'set' bit, we now need to work out
327                  * how bit a window to do.  To do this we need to scan
328                  * forward until the last set bit before the end of the
329                  * window */
330                 j=wstart;
331                 wvalue=1;
332                 wend=0;
333                 for (i=1; i<window; i++)
334                         {
335                         if (wstart-i < 0) break;
336                         if (BN_is_bit_set(p,wstart-i))
337                                 {
338                                 wvalue<<=(i-wend);
339                                 wvalue|=1;
340                                 wend=i;
341                                 }
342                         }
343
344                 /* wend is the size of the current window */
345                 j=wend+1;
346                 /* add the 'bytes above' */
347                 if (!start)
348                         for (i=0; i<j; i++)
349                                 {
350                                 if (!BN_mod_mul_reciprocal(r,r,r,&recp,ctx))
351                                         goto err;
352                                 }
353                 
354                 /* wvalue will be an odd number < 2^window */
355                 if (!BN_mod_mul_reciprocal(r,r,val[wvalue>>1],&recp,ctx))
356                         goto err;
357
358                 /* move the 'window' down further */
359                 wstart-=wend+1;
360                 wvalue=0;
361                 start=0;
362                 if (wstart < 0) break;
363                 }
364         ret=1;
365 err:
366         BN_CTX_end(ctx);
367         BN_RECP_CTX_free(&recp);
368         bn_check_top(r);
369         return(ret);
370         }
371
372
373 int BN_mod_exp_mont(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p,
374                     const BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *in_mont)
375         {
376         int i,j,bits,ret=0,wstart,wend,window,wvalue;
377         int start=1;
378         BIGNUM *d,*r;
379         const BIGNUM *aa;
380         /* Table of variables obtained from 'ctx' */
381         BIGNUM *val[TABLE_SIZE];
382         BN_MONT_CTX *mont=NULL;
383
384         if (BN_get_flags(p, BN_FLG_CONSTTIME) != 0)
385                 {
386                 return BN_mod_exp_mont_consttime(rr, a, p, m, ctx, in_mont);
387                 }
388
389         bn_check_top(a);
390         bn_check_top(p);
391         bn_check_top(m);
392
393         if (!BN_is_odd(m))
394                 {
395                 BNerr(BN_F_BN_MOD_EXP_MONT,BN_R_CALLED_WITH_EVEN_MODULUS);
396                 return(0);
397                 }
398         bits=BN_num_bits(p);
399         if (bits == 0)
400                 {
401                 ret = BN_one(rr);
402                 return ret;
403                 }
404
405         BN_CTX_start(ctx);
406         d = BN_CTX_get(ctx);
407         r = BN_CTX_get(ctx);
408         val[0] = BN_CTX_get(ctx);
409         if (!d || !r || !val[0]) goto err;
410
411         /* If this is not done, things will break in the montgomery
412          * part */
413
414         if (in_mont != NULL)
415                 mont=in_mont;
416         else
417                 {
418                 if ((mont=BN_MONT_CTX_new()) == NULL) goto err;
419                 if (!BN_MONT_CTX_set(mont,m,ctx)) goto err;
420                 }
421
422         if (a->neg || BN_ucmp(a,m) >= 0)
423                 {
424                 if (!BN_nnmod(val[0],a,m,ctx))
425                         goto err;
426                 aa= val[0];
427                 }
428         else
429                 aa=a;
430         if (BN_is_zero(aa))
431                 {
432                 BN_zero(rr);
433                 ret = 1;
434                 goto err;
435                 }
436         if (!BN_to_montgomery(val[0],aa,mont,ctx)) goto err; /* 1 */
437
438         window = BN_window_bits_for_exponent_size(bits);
439         if (window > 1)
440                 {
441                 if (!BN_mod_mul_montgomery(d,val[0],val[0],mont,ctx)) goto err; /* 2 */
442                 j=1<<(window-1);
443                 for (i=1; i<j; i++)
444                         {
445                         if(((val[i] = BN_CTX_get(ctx)) == NULL) ||
446                                         !BN_mod_mul_montgomery(val[i],val[i-1],
447                                                 d,mont,ctx))
448                                 goto err;
449                         }
450                 }
451
452         start=1;        /* This is used to avoid multiplication etc
453                          * when there is only the value '1' in the
454                          * buffer. */
455         wvalue=0;       /* The 'value' of the window */
456         wstart=bits-1;  /* The top bit of the window */
457         wend=0;         /* The bottom bit of the window */
458
459         if (!BN_to_montgomery(r,BN_value_one(),mont,ctx)) goto err;
460         for (;;)
461                 {
462                 if (BN_is_bit_set(p,wstart) == 0)
463                         {
464                         if (!start)
465                                 {
466                                 if (!BN_mod_mul_montgomery(r,r,r,mont,ctx))
467                                 goto err;
468                                 }
469                         if (wstart == 0) break;
470                         wstart--;
471                         continue;
472                         }
473                 /* We now have wstart on a 'set' bit, we now need to work out
474                  * how bit a window to do.  To do this we need to scan
475                  * forward until the last set bit before the end of the
476                  * window */
477                 j=wstart;
478                 wvalue=1;
479                 wend=0;
480                 for (i=1; i<window; i++)
481                         {
482                         if (wstart-i < 0) break;
483                         if (BN_is_bit_set(p,wstart-i))
484                                 {
485                                 wvalue<<=(i-wend);
486                                 wvalue|=1;
487                                 wend=i;
488                                 }
489                         }
490
491                 /* wend is the size of the current window */
492                 j=wend+1;
493                 /* add the 'bytes above' */
494                 if (!start)
495                         for (i=0; i<j; i++)
496                                 {
497                                 if (!BN_mod_mul_montgomery(r,r,r,mont,ctx))
498                                         goto err;
499                                 }
500                 
501                 /* wvalue will be an odd number < 2^window */
502                 if (!BN_mod_mul_montgomery(r,r,val[wvalue>>1],mont,ctx))
503                         goto err;
504
505                 /* move the 'window' down further */
506                 wstart-=wend+1;
507                 wvalue=0;
508                 start=0;
509                 if (wstart < 0) break;
510                 }
511         if (!BN_from_montgomery(rr,r,mont,ctx)) goto err;
512         ret=1;
513 err:
514         if ((in_mont == NULL) && (mont != NULL)) BN_MONT_CTX_free(mont);
515         BN_CTX_end(ctx);
516         bn_check_top(rr);
517         return(ret);
518         }
519
520
521 /* BN_mod_exp_mont_consttime() stores the precomputed powers in a specific layout
522  * so that accessing any of these table values shows the same access pattern as far
523  * as cache lines are concerned.  The following functions are used to transfer a BIGNUM
524  * from/to that table. */
525
526 static int MOD_EXP_CTIME_COPY_TO_PREBUF(BIGNUM *b, int top, unsigned char *buf, int idx, int width)
527         {
528         size_t i, j;
529
530         if (bn_wexpand(b, top) == NULL)
531                 return 0;
532         while (b->top < top)
533                 {
534                 b->d[b->top++] = 0;
535                 }
536         
537         for (i = 0, j=idx; i < top * sizeof b->d[0]; i++, j+=width)
538                 {
539                 buf[j] = ((unsigned char*)b->d)[i];
540                 }
541
542         bn_correct_top(b);
543         return 1;
544         }
545
546 static int MOD_EXP_CTIME_COPY_FROM_PREBUF(BIGNUM *b, int top, unsigned char *buf, int idx, int width)
547         {
548         size_t i, j;
549
550         if (bn_wexpand(b, top) == NULL)
551                 return 0;
552
553         for (i=0, j=idx; i < top * sizeof b->d[0]; i++, j+=width)
554                 {
555                 ((unsigned char*)b->d)[i] = buf[j];
556                 }
557
558         b->top = top;
559         bn_correct_top(b);
560         return 1;
561         }       
562
563 /* Given a pointer value, compute the next address that is a cache line multiple. */
564 #define MOD_EXP_CTIME_ALIGN(x_) \
565         ((unsigned char*)(x_) + (MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH - (((BN_ULONG)(x_)) & (MOD_EXP_CTIME_MIN_CACHE_LINE_MASK))))
566
567 /* This variant of BN_mod_exp_mont() uses fixed windows and the special
568  * precomputation memory layout to limit data-dependency to a minimum
569  * to protect secret exponents (cf. the hyper-threading timing attacks
570  * pointed out by Colin Percival,
571  * http://www.daemonology.net/hyperthreading-considered-harmful/)
572  */
573 int BN_mod_exp_mont_consttime(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p,
574                     const BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *in_mont)
575         {
576         int i,bits,ret=0,idx,window,wvalue;
577         int top;
578         BIGNUM *r;
579         const BIGNUM *aa;
580         BN_MONT_CTX *mont=NULL;
581
582         int numPowers;
583         unsigned char *powerbufFree=NULL;
584         int powerbufLen = 0;
585         unsigned char *powerbuf=NULL;
586         BIGNUM *computeTemp=NULL, *am=NULL;
587
588         bn_check_top(a);
589         bn_check_top(p);
590         bn_check_top(m);
591
592         top = m->top;
593
594         if (!(m->d[0] & 1))
595                 {
596                 BNerr(BN_F_BN_MOD_EXP_MONT_CONSTTIME,BN_R_CALLED_WITH_EVEN_MODULUS);
597                 return(0);
598                 }
599         bits=BN_num_bits(p);
600         if (bits == 0)
601                 {
602                 ret = BN_one(rr);
603                 return ret;
604                 }
605
606         /* Initialize BIGNUM context and allocate intermediate result */
607         BN_CTX_start(ctx);
608         r = BN_CTX_get(ctx);
609         if (r == NULL) goto err;
610
611         /* Allocate a montgomery context if it was not supplied by the caller.
612          * If this is not done, things will break in the montgomery part.
613          */
614         if (in_mont != NULL)
615                 mont=in_mont;
616         else
617                 {
618                 if ((mont=BN_MONT_CTX_new()) == NULL) goto err;
619                 if (!BN_MONT_CTX_set(mont,m,ctx)) goto err;
620                 }
621
622         /* Get the window size to use with size of p. */
623         window = BN_window_bits_for_ctime_exponent_size(bits);
624
625         /* Allocate a buffer large enough to hold all of the pre-computed
626          * powers of a.
627          */
628         numPowers = 1 << window;
629         powerbufLen = sizeof(m->d[0])*top*numPowers;
630         if ((powerbufFree=(unsigned char*)OPENSSL_malloc(powerbufLen+MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH)) == NULL)
631                 goto err;
632                 
633         powerbuf = MOD_EXP_CTIME_ALIGN(powerbufFree);
634         memset(powerbuf, 0, powerbufLen);
635
636         /* Initialize the intermediate result. Do this early to save double conversion,
637          * once each for a^0 and intermediate result.
638          */
639         if (!BN_to_montgomery(r,BN_value_one(),mont,ctx)) goto err;
640         if (!MOD_EXP_CTIME_COPY_TO_PREBUF(r, top, powerbuf, 0, numPowers)) goto err;
641
642         /* Initialize computeTemp as a^1 with montgomery precalcs */
643         computeTemp = BN_CTX_get(ctx);
644         am = BN_CTX_get(ctx);
645         if (computeTemp==NULL || am==NULL) goto err;
646
647         if (a->neg || BN_ucmp(a,m) >= 0)
648                 {
649                 if (!BN_mod(am,a,m,ctx))
650                         goto err;
651                 aa= am;
652                 }
653         else
654                 aa=a;
655         if (!BN_to_montgomery(am,aa,mont,ctx)) goto err;
656         if (!BN_copy(computeTemp, am)) goto err;
657         if (!MOD_EXP_CTIME_COPY_TO_PREBUF(am, top, powerbuf, 1, numPowers)) goto err;
658
659         /* If the window size is greater than 1, then calculate
660          * val[i=2..2^winsize-1]. Powers are computed as a*a^(i-1)
661          * (even powers could instead be computed as (a^(i/2))^2
662          * to use the slight performance advantage of sqr over mul).
663          */
664         if (window > 1)
665                 {
666                 for (i=2; i<numPowers; i++)
667                         {
668                         /* Calculate a^i = a^(i-1) * a */
669                         if (!BN_mod_mul_montgomery(computeTemp,am,computeTemp,mont,ctx))
670                                 goto err;
671                         if (!MOD_EXP_CTIME_COPY_TO_PREBUF(computeTemp, top, powerbuf, i, numPowers)) goto err;
672                         }
673                 }
674
675         /* Adjust the number of bits up to a multiple of the window size.
676          * If the exponent length is not a multiple of the window size, then
677          * this pads the most significant bits with zeros to normalize the
678          * scanning loop to there's no special cases.
679          *
680          * * NOTE: Making the window size a power of two less than the native
681          * * word size ensures that the padded bits won't go past the last
682          * * word in the internal BIGNUM structure. Going past the end will
683          * * still produce the correct result, but causes a different branch
684          * * to be taken in the BN_is_bit_set function.
685          */
686         bits = ((bits+window-1)/window)*window;
687         idx=bits-1;     /* The top bit of the window */
688
689         /* Scan the exponent one window at a time starting from the most
690          * significant bits.
691          */
692         while (idx >= 0)
693                 {
694                 wvalue=0; /* The 'value' of the window */
695                 
696                 /* Scan the window, squaring the result as we go */
697                 for (i=0; i<window; i++,idx--)
698                         {
699                         if (!BN_mod_mul_montgomery(r,r,r,mont,ctx))     goto err;
700                         wvalue = (wvalue<<1)+BN_is_bit_set(p,idx);
701                         }
702                 
703                 /* Fetch the appropriate pre-computed value from the pre-buf */
704                 if (!MOD_EXP_CTIME_COPY_FROM_PREBUF(computeTemp, top, powerbuf, wvalue, numPowers)) goto err;
705
706                 /* Multiply the result into the intermediate result */
707                 if (!BN_mod_mul_montgomery(r,r,computeTemp,mont,ctx)) goto err;
708                 }
709
710         /* Convert the final result from montgomery to standard format */
711         if (!BN_from_montgomery(rr,r,mont,ctx)) goto err;
712         ret=1;
713 err:
714         if ((in_mont == NULL) && (mont != NULL)) BN_MONT_CTX_free(mont);
715         if (powerbuf!=NULL)
716                 {
717                 OPENSSL_cleanse(powerbuf,powerbufLen);
718                 OPENSSL_free(powerbufFree);
719                 }
720         if (am!=NULL) BN_clear(am);
721         if (computeTemp!=NULL) BN_clear(computeTemp);
722         BN_CTX_end(ctx);
723         return(ret);
724         }
725
726 int BN_mod_exp_mont_word(BIGNUM *rr, BN_ULONG a, const BIGNUM *p,
727                          const BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *in_mont)
728         {
729         BN_MONT_CTX *mont = NULL;
730         int b, bits, ret=0;
731         int r_is_one;
732         BN_ULONG w, next_w;
733         BIGNUM *d, *r, *t;
734         BIGNUM *swap_tmp;
735 #define BN_MOD_MUL_WORD(r, w, m) \
736                 (BN_mul_word(r, (w)) && \
737                 (/* BN_ucmp(r, (m)) < 0 ? 1 :*/  \
738                         (BN_mod(t, r, m, ctx) && (swap_tmp = r, r = t, t = swap_tmp, 1))))
739                 /* BN_MOD_MUL_WORD is only used with 'w' large,
740                  * so the BN_ucmp test is probably more overhead
741                  * than always using BN_mod (which uses BN_copy if
742                  * a similar test returns true). */
743                 /* We can use BN_mod and do not need BN_nnmod because our
744                  * accumulator is never negative (the result of BN_mod does
745                  * not depend on the sign of the modulus).
746                  */
747 #define BN_TO_MONTGOMERY_WORD(r, w, mont) \
748                 (BN_set_word(r, (w)) && BN_to_montgomery(r, r, (mont), ctx))
749
750         if (BN_get_flags(p, BN_FLG_CONSTTIME) != 0)
751                 {
752                 /* BN_FLG_CONSTTIME only supported by BN_mod_exp_mont() */
753                 BNerr(BN_F_BN_MOD_EXP_MONT_WORD,ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
754                 return -1;
755                 }
756
757         bn_check_top(p);
758         bn_check_top(m);
759
760         if (!BN_is_odd(m))
761                 {
762                 BNerr(BN_F_BN_MOD_EXP_MONT_WORD,BN_R_CALLED_WITH_EVEN_MODULUS);
763                 return(0);
764                 }
765         if (m->top == 1)
766                 a %= m->d[0]; /* make sure that 'a' is reduced */
767
768         bits = BN_num_bits(p);
769         if (bits == 0)
770                 {
771                 ret = BN_one(rr);
772                 return ret;
773                 }
774         if (a == 0)
775                 {
776                 BN_zero(rr);
777                 ret = 1;
778                 return ret;
779                 }
780
781         BN_CTX_start(ctx);
782         d = BN_CTX_get(ctx);
783         r = BN_CTX_get(ctx);
784         t = BN_CTX_get(ctx);
785         if (d == NULL || r == NULL || t == NULL) goto err;
786
787         if (in_mont != NULL)
788                 mont=in_mont;
789         else
790                 {
791                 if ((mont = BN_MONT_CTX_new()) == NULL) goto err;
792                 if (!BN_MONT_CTX_set(mont, m, ctx)) goto err;
793                 }
794
795         r_is_one = 1; /* except for Montgomery factor */
796
797         /* bits-1 >= 0 */
798
799         /* The result is accumulated in the product r*w. */
800         w = a; /* bit 'bits-1' of 'p' is always set */
801         for (b = bits-2; b >= 0; b--)
802                 {
803                 /* First, square r*w. */
804                 next_w = w*w;
805                 if ((next_w/w) != w) /* overflow */
806                         {
807                         if (r_is_one)
808                                 {
809                                 if (!BN_TO_MONTGOMERY_WORD(r, w, mont)) goto err;
810                                 r_is_one = 0;
811                                 }
812                         else
813                                 {
814                                 if (!BN_MOD_MUL_WORD(r, w, m)) goto err;
815                                 }
816                         next_w = 1;
817                         }
818                 w = next_w;
819                 if (!r_is_one)
820                         {
821                         if (!BN_mod_mul_montgomery(r, r, r, mont, ctx)) goto err;
822                         }
823
824                 /* Second, multiply r*w by 'a' if exponent bit is set. */
825                 if (BN_is_bit_set(p, b))
826                         {
827                         next_w = w*a;
828                         if ((next_w/a) != w) /* overflow */
829                                 {
830                                 if (r_is_one)
831                                         {
832                                         if (!BN_TO_MONTGOMERY_WORD(r, w, mont)) goto err;
833                                         r_is_one = 0;
834                                         }
835                                 else
836                                         {
837                                         if (!BN_MOD_MUL_WORD(r, w, m)) goto err;
838                                         }
839                                 next_w = a;
840                                 }
841                         w = next_w;
842                         }
843                 }
844
845         /* Finally, set r:=r*w. */
846         if (w != 1)
847                 {
848                 if (r_is_one)
849                         {
850                         if (!BN_TO_MONTGOMERY_WORD(r, w, mont)) goto err;
851                         r_is_one = 0;
852                         }
853                 else
854                         {
855                         if (!BN_MOD_MUL_WORD(r, w, m)) goto err;
856                         }
857                 }
858
859         if (r_is_one) /* can happen only if a == 1*/
860                 {
861                 if (!BN_one(rr)) goto err;
862                 }
863         else
864                 {
865                 if (!BN_from_montgomery(rr, r, mont, ctx)) goto err;
866                 }
867         ret = 1;
868 err:
869         if ((in_mont == NULL) && (mont != NULL)) BN_MONT_CTX_free(mont);
870         BN_CTX_end(ctx);
871         bn_check_top(rr);
872         return(ret);
873         }
874
875
876 /* The old fallback, simple version :-) */
877 int BN_mod_exp_simple(BIGNUM *r, const BIGNUM *a, const BIGNUM *p,
878                 const BIGNUM *m, BN_CTX *ctx)
879         {
880         int i,j,bits,ret=0,wstart,wend,window,wvalue;
881         int start=1;
882         BIGNUM *d;
883         /* Table of variables obtained from 'ctx' */
884         BIGNUM *val[TABLE_SIZE];
885
886         if (BN_get_flags(p, BN_FLG_CONSTTIME) != 0)
887                 {
888                 /* BN_FLG_CONSTTIME only supported by BN_mod_exp_mont() */
889                 BNerr(BN_F_BN_MOD_EXP_SIMPLE,ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
890                 return -1;
891                 }
892
893         bits=BN_num_bits(p);
894
895         if (bits == 0)
896                 {
897                 ret = BN_one(r);
898                 return ret;
899                 }
900
901         BN_CTX_start(ctx);
902         d = BN_CTX_get(ctx);
903         val[0] = BN_CTX_get(ctx);
904         if(!d || !val[0]) goto err;
905
906         if (!BN_nnmod(val[0],a,m,ctx)) goto err;                /* 1 */
907         if (BN_is_zero(val[0]))
908                 {
909                 BN_zero(r);
910                 ret = 1;
911                 goto err;
912                 }
913
914         window = BN_window_bits_for_exponent_size(bits);
915         if (window > 1)
916                 {
917                 if (!BN_mod_mul(d,val[0],val[0],m,ctx))
918                         goto err;                               /* 2 */
919                 j=1<<(window-1);
920                 for (i=1; i<j; i++)
921                         {
922                         if(((val[i] = BN_CTX_get(ctx)) == NULL) ||
923                                         !BN_mod_mul(val[i],val[i-1],d,m,ctx))
924                                 goto err;
925                         }
926                 }
927
928         start=1;        /* This is used to avoid multiplication etc
929                          * when there is only the value '1' in the
930                          * buffer. */
931         wvalue=0;       /* The 'value' of the window */
932         wstart=bits-1;  /* The top bit of the window */
933         wend=0;         /* The bottom bit of the window */
934
935         if (!BN_one(r)) goto err;
936
937         for (;;)
938                 {
939                 if (BN_is_bit_set(p,wstart) == 0)
940                         {
941                         if (!start)
942                                 if (!BN_mod_mul(r,r,r,m,ctx))
943                                 goto err;
944                         if (wstart == 0) break;
945                         wstart--;
946                         continue;
947                         }
948                 /* We now have wstart on a 'set' bit, we now need to work out
949                  * how bit a window to do.  To do this we need to scan
950                  * forward until the last set bit before the end of the
951                  * window */
952                 j=wstart;
953                 wvalue=1;
954                 wend=0;
955                 for (i=1; i<window; i++)
956                         {
957                         if (wstart-i < 0) break;
958                         if (BN_is_bit_set(p,wstart-i))
959                                 {
960                                 wvalue<<=(i-wend);
961                                 wvalue|=1;
962                                 wend=i;
963                                 }
964                         }
965
966                 /* wend is the size of the current window */
967                 j=wend+1;
968                 /* add the 'bytes above' */
969                 if (!start)
970                         for (i=0; i<j; i++)
971                                 {
972                                 if (!BN_mod_mul(r,r,r,m,ctx))
973                                         goto err;
974                                 }
975                 
976                 /* wvalue will be an odd number < 2^window */
977                 if (!BN_mod_mul(r,r,val[wvalue>>1],m,ctx))
978                         goto err;
979
980                 /* move the 'window' down further */
981                 wstart-=wend+1;
982                 wvalue=0;
983                 start=0;
984                 if (wstart < 0) break;
985                 }
986         ret=1;
987 err:
988         BN_CTX_end(ctx);
989         bn_check_top(r);
990         return(ret);
991         }
992