2 * Copyright (c) 1997-1999 The Stanford SRP Authentication Project
5 * Permission is hereby granted, free of charge, to any person obtaining
6 * a copy of this software and associated documentation files (the
7 * "Software"), to deal in the Software without restriction, including
8 * without limitation the rights to use, copy, modify, merge, publish,
9 * distribute, sublicense, and/or sell copies of the Software, and to
10 * permit persons to whom the Software is furnished to do so, subject to
11 * the following conditions:
13 * The above copyright notice and this permission notice shall be
14 * included in all copies or substantial portions of the Software.
16 * THE SOFTWARE IS PROVIDED "AS-IS" AND WITHOUT WARRANTY OF ANY KIND,
17 * EXPRESS, IMPLIED OR OTHERWISE, INCLUDING WITHOUT LIMITATION, ANY
18 * WARRANTY OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
20 * IN NO EVENT SHALL STANFORD BE LIABLE FOR ANY SPECIAL, INCIDENTAL,
21 * INDIRECT OR CONSEQUENTIAL DAMAGES OF ANY KIND, OR ANY DAMAGES WHATSOEVER
22 * RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER OR NOT ADVISED OF
23 * THE POSSIBILITY OF DAMAGE, AND ON ANY THEORY OF LIABILITY, ARISING OUT
24 * OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
26 * In addition, the following conditions apply:
28 * 1. Any software that incorporates the SRP authentication technology
29 * must display the following acknowlegment:
30 * "This product uses the 'Secure Remote Password' cryptographic
31 * authentication system developed by Tom Wu (tjw@CS.Stanford.EDU)."
33 * 2. Any software that incorporates all or part of the SRP distribution
34 * itself must also display the following acknowledgment:
35 * "This product includes software developed by Tom Wu and Eugene
36 * Jhong for the SRP Distribution (http://srp.stanford.edu/srp/)."
38 * 3. Redistributions in source or binary form must retain an intact copy
39 * of this copyright notice and list of conditions.
44 #include "t_defines.h"
53 static int witness(BIGNUM *w, const BIGNUM *a, const BIGNUM *a1,
54 const BIGNUM *a1_odd, int k, BN_CTX *ctx, BN_MONT_CTX *mont);
57 * This is the safe prime generation logic.
58 * To generate a safe prime p (where p = 2q+1 and q is prime), we start
59 * with a random odd q that is one bit shorter than the desired length
60 * of p. We use a simple 30-element sieve to filter the values of q
61 * and consider only those that are 11, 23, or 29 (mod 30). (If q were
62 * anything else, either q or p would be divisible by 2, 3, or 5).
63 * For the values of q that are left, we apply the following tests in
69 * apply Fermat test to q (2^q == 2 (mod q))
70 * apply Fermat test to p (2^p == 2 (mod p))
71 * apply real probablistic primality test to q
72 * apply real probablistic primality test to p
74 * A number that passes all these tests is considered a safe prime for
75 * our purposes. The tests are ordered this way for efficiency; the
76 * slower tests are run rarely if ever at all.
83 static int primes[] = { /* All odd primes < 256 */
84 3, 5, 7, 11, 13, 17, 19, 23, 29,
85 31, 37, 41, 43, 47, 53, 59, 61, 67,
86 71, 73, 79, 83, 89, 97, 101, 103,
87 107, 109, 113, 127, 131, 137, 139, 149, 151,
88 157, 163, 167, 173, 179, 181, 191, 193, 197,
89 199, 211, 223, 227, 229, 233, 239, 241, 251
91 static int nprimes = sizeof(primes) / sizeof(int);
94 for(i = 0; i < nprimes; ++i) {
95 if(BigIntegerModInt(x, primes[i]) == 0)
101 /* x + sieve30[x%30] == 11, 23, or 29 (mod 30) */
103 static int sieve30[] =
104 { 11, 10, 9, 8, 7, 6, 5, 4, 3, 2,
105 1, 12, 11, 10, 9, 8, 7, 6, 5, 4,
106 3, 2, 1, 6, 5, 4, 3, 2, 1, 12
109 /* Find a Sophie-Germain prime between "lo" and "hi". NOTE: this is not
110 a "safe prime", but the smaller prime. Take 2q+1 to get the safe prime. */
113 sophie_germain(q, lo, hi)
114 BigInteger q; /* assumed initialized */
119 char parambuf[MAXPARAMLEN];
123 m = BigIntegerFromInt(0);
124 BigIntegerSub(m, hi, lo);
125 i = (BigIntegerBitLen(m) + 7) / 8;
126 t_random(parambuf, i);
127 r = BigIntegerFromBytes(parambuf, i);
128 BigIntegerMod(r, r, m);
130 BigIntegerAdd(q, r, lo);
131 if(BigIntegerModInt(q, 2) == 0)
132 BigIntegerAddInt(q, q, 1); /* make q odd */
134 mod30 = BigIntegerModInt(q, 30); /* mod30 = q % 30 */
137 m = BigIntegerFromInt(2); /* m = 2 */
138 p = BigIntegerFromInt(0);
140 while(BigIntegerCmp(q, hi) < 0) {
141 if(trialdiv(q) < 2) {
142 BigIntegerMulInt(p, q, 2); /* p = 2 * q */
143 BigIntegerAddInt(p, p, 1); /* p += 1 */
144 if(trialdiv(p) < 2) {
145 BigIntegerModExp(r, m, q, q); /* r = 2^q % q */
146 if(BigIntegerCmpInt(r, 2) == 0) { /* if(r == 2) */
147 BigIntegerModExp(r, m, p, p); /* r = 2^p % p */
148 if(BigIntegerCmpInt(r, 2) == 0) { /* if(r == 2) */
149 if(BigIntegerCheckPrime(q) && BigIntegerCheckPrime(p)) {
159 BigIntegerAddInt(q, q, i); /* q += i */
160 mod30 = (mod30 + i) % 30;
163 /* should wrap around on failure */
165 fprintf(stderr, "Prime generation failed!\n");
174 _TYPE( struct t_confent * )
175 t_makeconfent(tc, nsize)
179 BigInteger n, g, q, t, u;
181 t = BigIntegerFromInt(0);
182 u = BigIntegerFromInt(1); /* u = 1 */
183 BigIntegerLShift(t, u, nsize - 2); /* t = 2^(nsize-2) */
184 BigIntegerMulInt(u, t, 2); /* u = 2^(nsize-1) */
186 q = BigIntegerFromInt(0);
187 sophie_germain(q, t, u);
189 n = BigIntegerFromInt(0);
190 BigIntegerMulInt(n, q, 2);
191 BigIntegerAddInt(n, n, 1);
193 /* Look for a generator mod n */
194 g = BigIntegerFromInt(2);
196 BigIntegerModExp(t, g, q, n); /* t = g^q % n */
197 if(BigIntegerCmpInt(t, 1) == 0) /* if(t == 1) */
198 BigIntegerAddInt(g, g, 1); /* ++g */
206 tc->tcbuf.modulus.data = tc->modbuf;
207 tc->tcbuf.modulus.len = BigIntegerToBytes(n, tc->tcbuf.modulus.data);
210 tc->tcbuf.generator.data = tc->genbuf;
211 tc->tcbuf.generator.len = BigIntegerToBytes(g, tc->tcbuf.generator.data);
218 _TYPE( struct t_confent * )
219 t_makeconfent_c(tc, nsize)
223 BigInteger g, n, p, q, j, k, t, u;
227 qsize = nsize - psize;
229 t = BigIntegerFromInt(1); /* t = 1 */
230 u = BigIntegerFromInt(0);
231 BigIntegerLShift(u, t, psize - 3); /* u = t*2^(psize-3) = 2^(psize-3) */
232 BigIntegerMulInt(t, u, 3); /* t = 3*u = 1.5*2^(psize-2) */
233 BigIntegerAdd(u, u, t); /* u += t [u = 2^(psize-1)] */
234 j = BigIntegerFromInt(0);
235 sophie_germain(j, t, u);
237 k = BigIntegerFromInt(0);
240 t = BigIntegerFromInt(1); /* t = 1 */
241 BigIntegerLShift(u, t, qsize - 3); /* u = t*2^(qsize-3) = 2^(qsize-3) */
242 BigIntegerMulInt(t, u, 3); /* t = 3*u = 1.5*2^(qsize-2) */
243 BigIntegerAdd(u, u, t); /* u += t [u = 2^(qsize-1)] */
245 sophie_germain(k, t, u);
247 p = BigIntegerFromInt(0);
248 BigIntegerMulInt(p, j, 2); /* p = 2 * j */
249 BigIntegerAddInt(p, p, 1); /* p += 1 */
251 q = BigIntegerFromInt(0);
252 BigIntegerMulInt(q, k, 2); /* q = 2 * k */
253 BigIntegerAddInt(q, q, 1); /* q += 1 */
255 n = BigIntegerFromInt(0);
256 BigIntegerMul(n, p, q); /* n = p * q */
257 BigIntegerMul(u, j, k); /* u = j * k */
264 g = BigIntegerFromInt(2); /* g = 2 */
266 /* Look for a generator mod n */
268 BigIntegerModExp(t, g, u, n); /* t = g^u % n */
269 if(BigIntegerCmpInt(t, 1) == 0)
270 BigIntegerAddInt(g, g, 1); /* ++g */
278 tc->tcbuf.modulus.data = tc->modbuf;
279 tc->tcbuf.modulus.len = BigIntegerToBytes(n, tc->tcbuf.modulus.data);
282 tc->tcbuf.generator.data = tc->genbuf;
283 tc->tcbuf.generator.len = BigIntegerToBytes(g, tc->tcbuf.generator.data);
290 _TYPE( struct t_confent * )
295 tc->tcbuf.modulus.data = tc->modbuf;
296 tc->tcbuf.modulus.len = 0;
297 tc->tcbuf.generator.data = tc->genbuf;
298 tc->tcbuf.generator.len = 0;
303 t_putconfent(ent, fp)
304 const struct t_confent * ent;
307 char strbuf[MAXB64PARAMLEN];
309 fprintf(fp, "%d:%s:", ent->index,
310 t_tob64(strbuf, ent->modulus.data, ent->modulus.len));
312 t_tob64(strbuf, ent->generator.data, ent->generator.len));
319 return BN_num_bits(b);
323 BigIntegerCheckPrime(n)
326 BN_CTX * ctx = BN_CTX_new();
327 int rv = BN_is_prime(n, 25, NULL, ctx, NULL);
333 BigIntegerModInt(d, m)
337 return BN_mod_word(d, m);
341 BigIntegerMod(result, d, m)
342 BigInteger result, d, m;
344 BN_CTX * ctx = BN_CTX_new();
345 BN_mod(result, d, m, ctx);
350 BigIntegerMul(result, m1, m2)
351 BigInteger result, m1, m2;
353 BN_CTX * ctx = BN_CTX_new();
354 BN_mul(result, m1, m2, ctx);
359 BigIntegerLShift(result, x, bits)
360 BigInteger result, x;
363 BN_lshift(result, x, bits);
366 int BN_is_prime(const BIGNUM *a, int checks, void (*callback)(int,int,void *),
367 BN_CTX *ctx_passed, void *cb_arg)
369 return BN_is_prime_fasttest(a, checks, callback, ctx_passed, cb_arg, 0);
372 int BN_is_prime_fasttest(const BIGNUM *a, int checks,
373 void (*callback)(int,int,void *),
374 BN_CTX *ctx_passed, void *cb_arg,
375 int do_trial_division)
380 BIGNUM *A1, *A1_odd, *check; /* taken from ctx */
381 BN_MONT_CTX *mont = NULL;
382 const BIGNUM *A = NULL;
384 if (checks == BN_prime_checks)
385 checks = BN_prime_checks_for_size(BN_num_bits(a));
387 /* first look for small factors */
390 if (do_trial_division)
392 for (i = 1; i < NUMPRIMES; i++)
393 if (BN_mod_word(a, primes[i]) == 0)
395 if (callback != NULL) callback(1, -1, cb_arg);
398 if (ctx_passed != NULL)
401 if ((ctx=BN_CTX_new()) == NULL)
409 if ((t = BN_CTX_get(ctx)) == NULL) goto err;
416 A1 = BN_CTX_get(ctx);
417 A1_odd = BN_CTX_get(ctx);
418 check = BN_CTX_get(ctx);
419 if (check == NULL) goto err;
421 /* compute A1 := A - 1 */
424 if (!BN_sub_word(A1, 1))
432 /* write A1 as A1_odd * 2^k */
434 while (!BN_is_bit_set(A1, k))
436 if (!BN_rshift(A1_odd, A1, k))
439 /* Montgomery setup for computations mod A */
440 mont = BN_MONT_CTX_new();
443 if (!BN_MONT_CTX_set(mont, A, ctx))
446 for (i = 0; i < checks; i++)
448 if (!BN_pseudo_rand(check, BN_num_bits(A1), 0, 0))
450 if (BN_cmp(check, A1) >= 0)
451 if (!BN_sub(check, check, A1))
453 if (!BN_add_word(check, 1))
455 /* now 1 <= check < A */
457 j = witness(check, A, A1, A1_odd, k, ctx, mont);
458 if (j == -1) goto err;
464 if (callback != NULL) callback(1,i,cb_arg);
471 if (ctx_passed == NULL)
475 BN_MONT_CTX_free(mont);
480 static int witness(BIGNUM *w, const BIGNUM *a, const BIGNUM *a1,
481 const BIGNUM *a1_odd, int k, BN_CTX *ctx, BN_MONT_CTX *mont)
483 if (!BN_mod_exp_mont(w, w, a1_odd, a, ctx, mont)) /* w := w^a1_odd mod a */
486 return 0; /* probably prime */
487 if (BN_cmp(w, a1) == 0)
488 return 0; /* w == -1 (mod a), 'a' is probably prime */
491 if (!BN_mod_mul(w, w, w, a, ctx)) /* w := w^2 mod a */
494 return 1; /* 'a' is composite, otherwise a previous 'w' would
495 * have been == -1 (mod 'a') */
496 if (BN_cmp(w, a1) == 0)
497 return 0; /* w == -1 (mod a), 'a' is probably prime */
499 /* If we get here, 'w' is the (a-1)/2-th power of the original 'w',
500 * and it is neither -1 nor +1 -- so 'a' cannot be prime */
504 int BN_mod_exp_mont(BIGNUM *rr, BIGNUM *a, const BIGNUM *p,
505 const BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *in_mont)
507 int i,j,bits,ret=0,wstart,wend,window,wvalue;
511 BIGNUM val[TABLE_SIZE];
512 BN_MONT_CTX *mont=NULL;
531 if (d == NULL || r == NULL) goto err;
533 /* If this is not done, things will break in the montgomery
540 if ((mont=BN_MONT_CTX_new()) == NULL) goto err;
541 if (!BN_MONT_CTX_set(mont,m,ctx)) goto err;
546 if (BN_ucmp(a,m) >= 0)
548 if (!BN_mod(&(val[0]),a,m,ctx))
554 if (!BN_to_montgomery(&(val[0]),aa,mont,ctx)) goto err; /* 1 */
556 window = BN_window_bits_for_exponent_size(bits);
559 if (!BN_mod_mul_montgomery(d,&(val[0]),&(val[0]),mont,ctx)) goto err; /* 2 */
564 if (!BN_mod_mul_montgomery(&(val[i]),&(val[i-1]),d,mont,ctx))
570 start=1; /* This is used to avoid multiplication etc
571 * when there is only the value '1' in the
573 wvalue=0; /* The 'value' of the window */
574 wstart=bits-1; /* The top bit of the window */
575 wend=0; /* The bottom bit of the window */
577 if (!BN_to_montgomery(r,BN_value_one(),mont,ctx)) goto err;
580 if (BN_is_bit_set(p,wstart) == 0)
584 if (!BN_mod_mul_montgomery(r,r,r,mont,ctx))
587 if (wstart == 0) break;
591 /* We now have wstart on a 'set' bit, we now need to work out
592 * how bit a window to do. To do this we need to scan
593 * forward until the last set bit before the end of the
598 for (i=1; i<window; i++)
600 if (wstart-i < 0) break;
601 if (BN_is_bit_set(p,wstart-i))
609 /* wend is the size of the current window */
611 /* add the 'bytes above' */
615 if (!BN_mod_mul_montgomery(r,r,r,mont,ctx))
619 /* wvalue will be an odd number < 2^window */
620 if (!BN_mod_mul_montgomery(r,r,&(val[wvalue>>1]),mont,ctx))
623 /* move the 'window' down further */
627 if (wstart < 0) break;
629 if (!BN_from_montgomery(rr,r,mont,ctx)) goto err;
632 if ((in_mont == NULL) && (mont != NULL)) BN_MONT_CTX_free(mont);
635 BN_clear_free(&(val[i]));
639 BN_ULONG BN_mod_word(const BIGNUM *a, BN_ULONG w)
649 for (i=a->top-1; i>=0; i--)
652 ret=((ret<<BN_BITS4)|((a->d[i]>>BN_BITS4)&BN_MASK2l))%w;
653 ret=((ret<<BN_BITS4)|(a->d[i]&BN_MASK2l))%w;
655 ret=(BN_ULLONG)(((ret<<(BN_ULLONG)BN_BITS2)|a->d[i])%
659 return((BN_ULONG)ret);
662 static int bnrand(int pseudorand, BIGNUM *rnd, int bits, int top, int bottom)
664 unsigned char *buf=NULL;
665 int ret=0,bit,bytes,mask;
677 buf=(unsigned char *)malloc(bytes);
683 /* make a random number and set the top and bottom bits */
684 /* this ignores the pseudorand flag */
686 t_random(buf, bytes);
697 buf[0]|=(3<<(bit-1));
706 if (bottom) /* set bottom bits to whatever odd is */
708 if (!BN_bin2bn(buf,bytes,rnd)) goto err;
719 /* BN_pseudo_rand is the same as BN_rand, now. */
721 int BN_pseudo_rand(BIGNUM *rnd, int bits, int top, int bottom)
723 return bnrand(1, rnd, bits, top, bottom);
726 #define MONT_WORD /* use the faster word-based algorithm */
728 int BN_mod_mul_montgomery(BIGNUM *r, BIGNUM *a, BIGNUM *b,
729 BN_MONT_CTX *mont, BN_CTX *ctx)
735 tmp = BN_CTX_get(ctx);
736 tmp2 = BN_CTX_get(ctx);
737 if (tmp == NULL || tmp2 == NULL) goto err;
744 if (!BN_sqr(tmp,a,ctx)) goto err;
748 if (!BN_mul(tmp,a,b,ctx)) goto err;
750 /* reduce from aRR to aR */
751 if (!BN_from_montgomery(r,tmp,mont,ctx)) goto err;
758 int BN_from_montgomery(BIGNUM *ret, BIGNUM *a, BN_MONT_CTX *mont,
765 BN_ULONG *ap,*np,*rp,n0,v,*nrp;
766 int al,nl,max,i,x,ri;
769 if ((r = BN_CTX_get(ctx)) == NULL) goto err;
771 if (!BN_copy(r,a)) goto err;
775 /* mont->ri is the size of mont->N in bits (rounded up
777 al=ri=mont->ri/BN_BITS2;
780 if ((al == 0) || (nl == 0)) { r->top=0; return(1); }
782 max=(nl+al+1); /* allow for overflow (no?) XXX */
783 if (bn_wexpand(r,max) == NULL) goto err;
784 if (bn_wexpand(ret,max) == NULL) goto err;
786 r->neg=a->neg^n->neg;
791 /* clear the top words of T */
793 for (i=r->top; i<max; i++) /* memset? XXX */
796 memset(&(r->d[r->top]),0,(max-r->top)*sizeof(BN_ULONG));
803 printf("word BN_from_montgomery %d * %d\n",nl,nl);
812 t1 = rp[0] * (n0 & 0177777);
815 t3 = rp[0] & 0177777;
816 t2 = (t3 * t2) & BN_MASK2;
818 v=bn_mul_add_words(rp,np,nl,(BN_ULONG) t1);
821 v=bn_mul_add_words(rp,np,nl,(rp[0]*n0)&BN_MASK2);
825 if (((nrp[-1]+=v)&BN_MASK2) >= v)
829 if (((++nrp[0])&BN_MASK2) != 0) continue;
830 if (((++nrp[1])&BN_MASK2) != 0) continue;
831 for (x=2; (((++nrp[x])&BN_MASK2) == 0); x++) ;
836 /* mont->ri will be a multiple of the word size */
838 BN_rshift(ret,r,mont->ri);
850 for (i=0; i<al; i+=4)
852 BN_ULONG t1,t2,t3,t4;
867 #else /* !MONT_WORD */
871 t1 = BN_CTX_get(ctx);
872 t2 = BN_CTX_get(ctx);
873 if (t1 == NULL || t2 == NULL) goto err;
875 if (!BN_copy(t1,a)) goto err;
876 BN_mask_bits(t1,mont->ri);
878 if (!BN_mul(t2,t1,&mont->Ni,ctx)) goto err;
879 BN_mask_bits(t2,mont->ri);
881 if (!BN_mul(t1,t2,&mont->N,ctx)) goto err;
882 if (!BN_add(t2,a,t1)) goto err;
883 BN_rshift(ret,t2,mont->ri);
884 #endif /* MONT_WORD */
886 if (BN_ucmp(ret, &(mont->N)) >= 0)
888 BN_usub(ret,ret,&(mont->N));
896 void BN_MONT_CTX_init(BN_MONT_CTX *ctx)
905 BN_MONT_CTX *BN_MONT_CTX_new(void)
909 if ((ret=(BN_MONT_CTX *)malloc(sizeof(BN_MONT_CTX))) == NULL)
912 BN_MONT_CTX_init(ret);
913 ret->flags=BN_FLG_MALLOCED;
917 void BN_MONT_CTX_free(BN_MONT_CTX *mont)
922 BN_free(&(mont->RR));
924 BN_free(&(mont->Ni));
925 if (mont->flags & BN_FLG_MALLOCED)
929 int BN_MONT_CTX_set(BN_MONT_CTX *mont, const BIGNUM *mod, BN_CTX *ctx)
934 R= &(mont->RR); /* grab RR as a temp */
935 BN_copy(&(mont->N),mod); /* Set N */
942 mont->ri=(BN_num_bits(mod)+(BN_BITS2-1))/BN_BITS2*BN_BITS2;
944 BN_set_bit(R,BN_BITS2); /* R */
946 buf[0]=mod->d[0]; /* tmod = N mod word size */
953 if ((BN_mod_inverse(&Ri,R,&tmod,ctx)) == NULL)
955 BN_lshift(&Ri,&Ri,BN_BITS2); /* R*Ri */
956 if (!BN_is_zero(&Ri))
958 else /* if N mod word size == 1 */
959 BN_set_word(&Ri,BN_MASK2); /* Ri-- (mod word size) */
960 BN_div(&Ri,NULL,&Ri,&tmod,ctx); /* Ni = (R*Ri-1)/N,
961 * keep only least significant word: */
965 #else /* !MONT_WORD */
966 { /* bignum version */
967 mont->ri=BN_num_bits(mod);
969 BN_set_bit(R,mont->ri); /* R = 2^ri */
971 if ((BN_mod_inverse(&Ri,R,mod,ctx)) == NULL)
973 BN_lshift(&Ri,&Ri,mont->ri); /* R*Ri */
975 /* Ni = (R*Ri-1) / N */
976 BN_div(&(mont->Ni),NULL,&Ri,mod,ctx);
981 /* setup RR for conversions */
982 BN_zero(&(mont->RR));
983 BN_set_bit(&(mont->RR),mont->ri*2);
984 BN_mod(&(mont->RR),&(mont->RR),&(mont->N),ctx);
991 BIGNUM *BN_value_one(void)
993 static BN_ULONG data_one=1L;
994 static BIGNUM const_one={&data_one,1,1,0};
999 /* solves ax == 1 (mod n) */
1000 BIGNUM *BN_mod_inverse(BIGNUM *in, BIGNUM *a, const BIGNUM *n, BN_CTX *ctx)
1002 BIGNUM *A,*B,*X,*Y,*M,*D,*R=NULL;
1003 BIGNUM *T,*ret=NULL;
1010 A = BN_CTX_get(ctx);
1011 B = BN_CTX_get(ctx);
1012 X = BN_CTX_get(ctx);
1013 D = BN_CTX_get(ctx);
1014 M = BN_CTX_get(ctx);
1015 Y = BN_CTX_get(ctx);
1016 if (Y == NULL) goto err;
1022 if (R == NULL) goto err;
1026 if (BN_copy(A,a) == NULL) goto err;
1027 if (BN_copy(B,n) == NULL) goto err;
1030 while (!BN_is_zero(B))
1032 if (!BN_div(D,M,A,B,ctx)) goto err;
1036 /* T has a struct, M does not */
1038 if (!BN_mul(T,D,X,ctx)) goto err;
1039 if (!BN_add(T,T,Y)) goto err;
1047 if (!BN_sub(Y,n,Y)) goto err;
1051 { if (!BN_mod(R,Y,n,ctx)) goto err; }
1058 if ((ret == NULL) && (in == NULL)) BN_free(R);
1063 int BN_set_bit(BIGNUM *a, int n)
1071 if (bn_wexpand(a,i+1) == NULL) return(0);
1072 for(k=a->top; k<i+1; k++)
1077 a->d[i]|=(((BN_ULONG)1)<<j);