Fix bntest.c problem -- one of the primes got lost
[openssl.git] / crypto / bn / bn_modfs.c
1 /*
2  *
3  *      bn_modfs.c
4  *
5  *      Some Modular Arithmetic Functions.
6  *
7  *      Copyright (C) Lenka Fibikova 2000
8  *
9  *
10  */
11
12
13 #include <stdio.h>
14 #include <stdlib.h>
15 #include <assert.h>
16
17 #include "bn_modfs.h"
18
19 #define MAX_ROUNDS      10
20
21
22 int BN_mod_sqrt(BIGNUM *x, BIGNUM *a, BIGNUM *p, BN_CTX *ctx) 
23 /* x^2 = a (mod p) */
24         {
25         int ret;
26         BIGNUM *n0, *n1, *r, *b, *m;
27         int max;
28
29         assert(x != NULL && a != NULL && p != NULL && ctx != NULL);
30         assert(BN_cmp(a, p) < 0);
31
32         ret = BN_kronecker(a, p, ctx);
33         if (ret < 0 || ret > 1) return 0;
34         if (ret == 0)
35                 {
36                 if (!BN_zero(x)) return 0;
37                 return 1;
38                 }
39
40         BN_CTX_start(ctx);
41         n0 = BN_CTX_get(ctx);
42         n1 = BN_CTX_get(ctx);
43         if (n1 == NULL) goto err;
44
45         if ((r = BN_new()) == NULL) goto err;
46         if ((b = BN_new()) == NULL) goto err;
47         if ((m = BN_new()) == NULL) goto err;
48
49
50         if (!BN_zero(n0)) goto err;
51         if (!BN_zero(n1)) goto err;
52         if (!BN_zero(r)) goto err;
53         if (!BN_zero(b)) goto err;
54         if (!BN_zero(m)) goto err;
55
56         max = 0;
57
58         do
59                 {
60                 if (max++ > MAX_ROUNDS) goto err; /* if p is not prime could never stop*/
61                 if (!BN_add_word(m, 1)) goto err;
62                 ret = BN_kronecker(m, p, ctx);
63                 if (ret < -1 || ret > 1) goto err;
64                 }
65         while (ret != -1);
66
67         if (BN_copy(n1, p) == NULL) goto err;
68         if (!BN_sub_word(n1, 1)) goto err;
69
70         while (!BN_is_odd(n1))
71                 {
72                 if (!BN_add_word(r, 1)) goto err;
73                 if (!BN_rshift1(n1, n1)) goto err;
74                 }
75
76         if (!BN_mod_exp_simple(n0, m, n1, p, ctx)) goto err;
77
78         if (!BN_sub_word(n1, 1)) goto err;
79         if (!BN_rshift1(n1, n1)) goto err;
80         if (!BN_mod_exp_simple(x, a, n1, p, ctx)) goto err;
81
82         if (!BN_mod_sqr(b, x, p, ctx)) goto err;
83         if (!BN_mod_mul(b, b, a, p, ctx)) goto err;
84
85         if (!BN_mod_mul(x, x, a, p, ctx)) goto err;
86
87         while (!BN_is_one(b))
88                 {
89                 if (!BN_one(m)) goto err;
90                 if (!BN_mod_sqr(n1, b, p, ctx)) goto err;
91                 while(!BN_is_one(n1))
92                         {
93                         if (!BN_mod_mul(n1, n1, n1, p, ctx)) goto err;
94                         if (!BN_add_word(m, 1)) goto err;
95                         }
96
97                 if (!BN_sub(r, r, m)) goto err;
98                 if (!BN_sub_word(r, 1)) goto err;
99                 if (r->neg) goto err;
100
101                 if (BN_copy(n1, n0) == NULL) goto err;
102                 while(!BN_is_zero(r))
103                         {
104                         if (!BN_mod_mul(n1, n1, n1, p, ctx)) goto err;
105                         if (!BN_sub_word(r, 1)) goto err;
106                         }
107
108                 if (!BN_mod_mul(n0, n1, n1, p, ctx)) goto err;
109                 if (BN_copy(r, m) == NULL) goto err;
110                 if (!BN_mod_mul(x, x, n1, p, ctx)) goto err;
111                 if (!BN_mod_mul(b, b, n0, p, ctx)) goto err;
112                 }
113
114
115 #ifdef TEST
116         BN_mod_sqr(n0, x, p, ctx);
117         if (BN_cmp(n0, a)) goto err;
118 #endif
119
120         if (r != NULL) BN_clear_free(r);
121         if (b != NULL) BN_clear_free(b);
122         if (m != NULL) BN_clear_free(m);
123         BN_CTX_end(ctx);
124         return 1;
125 err:
126         if (r != NULL) BN_clear_free(r);
127         if (b != NULL) BN_clear_free(b);
128         if (m != NULL) BN_clear_free(m);
129         BN_CTX_end(ctx);
130         return 0;
131         }