Change submitted files so that they compile (in particular,
[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_legendre(BIGNUM *a, BIGNUM *p, BN_CTX *ctx) 
23         {
24         BIGNUM *x, *y, *y2;
25         BN_ULONG m;
26         int L;
27
28         assert(a != NULL && p != NULL && ctx != NULL);
29
30         BN_CTX_start(ctx);
31         x = BN_CTX_get(ctx);
32         y = BN_CTX_get(ctx);
33         y2 = BN_CTX_get(ctx);
34         if (y2 == NULL) goto err;
35
36         if (!BN_nnmod(x, a, p, ctx)) goto err;
37         if (BN_is_zero(x)) 
38                 {
39                 BN_CTX_end(ctx);
40                 return 0;
41                 }
42
43         if (BN_copy(y, p) == NULL) goto err;
44         L = 1;
45
46         while (1)
47                 {
48                 if (!BN_rshift1(y2, y)) goto err;
49                 if (BN_cmp(x, y2) > 0)
50                         {
51                         if (!BN_sub(x, y, x)) goto err;
52                         if (BN_mod_word(y, 4) == 3)
53                                 L = -L;                 
54                         }
55                 while (BN_mod_word(x, 4) == 0)
56                         BN_div_word(x, 4);
57                 if (BN_mod_word(x, 2) == 0)
58                         {
59                         BN_div_word(x, 2);
60                         m = BN_mod_word(y, 8);
61                         if (m == 3 || m == 5) L = -L;                   
62                         }
63                 if (BN_is_one(x)) 
64                         {
65                         BN_CTX_end(ctx);
66                         return L;
67                         }
68                 
69                 if (BN_mod_word(x, 4) == 3 && BN_mod_word(y, 4) == 3) L = -L;
70                 BN_swap(x, y);
71
72                 if (!BN_nnmod(x, x, y, ctx)) goto err;
73
74                 }
75
76
77 err:
78         BN_CTX_end(ctx);
79         return -2;
80
81         }
82
83 int BN_mod_sqrt(BIGNUM *x, BIGNUM *a, BIGNUM *p, BN_CTX *ctx) 
84 /* x^2 = a (mod p) */
85         {
86         int ret;
87         BIGNUM *n0, *n1, *r, *b, *m;
88         int max;
89
90         assert(x != NULL && a != NULL && p != NULL && ctx != NULL);
91         assert(BN_cmp(a, p) < 0);
92
93         ret = BN_legendre(a, p, ctx);
94         if (ret < 0 || ret > 1) return 0;
95         if (ret == 0)
96                 {
97                 if (!BN_zero(x)) return 0;
98                 return 1;
99                 }
100
101         BN_CTX_start(ctx);
102         n0 = BN_CTX_get(ctx);
103         n1 = BN_CTX_get(ctx);
104         if (n1 == NULL) goto err;
105
106         if ((r = BN_new()) == NULL) goto err;
107         if ((b = BN_new()) == NULL) goto err;
108         if ((m = BN_new()) == NULL) goto err;
109
110
111         if (!BN_zero(n0)) goto err;
112         if (!BN_zero(n1)) goto err;
113         if (!BN_zero(r)) goto err;
114         if (!BN_zero(b)) goto err;
115         if (!BN_zero(m)) goto err;
116
117         max = 0;
118
119         do
120                 {
121                 if (max++ > MAX_ROUNDS) goto err; /* if p is not prime could never stop*/
122                 if (!BN_add_word(m, 1)) goto err;
123                 ret = BN_legendre(m, p, ctx);
124                 if (ret < -1 || ret > 1) goto err;
125                 }
126         while (ret != -1);
127
128         if (BN_copy(n1, p) == NULL) goto err;
129         if (!BN_sub_word(n1, 1)) goto err;
130
131         while (!BN_is_odd(n1))
132                 {
133                 if (!BN_add_word(r, 1)) goto err;
134                 if (!BN_rshift1(n1, n1)) goto err;
135                 }
136
137         if (!BN_mod_exp_simple(n0, m, n1, p, ctx)) goto err;
138
139         if (!BN_sub_word(n1, 1)) goto err;
140         if (!BN_rshift1(n1, n1)) goto err;
141         if (!BN_mod_exp_simple(x, a, n1, p, ctx)) goto err;
142
143         if (!BN_mod_sqr(b, x, p, ctx)) goto err;
144         if (!BN_mod_mul(b, b, a, p, ctx)) goto err;
145
146         if (!BN_mod_mul(x, x, a, p, ctx)) goto err;
147
148         while (!BN_is_one(b))
149                 {
150                 if (!BN_one(m)) goto err;
151                 if (!BN_mod_sqr(n1, b, p, ctx)) goto err;
152                 while(!BN_is_one(n1))
153                         {
154                         if (!BN_mod_mul(n1, n1, n1, p, ctx)) goto err;
155                         if (!BN_add_word(m, 1)) goto err;
156                         }
157
158                 if (!BN_sub(r, r, m)) goto err;
159                 if (!BN_sub_word(r, 1)) goto err;
160                 if (r->neg) goto err;
161
162                 if (BN_copy(n1, n0) == NULL) goto err;
163                 while(!BN_is_zero(r))
164                         {
165                         if (!BN_mod_mul(n1, n1, n1, p, ctx)) goto err;
166                         if (!BN_sub_word(r, 1)) goto err;
167                         }
168
169                 if (!BN_mod_mul(n0, n1, n1, p, ctx)) goto err;
170                 if (BN_copy(r, m) == NULL) goto err;
171                 if (!BN_mod_mul(x, x, n1, p, ctx)) goto err;
172                 if (!BN_mod_mul(b, b, n0, p, ctx)) goto err;
173                 }
174
175
176 #ifdef TEST
177         BN_mod_sqr(n0, x, p, ctx);
178         if (BN_cmp(n0, a)) goto err;
179 #endif
180
181         if (r != NULL) BN_clear_free(r);
182         if (b != NULL) BN_clear_free(b);
183         if (m != NULL) BN_clear_free(m);
184         BN_CTX_end(ctx);
185         return 1;
186 err:
187         if (r != NULL) BN_clear_free(r);
188         if (b != NULL) BN_clear_free(b);
189         if (m != NULL) BN_clear_free(m);
190         BN_CTX_end(ctx);
191         return 0;
192         }