c6986fb2e770403dda3903e9410304cdc6a2cb8a
[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 int BN_smod(BIGNUM *rem, BIGNUM *m, BIGNUM *d, BN_CTX *ctx)
22 {
23         int r_sign;
24
25         assert(rem != NULL && m != NULL && d != NULL && ctx != NULL);
26
27         if (d->neg) return 0;
28         r_sign = m->neg;
29
30         if (r_sign) m->neg = 0;
31         if (!(BN_div(NULL,rem,m,d,ctx))) return 0;
32         if (r_sign) 
33         {
34                 m->neg = r_sign;
35                 if (!BN_is_zero(rem))
36                 {
37                         rem->neg = r_sign;
38                         BN_add(rem, rem, d);
39                 }
40         }
41         return 1;
42 }
43
44 int BN_mod_sub(BIGNUM *r, BIGNUM *a, BIGNUM *b, BIGNUM *m, BN_CTX *ctx) 
45 {
46         assert(r != NULL && a != NULL && b != NULL && m != NULL && ctx != NULL);
47
48         if (!BN_sub(r, a, b)) return 0;
49         return BN_smod(r, r, m, ctx);
50
51 }
52
53 int BN_mod_add(BIGNUM *r, BIGNUM *a, BIGNUM *b, BIGNUM *m, BN_CTX *ctx) 
54 {
55         assert(r != NULL && a != NULL && b != NULL && m != NULL && ctx != NULL);
56
57         if (!BN_add(r, a, b)) return 0;
58         return BN_smod(r, r, m, ctx);
59
60 }
61
62 int BN_mod_sqr(BIGNUM *r, BIGNUM *a, BIGNUM *p, BN_CTX *ctx)
63 {
64         assert(r != NULL && a != NULL && p != NULL && ctx != NULL);
65
66         if (!BN_sqr(r, a, ctx)) return 0;
67         return BN_div(NULL, r, r, p, ctx);
68 }
69
70 int BN_swap(BIGNUM *x, BIGNUM *y)
71 {
72         BIGNUM *c;
73
74         assert(x != NULL && y != NULL);
75
76         if ((c = BN_dup(x)) == NULL) goto err;
77         if ((BN_copy(x, y)) == NULL) goto err;
78         if ((BN_copy(y, c)) == NULL) goto err;
79         BN_clear_free(c);
80         return 1;
81
82 err:
83         if (c != NULL) BN_clear_free(c);
84         return 0;
85 }
86
87
88 int BN_legendre(BIGNUM *a, BIGNUM *p, BN_CTX *ctx) 
89 {
90         BIGNUM *x, *y, *y2;
91         BN_ULONG m;
92         int L;
93
94         assert(a != NULL && p != NULL && ctx != NULL);
95
96         x = ctx->bn[ctx->tos]; 
97         y = ctx->bn[ctx->tos + 1]; 
98         y2 = ctx->bn[ctx->tos + 2]; 
99
100         ctx->tos += 3;
101
102         if (!BN_smod(x, a, p, ctx)) goto err;
103         if (BN_is_zero(x)) 
104         {
105
106                 ctx->tos -= 3;
107                 return 0;
108         }
109
110         if (BN_copy(y, p) == NULL) goto err;
111         L = 1;
112
113         while (1)
114         {
115                 if (!BN_rshift1(y2, y)) goto err;
116                 if (BN_cmp(x, y2) > 0)
117                 {
118                         if (!BN_sub(x, y, x)) goto err;
119                         if (BN_mod_word(y, 4) == 3)
120                                 L = -L;                 
121                 }
122                 while (BN_mod_word(x, 4) == 0)
123                         BN_div_word(x, 4);
124                 if (BN_mod_word(x, 2) == 0)
125                 {
126                         BN_div_word(x, 2);
127                         m = BN_mod_word(y, 8);
128                         if (m == 3 || m == 5) L = -L;                   
129                 }
130                 if (BN_is_one(x)) 
131                 {
132                         ctx->tos -= 3;
133                         return L;
134                 }
135                 
136                 if (BN_mod_word(x, 4) == 3 && BN_mod_word(y, 4) == 3) L = -L;
137                 if (!BN_swap(x, y)) goto err;
138
139                 if (!BN_smod(x, x, y, ctx)) goto err;
140
141         }
142
143
144 err:
145         ctx->tos -= 3;
146         return -2;
147
148 }
149
150 int BN_mod_sqrt(BIGNUM *x, BIGNUM *a, BIGNUM *p, BN_CTX *ctx) 
151 /* x^2 = a (mod p) */
152 {
153         int ret;
154         BIGNUM *n0, *n1, *r, *b, *m;
155         int max;
156
157         assert(x != NULL && a != NULL && p != NULL && ctx != NULL);
158         assert(BN_cmp(a, p) < 0);
159
160         ret = BN_legendre(a, p, ctx);
161         if (ret < 0 || ret > 1) return 0;
162         if (ret == 0)
163         {
164                 if (!BN_zero(x)) return 0;
165                 return 1;
166         }
167
168         n0 = ctx->bn[ctx->tos]; 
169         n1 = ctx->bn[ctx->tos + 1]; 
170         ctx->tos += 2;
171
172         if ((r = BN_new()) == NULL) goto err;
173         if ((b = BN_new()) == NULL) goto err;
174         if ((m = BN_new()) == NULL) goto err;
175
176
177         if (!BN_zero(n0)) goto err;
178         if (!BN_zero(n1)) goto err;
179         if (!BN_zero(r)) goto err;
180         if (!BN_zero(b)) goto err;
181         if (!BN_zero(m)) goto err;
182
183         max = 0;
184
185         do{
186                 if (max++ > MAX_ROUNDS) goto err; /* if p is not prime could never stop*/
187                 if (!BN_add_word(m, 1)) goto err;
188                 ret = BN_legendre(m, p, ctx);
189                 if (ret < -1 || ret > 1) goto err;
190
191         }while(ret != -1);
192
193         if (BN_copy(n1, p) == NULL) goto err;
194         if (!BN_sub_word(n1, 1)) goto err;
195
196         while (!BN_is_odd(n1))
197         {
198                 if (!BN_add_word(r, 1)) goto err;
199                 if (!BN_rshift1(n1, n1)) goto err;
200         }
201
202         if (!BN_mod_exp_simple(n0, m, n1, p, ctx)) goto err;
203
204         if (!BN_sub_word(n1, 1)) goto err;
205         if (!BN_rshift1(n1, n1)) goto err;
206         if (!BN_mod_exp_simple(x, a, n1, p, ctx)) goto err;
207
208         if (!BN_mod_sqr(b, x, p, ctx)) goto err;
209         if (!BN_mod_mul(b, b, a, p, ctx)) goto err;
210
211         if (!BN_mod_mul(x, x, a, p, ctx)) goto err;
212
213         while (!BN_is_one(b))
214         {
215                 
216                 if (!BN_one(m)) goto err;
217                 if (!BN_mod_sqr(n1, b, p, ctx)) goto err;
218                 while(!BN_is_one(n1))
219                 {
220                         if (!BN_mod_mul(n1, n1, n1, p, ctx)) goto err;
221                         if (!BN_add_word(m, 1)) goto err;
222                 }
223
224                 if (!BN_sub(r, r, m)) goto err;
225                 if (!BN_sub_word(r, 1)) goto err;
226                 if (r->neg) goto err;
227
228                 if (BN_copy(n1, n0) == NULL) goto err;
229                 while(!BN_is_zero(r))
230                 {
231                         if (!BN_mod_mul(n1, n1, n1, p, ctx)) goto err;
232                         if (!BN_sub_word(r, 1)) goto err;
233                 }
234
235                 if (!BN_mod_mul(n0, n1, n1, p, ctx)) goto err;
236                 if (BN_copy(r, m) == NULL) goto err;
237                 if (!BN_mod_mul(x, x, n1, p, ctx)) goto err;
238                 if (!BN_mod_mul(b, b, n0, p, ctx)) goto err;
239         }
240
241
242 #ifdef TEST
243         BN_mod_sqr(n0, x, p, ctx);
244         if (BN_cmp(n0, a)) goto err;
245 #endif
246
247         if (r != NULL) BN_clear_free(r);
248         if (b != NULL) BN_clear_free(b);
249         if (m != NULL) BN_clear_free(m);
250         ctx->tos -= 2;
251         return 1;
252 err:
253         if (r != NULL) BN_clear_free(r);
254         if (b != NULL) BN_clear_free(b);
255         if (m != NULL) BN_clear_free(m);
256         ctx->tos -= 2;
257         return 0;
258 }