projects / openwrt / staging / chunkeey.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
history | raw | HEAD
kernel: fq_codel: dont reinit flow state
[openwrt/staging/chunkeey.git] / package / ead / src / tinysrp / t_conf.c
1 /*
2 * Copyright (c) 1997-1999 The Stanford SRP Authentication Project
3 * All Rights Reserved.
4 *
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:
12 *
13 * The above copyright notice and this permission notice shall be
14 * included in all copies or substantial portions of the Software.
15 *
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.
19 *
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.
25 *
26 * In addition, the following conditions apply:
27 *
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)."
32 *
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/)."
37 *
38 * 3. Redistributions in source or binary form must retain an intact copy
39 * of this copyright notice and list of conditions.
40 */
41
42 #include <stdio.h>
43
44 #include "t_defines.h"
45 #include "t_pwd.h"
46 #include "t_read.h"
47 #include "bn.h"
48 #include "bn_lcl.h"
49 #include "bn_prime.h"
50
51 #define TABLE_SIZE 32
52
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);
55
56 /*
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
64 * this order:
65 *
66 * trial divide q
67 * let p = 2q + 1
68 * trial divide p
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
73 *
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.
77 */
78
79 static int
80 trialdiv(x)
81 const BigInteger x;
82 {
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
90 };
91 static int nprimes = sizeof(primes) / sizeof(int);
92 int i;
93
94 for(i = 0; i < nprimes; ++i) {
95 if(BigIntegerModInt(x, primes[i]) == 0)
96 return primes[i];
97 }
98 return 1;
99 }
100
101 /* x + sieve30[x%30] == 11, 23, or 29 (mod 30) */
102
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
107 };
108
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. */
111
112 static void
113 sophie_germain(q, lo, hi)
114 BigInteger q; /* assumed initialized */
115 const BigInteger lo;
116 const BigInteger hi;
117 {
118 BigInteger m, p, r;
119 char parambuf[MAXPARAMLEN];
120 int foundprime = 0;
121 int i, mod30;
122
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);
129
130 BigIntegerAdd(q, r, lo);
131 if(BigIntegerModInt(q, 2) == 0)
132 BigIntegerAddInt(q, q, 1); /* make q odd */
133
134 mod30 = BigIntegerModInt(q, 30); /* mod30 = q % 30 */
135
136 BigIntegerFree(m);
137 m = BigIntegerFromInt(2); /* m = 2 */
138 p = BigIntegerFromInt(0);
139
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)) {
150 ++foundprime;
151 break;
152 }
153 }
154 }
155 }
156 }
157
158 i = sieve30[mod30];
159 BigIntegerAddInt(q, q, i); /* q += i */
160 mod30 = (mod30 + i) % 30;
161 }
162
163 /* should wrap around on failure */
164 if(!foundprime) {
165 fprintf(stderr, "Prime generation failed!\n");
166 exit(1);
167 }
168
169 BigIntegerFree(r);
170 BigIntegerFree(m);
171 BigIntegerFree(p);
172 }
173
174 _TYPE( struct t_confent * )
175 t_makeconfent(tc, nsize)
176 struct t_conf * tc;
177 int nsize;
178 {
179 BigInteger n, g, q, t, u;
180
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) */
185
186 q = BigIntegerFromInt(0);
187 sophie_germain(q, t, u);
188
189 n = BigIntegerFromInt(0);
190 BigIntegerMulInt(n, q, 2);
191 BigIntegerAddInt(n, n, 1);
192
193 /* Look for a generator mod n */
194 g = BigIntegerFromInt(2);
195 while(1) {
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 */
199 else
200 break;
201 }
202 BigIntegerFree(t);
203 BigIntegerFree(u);
204 BigIntegerFree(q);
205
206 tc->tcbuf.modulus.data = tc->modbuf;
207 tc->tcbuf.modulus.len = BigIntegerToBytes(n, tc->tcbuf.modulus.data);
208 BigIntegerFree(n);
209
210 tc->tcbuf.generator.data = tc->genbuf;
211 tc->tcbuf.generator.len = BigIntegerToBytes(g, tc->tcbuf.generator.data);
212 BigIntegerFree(g);
213
214 tc->tcbuf.index = 1;
215 return &tc->tcbuf;
216 }
217
218 _TYPE( struct t_confent * )
219 t_makeconfent_c(tc, nsize)
220 struct t_conf * tc;
221 int nsize;
222 {
223 BigInteger g, n, p, q, j, k, t, u;
224 int psize, qsize;
225
226 psize = nsize / 2;
227 qsize = nsize - psize;
228
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);
236
237 k = BigIntegerFromInt(0);
238 if(qsize != psize) {
239 BigIntegerFree(t);
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)] */
244 }
245 sophie_germain(k, t, u);
246
247 p = BigIntegerFromInt(0);
248 BigIntegerMulInt(p, j, 2); /* p = 2 * j */
249 BigIntegerAddInt(p, p, 1); /* p += 1 */
250
251 q = BigIntegerFromInt(0);
252 BigIntegerMulInt(q, k, 2); /* q = 2 * k */
253 BigIntegerAddInt(q, q, 1); /* q += 1 */
254
255 n = BigIntegerFromInt(0);
256 BigIntegerMul(n, p, q); /* n = p * q */
257 BigIntegerMul(u, j, k); /* u = j * k */
258
259 BigIntegerFree(p);
260 BigIntegerFree(q);
261 BigIntegerFree(j);
262 BigIntegerFree(k);
263
264 g = BigIntegerFromInt(2); /* g = 2 */
265
266 /* Look for a generator mod n */
267 while(1) {
268 BigIntegerModExp(t, g, u, n); /* t = g^u % n */
269 if(BigIntegerCmpInt(t, 1) == 0)
270 BigIntegerAddInt(g, g, 1); /* ++g */
271 else
272 break;
273 }
274
275 BigIntegerFree(u);
276 BigIntegerFree(t);
277
278 tc->tcbuf.modulus.data = tc->modbuf;
279 tc->tcbuf.modulus.len = BigIntegerToBytes(n, tc->tcbuf.modulus.data);
280 BigIntegerFree(n);
281
282 tc->tcbuf.generator.data = tc->genbuf;
283 tc->tcbuf.generator.len = BigIntegerToBytes(g, tc->tcbuf.generator.data);
284 BigIntegerFree(g);
285
286 tc->tcbuf.index = 1;
287 return &tc->tcbuf;
288 }
289
290 _TYPE( struct t_confent * )
291 t_newconfent(tc)
292 struct t_conf * tc;
293 {
294 tc->tcbuf.index = 0;
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;
299 return &tc->tcbuf;
300 }
301
302 _TYPE( void )
303 t_putconfent(ent, fp)
304 const struct t_confent * ent;
305 FILE * fp;
306 {
307 char strbuf[MAXB64PARAMLEN];
308
309 fprintf(fp, "%d:%s:", ent->index,
310 t_tob64(strbuf, ent->modulus.data, ent->modulus.len));
311 fprintf(fp, "%s\n",
312 t_tob64(strbuf, ent->generator.data, ent->generator.len));
313 }
314
315 int
316 BigIntegerBitLen(b)
317 BigInteger b;
318 {
319 return BN_num_bits(b);
320 }
321
322 int
323 BigIntegerCheckPrime(n)
324 BigInteger n;
325 {
326 BN_CTX * ctx = BN_CTX_new();
327 int rv = BN_is_prime(n, 25, NULL, ctx, NULL);
328 BN_CTX_free(ctx);
329 return rv;
330 }
331
332 unsigned int
333 BigIntegerModInt(d, m)
334 BigInteger d;
335 unsigned int m;
336 {
337 return BN_mod_word(d, m);
338 }
339
340 void
341 BigIntegerMod(result, d, m)
342 BigInteger result, d, m;
343 {
344 BN_CTX * ctx = BN_CTX_new();
345 BN_mod(result, d, m, ctx);
346 BN_CTX_free(ctx);
347 }
348
349 void
350 BigIntegerMul(result, m1, m2)
351 BigInteger result, m1, m2;
352 {
353 BN_CTX * ctx = BN_CTX_new();
354 BN_mul(result, m1, m2, ctx);
355 BN_CTX_free(ctx);
356 }
357
358 void
359 BigIntegerLShift(result, x, bits)
360 BigInteger result, x;
361 unsigned int bits;
362 {
363 BN_lshift(result, x, bits);
364 }
365
366 int BN_is_prime(const BIGNUM *a, int checks, void (*callback)(int,int,void *),
367 BN_CTX *ctx_passed, void *cb_arg)
368 {
369 return BN_is_prime_fasttest(a, checks, callback, ctx_passed, cb_arg, 0);
370 }
371
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)
376 {
377 int i, j, ret = -1;
378 int k;
379 BN_CTX *ctx = NULL;
380 BIGNUM *A1, *A1_odd, *check; /* taken from ctx */
381 BN_MONT_CTX *mont = NULL;
382 const BIGNUM *A = NULL;
383
384 if (checks == BN_prime_checks)
385 checks = BN_prime_checks_for_size(BN_num_bits(a));
386
387 /* first look for small factors */
388 if (!BN_is_odd(a))
389 return(0);
390 if (do_trial_division)
391 {
392 for (i = 1; i < NUMPRIMES; i++)
393 if (BN_mod_word(a, primes[i]) == 0)
394 return 0;
395 if (callback != NULL) callback(1, -1, cb_arg);
396 }
397
398 if (ctx_passed != NULL)
399 ctx = ctx_passed;
400 else
401 if ((ctx=BN_CTX_new()) == NULL)
402 goto err;
403 BN_CTX_start(ctx);
404
405 /* A := abs(a) */
406 if (a->neg)
407 {
408 BIGNUM *t;
409 if ((t = BN_CTX_get(ctx)) == NULL) goto err;
410 BN_copy(t, a);
411 t->neg = 0;
412 A = t;
413 }
414 else
415 A = a;
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;
420
421 /* compute A1 := A - 1 */
422 if (!BN_copy(A1, A))
423 goto err;
424 if (!BN_sub_word(A1, 1))
425 goto err;
426 if (BN_is_zero(A1))
427 {
428 ret = 0;
429 goto err;
430 }
431
432 /* write A1 as A1_odd * 2^k */
433 k = 1;
434 while (!BN_is_bit_set(A1, k))
435 k++;
436 if (!BN_rshift(A1_odd, A1, k))
437 goto err;
438
439 /* Montgomery setup for computations mod A */
440 mont = BN_MONT_CTX_new();
441 if (mont == NULL)
442 goto err;
443 if (!BN_MONT_CTX_set(mont, A, ctx))
444 goto err;
445
446 for (i = 0; i < checks; i++)
447 {
448 if (!BN_pseudo_rand(check, BN_num_bits(A1), 0, 0))
449 goto err;
450 if (BN_cmp(check, A1) >= 0)
451 if (!BN_sub(check, check, A1))
452 goto err;
453 if (!BN_add_word(check, 1))
454 goto err;
455 /* now 1 <= check < A */
456
457 j = witness(check, A, A1, A1_odd, k, ctx, mont);
458 if (j == -1) goto err;
459 if (j)
460 {
461 ret=0;
462 goto err;
463 }
464 if (callback != NULL) callback(1,i,cb_arg);
465 }
466 ret=1;
467 err:
468 if (ctx != NULL)
469 {
470 BN_CTX_end(ctx);
471 if (ctx_passed == NULL)
472 BN_CTX_free(ctx);
473 }
474 if (mont != NULL)
475 BN_MONT_CTX_free(mont);
476
477 return(ret);
478 }
479
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)
482 {
483 if (!BN_mod_exp_mont(w, w, a1_odd, a, ctx, mont)) /* w := w^a1_odd mod a */
484 return -1;
485 if (BN_is_one(w))
486 return 0; /* probably prime */
487 if (BN_cmp(w, a1) == 0)
488 return 0; /* w == -1 (mod a), 'a' is probably prime */
489 while (--k)
490 {
491 if (!BN_mod_mul(w, w, w, a, ctx)) /* w := w^2 mod a */
492 return -1;
493 if (BN_is_one(w))
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 */
498 }
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 */
501 return 1;
502 }
503
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)
506 {
507 int i,j,bits,ret=0,wstart,wend,window,wvalue;
508 int start=1,ts=0;
509 BIGNUM *d,*r;
510 BIGNUM *aa;
511 BIGNUM val[TABLE_SIZE];
512 BN_MONT_CTX *mont=NULL;
513
514 bn_check_top(a);
515 bn_check_top(p);
516 bn_check_top(m);
517
518 if (!(m->d[0] & 1))
519 {
520 return(0);
521 }
522 bits=BN_num_bits(p);
523 if (bits == 0)
524 {
525 BN_one(rr);
526 return(1);
527 }
528 BN_CTX_start(ctx);
529 d = BN_CTX_get(ctx);
530 r = BN_CTX_get(ctx);
531 if (d == NULL || r == NULL) goto err;
532
533 /* If this is not done, things will break in the montgomery
534 * part */
535
536 if (in_mont != NULL)
537 mont=in_mont;
538 else
539 {
540 if ((mont=BN_MONT_CTX_new()) == NULL) goto err;
541 if (!BN_MONT_CTX_set(mont,m,ctx)) goto err;
542 }
543
544 BN_init(&val[0]);
545 ts=1;
546 if (BN_ucmp(a,m) >= 0)
547 {
548 if (!BN_mod(&(val[0]),a,m,ctx))
549 goto err;
550 aa= &(val[0]);
551 }
552 else
553 aa=a;
554 if (!BN_to_montgomery(&(val[0]),aa,mont,ctx)) goto err; /* 1 */
555
556 window = BN_window_bits_for_exponent_size(bits);
557 if (window > 1)
558 {
559 if (!BN_mod_mul_montgomery(d,&(val[0]),&(val[0]),mont,ctx)) goto err; /* 2 */
560 j=1<<(window-1);
561 for (i=1; i<j; i++)
562 {
563 BN_init(&(val[i]));
564 if (!BN_mod_mul_montgomery(&(val[i]),&(val[i-1]),d,mont,ctx))
565 goto err;
566 }
567 ts=i;
568 }
569
570 start=1; /* This is used to avoid multiplication etc
571 * when there is only the value '1' in the
572 * buffer. */
573 wvalue=0; /* The 'value' of the window */
574 wstart=bits-1; /* The top bit of the window */
575 wend=0; /* The bottom bit of the window */
576
577 if (!BN_to_montgomery(r,BN_value_one(),mont,ctx)) goto err;
578 for (;;)
579 {
580 if (BN_is_bit_set(p,wstart) == 0)
581 {
582 if (!start)
583 {
584 if (!BN_mod_mul_montgomery(r,r,r,mont,ctx))
585 goto err;
586 }
587 if (wstart == 0) break;
588 wstart--;
589 continue;
590 }
591 /* We now have wstart on a 'set' bit, we now need to work out
592 * how bit a window to do. To do this we need to scan
593 * forward until the last set bit before the end of the
594 * window */
595 j=wstart;
596 wvalue=1;
597 wend=0;
598 for (i=1; i<window; i++)
599 {
600 if (wstart-i < 0) break;
601 if (BN_is_bit_set(p,wstart-i))
602 {
603 wvalue<<=(i-wend);
604 wvalue|=1;
605 wend=i;
606 }
607 }
608
609 /* wend is the size of the current window */
610 j=wend+1;
611 /* add the 'bytes above' */
612 if (!start)
613 for (i=0; i<j; i++)
614 {
615 if (!BN_mod_mul_montgomery(r,r,r,mont,ctx))
616 goto err;
617 }
618
619 /* wvalue will be an odd number < 2^window */
620 if (!BN_mod_mul_montgomery(r,r,&(val[wvalue>>1]),mont,ctx))
621 goto err;
622
623 /* move the 'window' down further */
624 wstart-=wend+1;
625 wvalue=0;
626 start=0;
627 if (wstart < 0) break;
628 }
629 if (!BN_from_montgomery(rr,r,mont,ctx)) goto err;
630 ret=1;
631 err:
632 if ((in_mont == NULL) && (mont != NULL)) BN_MONT_CTX_free(mont);
633 BN_CTX_end(ctx);
634 for (i=0; i<ts; i++)
635 BN_clear_free(&(val[i]));
636 return(ret);
637 }
638
639 BN_ULONG BN_mod_word(const BIGNUM *a, BN_ULONG w)
640 {
641 #ifndef BN_LLONG
642 BN_ULONG ret=0;
643 #else
644 BN_ULLONG ret=0;
645 #endif
646 int i;
647
648 w&=BN_MASK2;
649 for (i=a->top-1; i>=0; i--)
650 {
651 #ifndef BN_LLONG
652 ret=((ret<<BN_BITS4)|((a->d[i]>>BN_BITS4)&BN_MASK2l))%w;
653 ret=((ret<<BN_BITS4)|(a->d[i]&BN_MASK2l))%w;
654 #else
655 ret=(BN_ULLONG)(((ret<<(BN_ULLONG)BN_BITS2)|a->d[i])%
656 (BN_ULLONG)w);
657 #endif
658 }
659 return((BN_ULONG)ret);
660 }
661
662 static int bnrand(int pseudorand, BIGNUM *rnd, int bits, int top, int bottom)
663 {
664 unsigned char *buf=NULL;
665 int ret=0,bit,bytes,mask;
666
667 if (bits == 0)
668 {
669 BN_zero(rnd);
670 return 1;
671 }
672
673 bytes=(bits+7)/8;
674 bit=(bits-1)%8;
675 mask=0xff<<bit;
676
677 buf=(unsigned char *)malloc(bytes);
678 if (buf == NULL)
679 {
680 goto err;
681 }
682
683 /* make a random number and set the top and bottom bits */
684 /* this ignores the pseudorand flag */
685
686 t_random(buf, bytes);
687
688 if (top)
689 {
690 if (bit == 0)
691 {
692 buf[0]=1;
693 buf[1]|=0x80;
694 }
695 else
696 {
697 buf[0]|=(3<<(bit-1));
698 buf[0]&= ~(mask<<1);
699 }
700 }
701 else
702 {
703 buf[0]|=(1<<bit);
704 buf[0]&= ~(mask<<1);
705 }
706 if (bottom) /* set bottom bits to whatever odd is */
707 buf[bytes-1]|=1;
708 if (!BN_bin2bn(buf,bytes,rnd)) goto err;
709 ret=1;
710 err:
711 if (buf != NULL)
712 {
713 memset(buf,0,bytes);
714 free(buf);
715 }
716 return(ret);
717 }
718
719 /* BN_pseudo_rand is the same as BN_rand, now. */
720
721 int BN_pseudo_rand(BIGNUM *rnd, int bits, int top, int bottom)
722 {
723 return bnrand(1, rnd, bits, top, bottom);
724 }
725
726 #define MONT_WORD /* use the faster word-based algorithm */
727
728 int BN_mod_mul_montgomery(BIGNUM *r, BIGNUM *a, BIGNUM *b,
729 BN_MONT_CTX *mont, BN_CTX *ctx)
730 {
731 BIGNUM *tmp,*tmp2;
732 int ret=0;
733
734 BN_CTX_start(ctx);
735 tmp = BN_CTX_get(ctx);
736 tmp2 = BN_CTX_get(ctx);
737 if (tmp == NULL || tmp2 == NULL) goto err;
738
739 bn_check_top(tmp);
740 bn_check_top(tmp2);
741
742 if (a == b)
743 {
744 if (!BN_sqr(tmp,a,ctx)) goto err;
745 }
746 else
747 {
748 if (!BN_mul(tmp,a,b,ctx)) goto err;
749 }
750 /* reduce from aRR to aR */
751 if (!BN_from_montgomery(r,tmp,mont,ctx)) goto err;
752 ret=1;
753 err:
754 BN_CTX_end(ctx);
755 return(ret);
756 }
757
758 int BN_from_montgomery(BIGNUM *ret, BIGNUM *a, BN_MONT_CTX *mont,
759 BN_CTX *ctx)
760 {
761 int retn=0;
762
763 #ifdef MONT_WORD
764 BIGNUM *n,*r;
765 BN_ULONG *ap,*np,*rp,n0,v,*nrp;
766 int al,nl,max,i,x,ri;
767
768 BN_CTX_start(ctx);
769 if ((r = BN_CTX_get(ctx)) == NULL) goto err;
770
771 if (!BN_copy(r,a)) goto err;
772 n= &(mont->N);
773
774 ap=a->d;
775 /* mont->ri is the size of mont->N in bits (rounded up
776 to the word size) */
777 al=ri=mont->ri/BN_BITS2;
778
779 nl=n->top;
780 if ((al == 0) || (nl == 0)) { r->top=0; return(1); }
781
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;
785
786 r->neg=a->neg^n->neg;
787 np=n->d;
788 rp=r->d;
789 nrp= &(r->d[nl]);
790
791 /* clear the top words of T */
792 #if 1
793 for (i=r->top; i<max; i++) /* memset? XXX */
794 r->d[i]=0;
795 #else
796 memset(&(r->d[r->top]),0,(max-r->top)*sizeof(BN_ULONG));
797 #endif
798
799 r->top=max;
800 n0=mont->n0;
801
802 #ifdef BN_COUNT
803 printf("word BN_from_montgomery %d * %d\n",nl,nl);
804 #endif
805 for (i=0; i<nl; i++)
806 {
807 #ifdef __TANDEM
808 {
809 long long t1;
810 long long t2;
811 long long t3;
812 t1 = rp[0] * (n0 & 0177777);
813 t2 = 037777600000l;
814 t2 = n0 & t2;
815 t3 = rp[0] & 0177777;
816 t2 = (t3 * t2) & BN_MASK2;
817 t1 = t1 + t2;
818 v=bn_mul_add_words(rp,np,nl,(BN_ULONG) t1);
819 }
820 #else
821 v=bn_mul_add_words(rp,np,nl,(rp[0]*n0)&BN_MASK2);
822 #endif
823 nrp++;
824 rp++;
825 if (((nrp[-1]+=v)&BN_MASK2) >= v)
826 continue;
827 else
828 {
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++) ;
832 }
833 }
834 bn_fix_top(r);
835
836 /* mont->ri will be a multiple of the word size */
837 #if 0
838 BN_rshift(ret,r,mont->ri);
839 #else
840 ret->neg = r->neg;
841 x=ri;
842 rp=ret->d;
843 ap= &(r->d[x]);
844 if (r->top < x)
845 al=0;
846 else
847 al=r->top-x;
848 ret->top=al;
849 al-=4;
850 for (i=0; i<al; i+=4)
851 {
852 BN_ULONG t1,t2,t3,t4;
853
854 t1=ap[i+0];
855 t2=ap[i+1];
856 t3=ap[i+2];
857 t4=ap[i+3];
858 rp[i+0]=t1;
859 rp[i+1]=t2;
860 rp[i+2]=t3;
861 rp[i+3]=t4;
862 }
863 al+=4;
864 for (; i<al; i++)
865 rp[i]=ap[i];
866 #endif
867 #else /* !MONT_WORD */
868 BIGNUM *t1,*t2;
869
870 BN_CTX_start(ctx);
871 t1 = BN_CTX_get(ctx);
872 t2 = BN_CTX_get(ctx);
873 if (t1 == NULL || t2 == NULL) goto err;
874
875 if (!BN_copy(t1,a)) goto err;
876 BN_mask_bits(t1,mont->ri);
877
878 if (!BN_mul(t2,t1,&mont->Ni,ctx)) goto err;
879 BN_mask_bits(t2,mont->ri);
880
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 */
885
886 if (BN_ucmp(ret, &(mont->N)) >= 0)
887 {
888 BN_usub(ret,ret,&(mont->N));
889 }
890 retn=1;
891 err:
892 BN_CTX_end(ctx);
893 return(retn);
894 }
895
896 void BN_MONT_CTX_init(BN_MONT_CTX *ctx)
897 {
898 ctx->ri=0;
899 BN_init(&(ctx->RR));
900 BN_init(&(ctx->N));
901 BN_init(&(ctx->Ni));
902 ctx->flags=0;
903 }
904
905 BN_MONT_CTX *BN_MONT_CTX_new(void)
906 {
907 BN_MONT_CTX *ret;
908
909 if ((ret=(BN_MONT_CTX *)malloc(sizeof(BN_MONT_CTX))) == NULL)
910 return(NULL);
911
912 BN_MONT_CTX_init(ret);
913 ret->flags=BN_FLG_MALLOCED;
914 return(ret);
915 }
916
917 void BN_MONT_CTX_free(BN_MONT_CTX *mont)
918 {
919 if(mont == NULL)
920 return;
921
922 BN_free(&(mont->RR));
923 BN_free(&(mont->N));
924 BN_free(&(mont->Ni));
925 if (mont->flags & BN_FLG_MALLOCED)
926 free(mont);
927 }
928
929 int BN_MONT_CTX_set(BN_MONT_CTX *mont, const BIGNUM *mod, BN_CTX *ctx)
930 {
931 BIGNUM Ri,*R;
932
933 BN_init(&Ri);
934 R= &(mont->RR); /* grab RR as a temp */
935 BN_copy(&(mont->N),mod); /* Set N */
936
937 #ifdef MONT_WORD
938 {
939 BIGNUM tmod;
940 BN_ULONG buf[2];
941
942 mont->ri=(BN_num_bits(mod)+(BN_BITS2-1))/BN_BITS2*BN_BITS2;
943 BN_zero(R);
944 BN_set_bit(R,BN_BITS2); /* R */
945
946 buf[0]=mod->d[0]; /* tmod = N mod word size */
947 buf[1]=0;
948 tmod.d=buf;
949 tmod.top=1;
950 tmod.dmax=2;
951 tmod.neg=mod->neg;
952 /* Ri = R^-1 mod N*/
953 if ((BN_mod_inverse(&Ri,R,&tmod,ctx)) == NULL)
954 goto err;
955 BN_lshift(&Ri,&Ri,BN_BITS2); /* R*Ri */
956 if (!BN_is_zero(&Ri))
957 BN_sub_word(&Ri,1);
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: */
962 mont->n0=Ri.d[0];
963 BN_free(&Ri);
964 }
965 #else /* !MONT_WORD */
966 { /* bignum version */
967 mont->ri=BN_num_bits(mod);
968 BN_zero(R);
969 BN_set_bit(R,mont->ri); /* R = 2^ri */
970 /* Ri = R^-1 mod N*/
971 if ((BN_mod_inverse(&Ri,R,mod,ctx)) == NULL)
972 goto err;
973 BN_lshift(&Ri,&Ri,mont->ri); /* R*Ri */
974 BN_sub_word(&Ri,1);
975 /* Ni = (R*Ri-1) / N */
976 BN_div(&(mont->Ni),NULL,&Ri,mod,ctx);
977 BN_free(&Ri);
978 }
979 #endif
980
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);
985
986 return(1);
987 err:
988 return(0);
989 }
990
991 BIGNUM *BN_value_one(void)
992 {
993 static BN_ULONG data_one=1L;
994 static BIGNUM const_one={&data_one,1,1,0};
995
996 return(&const_one);
997 }
998
999 /* solves ax == 1 (mod n) */
1000 BIGNUM *BN_mod_inverse(BIGNUM *in, BIGNUM *a, const BIGNUM *n, BN_CTX *ctx)
1001 {
1002 BIGNUM *A,*B,*X,*Y,*M,*D,*R=NULL;
1003 BIGNUM *T,*ret=NULL;
1004 int sign;
1005
1006 bn_check_top(a);
1007 bn_check_top(n);
1008
1009 BN_CTX_start(ctx);
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;
1017
1018 if (in == NULL)
1019 R=BN_new();
1020 else
1021 R=in;
1022 if (R == NULL) goto err;
1023
1024 BN_zero(X);
1025 BN_one(Y);
1026 if (BN_copy(A,a) == NULL) goto err;
1027 if (BN_copy(B,n) == NULL) goto err;
1028 sign=1;
1029
1030 while (!BN_is_zero(B))
1031 {
1032 if (!BN_div(D,M,A,B,ctx)) goto err;
1033 T=A;
1034 A=B;
1035 B=M;
1036 /* T has a struct, M does not */
1037
1038 if (!BN_mul(T,D,X,ctx)) goto err;
1039 if (!BN_add(T,T,Y)) goto err;
1040 M=Y;
1041 Y=X;
1042 X=T;
1043 sign= -sign;
1044 }
1045 if (sign < 0)
1046 {
1047 if (!BN_sub(Y,n,Y)) goto err;
1048 }
1049
1050 if (BN_is_one(A))
1051 { if (!BN_mod(R,Y,n,ctx)) goto err; }
1052 else
1053 {
1054 goto err;
1055 }
1056 ret=R;
1057 err:
1058 if ((ret == NULL) && (in == NULL)) BN_free(R);
1059 BN_CTX_end(ctx);
1060 return(ret);
1061 }
1062
1063 int BN_set_bit(BIGNUM *a, int n)
1064 {
1065 int i,j,k;
1066
1067 i=n/BN_BITS2;
1068 j=n%BN_BITS2;
1069 if (a->top <= i)
1070 {
1071 if (bn_wexpand(a,i+1) == NULL) return(0);
1072 for(k=a->top; k<i+1; k++)
1073 a->d[k]=0;
1074 a->top=i+1;
1075 }
1076
1077 a->d[i]|=(((BN_ULONG)1)<<j);
1078 return(1);
1079 }
1080
Staging tree of Christian Lamparter