Root/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
53static 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
79static int
80trialdiv(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
103static 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
112static void
113sophie_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 * )
175t_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 * )
219t_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 * )
291t_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 )
303t_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
315int
316BigIntegerBitLen(b)
317     BigInteger b;
318{
319  return BN_num_bits(b);
320}
321
322int
323BigIntegerCheckPrime(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
332unsigned int
333BigIntegerModInt(d, m)
334     BigInteger d;
335     unsigned int m;
336{
337  return BN_mod_word(d, m);
338}
339
340void
341BigIntegerMod(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
349void
350BigIntegerMul(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
358void
359BigIntegerLShift(result, x, bits)
360     BigInteger result, x;
361     unsigned int bits;
362{
363  BN_lshift(result, x, bits);
364}
365
366int 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
372int 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;
467err:
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
480static 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
504int 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;
631err:
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
639BN_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
662static 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;
710err:
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
721int 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
728int 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;
753err:
754    BN_CTX_end(ctx);
755    return(ret);
756    }
757
758int 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
896void 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
905BN_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
917void 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
929int 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);
987err:
988    return(0);
989    }
990
991BIGNUM *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) */
1000BIGNUM *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;
1057err:
1058    if ((ret == NULL) && (in == NULL)) BN_free(R);
1059    BN_CTX_end(ctx);
1060    return(ret);
1061    }
1062
1063int 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
1081

Archive Download this file

Branches:
backfire
history
master
release_2010-11-17
release_2010-12-14
release_2011-02-23
release_2011-05-28
release_2011-08-27
release_2011-11-13
release_2012-03-18
release_2012-04-09
release_2012-10-11
uclibc_nptl



interactive