bn_exp.c revision 6b7257f756eb0530cdf54df9a7fab8d51a5001c3
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis * All rights reserved.
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis * This package is an SSL implementation written
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis * by Eric Young (eay@cryptsoft.com).
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis * The implementation was written so as to conform with Netscapes SSL.
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis * This library is free for commercial and non-commercial use as long as
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis * the following conditions are aheared to. The following conditions
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis * apply to all code found in this distribution, be it the RC4, RSA,
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis * lhash, DES, etc., code; not just the SSL code. The SSL documentation
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis * included with this distribution is covered by the same copyright terms
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis * except that the holder is Tim Hudson (tjh@cryptsoft.com).
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis * Copyright remains Eric Young's, and as such any Copyright notices in
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis * the code are not to be removed.
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis * If this package is used in a product, Eric Young should be given attribution
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis * as the author of the parts of the library used.
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis * This can be in the form of a textual message at program startup or
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis * in documentation (online or textual) provided with the package.
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis * Redistribution and use in source and binary forms, with or without
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis * modification, are permitted provided that the following conditions
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis * 1. Redistributions of source code must retain the copyright
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis * notice, this list of conditions and the following disclaimer.
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis * 2. Redistributions in binary form must reproduce the above copyright
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis * notice, this list of conditions and the following disclaimer in the
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis * documentation and/or other materials provided with the distribution.
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis * 3. All advertising materials mentioning features or use of this software
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis * must display the following acknowledgement:
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis * "This product includes cryptographic software written by
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis * Eric Young (eay@cryptsoft.com)"
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis * The word 'cryptographic' can be left out if the rouines from the library
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis * being used are not cryptographic related :-).
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis * 4. If you include any Windows specific code (or a derivative thereof) from
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis * the apps directory (application code) you must include an acknowledgement:
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis * SUCH DAMAGE.
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis * The licence and distribution terms for any publically available version or
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis * derivative of this code cannot be changed. i.e. this code cannot simply be
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis * copied and put under another distribution licence
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis * [including the GNU Public Licence.]
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis/* slow but works */
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtisint BN_mod_mul(BIGNUM *ret, BIGNUM *a, BIGNUM *b, const BIGNUM *m, BN_CTX *ctx)
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis if ((t = BN_CTX_get(ctx)) == NULL) goto err;
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis/* this one works - simple but works */
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtisint BN_mod_exp(BIGNUM *r, BIGNUM *a, BIGNUM *p, BIGNUM *m, BN_CTX *ctx)
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis/* this one works - simple but works */
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtisint BN_exp(BIGNUM *r, BIGNUM *a, BIGNUM *p, BN_CTX *ctx)
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis if ((r == a) || (r == p))
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis if ((v = BN_CTX_get(ctx)) == NULL) goto err;
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis * This routine will dynamically check for the existance of an Atalla AXL-200
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis * SSL accelerator module. If one is found, the variable
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis * asi_accelerator_present is set to 1 and the function pointers
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis * ptr_ASI_xxxxxx above will be initialized to corresponding ASI API calls.
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtistypedef int tfnASI_GetPerformanceStatistics(int reset_flag,
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis unsigned int *ret_buf);
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtistypedef int tfnASI_GetHardwareConfig(long card_num, unsigned int *ret_buf);
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtistypedef int tfnASI_RSAPrivateKeyOpFn(RSAPrivateKey * rsaKey,
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis unsigned char *output,
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis unsigned char *input,
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtisstatic tfnASI_GetHardwareConfig *ptr_ASI_GetHardwareConfig;
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtisstatic tfnASI_RSAPrivateKeyOpFn *ptr_ASI_RSAPrivateKeyOpFn;
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtisstatic tfnASI_GetPerformanceStatistics *ptr_ASI_GetPerformanceStatistics;
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtisvoid atalla_initialize_accelerator_handle(void)
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis * Check to see if the library is present on the system
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis/* printf("atasi.so library is not present on the system\n");
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis printf("No HW acceleration available\n");*/
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis * The library is present. Now we'll check to insure that the
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis * LDM is up and running. First we'll get the address of the
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis * function in the atasi library that we need to see if the
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis * LDM is operating.
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis (tfnASI_GetHardwareConfig *)dlsym(dl_handle,"ASI_GetHardwareConfig");
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis * We found the call, now we'll get our config
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis * status. If we get a non 0 result, the LDM is not
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis * running and we cannot use the Atalla ASI *
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis status = (*ptr_ASI_GetHardwareConfig)(0L, config_buf);
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis printf("atasi.so library is present but not initialized\n");
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis/* printf("We found the library, but not the function. Very Strange!\n");*/
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis * It looks like we have acceleration capabilities. Load up the
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis * pointers to our ASI API calls.
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis (tfnASI_RSAPrivateKeyOpFn *)dlsym(dl_handle, "ASI_RSAPrivateKeyOpFn");
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis/* printf("We found the library, but no RSA function. Very Strange!\n");*/
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis (tfnASI_GetPerformanceStatistics *)dlsym(dl_handle, "ASI_GetPerformanceStatistics");
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis if (ptr_ASI_GetPerformanceStatistics == NULL)
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis/* printf("We found the library, but no stat function. Very Strange!\n");*/
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis * Indicate that acceleration is available
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis/* printf("This system has acceleration!\n");*/
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis/* make sure this only gets called once when bn_mod_exp calls bn_mod_exp_mont */
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtisint BN_mod_exp_atalla(BIGNUM *r, BIGNUM *a, const BIGNUM *p, const BIGNUM *m)
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis unsigned char *abin;
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis unsigned char *pbin;
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis unsigned char *mbin;
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis unsigned char *rbin;
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis/* We should be able to run without size testing */
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis if(an <= ASIZE && pn <= ASIZE && mn <= ASIZE)
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis ret=(*ptr_ASI_RSAPrivateKeyOpFn)(&keydata,rbin,abin,keydata.modulus.len);
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis/*fprintf(stderr,"!%s\n",BN_bn2hex(a));*/
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis/*fprintf(stderr,"?%s\n",BN_bn2hex(r));*/
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis#endif /* def ATALLA */
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtisint BN_mod_exp(BIGNUM *r, BIGNUM *a, const BIGNUM *p, const BIGNUM *m,
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis/* If it fails, try the other methods (but don't try atalla again) */
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis /* I have finally been able to take out this pre-condition of
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis * the top bit being set. It was caused by an error in BN_div
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis * with negatives. There was also another problem when for a^b%m
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis * a >= m. eay 07-May-97 */
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis/* if ((m->d[m->top-1]&BN_TBIT) && BN_is_odd(m)) */
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis { ret=BN_mod_exp_mont(r,a,p,m,ctx,NULL); }
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis/* #ifdef RECP_MUL_MOD */
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtisint BN_mod_exp_recp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p,
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis int i,j,bits,ret=0,wstart,wend,window,wvalue;
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis if ((aa = BN_CTX_get(ctx)) == NULL) goto err;
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis if (BN_RECP_CTX_set(&recp,m,ctx) <= 0) goto err;
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis if (!BN_mod(&(val[0]),a,m,ctx)) goto err; /* 1 */
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis if (!BN_mod_mul_reciprocal(aa,&(val[0]),&(val[0]),&recp,ctx))
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis if (bits <= 17) /* This is probably 3 or 0x10001, so just do singles */
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis for (i=1; i<j; i++)
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis if (!BN_mod_mul_reciprocal(&(val[i]),&(val[i-1]),aa,&recp,ctx))
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis start=1; /* This is used to avoid multiplication etc
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis * when there is only the value '1' in the
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis wstart=bits-1; /* The top bit of the window */
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis wend=0; /* The bottom bit of the window */
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis if (!BN_mod_mul_reciprocal(r,r,r,&recp,ctx))
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis if (wstart == 0) break;
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis /* We now have wstart on a 'set' bit, we now need to work out
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis * how bit a window to do. To do this we need to scan
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis * forward until the last set bit before the end of the
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis if (wstart-i < 0) break;
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis /* wend is the size of the current window */
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis /* add the 'bytes above' */
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis for (i=0; i<j; i++)
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis if (!BN_mod_mul_reciprocal(r,r,r,&recp,ctx))
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis /* wvalue will be an odd number < 2^window */
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis if (!BN_mod_mul_reciprocal(r,r,&(val[wvalue>>1]),&recp,ctx))
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis /* move the 'window' down further */
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis if (wstart < 0) break;
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis for (i=0; i<ts; i++)
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis/* #ifdef MONT_MUL_MOD */
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtisint BN_mod_exp_mont(BIGNUM *rr, BIGNUM *a, const BIGNUM *p,
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis const BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *in_mont)
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis int i,j,bits,ret=0,wstart,wend,window,wvalue;
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis if(!tried_atalla && BN_mod_exp_atalla(rr,a,p,m))
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis/* If it fails, try the other methods */
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis if (!(m->d[0] & 1))
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis BNerr(BN_F_BN_MOD_EXP_MONT,BN_R_CALLED_WITH_EVEN_MODULUS);
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis /* If this is not done, things will break in the montgomery
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis if ((mont=BN_MONT_CTX_new()) == NULL) goto err;
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis if (!BN_MONT_CTX_set(mont,m,ctx)) goto err;
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis if (BN_ucmp(a,m) >= 0)
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis if (!BN_to_montgomery(&(val[0]),aa,mont,ctx)) goto err; /* 1 */
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis if (!BN_mod_mul_montgomery(d,&(val[0]),&(val[0]),mont,ctx)) goto err; /* 2 */
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis if (bits <= 20) /* This is probably 3 or 0x10001, so just do singles */
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis for (i=1; i<j; i++)
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis if (!BN_mod_mul_montgomery(&(val[i]),&(val[i-1]),d,mont,ctx))
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis start=1; /* This is used to avoid multiplication etc
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis * when there is only the value '1' in the
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis wstart=bits-1; /* The top bit of the window */
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis wend=0; /* The bottom bit of the window */
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis if (!BN_to_montgomery(r,BN_value_one(),mont,ctx)) goto err;
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis if (!BN_mod_mul_montgomery(r,r,r,mont,ctx))
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis if (wstart == 0) break;
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis /* We now have wstart on a 'set' bit, we now need to work out
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis * how bit a window to do. To do this we need to scan
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis * forward until the last set bit before the end of the
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis if (wstart-i < 0) break;
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis /* wend is the size of the current window */
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis /* add the 'bytes above' */
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis for (i=0; i<j; i++)
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis if (!BN_mod_mul_montgomery(r,r,r,mont,ctx))
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis /* wvalue will be an odd number < 2^window */
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis if (!BN_mod_mul_montgomery(r,r,&(val[wvalue>>1]),mont,ctx))
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis /* move the 'window' down further */
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis if (wstart < 0) break;
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis if ((in_mont == NULL) && (mont != NULL)) BN_MONT_CTX_free(mont);
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis for (i=0; i<ts; i++)
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis/* The old fallback, simple version :-) */
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtisint BN_mod_exp_simple(BIGNUM *r, BIGNUM *a, BIGNUM *p, BIGNUM *m,
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis int i,j,bits,ret=0,wstart,wend,window,wvalue,ts=0;
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis if ((d = BN_CTX_get(ctx)) == NULL) goto err;
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis if (!BN_mod(&(val[0]),a,m,ctx)) goto err; /* 1 */
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis if (!BN_mod_mul(d,&(val[0]),&(val[0]),m,ctx))
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis if (bits <= 17) /* This is probably 3 or 0x10001, so just do singles */
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis for (i=1; i<j; i++)
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis if (!BN_mod_mul(&(val[i]),&(val[i-1]),d,m,ctx))
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis start=1; /* This is used to avoid multiplication etc
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis * when there is only the value '1' in the
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis wstart=bits-1; /* The top bit of the window */
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis wend=0; /* The bottom bit of the window */
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis if (wstart == 0) break;
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis /* We now have wstart on a 'set' bit, we now need to work out
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis * how bit a window to do. To do this we need to scan
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis * forward until the last set bit before the end of the
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis if (wstart-i < 0) break;
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis /* wend is the size of the current window */
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis /* add the 'bytes above' */
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis for (i=0; i<j; i++)
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis /* wvalue will be an odd number < 2^window */
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis if (!BN_mod_mul(r,r,&(val[wvalue>>1]),m,ctx))
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis /* move the 'window' down further */
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis if (wstart < 0) break;
25c28e83beb90e7c80452a7c818c5e6f73a07dc8Piotr Jasiukajtis for (i=0; i<ts; i++)