X-Git-Url: http://git.openwrt.org/?a=blobdiff_plain;f=package%2Fead%2Fsrc%2Ftinysrp%2Ft_conf.c;fp=package%2Fead%2Fsrc%2Ftinysrp%2Ft_conf.c;h=0000000000000000000000000000000000000000;hb=405e21d16731b2764ab82aaaadcf36a813b105f7;hp=fbe6f410e2da16ddf86302b568c83c165a289204;hpb=d0ec348ded6f715b43b396b06ccb10599b37969d;p=openwrt%2Fstaging%2Fyousong.git diff --git a/package/ead/src/tinysrp/t_conf.c b/package/ead/src/tinysrp/t_conf.c deleted file mode 100644 index fbe6f410e2..0000000000 --- a/package/ead/src/tinysrp/t_conf.c +++ /dev/null @@ -1,1080 +0,0 @@ -/* - * Copyright (c) 1997-1999 The Stanford SRP Authentication Project - * All Rights Reserved. - * - * Permission is hereby granted, free of charge, to any person obtaining - * a copy of this software and associated documentation files (the - * "Software"), to deal in the Software without restriction, including - * without limitation the rights to use, copy, modify, merge, publish, - * distribute, sublicense, and/or sell copies of the Software, and to - * permit persons to whom the Software is furnished to do so, subject to - * the following conditions: - * - * The above copyright notice and this permission notice shall be - * included in all copies or substantial portions of the Software. - * - * THE SOFTWARE IS PROVIDED "AS-IS" AND WITHOUT WARRANTY OF ANY KIND, - * EXPRESS, IMPLIED OR OTHERWISE, INCLUDING WITHOUT LIMITATION, ANY - * WARRANTY OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. - * - * IN NO EVENT SHALL STANFORD BE LIABLE FOR ANY SPECIAL, INCIDENTAL, - * INDIRECT OR CONSEQUENTIAL DAMAGES OF ANY KIND, OR ANY DAMAGES WHATSOEVER - * RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER OR NOT ADVISED OF - * THE POSSIBILITY OF DAMAGE, AND ON ANY THEORY OF LIABILITY, ARISING OUT - * OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. - * - * In addition, the following conditions apply: - * - * 1. Any software that incorporates the SRP authentication technology - * must display the following acknowlegment: - * "This product uses the 'Secure Remote Password' cryptographic - * authentication system developed by Tom Wu (tjw@CS.Stanford.EDU)." - * - * 2. Any software that incorporates all or part of the SRP distribution - * itself must also display the following acknowledgment: - * "This product includes software developed by Tom Wu and Eugene - * Jhong for the SRP Distribution (http://srp.stanford.edu/srp/)." - * - * 3. Redistributions in source or binary form must retain an intact copy - * of this copyright notice and list of conditions. - */ - -#include - -#include "t_defines.h" -#include "t_pwd.h" -#include "t_read.h" -#include "bn.h" -#include "bn_lcl.h" -#include "bn_prime.h" - -#define TABLE_SIZE 32 - -static int witness(BIGNUM *w, const BIGNUM *a, const BIGNUM *a1, - const BIGNUM *a1_odd, int k, BN_CTX *ctx, BN_MONT_CTX *mont); - -/* - * This is the safe prime generation logic. - * To generate a safe prime p (where p = 2q+1 and q is prime), we start - * with a random odd q that is one bit shorter than the desired length - * of p. We use a simple 30-element sieve to filter the values of q - * and consider only those that are 11, 23, or 29 (mod 30). (If q were - * anything else, either q or p would be divisible by 2, 3, or 5). - * For the values of q that are left, we apply the following tests in - * this order: - * - * trial divide q - * let p = 2q + 1 - * trial divide p - * apply Fermat test to q (2^q == 2 (mod q)) - * apply Fermat test to p (2^p == 2 (mod p)) - * apply real probablistic primality test to q - * apply real probablistic primality test to p - * - * A number that passes all these tests is considered a safe prime for - * our purposes. The tests are ordered this way for efficiency; the - * slower tests are run rarely if ever at all. - */ - -static int -trialdiv(x) - const BigInteger x; -{ - static int primes[] = { /* All odd primes < 256 */ - 3, 5, 7, 11, 13, 17, 19, 23, 29, - 31, 37, 41, 43, 47, 53, 59, 61, 67, - 71, 73, 79, 83, 89, 97, 101, 103, - 107, 109, 113, 127, 131, 137, 139, 149, 151, - 157, 163, 167, 173, 179, 181, 191, 193, 197, - 199, 211, 223, 227, 229, 233, 239, 241, 251 - }; - static int nprimes = sizeof(primes) / sizeof(int); - int i; - - for(i = 0; i < nprimes; ++i) { - if(BigIntegerModInt(x, primes[i]) == 0) - return primes[i]; - } - return 1; -} - -/* x + sieve30[x%30] == 11, 23, or 29 (mod 30) */ - -static int sieve30[] = -{ 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, - 1, 12, 11, 10, 9, 8, 7, 6, 5, 4, - 3, 2, 1, 6, 5, 4, 3, 2, 1, 12 -}; - -/* Find a Sophie-Germain prime between "lo" and "hi". NOTE: this is not - a "safe prime", but the smaller prime. Take 2q+1 to get the safe prime. */ - -static void -sophie_germain(q, lo, hi) - BigInteger q; /* assumed initialized */ - const BigInteger lo; - const BigInteger hi; -{ - BigInteger m, p, r; - char parambuf[MAXPARAMLEN]; - int foundprime = 0; - int i, mod30; - - m = BigIntegerFromInt(0); - BigIntegerSub(m, hi, lo); - i = (BigIntegerBitLen(m) + 7) / 8; - t_random(parambuf, i); - r = BigIntegerFromBytes(parambuf, i); - BigIntegerMod(r, r, m); - - BigIntegerAdd(q, r, lo); - if(BigIntegerModInt(q, 2) == 0) - BigIntegerAddInt(q, q, 1); /* make q odd */ - - mod30 = BigIntegerModInt(q, 30); /* mod30 = q % 30 */ - - BigIntegerFree(m); - m = BigIntegerFromInt(2); /* m = 2 */ - p = BigIntegerFromInt(0); - - while(BigIntegerCmp(q, hi) < 0) { - if(trialdiv(q) < 2) { - BigIntegerMulInt(p, q, 2); /* p = 2 * q */ - BigIntegerAddInt(p, p, 1); /* p += 1 */ - if(trialdiv(p) < 2) { - BigIntegerModExp(r, m, q, q); /* r = 2^q % q */ - if(BigIntegerCmpInt(r, 2) == 0) { /* if(r == 2) */ - BigIntegerModExp(r, m, p, p); /* r = 2^p % p */ - if(BigIntegerCmpInt(r, 2) == 0) { /* if(r == 2) */ - if(BigIntegerCheckPrime(q) && BigIntegerCheckPrime(p)) { - ++foundprime; - break; - } - } - } - } - } - - i = sieve30[mod30]; - BigIntegerAddInt(q, q, i); /* q += i */ - mod30 = (mod30 + i) % 30; - } - - /* should wrap around on failure */ - if(!foundprime) { - fprintf(stderr, "Prime generation failed!\n"); - exit(1); - } - - BigIntegerFree(r); - BigIntegerFree(m); - BigIntegerFree(p); -} - -_TYPE( struct t_confent * ) -t_makeconfent(tc, nsize) - struct t_conf * tc; - int nsize; -{ - BigInteger n, g, q, t, u; - - t = BigIntegerFromInt(0); - u = BigIntegerFromInt(1); /* u = 1 */ - BigIntegerLShift(t, u, nsize - 2); /* t = 2^(nsize-2) */ - BigIntegerMulInt(u, t, 2); /* u = 2^(nsize-1) */ - - q = BigIntegerFromInt(0); - sophie_germain(q, t, u); - - n = BigIntegerFromInt(0); - BigIntegerMulInt(n, q, 2); - BigIntegerAddInt(n, n, 1); - - /* Look for a generator mod n */ - g = BigIntegerFromInt(2); - while(1) { - BigIntegerModExp(t, g, q, n); /* t = g^q % n */ - if(BigIntegerCmpInt(t, 1) == 0) /* if(t == 1) */ - BigIntegerAddInt(g, g, 1); /* ++g */ - else - break; - } - BigIntegerFree(t); - BigIntegerFree(u); - BigIntegerFree(q); - - tc->tcbuf.modulus.data = tc->modbuf; - tc->tcbuf.modulus.len = BigIntegerToBytes(n, tc->tcbuf.modulus.data); - BigIntegerFree(n); - - tc->tcbuf.generator.data = tc->genbuf; - tc->tcbuf.generator.len = BigIntegerToBytes(g, tc->tcbuf.generator.data); - BigIntegerFree(g); - - tc->tcbuf.index = 1; - return &tc->tcbuf; -} - -_TYPE( struct t_confent * ) -t_makeconfent_c(tc, nsize) - struct t_conf * tc; - int nsize; -{ - BigInteger g, n, p, q, j, k, t, u; - int psize, qsize; - - psize = nsize / 2; - qsize = nsize - psize; - - t = BigIntegerFromInt(1); /* t = 1 */ - u = BigIntegerFromInt(0); - BigIntegerLShift(u, t, psize - 3); /* u = t*2^(psize-3) = 2^(psize-3) */ - BigIntegerMulInt(t, u, 3); /* t = 3*u = 1.5*2^(psize-2) */ - BigIntegerAdd(u, u, t); /* u += t [u = 2^(psize-1)] */ - j = BigIntegerFromInt(0); - sophie_germain(j, t, u); - - k = BigIntegerFromInt(0); - if(qsize != psize) { - BigIntegerFree(t); - t = BigIntegerFromInt(1); /* t = 1 */ - BigIntegerLShift(u, t, qsize - 3); /* u = t*2^(qsize-3) = 2^(qsize-3) */ - BigIntegerMulInt(t, u, 3); /* t = 3*u = 1.5*2^(qsize-2) */ - BigIntegerAdd(u, u, t); /* u += t [u = 2^(qsize-1)] */ - } - sophie_germain(k, t, u); - - p = BigIntegerFromInt(0); - BigIntegerMulInt(p, j, 2); /* p = 2 * j */ - BigIntegerAddInt(p, p, 1); /* p += 1 */ - - q = BigIntegerFromInt(0); - BigIntegerMulInt(q, k, 2); /* q = 2 * k */ - BigIntegerAddInt(q, q, 1); /* q += 1 */ - - n = BigIntegerFromInt(0); - BigIntegerMul(n, p, q); /* n = p * q */ - BigIntegerMul(u, j, k); /* u = j * k */ - - BigIntegerFree(p); - BigIntegerFree(q); - BigIntegerFree(j); - BigIntegerFree(k); - - g = BigIntegerFromInt(2); /* g = 2 */ - - /* Look for a generator mod n */ - while(1) { - BigIntegerModExp(t, g, u, n); /* t = g^u % n */ - if(BigIntegerCmpInt(t, 1) == 0) - BigIntegerAddInt(g, g, 1); /* ++g */ - else - break; - } - - BigIntegerFree(u); - BigIntegerFree(t); - - tc->tcbuf.modulus.data = tc->modbuf; - tc->tcbuf.modulus.len = BigIntegerToBytes(n, tc->tcbuf.modulus.data); - BigIntegerFree(n); - - tc->tcbuf.generator.data = tc->genbuf; - tc->tcbuf.generator.len = BigIntegerToBytes(g, tc->tcbuf.generator.data); - BigIntegerFree(g); - - tc->tcbuf.index = 1; - return &tc->tcbuf; -} - -_TYPE( struct t_confent * ) -t_newconfent(tc) - struct t_conf * tc; -{ - tc->tcbuf.index = 0; - tc->tcbuf.modulus.data = tc->modbuf; - tc->tcbuf.modulus.len = 0; - tc->tcbuf.generator.data = tc->genbuf; - tc->tcbuf.generator.len = 0; - return &tc->tcbuf; -} - -_TYPE( void ) -t_putconfent(ent, fp) - const struct t_confent * ent; - FILE * fp; -{ - char strbuf[MAXB64PARAMLEN]; - - fprintf(fp, "%d:%s:", ent->index, - t_tob64(strbuf, ent->modulus.data, ent->modulus.len)); - fprintf(fp, "%s\n", - t_tob64(strbuf, ent->generator.data, ent->generator.len)); -} - -int -BigIntegerBitLen(b) - BigInteger b; -{ - return BN_num_bits(b); -} - -int -BigIntegerCheckPrime(n) - BigInteger n; -{ - BN_CTX * ctx = BN_CTX_new(); - int rv = BN_is_prime(n, 25, NULL, ctx, NULL); - BN_CTX_free(ctx); - return rv; -} - -unsigned int -BigIntegerModInt(d, m) - BigInteger d; - unsigned int m; -{ - return BN_mod_word(d, m); -} - -void -BigIntegerMod(result, d, m) - BigInteger result, d, m; -{ - BN_CTX * ctx = BN_CTX_new(); - BN_mod(result, d, m, ctx); - BN_CTX_free(ctx); -} - -void -BigIntegerMul(result, m1, m2) - BigInteger result, m1, m2; -{ - BN_CTX * ctx = BN_CTX_new(); - BN_mul(result, m1, m2, ctx); - BN_CTX_free(ctx); -} - -void -BigIntegerLShift(result, x, bits) - BigInteger result, x; - unsigned int bits; -{ - BN_lshift(result, x, bits); -} - -int BN_is_prime(const BIGNUM *a, int checks, void (*callback)(int,int,void *), - BN_CTX *ctx_passed, void *cb_arg) - { - return BN_is_prime_fasttest(a, checks, callback, ctx_passed, cb_arg, 0); - } - -int BN_is_prime_fasttest(const BIGNUM *a, int checks, - void (*callback)(int,int,void *), - BN_CTX *ctx_passed, void *cb_arg, - int do_trial_division) - { - int i, j, ret = -1; - int k; - BN_CTX *ctx = NULL; - BIGNUM *A1, *A1_odd, *check; /* taken from ctx */ - BN_MONT_CTX *mont = NULL; - const BIGNUM *A = NULL; - - if (checks == BN_prime_checks) - checks = BN_prime_checks_for_size(BN_num_bits(a)); - - /* first look for small factors */ - if (!BN_is_odd(a)) - return(0); - if (do_trial_division) - { - for (i = 1; i < NUMPRIMES; i++) - if (BN_mod_word(a, primes[i]) == 0) - return 0; - if (callback != NULL) callback(1, -1, cb_arg); - } - - if (ctx_passed != NULL) - ctx = ctx_passed; - else - if ((ctx=BN_CTX_new()) == NULL) - goto err; - BN_CTX_start(ctx); - - /* A := abs(a) */ - if (a->neg) - { - BIGNUM *t; - if ((t = BN_CTX_get(ctx)) == NULL) goto err; - BN_copy(t, a); - t->neg = 0; - A = t; - } - else - A = a; - A1 = BN_CTX_get(ctx); - A1_odd = BN_CTX_get(ctx); - check = BN_CTX_get(ctx); - if (check == NULL) goto err; - - /* compute A1 := A - 1 */ - if (!BN_copy(A1, A)) - goto err; - if (!BN_sub_word(A1, 1)) - goto err; - if (BN_is_zero(A1)) - { - ret = 0; - goto err; - } - - /* write A1 as A1_odd * 2^k */ - k = 1; - while (!BN_is_bit_set(A1, k)) - k++; - if (!BN_rshift(A1_odd, A1, k)) - goto err; - - /* Montgomery setup for computations mod A */ - mont = BN_MONT_CTX_new(); - if (mont == NULL) - goto err; - if (!BN_MONT_CTX_set(mont, A, ctx)) - goto err; - - for (i = 0; i < checks; i++) - { - if (!BN_pseudo_rand(check, BN_num_bits(A1), 0, 0)) - goto err; - if (BN_cmp(check, A1) >= 0) - if (!BN_sub(check, check, A1)) - goto err; - if (!BN_add_word(check, 1)) - goto err; - /* now 1 <= check < A */ - - j = witness(check, A, A1, A1_odd, k, ctx, mont); - if (j == -1) goto err; - if (j) - { - ret=0; - goto err; - } - if (callback != NULL) callback(1,i,cb_arg); - } - ret=1; -err: - if (ctx != NULL) - { - BN_CTX_end(ctx); - if (ctx_passed == NULL) - BN_CTX_free(ctx); - } - if (mont != NULL) - BN_MONT_CTX_free(mont); - - return(ret); - } - -static int witness(BIGNUM *w, const BIGNUM *a, const BIGNUM *a1, - const BIGNUM *a1_odd, int k, BN_CTX *ctx, BN_MONT_CTX *mont) - { - if (!BN_mod_exp_mont(w, w, a1_odd, a, ctx, mont)) /* w := w^a1_odd mod a */ - return -1; - if (BN_is_one(w)) - return 0; /* probably prime */ - if (BN_cmp(w, a1) == 0) - return 0; /* w == -1 (mod a), 'a' is probably prime */ - while (--k) - { - if (!BN_mod_mul(w, w, w, a, ctx)) /* w := w^2 mod a */ - return -1; - if (BN_is_one(w)) - return 1; /* 'a' is composite, otherwise a previous 'w' would - * have been == -1 (mod 'a') */ - if (BN_cmp(w, a1) == 0) - return 0; /* w == -1 (mod a), 'a' is probably prime */ - } - /* If we get here, 'w' is the (a-1)/2-th power of the original 'w', - * and it is neither -1 nor +1 -- so 'a' cannot be prime */ - return 1; - } - -int BN_mod_exp_mont(BIGNUM *rr, 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,ts=0; - BIGNUM *d,*r; - BIGNUM *aa; - BIGNUM val[TABLE_SIZE]; - BN_MONT_CTX *mont=NULL; - - bn_check_top(a); - bn_check_top(p); - bn_check_top(m); - - if (!(m->d[0] & 1)) - { - return(0); - } - bits=BN_num_bits(p); - if (bits == 0) - { - BN_one(rr); - return(1); - } - BN_CTX_start(ctx); - d = BN_CTX_get(ctx); - r = BN_CTX_get(ctx); - if (d == NULL || r == NULL) 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; - } - - BN_init(&val[0]); - ts=1; - if (BN_ucmp(a,m) >= 0) - { - if (!BN_mod(&(val[0]),a,m,ctx)) - goto err; - aa= &(val[0]); - } - else - aa=a; - 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); - for (i=0; itop-1; i>=0; i--) - { -#ifndef BN_LLONG - ret=((ret<d[i]>>BN_BITS4)&BN_MASK2l))%w; - ret=((ret<d[i]&BN_MASK2l))%w; -#else - ret=(BN_ULLONG)(((ret<<(BN_ULLONG)BN_BITS2)|a->d[i])% - (BN_ULLONG)w); -#endif - } - return((BN_ULONG)ret); - } - -static int bnrand(int pseudorand, BIGNUM *rnd, int bits, int top, int bottom) - { - unsigned char *buf=NULL; - int ret=0,bit,bytes,mask; - - if (bits == 0) - { - BN_zero(rnd); - return 1; - } - - bytes=(bits+7)/8; - bit=(bits-1)%8; - mask=0xff<N); - - ap=a->d; - /* mont->ri is the size of mont->N in bits (rounded up - to the word size) */ - al=ri=mont->ri/BN_BITS2; - - nl=n->top; - if ((al == 0) || (nl == 0)) { r->top=0; return(1); } - - max=(nl+al+1); /* allow for overflow (no?) XXX */ - if (bn_wexpand(r,max) == NULL) goto err; - if (bn_wexpand(ret,max) == NULL) goto err; - - r->neg=a->neg^n->neg; - np=n->d; - rp=r->d; - nrp= &(r->d[nl]); - - /* clear the top words of T */ -#if 1 - for (i=r->top; id[i]=0; -#else - memset(&(r->d[r->top]),0,(max-r->top)*sizeof(BN_ULONG)); -#endif - - r->top=max; - n0=mont->n0; - -#ifdef BN_COUNT - printf("word BN_from_montgomery %d * %d\n",nl,nl); -#endif - for (i=0; i= v) - continue; - else - { - if (((++nrp[0])&BN_MASK2) != 0) continue; - if (((++nrp[1])&BN_MASK2) != 0) continue; - for (x=2; (((++nrp[x])&BN_MASK2) == 0); x++) ; - } - } - bn_fix_top(r); - - /* mont->ri will be a multiple of the word size */ -#if 0 - BN_rshift(ret,r,mont->ri); -#else - ret->neg = r->neg; - x=ri; - rp=ret->d; - ap= &(r->d[x]); - if (r->top < x) - al=0; - else - al=r->top-x; - ret->top=al; - al-=4; - for (i=0; iri); - - if (!BN_mul(t2,t1,&mont->Ni,ctx)) goto err; - BN_mask_bits(t2,mont->ri); - - if (!BN_mul(t1,t2,&mont->N,ctx)) goto err; - if (!BN_add(t2,a,t1)) goto err; - BN_rshift(ret,t2,mont->ri); -#endif /* MONT_WORD */ - - if (BN_ucmp(ret, &(mont->N)) >= 0) - { - BN_usub(ret,ret,&(mont->N)); - } - retn=1; - err: - BN_CTX_end(ctx); - return(retn); - } - -void BN_MONT_CTX_init(BN_MONT_CTX *ctx) - { - ctx->ri=0; - BN_init(&(ctx->RR)); - BN_init(&(ctx->N)); - BN_init(&(ctx->Ni)); - ctx->flags=0; - } - -BN_MONT_CTX *BN_MONT_CTX_new(void) - { - BN_MONT_CTX *ret; - - if ((ret=(BN_MONT_CTX *)malloc(sizeof(BN_MONT_CTX))) == NULL) - return(NULL); - - BN_MONT_CTX_init(ret); - ret->flags=BN_FLG_MALLOCED; - return(ret); - } - -void BN_MONT_CTX_free(BN_MONT_CTX *mont) - { - if(mont == NULL) - return; - - BN_free(&(mont->RR)); - BN_free(&(mont->N)); - BN_free(&(mont->Ni)); - if (mont->flags & BN_FLG_MALLOCED) - free(mont); - } - -int BN_MONT_CTX_set(BN_MONT_CTX *mont, const BIGNUM *mod, BN_CTX *ctx) - { - BIGNUM Ri,*R; - - BN_init(&Ri); - R= &(mont->RR); /* grab RR as a temp */ - BN_copy(&(mont->N),mod); /* Set N */ - -#ifdef MONT_WORD - { - BIGNUM tmod; - BN_ULONG buf[2]; - - mont->ri=(BN_num_bits(mod)+(BN_BITS2-1))/BN_BITS2*BN_BITS2; - BN_zero(R); - BN_set_bit(R,BN_BITS2); /* R */ - - buf[0]=mod->d[0]; /* tmod = N mod word size */ - buf[1]=0; - tmod.d=buf; - tmod.top=1; - tmod.dmax=2; - tmod.neg=mod->neg; - /* Ri = R^-1 mod N*/ - if ((BN_mod_inverse(&Ri,R,&tmod,ctx)) == NULL) - goto err; - BN_lshift(&Ri,&Ri,BN_BITS2); /* R*Ri */ - if (!BN_is_zero(&Ri)) - BN_sub_word(&Ri,1); - else /* if N mod word size == 1 */ - BN_set_word(&Ri,BN_MASK2); /* Ri-- (mod word size) */ - BN_div(&Ri,NULL,&Ri,&tmod,ctx); /* Ni = (R*Ri-1)/N, - * keep only least significant word: */ - mont->n0=Ri.d[0]; - BN_free(&Ri); - } -#else /* !MONT_WORD */ - { /* bignum version */ - mont->ri=BN_num_bits(mod); - BN_zero(R); - BN_set_bit(R,mont->ri); /* R = 2^ri */ - /* Ri = R^-1 mod N*/ - if ((BN_mod_inverse(&Ri,R,mod,ctx)) == NULL) - goto err; - BN_lshift(&Ri,&Ri,mont->ri); /* R*Ri */ - BN_sub_word(&Ri,1); - /* Ni = (R*Ri-1) / N */ - BN_div(&(mont->Ni),NULL,&Ri,mod,ctx); - BN_free(&Ri); - } -#endif - - /* setup RR for conversions */ - BN_zero(&(mont->RR)); - BN_set_bit(&(mont->RR),mont->ri*2); - BN_mod(&(mont->RR),&(mont->RR),&(mont->N),ctx); - - return(1); -err: - return(0); - } - -BIGNUM *BN_value_one(void) - { - static BN_ULONG data_one=1L; - static BIGNUM const_one={&data_one,1,1,0}; - - return(&const_one); - } - -/* solves ax == 1 (mod n) */ -BIGNUM *BN_mod_inverse(BIGNUM *in, BIGNUM *a, const BIGNUM *n, BN_CTX *ctx) - { - BIGNUM *A,*B,*X,*Y,*M,*D,*R=NULL; - BIGNUM *T,*ret=NULL; - int sign; - - bn_check_top(a); - bn_check_top(n); - - BN_CTX_start(ctx); - A = BN_CTX_get(ctx); - B = BN_CTX_get(ctx); - X = BN_CTX_get(ctx); - D = BN_CTX_get(ctx); - M = BN_CTX_get(ctx); - Y = BN_CTX_get(ctx); - if (Y == NULL) goto err; - - if (in == NULL) - R=BN_new(); - else - R=in; - if (R == NULL) goto err; - - BN_zero(X); - BN_one(Y); - if (BN_copy(A,a) == NULL) goto err; - if (BN_copy(B,n) == NULL) goto err; - sign=1; - - while (!BN_is_zero(B)) - { - if (!BN_div(D,M,A,B,ctx)) goto err; - T=A; - A=B; - B=M; - /* T has a struct, M does not */ - - if (!BN_mul(T,D,X,ctx)) goto err; - if (!BN_add(T,T,Y)) goto err; - M=Y; - Y=X; - X=T; - sign= -sign; - } - if (sign < 0) - { - if (!BN_sub(Y,n,Y)) goto err; - } - - if (BN_is_one(A)) - { if (!BN_mod(R,Y,n,ctx)) goto err; } - else - { - goto err; - } - ret=R; -err: - if ((ret == NULL) && (in == NULL)) BN_free(R); - BN_CTX_end(ctx); - return(ret); - } - -int BN_set_bit(BIGNUM *a, int n) - { - int i,j,k; - - i=n/BN_BITS2; - j=n%BN_BITS2; - if (a->top <= i) - { - if (bn_wexpand(a,i+1) == NULL) return(0); - for(k=a->top; kd[k]=0; - a->top=i+1; - } - - a->d[i]|=(((BN_ULONG)1)<