Speed up DH with small generator.
[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 #include <stdio.h>
60 #include "cryptlib.h"
61 #include "bn_lcl.h"
62 #ifdef ATALLA
63 # include <alloca.h>
64 # include <atasi.h>
65 # include <assert.h>
66 # include <dlfcn.h>
67 #endif
68
69
70 #define TABLE_SIZE      16
71
72 /* slow but works */
73 int BN_mod_mul(BIGNUM *ret, BIGNUM *a, BIGNUM *b, const BIGNUM *m, BN_CTX *ctx)
74         {
75         BIGNUM *t;
76         int r=0;
77
78         bn_check_top(a);
79         bn_check_top(b);
80         bn_check_top(m);
81
82         BN_CTX_start(ctx);
83         if ((t = BN_CTX_get(ctx)) == NULL) goto err;
84         if (a == b)
85                 { if (!BN_sqr(t,a,ctx)) goto err; }
86         else
87                 { if (!BN_mul(t,a,b,ctx)) goto err; }
88         if (!BN_mod(ret,t,m,ctx)) goto err;
89         r=1;
90 err:
91         BN_CTX_end(ctx);
92         return(r);
93         }
94
95
96 /* this one works - simple but works */
97 int BN_exp(BIGNUM *r, BIGNUM *a, BIGNUM *p, BN_CTX *ctx)
98         {
99         int i,bits,ret=0;
100         BIGNUM *v,*rr;
101
102         BN_CTX_start(ctx);
103         if ((r == a) || (r == p))
104                 rr = BN_CTX_get(ctx);
105         else
106                 rr = r;
107         if ((v = BN_CTX_get(ctx)) == NULL) goto err;
108
109         if (BN_copy(v,a) == NULL) goto err;
110         bits=BN_num_bits(p);
111
112         if (BN_is_odd(p))
113                 { if (BN_copy(rr,a) == NULL) goto err; }
114         else    { if (!BN_one(rr)) goto err; }
115
116         for (i=1; i<bits; i++)
117                 {
118                 if (!BN_sqr(v,v,ctx)) goto err;
119                 if (BN_is_bit_set(p,i))
120                         {
121                         if (!BN_mul(rr,rr,v,ctx)) goto err;
122                         }
123                 }
124         ret=1;
125 err:
126         if (r != rr) BN_copy(r,rr);
127         BN_CTX_end(ctx);
128         return(ret);
129         }
130
131
132 #ifdef ATALLA
133
134 /*
135  * This routine will dynamically check for the existance of an Atalla AXL-200
136  * SSL accelerator module.  If one is found, the variable
137  * asi_accelerator_present is set to 1 and the function pointers
138  * ptr_ASI_xxxxxx above will be initialized to corresponding ASI API calls.
139  */
140 typedef int tfnASI_GetPerformanceStatistics(int reset_flag,
141                                             unsigned int *ret_buf);
142 typedef int tfnASI_GetHardwareConfig(long card_num, unsigned int *ret_buf);
143 typedef int tfnASI_RSAPrivateKeyOpFn(RSAPrivateKey * rsaKey,
144                                      unsigned char *output,
145                                      unsigned char *input,
146                                      unsigned int modulus_len);
147
148 static tfnASI_GetHardwareConfig *ptr_ASI_GetHardwareConfig;
149 static tfnASI_RSAPrivateKeyOpFn *ptr_ASI_RSAPrivateKeyOpFn;
150 static tfnASI_GetPerformanceStatistics *ptr_ASI_GetPerformanceStatistics;
151 static int asi_accelerator_present;
152 static int tried_atalla;
153
154 void atalla_initialize_accelerator_handle(void)
155         {
156         void *dl_handle;
157         int status;
158         unsigned int config_buf[1024]; 
159         static int tested;
160
161         if(tested)
162                 return;
163
164         tested=1;
165
166         bzero((void *)config_buf, 1024);
167
168         /*
169          * Check to see if the library is present on the system
170          */
171         dl_handle = dlopen("atasi.so", RTLD_NOW);
172         if (dl_handle == (void *) NULL)
173                 {
174 /*              printf("atasi.so library is not present on the system\n");
175                 printf("No HW acceleration available\n");*/
176                 return;
177                 }
178
179         /*
180          * The library is present.  Now we'll check to insure that the
181          * LDM is up and running. First we'll get the address of the
182          * function in the atasi library that we need to see if the
183          * LDM is operating.
184          */
185
186         ptr_ASI_GetHardwareConfig =
187           (tfnASI_GetHardwareConfig *)dlsym(dl_handle,"ASI_GetHardwareConfig");
188
189         if (ptr_ASI_GetHardwareConfig)
190                 {
191                 /*
192                  * We found the call, now we'll get our config
193                  * status.  If we get a non 0 result, the LDM is not
194                  * running and we cannot use the Atalla ASI *
195                  * library.
196                  */
197                 status = (*ptr_ASI_GetHardwareConfig)(0L, config_buf);
198                 if (status != 0)
199                         {
200                         printf("atasi.so library is present but not initialized\n");
201                         printf("No HW acceleration available\n");
202                         return;
203                         }    
204                 }
205         else
206                 {
207 /*              printf("We found the library, but not the function. Very Strange!\n");*/
208                 return ;
209                 }
210
211         /* 
212          * It looks like we have acceleration capabilities.  Load up the
213          * pointers to our ASI API calls.
214          */
215         ptr_ASI_RSAPrivateKeyOpFn=
216           (tfnASI_RSAPrivateKeyOpFn *)dlsym(dl_handle, "ASI_RSAPrivateKeyOpFn");
217         if (ptr_ASI_RSAPrivateKeyOpFn == NULL)
218                 {
219 /*              printf("We found the library, but no RSA function. Very Strange!\n");*/
220                 return;
221                 }
222
223         ptr_ASI_GetPerformanceStatistics =
224           (tfnASI_GetPerformanceStatistics *)dlsym(dl_handle, "ASI_GetPerformanceStatistics");
225         if (ptr_ASI_GetPerformanceStatistics == NULL)
226                 {
227 /*              printf("We found the library, but no stat function. Very Strange!\n");*/
228                 return;
229               }
230
231         /*
232          * Indicate that acceleration is available
233          */
234         asi_accelerator_present = 1;
235
236 /*      printf("This system has acceleration!\n");*/
237
238         return;
239         }
240
241 /* make sure this only gets called once when bn_mod_exp calls bn_mod_exp_mont */
242 int BN_mod_exp_atalla(BIGNUM *r, BIGNUM *a, const BIGNUM *p, const BIGNUM *m)
243         {
244         unsigned char *abin;
245         unsigned char *pbin;
246         unsigned char *mbin;
247         unsigned char *rbin;
248         int an,pn,mn,ret;
249         RSAPrivateKey keydata;
250
251         atalla_initialize_accelerator_handle();
252         if(!asi_accelerator_present)
253                 return 0;
254
255
256 /* We should be able to run without size testing */
257 # define ASIZE  128
258         an=BN_num_bytes(a);
259         pn=BN_num_bytes(p);
260         mn=BN_num_bytes(m);
261
262         if(an <= ASIZE && pn <= ASIZE && mn <= ASIZE)
263             {
264             int size=mn;
265
266             assert(an <= mn);
267             abin=alloca(size);
268             memset(abin,'\0',mn);
269             BN_bn2bin(a,abin+size-an);
270
271             pbin=alloca(pn);
272             BN_bn2bin(p,pbin);
273
274             mbin=alloca(size);
275             memset(mbin,'\0',mn);
276             BN_bn2bin(m,mbin+size-mn);
277
278             rbin=alloca(size);
279
280             memset(&keydata,'\0',sizeof keydata);
281             keydata.privateExponent.data=pbin;
282             keydata.privateExponent.len=pn;
283             keydata.modulus.data=mbin;
284             keydata.modulus.len=size;
285
286             ret=(*ptr_ASI_RSAPrivateKeyOpFn)(&keydata,rbin,abin,keydata.modulus.len);
287 /*fprintf(stderr,"!%s\n",BN_bn2hex(a));*/
288             if(!ret)
289                 {
290                 BN_bin2bn(rbin,keydata.modulus.len,r);
291 /*fprintf(stderr,"?%s\n",BN_bn2hex(r));*/
292                 return 1;
293                 }
294             }
295         return 0;
296         }
297 #endif /* def ATALLA */
298
299
300 int BN_mod_exp(BIGNUM *r, BIGNUM *a, const BIGNUM *p, const BIGNUM *m,
301                BN_CTX *ctx)
302         {
303         int ret;
304
305         bn_check_top(a);
306         bn_check_top(p);
307         bn_check_top(m);
308
309 #ifdef ATALLA
310         if(BN_mod_exp_atalla(r,a,p,m))
311             return 1;
312 /* If it fails, try the other methods (but don't try atalla again) */
313         tried_atalla=1;
314 #endif
315
316 #ifdef MONT_MUL_MOD
317         /* I have finally been able to take out this pre-condition of
318          * the top bit being set.  It was caused by an error in BN_div
319          * with negatives.  There was also another problem when for a^b%m
320          * a >= m.  eay 07-May-97 */
321 /*      if ((m->d[m->top-1]&BN_TBIT) && BN_is_odd(m)) */
322
323         if (BN_is_odd(m))
324                 {
325                 if (a->top == 1)
326                         {
327                         BN_ULONG A = a->d[0];
328                         ret=BN_mod_exp_mont_word(r,A,p,m,ctx,NULL);
329                         }
330                 else
331                         ret=BN_mod_exp_mont(r,a,p,m,ctx,NULL);
332                 }
333         else
334 #endif
335 #ifdef RECP_MUL_MOD
336                 { ret=BN_mod_exp_recp(r,a,p,m,ctx); }
337 #else
338                 { ret=BN_mod_exp_simple(r,a,p,m,ctx); }
339 #endif
340
341 #ifdef ATALLA
342         tried_atalla=0;
343 #endif
344
345         return(ret);
346         }
347
348
349 int BN_mod_exp_recp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p,
350                     const BIGNUM *m, BN_CTX *ctx)
351         {
352         int i,j,bits,ret=0,wstart,wend,window,wvalue;
353         int start=1,ts=0;
354         BIGNUM *aa;
355         BIGNUM val[TABLE_SIZE];
356         BN_RECP_CTX recp;
357
358         bits=BN_num_bits(p);
359
360         if (bits == 0)
361                 {
362                 BN_one(r);
363                 return(1);
364                 }
365
366         BN_CTX_start(ctx);
367         if ((aa = BN_CTX_get(ctx)) == NULL) goto err;
368
369         BN_RECP_CTX_init(&recp);
370         if (BN_RECP_CTX_set(&recp,m,ctx) <= 0) goto err;
371
372         BN_init(&(val[0]));
373         ts=1;
374
375         if (!BN_mod(&(val[0]),a,m,ctx)) goto err;               /* 1 */
376         if (!BN_mod_mul_reciprocal(aa,&(val[0]),&(val[0]),&recp,ctx))
377                 goto err;                               /* 2 */
378
379         if (bits <= 17) /* This is probably 3 or 0x10001, so just do singles */
380                 window=1;
381         else if (bits >= 256)
382                 window=5;       /* max size of window */
383         else if (bits >= 128)
384                 window=4;
385         else
386                 window=3;
387
388         j=1<<(window-1);
389         for (i=1; i<j; i++)
390                 {
391                 BN_init(&val[i]);
392                 if (!BN_mod_mul_reciprocal(&(val[i]),&(val[i-1]),aa,&recp,ctx))
393                         goto err;
394                 }
395         ts=i;
396
397         start=1;        /* This is used to avoid multiplication etc
398                          * when there is only the value '1' in the
399                          * buffer. */
400         wvalue=0;       /* The 'value' of the window */
401         wstart=bits-1;  /* The top bit of the window */
402         wend=0;         /* The bottom bit of the window */
403
404         if (!BN_one(r)) goto err;
405
406         for (;;)
407                 {
408                 if (BN_is_bit_set(p,wstart) == 0)
409                         {
410                         if (!start)
411                                 if (!BN_mod_mul_reciprocal(r,r,r,&recp,ctx))
412                                 goto err;
413                         if (wstart == 0) break;
414                         wstart--;
415                         continue;
416                         }
417                 /* We now have wstart on a 'set' bit, we now need to work out
418                  * how bit a window to do.  To do this we need to scan
419                  * forward until the last set bit before the end of the
420                  * window */
421                 j=wstart;
422                 wvalue=1;
423                 wend=0;
424                 for (i=1; i<window; i++)
425                         {
426                         if (wstart-i < 0) break;
427                         if (BN_is_bit_set(p,wstart-i))
428                                 {
429                                 wvalue<<=(i-wend);
430                                 wvalue|=1;
431                                 wend=i;
432                                 }
433                         }
434
435                 /* wend is the size of the current window */
436                 j=wend+1;
437                 /* add the 'bytes above' */
438                 if (!start)
439                         for (i=0; i<j; i++)
440                                 {
441                                 if (!BN_mod_mul_reciprocal(r,r,r,&recp,ctx))
442                                         goto err;
443                                 }
444                 
445                 /* wvalue will be an odd number < 2^window */
446                 if (!BN_mod_mul_reciprocal(r,r,&(val[wvalue>>1]),&recp,ctx))
447                         goto err;
448
449                 /* move the 'window' down further */
450                 wstart-=wend+1;
451                 wvalue=0;
452                 start=0;
453                 if (wstart < 0) break;
454                 }
455         ret=1;
456 err:
457         BN_CTX_end(ctx);
458         for (i=0; i<ts; i++)
459                 BN_clear_free(&(val[i]));
460         BN_RECP_CTX_free(&recp);
461         return(ret);
462         }
463
464
465 int BN_mod_exp_mont(BIGNUM *rr, BIGNUM *a, const BIGNUM *p,
466                     const BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *in_mont)
467         {
468         int i,j,bits,ret=0,wstart,wend,window,wvalue;
469         int start=1,ts=0;
470         BIGNUM *d,*r;
471         BIGNUM *aa;
472         BIGNUM val[TABLE_SIZE];
473         BN_MONT_CTX *mont=NULL;
474
475         bn_check_top(a);
476         bn_check_top(p);
477         bn_check_top(m);
478
479 #ifdef ATALLA
480         if(!tried_atalla && BN_mod_exp_atalla(rr,a,p,m))
481             return 1;
482 /* If it fails, try the other methods */
483 #endif
484
485         if (!(m->d[0] & 1))
486                 {
487                 BNerr(BN_F_BN_MOD_EXP_MONT,BN_R_CALLED_WITH_EVEN_MODULUS);
488                 return(0);
489                 }
490         bits=BN_num_bits(p);
491         if (bits == 0)
492                 {
493                 BN_one(rr);
494                 return(1);
495                 }
496         BN_CTX_start(ctx);
497         d = BN_CTX_get(ctx);
498         r = BN_CTX_get(ctx);
499         if (d == NULL || r == NULL) goto err;
500
501         /* If this is not done, things will break in the montgomery
502          * part */
503
504         if (in_mont != NULL)
505                 mont=in_mont;
506         else
507                 {
508                 if ((mont=BN_MONT_CTX_new()) == NULL) goto err;
509                 if (!BN_MONT_CTX_set(mont,m,ctx)) goto err;
510                 }
511
512         BN_init(&val[0]);
513         ts=1;
514         if (BN_ucmp(a,m) >= 0)
515                 {
516                 if (!BN_mod(&(val[0]),a,m,ctx))
517                         goto err;
518                 aa= &(val[0]);
519                 }
520         else
521                 aa=a;
522         if (!BN_to_montgomery(&(val[0]),aa,mont,ctx)) goto err; /* 1 */
523         if (!BN_mod_mul_montgomery(d,&(val[0]),&(val[0]),mont,ctx)) goto err; /* 2 */
524
525         if (bits <= 20) /* This is probably 3 or 0x10001, so just do singles */
526                 window=1;
527         else if (bits >= 256)
528                 window=5;       /* max size of window */
529         else if (bits >= 128)
530                 window=4;
531         else
532                 window=3;
533
534         j=1<<(window-1);
535         for (i=1; i<j; i++)
536                 {
537                 BN_init(&(val[i]));
538                 if (!BN_mod_mul_montgomery(&(val[i]),&(val[i-1]),d,mont,ctx))
539                         goto err;
540                 }
541         ts=i;
542
543         start=1;        /* This is used to avoid multiplication etc
544                          * when there is only the value '1' in the
545                          * buffer. */
546         wvalue=0;       /* The 'value' of the window */
547         wstart=bits-1;  /* The top bit of the window */
548         wend=0;         /* The bottom bit of the window */
549
550         if (!BN_to_montgomery(r,BN_value_one(),mont,ctx)) goto err;
551         for (;;)
552                 {
553                 if (BN_is_bit_set(p,wstart) == 0)
554                         {
555                         if (!start)
556                                 {
557                                 if (!BN_mod_mul_montgomery(r,r,r,mont,ctx))
558                                 goto err;
559                                 }
560                         if (wstart == 0) break;
561                         wstart--;
562                         continue;
563                         }
564                 /* We now have wstart on a 'set' bit, we now need to work out
565                  * how bit a window to do.  To do this we need to scan
566                  * forward until the last set bit before the end of the
567                  * window */
568                 j=wstart;
569                 wvalue=1;
570                 wend=0;
571                 for (i=1; i<window; i++)
572                         {
573                         if (wstart-i < 0) break;
574                         if (BN_is_bit_set(p,wstart-i))
575                                 {
576                                 wvalue<<=(i-wend);
577                                 wvalue|=1;
578                                 wend=i;
579                                 }
580                         }
581
582                 /* wend is the size of the current window */
583                 j=wend+1;
584                 /* add the 'bytes above' */
585                 if (!start)
586                         for (i=0; i<j; i++)
587                                 {
588                                 if (!BN_mod_mul_montgomery(r,r,r,mont,ctx))
589                                         goto err;
590                                 }
591                 
592                 /* wvalue will be an odd number < 2^window */
593                 if (!BN_mod_mul_montgomery(r,r,&(val[wvalue>>1]),mont,ctx))
594                         goto err;
595
596                 /* move the 'window' down further */
597                 wstart-=wend+1;
598                 wvalue=0;
599                 start=0;
600                 if (wstart < 0) break;
601                 }
602         BN_from_montgomery(rr,r,mont,ctx);
603         ret=1;
604 err:
605         if ((in_mont == NULL) && (mont != NULL)) BN_MONT_CTX_free(mont);
606         BN_CTX_end(ctx);
607         for (i=0; i<ts; i++)
608                 BN_clear_free(&(val[i]));
609         return(ret);
610         }
611
612 int BN_mod_exp_mont_word(BIGNUM *rr, BN_ULONG a, const BIGNUM *p,
613                          const BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *in_mont)
614 /* if we had BN_mod_exp_mont_2, we could even use windowing in it */
615         {
616         int b, bits, ret=0;
617         BIGNUM *d, *r, *t;
618         BN_MONT_CTX *mont = NULL;
619
620         bn_check_top(p);
621         bn_check_top(m);
622
623         if (!(m->d[0] & 1))
624                 {
625                 BNerr(BN_F_BN_MOD_EXP_MONT_WORD,BN_R_CALLED_WITH_EVEN_MODULUS);
626                 return(0);
627                 }
628         bits = BN_num_bits(p);
629         if (bits == 0)
630                 {
631                 BN_one(rr);
632                 return(1);
633                 }
634         BN_CTX_start(ctx);
635         d = BN_CTX_get(ctx);
636         r = BN_CTX_get(ctx);
637         t = BN_CTX_get(ctx);
638         if (d == NULL || r == NULL || t == NULL) goto err;
639
640 #ifdef ATALLA
641         if (!tried_atalla)
642                 {
643                 BN_set_word(t, a);
644                 if (BN_mod_exp_word_atalla(rr, t, p, m))
645                         return 1;
646                 }
647 /* If it fails, try the other methods */
648 #endif
649
650         if (in_mont != NULL)
651                 mont=in_mont;
652         else
653                 {
654                 if ((mont = BN_MONT_CTX_new()) == NULL) goto err;
655                 if (!BN_MONT_CTX_set(mont, m, ctx)) goto err;
656                 }
657
658         if (!BN_to_montgomery(r, BN_value_one(), mont, ctx)) goto err;
659         for (b = bits-1; b >= 0; b--)
660                 {
661                 if (BN_is_bit_set(p, b))
662                         {
663                         if (!BN_mul_word(r, a))
664                                 goto err;
665                         if (BN_ucmp(r, m) >= 0)
666                                 {
667                                 if (!BN_mod(t, r, m, ctx))
668                                         goto err;
669                                 { BIGNUM *swap_tmp = r; r = t; t = swap_tmp; }
670                                 }
671                         }
672                 
673                 if (b > 0)
674                         {
675                         if (!BN_mod_mul_montgomery(r, r, r, mont, ctx))
676                                 goto err;
677                         }
678                 }
679         BN_from_montgomery(rr, r, mont, ctx);
680         ret = 1;
681 err:
682         if ((in_mont == NULL) && (mont != NULL)) BN_MONT_CTX_free(mont);
683         BN_CTX_end(ctx);
684         return(ret);
685         }
686
687
688 /* The old fallback, simple version :-) */
689 int BN_mod_exp_simple(BIGNUM *r, BIGNUM *a, BIGNUM *p, BIGNUM *m,
690              BN_CTX *ctx)
691         {
692         int i,j,bits,ret=0,wstart,wend,window,wvalue,ts=0;
693         int start=1;
694         BIGNUM *d;
695         BIGNUM val[TABLE_SIZE];
696
697         bits=BN_num_bits(p);
698
699         if (bits == 0)
700                 {
701                 BN_one(r);
702                 return(1);
703                 }
704
705         BN_CTX_start(ctx);
706         if ((d = BN_CTX_get(ctx)) == NULL) goto err;
707
708         BN_init(&(val[0]));
709         ts=1;
710         if (!BN_mod(&(val[0]),a,m,ctx)) goto err;               /* 1 */
711         if (!BN_mod_mul(d,&(val[0]),&(val[0]),m,ctx))
712                 goto err;                               /* 2 */
713
714         if (bits <= 17) /* This is probably 3 or 0x10001, so just do singles */
715                 window=1;
716         else if (bits >= 256)
717                 window=5;       /* max size of window */
718         else if (bits >= 128)
719                 window=4;
720         else
721                 window=3;
722
723         j=1<<(window-1);
724         for (i=1; i<j; i++)
725                 {
726                 BN_init(&(val[i]));
727                 if (!BN_mod_mul(&(val[i]),&(val[i-1]),d,m,ctx))
728                         goto err;
729                 }
730         ts=i;
731
732         start=1;        /* This is used to avoid multiplication etc
733                          * when there is only the value '1' in the
734                          * buffer. */
735         wvalue=0;       /* The 'value' of the window */
736         wstart=bits-1;  /* The top bit of the window */
737         wend=0;         /* The bottom bit of the window */
738
739         if (!BN_one(r)) goto err;
740
741         for (;;)
742                 {
743                 if (BN_is_bit_set(p,wstart) == 0)
744                         {
745                         if (!start)
746                                 if (!BN_mod_mul(r,r,r,m,ctx))
747                                 goto err;
748                         if (wstart == 0) break;
749                         wstart--;
750                         continue;
751                         }
752                 /* We now have wstart on a 'set' bit, we now need to work out
753                  * how bit a window to do.  To do this we need to scan
754                  * forward until the last set bit before the end of the
755                  * window */
756                 j=wstart;
757                 wvalue=1;
758                 wend=0;
759                 for (i=1; i<window; i++)
760                         {
761                         if (wstart-i < 0) break;
762                         if (BN_is_bit_set(p,wstart-i))
763                                 {
764                                 wvalue<<=(i-wend);
765                                 wvalue|=1;
766                                 wend=i;
767                                 }
768                         }
769
770                 /* wend is the size of the current window */
771                 j=wend+1;
772                 /* add the 'bytes above' */
773                 if (!start)
774                         for (i=0; i<j; i++)
775                                 {
776                                 if (!BN_mod_mul(r,r,r,m,ctx))
777                                         goto err;
778                                 }
779                 
780                 /* wvalue will be an odd number < 2^window */
781                 if (!BN_mod_mul(r,r,&(val[wvalue>>1]),m,ctx))
782                         goto err;
783
784                 /* move the 'window' down further */
785                 wstart-=wend+1;
786                 wvalue=0;
787                 start=0;
788                 if (wstart < 0) break;
789                 }
790         ret=1;
791 err:
792         BN_CTX_end(ctx);
793         for (i=0; i<ts; i++)
794                 BN_clear_free(&(val[i]));
795         return(ret);
796         }
797