modular arithmetics
[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         x = ctx->bn[ctx->tos]; 
31         y = ctx->bn[ctx->tos + 1]; 
32         y2 = ctx->bn[ctx->tos + 2]; 
33
34         ctx->tos += 3;
35
36         if (!BN_nnmod(x, a, p, ctx)) goto err;
37         if (BN_is_zero(x)) 
38         {
39
40                 ctx->tos -= 3;
41                 return 0;
42         }
43
44         if (BN_copy(y, p) == NULL) goto err;
45         L = 1;
46
47         while (1)
48         {
49                 if (!BN_rshift1(y2, y)) goto err;
50                 if (BN_cmp(x, y2) > 0)
51                 {
52                         if (!BN_sub(x, y, x)) goto err;
53                         if (BN_mod_word(y, 4) == 3)
54                                 L = -L;                 
55                 }
56                 while (BN_mod_word(x, 4) == 0)
57                         BN_div_word(x, 4);
58                 if (BN_mod_word(x, 2) == 0)
59                 {
60                         BN_div_word(x, 2);
61                         m = BN_mod_word(y, 8);
62                         if (m == 3 || m == 5) L = -L;                   
63                 }
64                 if (BN_is_one(x)) 
65                 {
66                         ctx->tos -= 3;
67                         return L;
68                 }
69                 
70                 if (BN_mod_word(x, 4) == 3 && BN_mod_word(y, 4) == 3) L = -L;
71                 if (!BN_swap(x, y)) goto err;
72
73                 if (!BN_nnmod(x, x, y, ctx)) goto err;
74
75         }
76
77
78 err:
79         ctx->tos -= 3;
80         return -2;
81
82 }
83
84 int BN_mod_sqrt(BIGNUM *x, BIGNUM *a, BIGNUM *p, BN_CTX *ctx) 
85 /* x^2 = a (mod p) */
86 {
87         int ret;
88         BIGNUM *n0, *n1, *r, *b, *m;
89         int max;
90
91         assert(x != NULL && a != NULL && p != NULL && ctx != NULL);
92         assert(BN_cmp(a, p) < 0);
93
94         ret = BN_legendre(a, p, ctx);
95         if (ret < 0 || ret > 1) return 0;
96         if (ret == 0)
97         {
98                 if (!BN_zero(x)) return 0;
99                 return 1;
100         }
101
102         n0 = ctx->bn[ctx->tos]; 
103         n1 = ctx->bn[ctx->tos + 1]; 
104         ctx->tos += 2;
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                 if (max++ > MAX_ROUNDS) goto err; /* if p is not prime could never stop*/
121                 if (!BN_add_word(m, 1)) goto err;
122                 ret = BN_legendre(m, p, ctx);
123                 if (ret < -1 || ret > 1) goto err;
124
125         }while(ret != -1);
126
127         if (BN_copy(n1, p) == NULL) goto err;
128         if (!BN_sub_word(n1, 1)) goto err;
129
130         while (!BN_is_odd(n1))
131         {
132                 if (!BN_add_word(r, 1)) goto err;
133                 if (!BN_rshift1(n1, n1)) goto err;
134         }
135
136         if (!BN_mod_exp_simple(n0, m, n1, p, ctx)) goto err;
137
138         if (!BN_sub_word(n1, 1)) goto err;
139         if (!BN_rshift1(n1, n1)) goto err;
140         if (!BN_mod_exp_simple(x, a, n1, p, ctx)) goto err;
141
142         if (!BN_mod_sqr(b, x, p, ctx)) goto err;
143         if (!BN_mod_mul(b, b, a, p, ctx)) goto err;
144
145         if (!BN_mod_mul(x, x, a, p, ctx)) goto err;
146
147         while (!BN_is_one(b))
148         {
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         ctx->tos -= 2;
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         ctx->tos -= 2;
191         return 0;
192 }