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