d2c91628acba0ecce6f4898e67417a340e73ad80
[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-2000 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 #include <stdio.h>
114 #include "cryptlib.h"
115 #include "bn_lcl.h"
116
117 #define TABLE_SIZE      32
118
119 /* slow but works */
120 int BN_mod_mul(BIGNUM *ret, BIGNUM *a, BIGNUM *b, const BIGNUM *m, BN_CTX *ctx)
121         {
122         BIGNUM *t;
123         int r=0;
124
125         bn_check_top(a);
126         bn_check_top(b);
127         bn_check_top(m);
128
129         BN_CTX_start(ctx);
130         if ((t = BN_CTX_get(ctx)) == NULL) goto err;
131         if (a == b)
132                 { if (!BN_sqr(t,a,ctx)) goto err; }
133         else
134                 { if (!BN_mul(t,a,b,ctx)) goto err; }
135         if (!BN_mod(ret,t,m,ctx)) goto err;
136         r=1;
137 err:
138         BN_CTX_end(ctx);
139         return(r);
140         }
141
142
143 /* this one works - simple but works */
144 int BN_exp(BIGNUM *r, BIGNUM *a, BIGNUM *p, BN_CTX *ctx)
145         {
146         int i,bits,ret=0;
147         BIGNUM *v,*rr;
148
149         BN_CTX_start(ctx);
150         if ((r == a) || (r == p))
151                 rr = BN_CTX_get(ctx);
152         else
153                 rr = r;
154         if ((v = BN_CTX_get(ctx)) == NULL) goto err;
155
156         if (BN_copy(v,a) == NULL) goto err;
157         bits=BN_num_bits(p);
158
159         if (BN_is_odd(p))
160                 { if (BN_copy(rr,a) == NULL) goto err; }
161         else    { if (!BN_one(rr)) goto err; }
162
163         for (i=1; i<bits; i++)
164                 {
165                 if (!BN_sqr(v,v,ctx)) goto err;
166                 if (BN_is_bit_set(p,i))
167                         {
168                         if (!BN_mul(rr,rr,v,ctx)) goto err;
169                         }
170                 }
171         ret=1;
172 err:
173         if (r != rr) BN_copy(r,rr);
174         BN_CTX_end(ctx);
175         return(ret);
176         }
177
178
179 int BN_mod_exp(BIGNUM *r, BIGNUM *a, const BIGNUM *p, const BIGNUM *m,
180                BN_CTX *ctx)
181         {
182         int ret;
183
184         bn_check_top(a);
185         bn_check_top(p);
186         bn_check_top(m);
187
188 #ifdef MONT_MUL_MOD
189         /* I have finally been able to take out this pre-condition of
190          * the top bit being set.  It was caused by an error in BN_div
191          * with negatives.  There was also another problem when for a^b%m
192          * a >= m.  eay 07-May-97 */
193 /*      if ((m->d[m->top-1]&BN_TBIT) && BN_is_odd(m)) */
194
195         if (BN_is_odd(m))
196                 {
197                 if (a->top == 1)
198                         {
199                         BN_ULONG A = a->d[0];
200                         ret=BN_mod_exp_mont_word(r,A,p,m,ctx,NULL);
201                         }
202                 else
203                         ret=BN_mod_exp_mont(r,a,p,m,ctx,NULL);
204                 }
205         else
206 #endif
207 #ifdef RECP_MUL_MOD
208                 { ret=BN_mod_exp_recp(r,a,p,m,ctx); }
209 #else
210                 { ret=BN_mod_exp_simple(r,a,p,m,ctx); }
211 #endif
212
213         return(ret);
214         }
215
216
217 int BN_mod_exp_recp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p,
218                     const BIGNUM *m, BN_CTX *ctx)
219         {
220         int i,j,bits,ret=0,wstart,wend,window,wvalue;
221         int start=1,ts=0;
222         BIGNUM *aa;
223         BIGNUM val[TABLE_SIZE];
224         BN_RECP_CTX recp;
225
226         bits=BN_num_bits(p);
227
228         if (bits == 0)
229                 {
230                 BN_one(r);
231                 return(1);
232                 }
233
234         BN_CTX_start(ctx);
235         if ((aa = BN_CTX_get(ctx)) == NULL) goto err;
236
237         BN_RECP_CTX_init(&recp);
238         if (BN_RECP_CTX_set(&recp,m,ctx) <= 0) goto err;
239
240         BN_init(&(val[0]));
241         ts=1;
242
243         if (!BN_mod(&(val[0]),a,m,ctx)) goto err;               /* 1 */
244
245         window = BN_window_bits_for_exponent_size(bits);
246         if (window > 1)
247                 {
248                 if (!BN_mod_mul_reciprocal(aa,&(val[0]),&(val[0]),&recp,ctx))
249                         goto err;                               /* 2 */
250                 j=1<<(window-1);
251                 for (i=1; i<j; i++)
252                         {
253                         BN_init(&val[i]);
254                         if (!BN_mod_mul_reciprocal(&(val[i]),&(val[i-1]),aa,&recp,ctx))
255                                 goto err;
256                         }
257                 ts=i;
258                 }
259                 
260         start=1;        /* This is used to avoid multiplication etc
261                          * when there is only the value '1' in the
262                          * buffer. */
263         wvalue=0;       /* The 'value' of the window */
264         wstart=bits-1;  /* The top bit of the window */
265         wend=0;         /* The bottom bit of the window */
266
267         if (!BN_one(r)) goto err;
268
269         for (;;)
270                 {
271                 if (BN_is_bit_set(p,wstart) == 0)
272                         {
273                         if (!start)
274                                 if (!BN_mod_mul_reciprocal(r,r,r,&recp,ctx))
275                                 goto err;
276                         if (wstart == 0) break;
277                         wstart--;
278                         continue;
279                         }
280                 /* We now have wstart on a 'set' bit, we now need to work out
281                  * how bit a window to do.  To do this we need to scan
282                  * forward until the last set bit before the end of the
283                  * window */
284                 j=wstart;
285                 wvalue=1;
286                 wend=0;
287                 for (i=1; i<window; i++)
288                         {
289                         if (wstart-i < 0) break;
290                         if (BN_is_bit_set(p,wstart-i))
291                                 {
292                                 wvalue<<=(i-wend);
293                                 wvalue|=1;
294                                 wend=i;
295                                 }
296                         }
297
298                 /* wend is the size of the current window */
299                 j=wend+1;
300                 /* add the 'bytes above' */
301                 if (!start)
302                         for (i=0; i<j; i++)
303                                 {
304                                 if (!BN_mod_mul_reciprocal(r,r,r,&recp,ctx))
305                                         goto err;
306                                 }
307                 
308                 /* wvalue will be an odd number < 2^window */
309                 if (!BN_mod_mul_reciprocal(r,r,&(val[wvalue>>1]),&recp,ctx))
310                         goto err;
311
312                 /* move the 'window' down further */
313                 wstart-=wend+1;
314                 wvalue=0;
315                 start=0;
316                 if (wstart < 0) break;
317                 }
318         ret=1;
319 err:
320         BN_CTX_end(ctx);
321         for (i=0; i<ts; i++)
322                 BN_clear_free(&(val[i]));
323         BN_RECP_CTX_free(&recp);
324         return(ret);
325         }
326
327
328 int BN_mod_exp_mont(BIGNUM *rr, BIGNUM *a, const BIGNUM *p,
329                     const BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *in_mont)
330         {
331         int i,j,bits,ret=0,wstart,wend,window,wvalue;
332         int start=1,ts=0;
333         BIGNUM *d,*r;
334         BIGNUM *aa;
335         BIGNUM val[TABLE_SIZE];
336         BN_MONT_CTX *mont=NULL;
337
338         bn_check_top(a);
339         bn_check_top(p);
340         bn_check_top(m);
341
342         if (!(m->d[0] & 1))
343                 {
344                 BNerr(BN_F_BN_MOD_EXP_MONT,BN_R_CALLED_WITH_EVEN_MODULUS);
345                 return(0);
346                 }
347         bits=BN_num_bits(p);
348         if (bits == 0)
349                 {
350                 BN_one(rr);
351                 return(1);
352                 }
353         BN_CTX_start(ctx);
354         d = BN_CTX_get(ctx);
355         r = BN_CTX_get(ctx);
356         if (d == NULL || r == NULL) goto err;
357
358         /* If this is not done, things will break in the montgomery
359          * part */
360
361         if (in_mont != NULL)
362                 mont=in_mont;
363         else
364                 {
365                 if ((mont=BN_MONT_CTX_new()) == NULL) goto err;
366                 if (!BN_MONT_CTX_set(mont,m,ctx)) goto err;
367                 }
368
369         BN_init(&val[0]);
370         ts=1;
371         if (BN_ucmp(a,m) >= 0)
372                 {
373                 if (!BN_mod(&(val[0]),a,m,ctx))
374                         goto err;
375                 aa= &(val[0]);
376                 }
377         else
378                 aa=a;
379         if (!BN_to_montgomery(&(val[0]),aa,mont,ctx)) goto err; /* 1 */
380
381         window = BN_window_bits_for_exponent_size(bits);
382         if (window > 1)
383                 {
384                 if (!BN_mod_mul_montgomery(d,&(val[0]),&(val[0]),mont,ctx)) goto err; /* 2 */
385                 j=1<<(window-1);
386                 for (i=1; i<j; i++)
387                         {
388                         BN_init(&(val[i]));
389                         if (!BN_mod_mul_montgomery(&(val[i]),&(val[i-1]),d,mont,ctx))
390                                 goto err;
391                         }
392                 ts=i;
393                 }
394
395         start=1;        /* This is used to avoid multiplication etc
396                          * when there is only the value '1' in the
397                          * buffer. */
398         wvalue=0;       /* The 'value' of the window */
399         wstart=bits-1;  /* The top bit of the window */
400         wend=0;         /* The bottom bit of the window */
401
402         if (!BN_to_montgomery(r,BN_value_one(),mont,ctx)) goto err;
403         for (;;)
404                 {
405                 if (BN_is_bit_set(p,wstart) == 0)
406                         {
407                         if (!start)
408                                 {
409                                 if (!BN_mod_mul_montgomery(r,r,r,mont,ctx))
410                                 goto err;
411                                 }
412                         if (wstart == 0) break;
413                         wstart--;
414                         continue;
415                         }
416                 /* We now have wstart on a 'set' bit, we now need to work out
417                  * how bit a window to do.  To do this we need to scan
418                  * forward until the last set bit before the end of the
419                  * window */
420                 j=wstart;
421                 wvalue=1;
422                 wend=0;
423                 for (i=1; i<window; i++)
424                         {
425                         if (wstart-i < 0) break;
426                         if (BN_is_bit_set(p,wstart-i))
427                                 {
428                                 wvalue<<=(i-wend);
429                                 wvalue|=1;
430                                 wend=i;
431                                 }
432                         }
433
434                 /* wend is the size of the current window */
435                 j=wend+1;
436                 /* add the 'bytes above' */
437                 if (!start)
438                         for (i=0; i<j; i++)
439                                 {
440                                 if (!BN_mod_mul_montgomery(r,r,r,mont,ctx))
441                                         goto err;
442                                 }
443                 
444                 /* wvalue will be an odd number < 2^window */
445                 if (!BN_mod_mul_montgomery(r,r,&(val[wvalue>>1]),mont,ctx))
446                         goto err;
447
448                 /* move the 'window' down further */
449                 wstart-=wend+1;
450                 wvalue=0;
451                 start=0;
452                 if (wstart < 0) break;
453                 }
454         if (!BN_from_montgomery(rr,r,mont,ctx)) goto err;
455         ret=1;
456 err:
457         if ((in_mont == NULL) && (mont != NULL)) BN_MONT_CTX_free(mont);
458         BN_CTX_end(ctx);
459         for (i=0; i<ts; i++)
460                 BN_clear_free(&(val[i]));
461         return(ret);
462         }
463
464 int BN_mod_exp_mont_word(BIGNUM *rr, BN_ULONG a, const BIGNUM *p,
465                          const BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *in_mont)
466         {
467         BN_MONT_CTX *mont = NULL;
468         int b, bits, ret=0;
469         int r_is_one;
470         BN_ULONG w, next_w;
471         BIGNUM *d, *r, *t;
472         BIGNUM *swap_tmp;
473 #define BN_MOD_MUL_WORD(r, w, m) \
474                 (BN_mul_word(r, (w)) && \
475                 (/* BN_ucmp(r, (m)) < 0 ? 1 :*/  \
476                         (BN_mod(t, r, m, ctx) && (swap_tmp = r, r = t, t = swap_tmp, 1))))
477                 /* BN_MOD_MUL_WORD is only used with 'w' large,
478                   * so the BN_ucmp test is probably more overhead
479                   * than always using BN_mod (which uses BN_copy if
480                   * a similar test returns true). */
481 #define BN_TO_MONTGOMERY_WORD(r, w, mont) \
482                 (BN_set_word(r, (w)) && BN_to_montgomery(r, r, (mont), ctx))
483
484         bn_check_top(p);
485         bn_check_top(m);
486
487         if (!(m->d[0] & 1))
488                 {
489                 BNerr(BN_F_BN_MOD_EXP_MONT_WORD,BN_R_CALLED_WITH_EVEN_MODULUS);
490                 return(0);
491                 }
492         bits = BN_num_bits(p);
493         if (bits == 0)
494                 {
495                 BN_one(rr);
496                 return(1);
497                 }
498         BN_CTX_start(ctx);
499         d = BN_CTX_get(ctx);
500         r = BN_CTX_get(ctx);
501         t = BN_CTX_get(ctx);
502         if (d == NULL || r == NULL || t == NULL) goto err;
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         r_is_one = 1; /* except for Montgomery factor */
513
514         /* bits-1 >= 0 */
515
516         /* The result is accumulated in the product r*w. */
517         w = a; /* bit 'bits-1' of 'p' is always set */
518         for (b = bits-2; b >= 0; b--)
519                 {
520                 /* First, square r*w. */
521                 next_w = w*w;
522                 if ((next_w/w) != w) /* overflow */
523                         {
524                         if (r_is_one)
525                                 {
526                                 if (!BN_TO_MONTGOMERY_WORD(r, w, mont)) goto err;
527                                 r_is_one = 0;
528                                 }
529                         else
530                                 {
531                                 if (!BN_MOD_MUL_WORD(r, w, m)) goto err;
532                                 }
533                         next_w = 1;
534                         }
535                 w = next_w;
536                 if (!r_is_one)
537                         {
538                         if (!BN_mod_mul_montgomery(r, r, r, mont, ctx)) goto err;
539                         }
540
541                 /* Second, multiply r*w by 'a' if exponent bit is set. */
542                 if (BN_is_bit_set(p, b))
543                         {
544                         next_w = w*a;
545                         if ((next_w/a) != w) /* overflow */
546                                 {
547                                 if (r_is_one)
548                                         {
549                                         if (!BN_TO_MONTGOMERY_WORD(r, w, mont)) goto err;
550                                         r_is_one = 0;
551                                         }
552                                 else
553                                         {
554                                         if (!BN_MOD_MUL_WORD(r, w, m)) goto err;
555                                         }
556                                 next_w = a;
557                                 }
558                         w = next_w;
559                         }
560                 }
561
562         /* Finally, set r:=r*w. */
563         if (w != 1)
564                 {
565                 if (r_is_one)
566                         {
567                         if (!BN_TO_MONTGOMERY_WORD(r, w, mont)) goto err;
568                         r_is_one = 0;
569                         }
570                 else
571                         {
572                         if (!BN_MOD_MUL_WORD(r, w, m)) goto err;
573                         }
574                 }
575
576         if (r_is_one) /* can happen only if a == 1*/
577                 {
578                 if (!BN_one(rr)) goto err;
579                 }
580         else
581                 {
582                 if (!BN_from_montgomery(rr, r, mont, ctx)) goto err;
583                 }
584         ret = 1;
585 err:
586         if ((in_mont == NULL) && (mont != NULL)) BN_MONT_CTX_free(mont);
587         BN_CTX_end(ctx);
588         return(ret);
589         }
590
591
592 /* The old fallback, simple version :-) */
593 int BN_mod_exp_simple(BIGNUM *r, BIGNUM *a, BIGNUM *p, BIGNUM *m,
594              BN_CTX *ctx)
595         {
596         int i,j,bits,ret=0,wstart,wend,window,wvalue,ts=0;
597         int start=1;
598         BIGNUM *d;
599         BIGNUM val[TABLE_SIZE];
600
601         bits=BN_num_bits(p);
602
603         if (bits == 0)
604                 {
605                 BN_one(r);
606                 return(1);
607                 }
608
609         BN_CTX_start(ctx);
610         if ((d = BN_CTX_get(ctx)) == NULL) goto err;
611
612         BN_init(&(val[0]));
613         ts=1;
614         if (!BN_mod(&(val[0]),a,m,ctx)) goto err;               /* 1 */
615
616         window = BN_window_bits_for_exponent_size(bits);
617         if (window > 1)
618                 {
619                 if (!BN_mod_mul(d,&(val[0]),&(val[0]),m,ctx))
620                         goto err;                               /* 2 */
621                 j=1<<(window-1);
622                 for (i=1; i<j; i++)
623                         {
624                         BN_init(&(val[i]));
625                         if (!BN_mod_mul(&(val[i]),&(val[i-1]),d,m,ctx))
626                                 goto err;
627                         }
628                 ts=i;
629                 }
630
631         start=1;        /* This is used to avoid multiplication etc
632                          * when there is only the value '1' in the
633                          * buffer. */
634         wvalue=0;       /* The 'value' of the window */
635         wstart=bits-1;  /* The top bit of the window */
636         wend=0;         /* The bottom bit of the window */
637
638         if (!BN_one(r)) goto err;
639
640         for (;;)
641                 {
642                 if (BN_is_bit_set(p,wstart) == 0)
643                         {
644                         if (!start)
645                                 if (!BN_mod_mul(r,r,r,m,ctx))
646                                 goto err;
647                         if (wstart == 0) break;
648                         wstart--;
649                         continue;
650                         }
651                 /* We now have wstart on a 'set' bit, we now need to work out
652                  * how bit a window to do.  To do this we need to scan
653                  * forward until the last set bit before the end of the
654                  * window */
655                 j=wstart;
656                 wvalue=1;
657                 wend=0;
658                 for (i=1; i<window; i++)
659                         {
660                         if (wstart-i < 0) break;
661                         if (BN_is_bit_set(p,wstart-i))
662                                 {
663                                 wvalue<<=(i-wend);
664                                 wvalue|=1;
665                                 wend=i;
666                                 }
667                         }
668
669                 /* wend is the size of the current window */
670                 j=wend+1;
671                 /* add the 'bytes above' */
672                 if (!start)
673                         for (i=0; i<j; i++)
674                                 {
675                                 if (!BN_mod_mul(r,r,r,m,ctx))
676                                         goto err;
677                                 }
678                 
679                 /* wvalue will be an odd number < 2^window */
680                 if (!BN_mod_mul(r,r,&(val[wvalue>>1]),m,ctx))
681                         goto err;
682
683                 /* move the 'window' down further */
684                 wstart-=wend+1;
685                 wvalue=0;
686                 start=0;
687                 if (wstart < 0) break;
688                 }
689         ret=1;
690 err:
691         BN_CTX_end(ctx);
692         for (i=0; i<ts; i++)
693                 BN_clear_free(&(val[i]));
694         return(ret);
695         }
696