From 5fc5d37330d3535a0f421632694d1e7918fc22d7 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Parm=C3=A9nides=20GV?= Date: Tue, 8 Apr 2014 11:38:09 +0200 Subject: Compiles correctly: app/build-native + gradle. --- app/openssl/crypto/bn/bn_exp.c | 991 +++++++++++++++++++++++++++++++++++++++++ 1 file changed, 991 insertions(+) create mode 100644 app/openssl/crypto/bn/bn_exp.c (limited to 'app/openssl/crypto/bn/bn_exp.c') diff --git a/app/openssl/crypto/bn/bn_exp.c b/app/openssl/crypto/bn/bn_exp.c new file mode 100644 index 00000000..d9b6c737 --- /dev/null +++ b/app/openssl/crypto/bn/bn_exp.c @@ -0,0 +1,991 @@ +/* crypto/bn/bn_exp.c */ +/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) + * All rights reserved. + * + * This package is an SSL implementation written + * by Eric Young (eay@cryptsoft.com). + * The implementation was written so as to conform with Netscapes SSL. + * + * This library is free for commercial and non-commercial use as long as + * the following conditions are aheared to. The following conditions + * apply to all code found in this distribution, be it the RC4, RSA, + * lhash, DES, etc., code; not just the SSL code. The SSL documentation + * included with this distribution is covered by the same copyright terms + * except that the holder is Tim Hudson (tjh@cryptsoft.com). + * + * Copyright remains Eric Young's, and as such any Copyright notices in + * the code are not to be removed. + * If this package is used in a product, Eric Young should be given attribution + * as the author of the parts of the library used. + * This can be in the form of a textual message at program startup or + * in documentation (online or textual) provided with the package. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * 3. All advertising materials mentioning features or use of this software + * must display the following acknowledgement: + * "This product includes cryptographic software written by + * Eric Young (eay@cryptsoft.com)" + * The word 'cryptographic' can be left out if the rouines from the library + * being used are not cryptographic related :-). + * 4. If you include any Windows specific code (or a derivative thereof) from + * the apps directory (application code) you must include an acknowledgement: + * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)" + * + * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + * + * The licence and distribution terms for any publically available version or + * derivative of this code cannot be changed. i.e. this code cannot simply be + * copied and put under another distribution licence + * [including the GNU Public Licence.] + */ +/* ==================================================================== + * Copyright (c) 1998-2005 The OpenSSL Project. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in + * the documentation and/or other materials provided with the + * distribution. + * + * 3. All advertising materials mentioning features or use of this + * software must display the following acknowledgment: + * "This product includes software developed by the OpenSSL Project + * for use in the OpenSSL Toolkit. (http://www.openssl.org/)" + * + * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to + * endorse or promote products derived from this software without + * prior written permission. For written permission, please contact + * openssl-core@openssl.org. + * + * 5. Products derived from this software may not be called "OpenSSL" + * nor may "OpenSSL" appear in their names without prior written + * permission of the OpenSSL Project. + * + * 6. Redistributions of any form whatsoever must retain the following + * acknowledgment: + * "This product includes software developed by the OpenSSL Project + * for use in the OpenSSL Toolkit (http://www.openssl.org/)" + * + * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY + * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR + * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED + * OF THE POSSIBILITY OF SUCH DAMAGE. + * ==================================================================== + * + * This product includes cryptographic software written by Eric Young + * (eay@cryptsoft.com). This product includes software written by Tim + * Hudson (tjh@cryptsoft.com). + * + */ + + +#include "cryptlib.h" +#include "bn_lcl.h" + +/* maximum precomputation table size for *variable* sliding windows */ +#define TABLE_SIZE 32 + +/* this one works - simple but works */ +int BN_exp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx) + { + int i,bits,ret=0; + BIGNUM *v,*rr; + + if (BN_get_flags(p, BN_FLG_CONSTTIME) != 0) + { + /* BN_FLG_CONSTTIME only supported by BN_mod_exp_mont() */ + BNerr(BN_F_BN_EXP,ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); + return -1; + } + + BN_CTX_start(ctx); + if ((r == a) || (r == p)) + rr = BN_CTX_get(ctx); + else + rr = r; + v = BN_CTX_get(ctx); + if (rr == NULL || v == NULL) goto err; + + if (BN_copy(v,a) == NULL) goto err; + bits=BN_num_bits(p); + + if (BN_is_odd(p)) + { if (BN_copy(rr,a) == NULL) goto err; } + else { if (!BN_one(rr)) goto err; } + + for (i=1; i= m. eay 07-May-97 */ +/* if ((m->d[m->top-1]&BN_TBIT) && BN_is_odd(m)) */ + + if (BN_is_odd(m)) + { +# ifdef MONT_EXP_WORD + if (a->top == 1 && !a->neg && (BN_get_flags(p, BN_FLG_CONSTTIME) == 0)) + { + BN_ULONG A = a->d[0]; + ret=BN_mod_exp_mont_word(r,A,p,m,ctx,NULL); + } + else +# endif + ret=BN_mod_exp_mont(r,a,p,m,ctx,NULL); + } + else +#endif +#ifdef RECP_MUL_MOD + { ret=BN_mod_exp_recp(r,a,p,m,ctx); } +#else + { ret=BN_mod_exp_simple(r,a,p,m,ctx); } +#endif + + bn_check_top(r); + return(ret); + } + + +int BN_mod_exp_recp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, + const BIGNUM *m, BN_CTX *ctx) + { + int i,j,bits,ret=0,wstart,wend,window,wvalue; + int start=1; + BIGNUM *aa; + /* Table of variables obtained from 'ctx' */ + BIGNUM *val[TABLE_SIZE]; + BN_RECP_CTX recp; + + if (BN_get_flags(p, BN_FLG_CONSTTIME) != 0) + { + /* BN_FLG_CONSTTIME only supported by BN_mod_exp_mont() */ + BNerr(BN_F_BN_MOD_EXP_RECP,ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); + return -1; + } + + bits=BN_num_bits(p); + + if (bits == 0) + { + ret = BN_one(r); + return ret; + } + + BN_CTX_start(ctx); + aa = BN_CTX_get(ctx); + val[0] = BN_CTX_get(ctx); + if(!aa || !val[0]) goto err; + + BN_RECP_CTX_init(&recp); + if (m->neg) + { + /* ignore sign of 'm' */ + if (!BN_copy(aa, m)) goto err; + aa->neg = 0; + if (BN_RECP_CTX_set(&recp,aa,ctx) <= 0) goto err; + } + else + { + if (BN_RECP_CTX_set(&recp,m,ctx) <= 0) goto err; + } + + if (!BN_nnmod(val[0],a,m,ctx)) goto err; /* 1 */ + if (BN_is_zero(val[0])) + { + BN_zero(r); + ret = 1; + goto err; + } + + window = BN_window_bits_for_exponent_size(bits); + if (window > 1) + { + if (!BN_mod_mul_reciprocal(aa,val[0],val[0],&recp,ctx)) + goto err; /* 2 */ + j=1<<(window-1); + for (i=1; i>1],&recp,ctx)) + goto err; + + /* move the 'window' down further */ + wstart-=wend+1; + wvalue=0; + start=0; + if (wstart < 0) break; + } + ret=1; +err: + BN_CTX_end(ctx); + BN_RECP_CTX_free(&recp); + bn_check_top(r); + return(ret); + } + + +int BN_mod_exp_mont(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p, + const BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *in_mont) + { + int i,j,bits,ret=0,wstart,wend,window,wvalue; + int start=1; + BIGNUM *d,*r; + const BIGNUM *aa; + /* Table of variables obtained from 'ctx' */ + BIGNUM *val[TABLE_SIZE]; + BN_MONT_CTX *mont=NULL; + + if (BN_get_flags(p, BN_FLG_CONSTTIME) != 0) + { + return BN_mod_exp_mont_consttime(rr, a, p, m, ctx, in_mont); + } + + bn_check_top(a); + bn_check_top(p); + bn_check_top(m); + + if (!BN_is_odd(m)) + { + BNerr(BN_F_BN_MOD_EXP_MONT,BN_R_CALLED_WITH_EVEN_MODULUS); + return(0); + } + bits=BN_num_bits(p); + if (bits == 0) + { + ret = BN_one(rr); + return ret; + } + + BN_CTX_start(ctx); + d = BN_CTX_get(ctx); + r = BN_CTX_get(ctx); + val[0] = BN_CTX_get(ctx); + if (!d || !r || !val[0]) goto err; + + /* If this is not done, things will break in the montgomery + * part */ + + if (in_mont != NULL) + mont=in_mont; + else + { + if ((mont=BN_MONT_CTX_new()) == NULL) goto err; + if (!BN_MONT_CTX_set(mont,m,ctx)) goto err; + } + + if (a->neg || BN_ucmp(a,m) >= 0) + { + if (!BN_nnmod(val[0],a,m,ctx)) + goto err; + aa= val[0]; + } + else + aa=a; + if (BN_is_zero(aa)) + { + BN_zero(rr); + ret = 1; + goto err; + } + if (!BN_to_montgomery(val[0],aa,mont,ctx)) goto err; /* 1 */ + + window = BN_window_bits_for_exponent_size(bits); + if (window > 1) + { + if (!BN_mod_mul_montgomery(d,val[0],val[0],mont,ctx)) goto err; /* 2 */ + j=1<<(window-1); + for (i=1; i>1],mont,ctx)) + goto err; + + /* move the 'window' down further */ + wstart-=wend+1; + wvalue=0; + start=0; + if (wstart < 0) break; + } + if (!BN_from_montgomery(rr,r,mont,ctx)) goto err; + ret=1; +err: + if ((in_mont == NULL) && (mont != NULL)) BN_MONT_CTX_free(mont); + BN_CTX_end(ctx); + bn_check_top(rr); + return(ret); + } + + +/* BN_mod_exp_mont_consttime() stores the precomputed powers in a specific layout + * so that accessing any of these table values shows the same access pattern as far + * as cache lines are concerned. The following functions are used to transfer a BIGNUM + * from/to that table. */ + +static int MOD_EXP_CTIME_COPY_TO_PREBUF(BIGNUM *b, int top, unsigned char *buf, int idx, int width) + { + size_t i, j; + + if (bn_wexpand(b, top) == NULL) + return 0; + while (b->top < top) + { + b->d[b->top++] = 0; + } + + for (i = 0, j=idx; i < top * sizeof b->d[0]; i++, j+=width) + { + buf[j] = ((unsigned char*)b->d)[i]; + } + + bn_correct_top(b); + return 1; + } + +static int MOD_EXP_CTIME_COPY_FROM_PREBUF(BIGNUM *b, int top, unsigned char *buf, int idx, int width) + { + size_t i, j; + + if (bn_wexpand(b, top) == NULL) + return 0; + + for (i=0, j=idx; i < top * sizeof b->d[0]; i++, j+=width) + { + ((unsigned char*)b->d)[i] = buf[j]; + } + + b->top = top; + bn_correct_top(b); + return 1; + } + +/* Given a pointer value, compute the next address that is a cache line multiple. */ +#define MOD_EXP_CTIME_ALIGN(x_) \ + ((unsigned char*)(x_) + (MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH - (((BN_ULONG)(x_)) & (MOD_EXP_CTIME_MIN_CACHE_LINE_MASK)))) + +/* This variant of BN_mod_exp_mont() uses fixed windows and the special + * precomputation memory layout to limit data-dependency to a minimum + * to protect secret exponents (cf. the hyper-threading timing attacks + * pointed out by Colin Percival, + * http://www.daemonology.net/hyperthreading-considered-harmful/) + */ +int BN_mod_exp_mont_consttime(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p, + const BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *in_mont) + { + int i,bits,ret=0,idx,window,wvalue; + int top; + BIGNUM *r; + const BIGNUM *aa; + BN_MONT_CTX *mont=NULL; + + int numPowers; + unsigned char *powerbufFree=NULL; + int powerbufLen = 0; + unsigned char *powerbuf=NULL; + BIGNUM *computeTemp=NULL, *am=NULL; + + bn_check_top(a); + bn_check_top(p); + bn_check_top(m); + + top = m->top; + + if (!(m->d[0] & 1)) + { + BNerr(BN_F_BN_MOD_EXP_MONT_CONSTTIME,BN_R_CALLED_WITH_EVEN_MODULUS); + return(0); + } + bits=BN_num_bits(p); + if (bits == 0) + { + ret = BN_one(rr); + return ret; + } + + /* Initialize BIGNUM context and allocate intermediate result */ + BN_CTX_start(ctx); + r = BN_CTX_get(ctx); + if (r == NULL) goto err; + + /* Allocate a montgomery context if it was not supplied by the caller. + * If this is not done, things will break in the montgomery part. + */ + if (in_mont != NULL) + mont=in_mont; + else + { + if ((mont=BN_MONT_CTX_new()) == NULL) goto err; + if (!BN_MONT_CTX_set(mont,m,ctx)) goto err; + } + + /* Get the window size to use with size of p. */ + window = BN_window_bits_for_ctime_exponent_size(bits); + + /* Allocate a buffer large enough to hold all of the pre-computed + * powers of a. + */ + numPowers = 1 << window; + powerbufLen = sizeof(m->d[0])*top*numPowers; + if ((powerbufFree=(unsigned char*)OPENSSL_malloc(powerbufLen+MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH)) == NULL) + goto err; + + powerbuf = MOD_EXP_CTIME_ALIGN(powerbufFree); + memset(powerbuf, 0, powerbufLen); + + /* Initialize the intermediate result. Do this early to save double conversion, + * once each for a^0 and intermediate result. + */ + if (!BN_to_montgomery(r,BN_value_one(),mont,ctx)) goto err; + if (!MOD_EXP_CTIME_COPY_TO_PREBUF(r, top, powerbuf, 0, numPowers)) goto err; + + /* Initialize computeTemp as a^1 with montgomery precalcs */ + computeTemp = BN_CTX_get(ctx); + am = BN_CTX_get(ctx); + if (computeTemp==NULL || am==NULL) goto err; + + if (a->neg || BN_ucmp(a,m) >= 0) + { + if (!BN_mod(am,a,m,ctx)) + goto err; + aa= am; + } + else + aa=a; + if (!BN_to_montgomery(am,aa,mont,ctx)) goto err; + if (!BN_copy(computeTemp, am)) goto err; + if (!MOD_EXP_CTIME_COPY_TO_PREBUF(am, top, powerbuf, 1, numPowers)) goto err; + + /* If the window size is greater than 1, then calculate + * val[i=2..2^winsize-1]. Powers are computed as a*a^(i-1) + * (even powers could instead be computed as (a^(i/2))^2 + * to use the slight performance advantage of sqr over mul). + */ + if (window > 1) + { + for (i=2; i= 0) + { + wvalue=0; /* The 'value' of the window */ + + /* Scan the window, squaring the result as we go */ + for (i=0; itop == 1) + a %= m->d[0]; /* make sure that 'a' is reduced */ + + bits = BN_num_bits(p); + if (bits == 0) + { + ret = BN_one(rr); + return ret; + } + if (a == 0) + { + BN_zero(rr); + ret = 1; + return ret; + } + + BN_CTX_start(ctx); + d = BN_CTX_get(ctx); + r = BN_CTX_get(ctx); + t = BN_CTX_get(ctx); + if (d == NULL || r == NULL || t == NULL) goto err; + + if (in_mont != NULL) + mont=in_mont; + else + { + if ((mont = BN_MONT_CTX_new()) == NULL) goto err; + if (!BN_MONT_CTX_set(mont, m, ctx)) goto err; + } + + r_is_one = 1; /* except for Montgomery factor */ + + /* bits-1 >= 0 */ + + /* The result is accumulated in the product r*w. */ + w = a; /* bit 'bits-1' of 'p' is always set */ + for (b = bits-2; b >= 0; b--) + { + /* First, square r*w. */ + next_w = w*w; + if ((next_w/w) != w) /* overflow */ + { + if (r_is_one) + { + if (!BN_TO_MONTGOMERY_WORD(r, w, mont)) goto err; + r_is_one = 0; + } + else + { + if (!BN_MOD_MUL_WORD(r, w, m)) goto err; + } + next_w = 1; + } + w = next_w; + if (!r_is_one) + { + if (!BN_mod_mul_montgomery(r, r, r, mont, ctx)) goto err; + } + + /* Second, multiply r*w by 'a' if exponent bit is set. */ + if (BN_is_bit_set(p, b)) + { + next_w = w*a; + if ((next_w/a) != w) /* overflow */ + { + if (r_is_one) + { + if (!BN_TO_MONTGOMERY_WORD(r, w, mont)) goto err; + r_is_one = 0; + } + else + { + if (!BN_MOD_MUL_WORD(r, w, m)) goto err; + } + next_w = a; + } + w = next_w; + } + } + + /* Finally, set r:=r*w. */ + if (w != 1) + { + if (r_is_one) + { + if (!BN_TO_MONTGOMERY_WORD(r, w, mont)) goto err; + r_is_one = 0; + } + else + { + if (!BN_MOD_MUL_WORD(r, w, m)) goto err; + } + } + + if (r_is_one) /* can happen only if a == 1*/ + { + if (!BN_one(rr)) goto err; + } + else + { + if (!BN_from_montgomery(rr, r, mont, ctx)) goto err; + } + ret = 1; +err: + if ((in_mont == NULL) && (mont != NULL)) BN_MONT_CTX_free(mont); + BN_CTX_end(ctx); + bn_check_top(rr); + return(ret); + } + + +/* The old fallback, simple version :-) */ +int BN_mod_exp_simple(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, + const BIGNUM *m, BN_CTX *ctx) + { + int i,j,bits,ret=0,wstart,wend,window,wvalue; + int start=1; + BIGNUM *d; + /* Table of variables obtained from 'ctx' */ + BIGNUM *val[TABLE_SIZE]; + + if (BN_get_flags(p, BN_FLG_CONSTTIME) != 0) + { + /* BN_FLG_CONSTTIME only supported by BN_mod_exp_mont() */ + BNerr(BN_F_BN_MOD_EXP_SIMPLE,ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); + return -1; + } + + bits=BN_num_bits(p); + + if (bits == 0) + { + ret = BN_one(r); + return ret; + } + + BN_CTX_start(ctx); + d = BN_CTX_get(ctx); + val[0] = BN_CTX_get(ctx); + if(!d || !val[0]) goto err; + + if (!BN_nnmod(val[0],a,m,ctx)) goto err; /* 1 */ + if (BN_is_zero(val[0])) + { + BN_zero(r); + ret = 1; + goto err; + } + + window = BN_window_bits_for_exponent_size(bits); + if (window > 1) + { + if (!BN_mod_mul(d,val[0],val[0],m,ctx)) + goto err; /* 2 */ + j=1<<(window-1); + for (i=1; i>1],m,ctx)) + goto err; + + /* move the 'window' down further */ + wstart-=wend+1; + wvalue=0; + start=0; + if (wstart < 0) break; + } + ret=1; +err: + BN_CTX_end(ctx); + bn_check_top(r); + return(ret); + } + -- cgit v1.2.3 From 3c3421afd8f74a3aa8d1011de07a8c18f9549210 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Parm=C3=A9nides=20GV?= Date: Tue, 8 Apr 2014 12:04:17 +0200 Subject: Rename app->bitmask_android This way, gradle commands generate apks correctly named. --- app/openssl/crypto/bn/bn_exp.c | 991 ----------------------------------------- 1 file changed, 991 deletions(-) delete mode 100644 app/openssl/crypto/bn/bn_exp.c (limited to 'app/openssl/crypto/bn/bn_exp.c') diff --git a/app/openssl/crypto/bn/bn_exp.c b/app/openssl/crypto/bn/bn_exp.c deleted file mode 100644 index d9b6c737..00000000 --- a/app/openssl/crypto/bn/bn_exp.c +++ /dev/null @@ -1,991 +0,0 @@ -/* crypto/bn/bn_exp.c */ -/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) - * All rights reserved. - * - * This package is an SSL implementation written - * by Eric Young (eay@cryptsoft.com). - * The implementation was written so as to conform with Netscapes SSL. - * - * This library is free for commercial and non-commercial use as long as - * the following conditions are aheared to. The following conditions - * apply to all code found in this distribution, be it the RC4, RSA, - * lhash, DES, etc., code; not just the SSL code. The SSL documentation - * included with this distribution is covered by the same copyright terms - * except that the holder is Tim Hudson (tjh@cryptsoft.com). - * - * Copyright remains Eric Young's, and as such any Copyright notices in - * the code are not to be removed. - * If this package is used in a product, Eric Young should be given attribution - * as the author of the parts of the library used. - * This can be in the form of a textual message at program startup or - * in documentation (online or textual) provided with the package. - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions - * are met: - * 1. Redistributions of source code must retain the copyright - * notice, this list of conditions and the following disclaimer. - * 2. Redistributions in binary form must reproduce the above copyright - * notice, this list of conditions and the following disclaimer in the - * documentation and/or other materials provided with the distribution. - * 3. All advertising materials mentioning features or use of this software - * must display the following acknowledgement: - * "This product includes cryptographic software written by - * Eric Young (eay@cryptsoft.com)" - * The word 'cryptographic' can be left out if the rouines from the library - * being used are not cryptographic related :-). - * 4. If you include any Windows specific code (or a derivative thereof) from - * the apps directory (application code) you must include an acknowledgement: - * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)" - * - * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND - * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE - * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE - * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE - * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL - * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS - * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) - * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT - * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY - * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF - * SUCH DAMAGE. - * - * The licence and distribution terms for any publically available version or - * derivative of this code cannot be changed. i.e. this code cannot simply be - * copied and put under another distribution licence - * [including the GNU Public Licence.] - */ -/* ==================================================================== - * Copyright (c) 1998-2005 The OpenSSL Project. All rights reserved. - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions - * are met: - * - * 1. Redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer. - * - * 2. Redistributions in binary form must reproduce the above copyright - * notice, this list of conditions and the following disclaimer in - * the documentation and/or other materials provided with the - * distribution. - * - * 3. All advertising materials mentioning features or use of this - * software must display the following acknowledgment: - * "This product includes software developed by the OpenSSL Project - * for use in the OpenSSL Toolkit. (http://www.openssl.org/)" - * - * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to - * endorse or promote products derived from this software without - * prior written permission. For written permission, please contact - * openssl-core@openssl.org. - * - * 5. Products derived from this software may not be called "OpenSSL" - * nor may "OpenSSL" appear in their names without prior written - * permission of the OpenSSL Project. - * - * 6. Redistributions of any form whatsoever must retain the following - * acknowledgment: - * "This product includes software developed by the OpenSSL Project - * for use in the OpenSSL Toolkit (http://www.openssl.org/)" - * - * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY - * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE - * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR - * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR - * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, - * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT - * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; - * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) - * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, - * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) - * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED - * OF THE POSSIBILITY OF SUCH DAMAGE. - * ==================================================================== - * - * This product includes cryptographic software written by Eric Young - * (eay@cryptsoft.com). This product includes software written by Tim - * Hudson (tjh@cryptsoft.com). - * - */ - - -#include "cryptlib.h" -#include "bn_lcl.h" - -/* maximum precomputation table size for *variable* sliding windows */ -#define TABLE_SIZE 32 - -/* this one works - simple but works */ -int BN_exp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx) - { - int i,bits,ret=0; - BIGNUM *v,*rr; - - if (BN_get_flags(p, BN_FLG_CONSTTIME) != 0) - { - /* BN_FLG_CONSTTIME only supported by BN_mod_exp_mont() */ - BNerr(BN_F_BN_EXP,ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); - return -1; - } - - BN_CTX_start(ctx); - if ((r == a) || (r == p)) - rr = BN_CTX_get(ctx); - else - rr = r; - v = BN_CTX_get(ctx); - if (rr == NULL || v == NULL) goto err; - - if (BN_copy(v,a) == NULL) goto err; - bits=BN_num_bits(p); - - if (BN_is_odd(p)) - { if (BN_copy(rr,a) == NULL) goto err; } - else { if (!BN_one(rr)) goto err; } - - for (i=1; i= m. eay 07-May-97 */ -/* if ((m->d[m->top-1]&BN_TBIT) && BN_is_odd(m)) */ - - if (BN_is_odd(m)) - { -# ifdef MONT_EXP_WORD - if (a->top == 1 && !a->neg && (BN_get_flags(p, BN_FLG_CONSTTIME) == 0)) - { - BN_ULONG A = a->d[0]; - ret=BN_mod_exp_mont_word(r,A,p,m,ctx,NULL); - } - else -# endif - ret=BN_mod_exp_mont(r,a,p,m,ctx,NULL); - } - else -#endif -#ifdef RECP_MUL_MOD - { ret=BN_mod_exp_recp(r,a,p,m,ctx); } -#else - { ret=BN_mod_exp_simple(r,a,p,m,ctx); } -#endif - - bn_check_top(r); - return(ret); - } - - -int BN_mod_exp_recp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, - const BIGNUM *m, BN_CTX *ctx) - { - int i,j,bits,ret=0,wstart,wend,window,wvalue; - int start=1; - BIGNUM *aa; - /* Table of variables obtained from 'ctx' */ - BIGNUM *val[TABLE_SIZE]; - BN_RECP_CTX recp; - - if (BN_get_flags(p, BN_FLG_CONSTTIME) != 0) - { - /* BN_FLG_CONSTTIME only supported by BN_mod_exp_mont() */ - BNerr(BN_F_BN_MOD_EXP_RECP,ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); - return -1; - } - - bits=BN_num_bits(p); - - if (bits == 0) - { - ret = BN_one(r); - return ret; - } - - BN_CTX_start(ctx); - aa = BN_CTX_get(ctx); - val[0] = BN_CTX_get(ctx); - if(!aa || !val[0]) goto err; - - BN_RECP_CTX_init(&recp); - if (m->neg) - { - /* ignore sign of 'm' */ - if (!BN_copy(aa, m)) goto err; - aa->neg = 0; - if (BN_RECP_CTX_set(&recp,aa,ctx) <= 0) goto err; - } - else - { - if (BN_RECP_CTX_set(&recp,m,ctx) <= 0) goto err; - } - - if (!BN_nnmod(val[0],a,m,ctx)) goto err; /* 1 */ - if (BN_is_zero(val[0])) - { - BN_zero(r); - ret = 1; - goto err; - } - - window = BN_window_bits_for_exponent_size(bits); - if (window > 1) - { - if (!BN_mod_mul_reciprocal(aa,val[0],val[0],&recp,ctx)) - goto err; /* 2 */ - j=1<<(window-1); - for (i=1; i>1],&recp,ctx)) - goto err; - - /* move the 'window' down further */ - wstart-=wend+1; - wvalue=0; - start=0; - if (wstart < 0) break; - } - ret=1; -err: - BN_CTX_end(ctx); - BN_RECP_CTX_free(&recp); - bn_check_top(r); - return(ret); - } - - -int BN_mod_exp_mont(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p, - const BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *in_mont) - { - int i,j,bits,ret=0,wstart,wend,window,wvalue; - int start=1; - BIGNUM *d,*r; - const BIGNUM *aa; - /* Table of variables obtained from 'ctx' */ - BIGNUM *val[TABLE_SIZE]; - BN_MONT_CTX *mont=NULL; - - if (BN_get_flags(p, BN_FLG_CONSTTIME) != 0) - { - return BN_mod_exp_mont_consttime(rr, a, p, m, ctx, in_mont); - } - - bn_check_top(a); - bn_check_top(p); - bn_check_top(m); - - if (!BN_is_odd(m)) - { - BNerr(BN_F_BN_MOD_EXP_MONT,BN_R_CALLED_WITH_EVEN_MODULUS); - return(0); - } - bits=BN_num_bits(p); - if (bits == 0) - { - ret = BN_one(rr); - return ret; - } - - BN_CTX_start(ctx); - d = BN_CTX_get(ctx); - r = BN_CTX_get(ctx); - val[0] = BN_CTX_get(ctx); - if (!d || !r || !val[0]) goto err; - - /* If this is not done, things will break in the montgomery - * part */ - - if (in_mont != NULL) - mont=in_mont; - else - { - if ((mont=BN_MONT_CTX_new()) == NULL) goto err; - if (!BN_MONT_CTX_set(mont,m,ctx)) goto err; - } - - if (a->neg || BN_ucmp(a,m) >= 0) - { - if (!BN_nnmod(val[0],a,m,ctx)) - goto err; - aa= val[0]; - } - else - aa=a; - if (BN_is_zero(aa)) - { - BN_zero(rr); - ret = 1; - goto err; - } - if (!BN_to_montgomery(val[0],aa,mont,ctx)) goto err; /* 1 */ - - window = BN_window_bits_for_exponent_size(bits); - if (window > 1) - { - if (!BN_mod_mul_montgomery(d,val[0],val[0],mont,ctx)) goto err; /* 2 */ - j=1<<(window-1); - for (i=1; i>1],mont,ctx)) - goto err; - - /* move the 'window' down further */ - wstart-=wend+1; - wvalue=0; - start=0; - if (wstart < 0) break; - } - if (!BN_from_montgomery(rr,r,mont,ctx)) goto err; - ret=1; -err: - if ((in_mont == NULL) && (mont != NULL)) BN_MONT_CTX_free(mont); - BN_CTX_end(ctx); - bn_check_top(rr); - return(ret); - } - - -/* BN_mod_exp_mont_consttime() stores the precomputed powers in a specific layout - * so that accessing any of these table values shows the same access pattern as far - * as cache lines are concerned. The following functions are used to transfer a BIGNUM - * from/to that table. */ - -static int MOD_EXP_CTIME_COPY_TO_PREBUF(BIGNUM *b, int top, unsigned char *buf, int idx, int width) - { - size_t i, j; - - if (bn_wexpand(b, top) == NULL) - return 0; - while (b->top < top) - { - b->d[b->top++] = 0; - } - - for (i = 0, j=idx; i < top * sizeof b->d[0]; i++, j+=width) - { - buf[j] = ((unsigned char*)b->d)[i]; - } - - bn_correct_top(b); - return 1; - } - -static int MOD_EXP_CTIME_COPY_FROM_PREBUF(BIGNUM *b, int top, unsigned char *buf, int idx, int width) - { - size_t i, j; - - if (bn_wexpand(b, top) == NULL) - return 0; - - for (i=0, j=idx; i < top * sizeof b->d[0]; i++, j+=width) - { - ((unsigned char*)b->d)[i] = buf[j]; - } - - b->top = top; - bn_correct_top(b); - return 1; - } - -/* Given a pointer value, compute the next address that is a cache line multiple. */ -#define MOD_EXP_CTIME_ALIGN(x_) \ - ((unsigned char*)(x_) + (MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH - (((BN_ULONG)(x_)) & (MOD_EXP_CTIME_MIN_CACHE_LINE_MASK)))) - -/* This variant of BN_mod_exp_mont() uses fixed windows and the special - * precomputation memory layout to limit data-dependency to a minimum - * to protect secret exponents (cf. the hyper-threading timing attacks - * pointed out by Colin Percival, - * http://www.daemonology.net/hyperthreading-considered-harmful/) - */ -int BN_mod_exp_mont_consttime(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p, - const BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *in_mont) - { - int i,bits,ret=0,idx,window,wvalue; - int top; - BIGNUM *r; - const BIGNUM *aa; - BN_MONT_CTX *mont=NULL; - - int numPowers; - unsigned char *powerbufFree=NULL; - int powerbufLen = 0; - unsigned char *powerbuf=NULL; - BIGNUM *computeTemp=NULL, *am=NULL; - - bn_check_top(a); - bn_check_top(p); - bn_check_top(m); - - top = m->top; - - if (!(m->d[0] & 1)) - { - BNerr(BN_F_BN_MOD_EXP_MONT_CONSTTIME,BN_R_CALLED_WITH_EVEN_MODULUS); - return(0); - } - bits=BN_num_bits(p); - if (bits == 0) - { - ret = BN_one(rr); - return ret; - } - - /* Initialize BIGNUM context and allocate intermediate result */ - BN_CTX_start(ctx); - r = BN_CTX_get(ctx); - if (r == NULL) goto err; - - /* Allocate a montgomery context if it was not supplied by the caller. - * If this is not done, things will break in the montgomery part. - */ - if (in_mont != NULL) - mont=in_mont; - else - { - if ((mont=BN_MONT_CTX_new()) == NULL) goto err; - if (!BN_MONT_CTX_set(mont,m,ctx)) goto err; - } - - /* Get the window size to use with size of p. */ - window = BN_window_bits_for_ctime_exponent_size(bits); - - /* Allocate a buffer large enough to hold all of the pre-computed - * powers of a. - */ - numPowers = 1 << window; - powerbufLen = sizeof(m->d[0])*top*numPowers; - if ((powerbufFree=(unsigned char*)OPENSSL_malloc(powerbufLen+MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH)) == NULL) - goto err; - - powerbuf = MOD_EXP_CTIME_ALIGN(powerbufFree); - memset(powerbuf, 0, powerbufLen); - - /* Initialize the intermediate result. Do this early to save double conversion, - * once each for a^0 and intermediate result. - */ - if (!BN_to_montgomery(r,BN_value_one(),mont,ctx)) goto err; - if (!MOD_EXP_CTIME_COPY_TO_PREBUF(r, top, powerbuf, 0, numPowers)) goto err; - - /* Initialize computeTemp as a^1 with montgomery precalcs */ - computeTemp = BN_CTX_get(ctx); - am = BN_CTX_get(ctx); - if (computeTemp==NULL || am==NULL) goto err; - - if (a->neg || BN_ucmp(a,m) >= 0) - { - if (!BN_mod(am,a,m,ctx)) - goto err; - aa= am; - } - else - aa=a; - if (!BN_to_montgomery(am,aa,mont,ctx)) goto err; - if (!BN_copy(computeTemp, am)) goto err; - if (!MOD_EXP_CTIME_COPY_TO_PREBUF(am, top, powerbuf, 1, numPowers)) goto err; - - /* If the window size is greater than 1, then calculate - * val[i=2..2^winsize-1]. Powers are computed as a*a^(i-1) - * (even powers could instead be computed as (a^(i/2))^2 - * to use the slight performance advantage of sqr over mul). - */ - if (window > 1) - { - for (i=2; i= 0) - { - wvalue=0; /* The 'value' of the window */ - - /* Scan the window, squaring the result as we go */ - for (i=0; itop == 1) - a %= m->d[0]; /* make sure that 'a' is reduced */ - - bits = BN_num_bits(p); - if (bits == 0) - { - ret = BN_one(rr); - return ret; - } - if (a == 0) - { - BN_zero(rr); - ret = 1; - return ret; - } - - BN_CTX_start(ctx); - d = BN_CTX_get(ctx); - r = BN_CTX_get(ctx); - t = BN_CTX_get(ctx); - if (d == NULL || r == NULL || t == NULL) goto err; - - if (in_mont != NULL) - mont=in_mont; - else - { - if ((mont = BN_MONT_CTX_new()) == NULL) goto err; - if (!BN_MONT_CTX_set(mont, m, ctx)) goto err; - } - - r_is_one = 1; /* except for Montgomery factor */ - - /* bits-1 >= 0 */ - - /* The result is accumulated in the product r*w. */ - w = a; /* bit 'bits-1' of 'p' is always set */ - for (b = bits-2; b >= 0; b--) - { - /* First, square r*w. */ - next_w = w*w; - if ((next_w/w) != w) /* overflow */ - { - if (r_is_one) - { - if (!BN_TO_MONTGOMERY_WORD(r, w, mont)) goto err; - r_is_one = 0; - } - else - { - if (!BN_MOD_MUL_WORD(r, w, m)) goto err; - } - next_w = 1; - } - w = next_w; - if (!r_is_one) - { - if (!BN_mod_mul_montgomery(r, r, r, mont, ctx)) goto err; - } - - /* Second, multiply r*w by 'a' if exponent bit is set. */ - if (BN_is_bit_set(p, b)) - { - next_w = w*a; - if ((next_w/a) != w) /* overflow */ - { - if (r_is_one) - { - if (!BN_TO_MONTGOMERY_WORD(r, w, mont)) goto err; - r_is_one = 0; - } - else - { - if (!BN_MOD_MUL_WORD(r, w, m)) goto err; - } - next_w = a; - } - w = next_w; - } - } - - /* Finally, set r:=r*w. */ - if (w != 1) - { - if (r_is_one) - { - if (!BN_TO_MONTGOMERY_WORD(r, w, mont)) goto err; - r_is_one = 0; - } - else - { - if (!BN_MOD_MUL_WORD(r, w, m)) goto err; - } - } - - if (r_is_one) /* can happen only if a == 1*/ - { - if (!BN_one(rr)) goto err; - } - else - { - if (!BN_from_montgomery(rr, r, mont, ctx)) goto err; - } - ret = 1; -err: - if ((in_mont == NULL) && (mont != NULL)) BN_MONT_CTX_free(mont); - BN_CTX_end(ctx); - bn_check_top(rr); - return(ret); - } - - -/* The old fallback, simple version :-) */ -int BN_mod_exp_simple(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, - const BIGNUM *m, BN_CTX *ctx) - { - int i,j,bits,ret=0,wstart,wend,window,wvalue; - int start=1; - BIGNUM *d; - /* Table of variables obtained from 'ctx' */ - BIGNUM *val[TABLE_SIZE]; - - if (BN_get_flags(p, BN_FLG_CONSTTIME) != 0) - { - /* BN_FLG_CONSTTIME only supported by BN_mod_exp_mont() */ - BNerr(BN_F_BN_MOD_EXP_SIMPLE,ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); - return -1; - } - - bits=BN_num_bits(p); - - if (bits == 0) - { - ret = BN_one(r); - return ret; - } - - BN_CTX_start(ctx); - d = BN_CTX_get(ctx); - val[0] = BN_CTX_get(ctx); - if(!d || !val[0]) goto err; - - if (!BN_nnmod(val[0],a,m,ctx)) goto err; /* 1 */ - if (BN_is_zero(val[0])) - { - BN_zero(r); - ret = 1; - goto err; - } - - window = BN_window_bits_for_exponent_size(bits); - if (window > 1) - { - if (!BN_mod_mul(d,val[0],val[0],m,ctx)) - goto err; /* 2 */ - j=1<<(window-1); - for (i=1; i>1],m,ctx)) - goto err; - - /* move the 'window' down further */ - wstart-=wend+1; - wvalue=0; - start=0; - if (wstart < 0) break; - } - ret=1; -err: - BN_CTX_end(ctx); - bn_check_top(r); - return(ret); - } - -- cgit v1.2.3 From 1684c8f398922065a97e7da4dac4ac6a33cc5218 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Parm=C3=A9nides=20GV?= Date: Wed, 9 Apr 2014 16:03:55 +0200 Subject: Back to the standard "app" module. This return to "app" instead of "bitmask_android" is due to this reading: https://developer.android.com/sdk/installing/studio-build.html#projectStructure I'll have to tweak the final apk name in build.gradle. --- app/openssl/crypto/bn/bn_exp.c | 991 +++++++++++++++++++++++++++++++++++++++++ 1 file changed, 991 insertions(+) create mode 100644 app/openssl/crypto/bn/bn_exp.c (limited to 'app/openssl/crypto/bn/bn_exp.c') diff --git a/app/openssl/crypto/bn/bn_exp.c b/app/openssl/crypto/bn/bn_exp.c new file mode 100644 index 00000000..d9b6c737 --- /dev/null +++ b/app/openssl/crypto/bn/bn_exp.c @@ -0,0 +1,991 @@ +/* crypto/bn/bn_exp.c */ +/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) + * All rights reserved. + * + * This package is an SSL implementation written + * by Eric Young (eay@cryptsoft.com). + * The implementation was written so as to conform with Netscapes SSL. + * + * This library is free for commercial and non-commercial use as long as + * the following conditions are aheared to. The following conditions + * apply to all code found in this distribution, be it the RC4, RSA, + * lhash, DES, etc., code; not just the SSL code. The SSL documentation + * included with this distribution is covered by the same copyright terms + * except that the holder is Tim Hudson (tjh@cryptsoft.com). + * + * Copyright remains Eric Young's, and as such any Copyright notices in + * the code are not to be removed. + * If this package is used in a product, Eric Young should be given attribution + * as the author of the parts of the library used. + * This can be in the form of a textual message at program startup or + * in documentation (online or textual) provided with the package. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * 3. All advertising materials mentioning features or use of this software + * must display the following acknowledgement: + * "This product includes cryptographic software written by + * Eric Young (eay@cryptsoft.com)" + * The word 'cryptographic' can be left out if the rouines from the library + * being used are not cryptographic related :-). + * 4. If you include any Windows specific code (or a derivative thereof) from + * the apps directory (application code) you must include an acknowledgement: + * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)" + * + * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + * + * The licence and distribution terms for any publically available version or + * derivative of this code cannot be changed. i.e. this code cannot simply be + * copied and put under another distribution licence + * [including the GNU Public Licence.] + */ +/* ==================================================================== + * Copyright (c) 1998-2005 The OpenSSL Project. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in + * the documentation and/or other materials provided with the + * distribution. + * + * 3. All advertising materials mentioning features or use of this + * software must display the following acknowledgment: + * "This product includes software developed by the OpenSSL Project + * for use in the OpenSSL Toolkit. (http://www.openssl.org/)" + * + * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to + * endorse or promote products derived from this software without + * prior written permission. For written permission, please contact + * openssl-core@openssl.org. + * + * 5. Products derived from this software may not be called "OpenSSL" + * nor may "OpenSSL" appear in their names without prior written + * permission of the OpenSSL Project. + * + * 6. Redistributions of any form whatsoever must retain the following + * acknowledgment: + * "This product includes software developed by the OpenSSL Project + * for use in the OpenSSL Toolkit (http://www.openssl.org/)" + * + * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY + * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR + * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED + * OF THE POSSIBILITY OF SUCH DAMAGE. + * ==================================================================== + * + * This product includes cryptographic software written by Eric Young + * (eay@cryptsoft.com). This product includes software written by Tim + * Hudson (tjh@cryptsoft.com). + * + */ + + +#include "cryptlib.h" +#include "bn_lcl.h" + +/* maximum precomputation table size for *variable* sliding windows */ +#define TABLE_SIZE 32 + +/* this one works - simple but works */ +int BN_exp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx) + { + int i,bits,ret=0; + BIGNUM *v,*rr; + + if (BN_get_flags(p, BN_FLG_CONSTTIME) != 0) + { + /* BN_FLG_CONSTTIME only supported by BN_mod_exp_mont() */ + BNerr(BN_F_BN_EXP,ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); + return -1; + } + + BN_CTX_start(ctx); + if ((r == a) || (r == p)) + rr = BN_CTX_get(ctx); + else + rr = r; + v = BN_CTX_get(ctx); + if (rr == NULL || v == NULL) goto err; + + if (BN_copy(v,a) == NULL) goto err; + bits=BN_num_bits(p); + + if (BN_is_odd(p)) + { if (BN_copy(rr,a) == NULL) goto err; } + else { if (!BN_one(rr)) goto err; } + + for (i=1; i= m. eay 07-May-97 */ +/* if ((m->d[m->top-1]&BN_TBIT) && BN_is_odd(m)) */ + + if (BN_is_odd(m)) + { +# ifdef MONT_EXP_WORD + if (a->top == 1 && !a->neg && (BN_get_flags(p, BN_FLG_CONSTTIME) == 0)) + { + BN_ULONG A = a->d[0]; + ret=BN_mod_exp_mont_word(r,A,p,m,ctx,NULL); + } + else +# endif + ret=BN_mod_exp_mont(r,a,p,m,ctx,NULL); + } + else +#endif +#ifdef RECP_MUL_MOD + { ret=BN_mod_exp_recp(r,a,p,m,ctx); } +#else + { ret=BN_mod_exp_simple(r,a,p,m,ctx); } +#endif + + bn_check_top(r); + return(ret); + } + + +int BN_mod_exp_recp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, + const BIGNUM *m, BN_CTX *ctx) + { + int i,j,bits,ret=0,wstart,wend,window,wvalue; + int start=1; + BIGNUM *aa; + /* Table of variables obtained from 'ctx' */ + BIGNUM *val[TABLE_SIZE]; + BN_RECP_CTX recp; + + if (BN_get_flags(p, BN_FLG_CONSTTIME) != 0) + { + /* BN_FLG_CONSTTIME only supported by BN_mod_exp_mont() */ + BNerr(BN_F_BN_MOD_EXP_RECP,ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); + return -1; + } + + bits=BN_num_bits(p); + + if (bits == 0) + { + ret = BN_one(r); + return ret; + } + + BN_CTX_start(ctx); + aa = BN_CTX_get(ctx); + val[0] = BN_CTX_get(ctx); + if(!aa || !val[0]) goto err; + + BN_RECP_CTX_init(&recp); + if (m->neg) + { + /* ignore sign of 'm' */ + if (!BN_copy(aa, m)) goto err; + aa->neg = 0; + if (BN_RECP_CTX_set(&recp,aa,ctx) <= 0) goto err; + } + else + { + if (BN_RECP_CTX_set(&recp,m,ctx) <= 0) goto err; + } + + if (!BN_nnmod(val[0],a,m,ctx)) goto err; /* 1 */ + if (BN_is_zero(val[0])) + { + BN_zero(r); + ret = 1; + goto err; + } + + window = BN_window_bits_for_exponent_size(bits); + if (window > 1) + { + if (!BN_mod_mul_reciprocal(aa,val[0],val[0],&recp,ctx)) + goto err; /* 2 */ + j=1<<(window-1); + for (i=1; i>1],&recp,ctx)) + goto err; + + /* move the 'window' down further */ + wstart-=wend+1; + wvalue=0; + start=0; + if (wstart < 0) break; + } + ret=1; +err: + BN_CTX_end(ctx); + BN_RECP_CTX_free(&recp); + bn_check_top(r); + return(ret); + } + + +int BN_mod_exp_mont(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p, + const BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *in_mont) + { + int i,j,bits,ret=0,wstart,wend,window,wvalue; + int start=1; + BIGNUM *d,*r; + const BIGNUM *aa; + /* Table of variables obtained from 'ctx' */ + BIGNUM *val[TABLE_SIZE]; + BN_MONT_CTX *mont=NULL; + + if (BN_get_flags(p, BN_FLG_CONSTTIME) != 0) + { + return BN_mod_exp_mont_consttime(rr, a, p, m, ctx, in_mont); + } + + bn_check_top(a); + bn_check_top(p); + bn_check_top(m); + + if (!BN_is_odd(m)) + { + BNerr(BN_F_BN_MOD_EXP_MONT,BN_R_CALLED_WITH_EVEN_MODULUS); + return(0); + } + bits=BN_num_bits(p); + if (bits == 0) + { + ret = BN_one(rr); + return ret; + } + + BN_CTX_start(ctx); + d = BN_CTX_get(ctx); + r = BN_CTX_get(ctx); + val[0] = BN_CTX_get(ctx); + if (!d || !r || !val[0]) goto err; + + /* If this is not done, things will break in the montgomery + * part */ + + if (in_mont != NULL) + mont=in_mont; + else + { + if ((mont=BN_MONT_CTX_new()) == NULL) goto err; + if (!BN_MONT_CTX_set(mont,m,ctx)) goto err; + } + + if (a->neg || BN_ucmp(a,m) >= 0) + { + if (!BN_nnmod(val[0],a,m,ctx)) + goto err; + aa= val[0]; + } + else + aa=a; + if (BN_is_zero(aa)) + { + BN_zero(rr); + ret = 1; + goto err; + } + if (!BN_to_montgomery(val[0],aa,mont,ctx)) goto err; /* 1 */ + + window = BN_window_bits_for_exponent_size(bits); + if (window > 1) + { + if (!BN_mod_mul_montgomery(d,val[0],val[0],mont,ctx)) goto err; /* 2 */ + j=1<<(window-1); + for (i=1; i>1],mont,ctx)) + goto err; + + /* move the 'window' down further */ + wstart-=wend+1; + wvalue=0; + start=0; + if (wstart < 0) break; + } + if (!BN_from_montgomery(rr,r,mont,ctx)) goto err; + ret=1; +err: + if ((in_mont == NULL) && (mont != NULL)) BN_MONT_CTX_free(mont); + BN_CTX_end(ctx); + bn_check_top(rr); + return(ret); + } + + +/* BN_mod_exp_mont_consttime() stores the precomputed powers in a specific layout + * so that accessing any of these table values shows the same access pattern as far + * as cache lines are concerned. The following functions are used to transfer a BIGNUM + * from/to that table. */ + +static int MOD_EXP_CTIME_COPY_TO_PREBUF(BIGNUM *b, int top, unsigned char *buf, int idx, int width) + { + size_t i, j; + + if (bn_wexpand(b, top) == NULL) + return 0; + while (b->top < top) + { + b->d[b->top++] = 0; + } + + for (i = 0, j=idx; i < top * sizeof b->d[0]; i++, j+=width) + { + buf[j] = ((unsigned char*)b->d)[i]; + } + + bn_correct_top(b); + return 1; + } + +static int MOD_EXP_CTIME_COPY_FROM_PREBUF(BIGNUM *b, int top, unsigned char *buf, int idx, int width) + { + size_t i, j; + + if (bn_wexpand(b, top) == NULL) + return 0; + + for (i=0, j=idx; i < top * sizeof b->d[0]; i++, j+=width) + { + ((unsigned char*)b->d)[i] = buf[j]; + } + + b->top = top; + bn_correct_top(b); + return 1; + } + +/* Given a pointer value, compute the next address that is a cache line multiple. */ +#define MOD_EXP_CTIME_ALIGN(x_) \ + ((unsigned char*)(x_) + (MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH - (((BN_ULONG)(x_)) & (MOD_EXP_CTIME_MIN_CACHE_LINE_MASK)))) + +/* This variant of BN_mod_exp_mont() uses fixed windows and the special + * precomputation memory layout to limit data-dependency to a minimum + * to protect secret exponents (cf. the hyper-threading timing attacks + * pointed out by Colin Percival, + * http://www.daemonology.net/hyperthreading-considered-harmful/) + */ +int BN_mod_exp_mont_consttime(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p, + const BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *in_mont) + { + int i,bits,ret=0,idx,window,wvalue; + int top; + BIGNUM *r; + const BIGNUM *aa; + BN_MONT_CTX *mont=NULL; + + int numPowers; + unsigned char *powerbufFree=NULL; + int powerbufLen = 0; + unsigned char *powerbuf=NULL; + BIGNUM *computeTemp=NULL, *am=NULL; + + bn_check_top(a); + bn_check_top(p); + bn_check_top(m); + + top = m->top; + + if (!(m->d[0] & 1)) + { + BNerr(BN_F_BN_MOD_EXP_MONT_CONSTTIME,BN_R_CALLED_WITH_EVEN_MODULUS); + return(0); + } + bits=BN_num_bits(p); + if (bits == 0) + { + ret = BN_one(rr); + return ret; + } + + /* Initialize BIGNUM context and allocate intermediate result */ + BN_CTX_start(ctx); + r = BN_CTX_get(ctx); + if (r == NULL) goto err; + + /* Allocate a montgomery context if it was not supplied by the caller. + * If this is not done, things will break in the montgomery part. + */ + if (in_mont != NULL) + mont=in_mont; + else + { + if ((mont=BN_MONT_CTX_new()) == NULL) goto err; + if (!BN_MONT_CTX_set(mont,m,ctx)) goto err; + } + + /* Get the window size to use with size of p. */ + window = BN_window_bits_for_ctime_exponent_size(bits); + + /* Allocate a buffer large enough to hold all of the pre-computed + * powers of a. + */ + numPowers = 1 << window; + powerbufLen = sizeof(m->d[0])*top*numPowers; + if ((powerbufFree=(unsigned char*)OPENSSL_malloc(powerbufLen+MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH)) == NULL) + goto err; + + powerbuf = MOD_EXP_CTIME_ALIGN(powerbufFree); + memset(powerbuf, 0, powerbufLen); + + /* Initialize the intermediate result. Do this early to save double conversion, + * once each for a^0 and intermediate result. + */ + if (!BN_to_montgomery(r,BN_value_one(),mont,ctx)) goto err; + if (!MOD_EXP_CTIME_COPY_TO_PREBUF(r, top, powerbuf, 0, numPowers)) goto err; + + /* Initialize computeTemp as a^1 with montgomery precalcs */ + computeTemp = BN_CTX_get(ctx); + am = BN_CTX_get(ctx); + if (computeTemp==NULL || am==NULL) goto err; + + if (a->neg || BN_ucmp(a,m) >= 0) + { + if (!BN_mod(am,a,m,ctx)) + goto err; + aa= am; + } + else + aa=a; + if (!BN_to_montgomery(am,aa,mont,ctx)) goto err; + if (!BN_copy(computeTemp, am)) goto err; + if (!MOD_EXP_CTIME_COPY_TO_PREBUF(am, top, powerbuf, 1, numPowers)) goto err; + + /* If the window size is greater than 1, then calculate + * val[i=2..2^winsize-1]. Powers are computed as a*a^(i-1) + * (even powers could instead be computed as (a^(i/2))^2 + * to use the slight performance advantage of sqr over mul). + */ + if (window > 1) + { + for (i=2; i= 0) + { + wvalue=0; /* The 'value' of the window */ + + /* Scan the window, squaring the result as we go */ + for (i=0; itop == 1) + a %= m->d[0]; /* make sure that 'a' is reduced */ + + bits = BN_num_bits(p); + if (bits == 0) + { + ret = BN_one(rr); + return ret; + } + if (a == 0) + { + BN_zero(rr); + ret = 1; + return ret; + } + + BN_CTX_start(ctx); + d = BN_CTX_get(ctx); + r = BN_CTX_get(ctx); + t = BN_CTX_get(ctx); + if (d == NULL || r == NULL || t == NULL) goto err; + + if (in_mont != NULL) + mont=in_mont; + else + { + if ((mont = BN_MONT_CTX_new()) == NULL) goto err; + if (!BN_MONT_CTX_set(mont, m, ctx)) goto err; + } + + r_is_one = 1; /* except for Montgomery factor */ + + /* bits-1 >= 0 */ + + /* The result is accumulated in the product r*w. */ + w = a; /* bit 'bits-1' of 'p' is always set */ + for (b = bits-2; b >= 0; b--) + { + /* First, square r*w. */ + next_w = w*w; + if ((next_w/w) != w) /* overflow */ + { + if (r_is_one) + { + if (!BN_TO_MONTGOMERY_WORD(r, w, mont)) goto err; + r_is_one = 0; + } + else + { + if (!BN_MOD_MUL_WORD(r, w, m)) goto err; + } + next_w = 1; + } + w = next_w; + if (!r_is_one) + { + if (!BN_mod_mul_montgomery(r, r, r, mont, ctx)) goto err; + } + + /* Second, multiply r*w by 'a' if exponent bit is set. */ + if (BN_is_bit_set(p, b)) + { + next_w = w*a; + if ((next_w/a) != w) /* overflow */ + { + if (r_is_one) + { + if (!BN_TO_MONTGOMERY_WORD(r, w, mont)) goto err; + r_is_one = 0; + } + else + { + if (!BN_MOD_MUL_WORD(r, w, m)) goto err; + } + next_w = a; + } + w = next_w; + } + } + + /* Finally, set r:=r*w. */ + if (w != 1) + { + if (r_is_one) + { + if (!BN_TO_MONTGOMERY_WORD(r, w, mont)) goto err; + r_is_one = 0; + } + else + { + if (!BN_MOD_MUL_WORD(r, w, m)) goto err; + } + } + + if (r_is_one) /* can happen only if a == 1*/ + { + if (!BN_one(rr)) goto err; + } + else + { + if (!BN_from_montgomery(rr, r, mont, ctx)) goto err; + } + ret = 1; +err: + if ((in_mont == NULL) && (mont != NULL)) BN_MONT_CTX_free(mont); + BN_CTX_end(ctx); + bn_check_top(rr); + return(ret); + } + + +/* The old fallback, simple version :-) */ +int BN_mod_exp_simple(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, + const BIGNUM *m, BN_CTX *ctx) + { + int i,j,bits,ret=0,wstart,wend,window,wvalue; + int start=1; + BIGNUM *d; + /* Table of variables obtained from 'ctx' */ + BIGNUM *val[TABLE_SIZE]; + + if (BN_get_flags(p, BN_FLG_CONSTTIME) != 0) + { + /* BN_FLG_CONSTTIME only supported by BN_mod_exp_mont() */ + BNerr(BN_F_BN_MOD_EXP_SIMPLE,ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); + return -1; + } + + bits=BN_num_bits(p); + + if (bits == 0) + { + ret = BN_one(r); + return ret; + } + + BN_CTX_start(ctx); + d = BN_CTX_get(ctx); + val[0] = BN_CTX_get(ctx); + if(!d || !val[0]) goto err; + + if (!BN_nnmod(val[0],a,m,ctx)) goto err; /* 1 */ + if (BN_is_zero(val[0])) + { + BN_zero(r); + ret = 1; + goto err; + } + + window = BN_window_bits_for_exponent_size(bits); + if (window > 1) + { + if (!BN_mod_mul(d,val[0],val[0],m,ctx)) + goto err; /* 2 */ + j=1<<(window-1); + for (i=1; i>1],m,ctx)) + goto err; + + /* move the 'window' down further */ + wstart-=wend+1; + wvalue=0; + start=0; + if (wstart < 0) break; + } + ret=1; +err: + BN_CTX_end(ctx); + bn_check_top(r); + return(ret); + } + -- cgit v1.2.3