9f6222fb13204caf541411da0023ae40616f7648
[openssl.git] / crypto / bn / bn_mont2.c
1 /*\r
2  *\r
3  *      bn_mont2.c\r
4  *\r
5  *      Montgomery Modular Arithmetic Functions.\r
6  *\r
7  *      Copyright (C) Lenka Fibikova 2000\r
8  *\r
9  *\r
10  */\r
11 \r
12 \r
13 #include <stdio.h>\r
14 #include <stdlib.h>\r
15 #include <assert.h>\r
16 \r
17 #include "bn.h"\r
18 #include "bn_modfs.h"\r
19 #include "bn_mont2.h"\r
20 \r
21 #define BN_mask_word(x, m) ((x->d[0]) & (m))\r
22 \r
23 BN_MONTGOMERY *BN_mont_new()\r
24 {\r
25         BN_MONTGOMERY *ret;\r
26 \r
27         ret=(BN_MONTGOMERY *)malloc(sizeof(BN_MONTGOMERY));\r
28 \r
29         if (ret == NULL) return NULL;\r
30 \r
31         if ((ret->p = BN_new()) == NULL)\r
32         {\r
33                 free(ret);\r
34                 return NULL;\r
35         }\r
36 \r
37         return ret;\r
38 }\r
39 \r
40 \r
41 void BN_mont_clear_free(BN_MONTGOMERY *mont)\r
42 {\r
43         if (mont == NULL) return;\r
44 \r
45         if (mont->p != NULL) BN_clear_free(mont->p);\r
46 \r
47         mont->p_num_bytes = 0;\r
48         mont->R_num_bits = 0;\r
49         mont->p_inv_b_neg = 0;\r
50 }\r
51 \r
52 int BN_to_mont(BIGNUM *x, BN_MONTGOMERY *mont, BN_CTX *ctx)\r
53 {\r
54         assert(x != NULL);\r
55 \r
56         assert(mont != NULL);\r
57         assert(mont->p != NULL);\r
58 \r
59         assert(ctx != NULL);\r
60 \r
61         if (!BN_lshift(x, x, mont->R_num_bits)) return 0;\r
62         if (!BN_mod(x, x, mont->p, ctx)) return 0;\r
63 \r
64         return 1;\r
65 }\r
66 \r
67 \r
68 static BN_ULONG BN_mont_inv(BIGNUM *a, int e, BN_CTX *ctx)\r
69 /* y = a^{-1} (mod 2^e) for an odd number a */\r
70 {\r
71         BN_ULONG y, exp, mask;\r
72         BIGNUM *x, *xy, *x_sh;\r
73         int i;\r
74 \r
75         assert(a != NULL && ctx != NULL);\r
76         assert(e <= BN_BITS2);\r
77         assert(BN_is_odd(a));\r
78         assert(!BN_is_zero(a) && !a->neg);\r
79 \r
80 \r
81         y = 1;\r
82         exp = 2;\r
83         mask = 3;\r
84         if((x = BN_dup(a)) == NULL) return 0;\r
85         if(!BN_mask_bits(x, e)) return 0;\r
86 \r
87         xy = ctx->bn[ctx->tos]; \r
88         x_sh = ctx->bn[ctx->tos + 1]; \r
89         ctx->tos += 2;\r
90 \r
91         if (BN_copy(xy, x) == NULL) goto err;\r
92         if (!BN_lshift1(x_sh, x)) goto err;\r
93 \r
94 \r
95         for (i = 2; i <= e; i++)\r
96         {\r
97                 if (exp < BN_mask_word(xy, mask))\r
98                 {\r
99                         y = y + exp;\r
100                         if (!BN_add(xy, xy, x_sh)) goto err;\r
101                 }\r
102 \r
103                 exp <<= 1;\r
104                 if (!BN_lshift1(x_sh, x_sh)) goto err;\r
105                 mask <<= 1;\r
106                 mask++;\r
107         }\r
108 \r
109 \r
110 #ifdef TEST\r
111         if (xy->d[0] != 1) goto err;\r
112 #endif\r
113 \r
114         if (x != NULL) BN_clear_free(x);\r
115         ctx->tos -= 2;\r
116         return y;\r
117 \r
118 \r
119 err:\r
120         if (x != NULL) BN_clear_free(x);\r
121         ctx->tos -= 2;\r
122         return 0;\r
123 \r
124 }\r
125 \r
126 int BN_mont_set(BIGNUM *p, BN_MONTGOMERY *mont, BN_CTX *ctx)\r
127 {\r
128         assert(p != NULL && ctx != NULL);\r
129         assert(mont != NULL);\r
130         assert(mont->p != NULL);\r
131         assert(!BN_is_zero(p) && !p->neg);\r
132 \r
133 \r
134         mont->p_num_bytes = p->top;\r
135         mont->R_num_bits = (mont->p_num_bytes) * BN_BITS2;\r
136 \r
137         if (BN_copy(mont->p, p) == NULL);\r
138         \r
139         mont->p_inv_b_neg =  BN_mont_inv(p, BN_BITS2, ctx);\r
140         mont->p_inv_b_neg = 0 - mont->p_inv_b_neg;\r
141 \r
142         return 1;\r
143 }\r
144 \r
145 static int BN_cpy_mul_word(BIGNUM *ret, BIGNUM *a, BN_ULONG w)\r
146 /* ret = a * w */\r
147 {\r
148         if (BN_copy(ret, a) == NULL) return 0;\r
149 \r
150         if (!BN_mul_word(ret, w)) return 0;\r
151 \r
152         return 1;\r
153 }\r
154 \r
155 \r
156 int BN_mont_red(BIGNUM *y, BN_MONTGOMERY *mont, BN_CTX *ctx)\r
157 /* yR^{-1} (mod p) */\r
158 {\r
159         int i;\r
160         BIGNUM *up, *p;\r
161         BN_ULONG u;\r
162 \r
163         assert(y != NULL && mont != NULL && ctx != NULL);\r
164         assert(mont->p != NULL);\r
165         assert(BN_cmp(y, mont->p) < 0);\r
166         assert(!y->neg);\r
167 \r
168 \r
169         if (BN_is_zero(y)) return 1;\r
170 \r
171         p = mont->p;\r
172         up = ctx->bn[ctx->tos]; \r
173         ctx->tos += 1;\r
174 \r
175 \r
176         for (i = 0; i < mont->p_num_bytes; i++)\r
177         {\r
178                 u = (y->d[0]) * mont->p_inv_b_neg;                      /* u = y_0 * p' */\r
179 \r
180                 if (!BN_cpy_mul_word(up, p, u)) goto err;       /* up = u * p */\r
181 \r
182                 if (!BN_add(y, y, up)) goto err;                        \r
183 #ifdef TEST\r
184                 if (y->d[0]) goto err;\r
185 #endif\r
186                 if (!BN_rshift(y, y, BN_BITS2)) goto err;       /* y = (y + up)/b */\r
187         }\r
188 \r
189 \r
190         if (BN_cmp(y, mont->p) >= 0) \r
191         {\r
192                 if (!BN_sub(y, y, mont->p)) goto err;\r
193         }\r
194 \r
195         ctx->tos -= 1;\r
196         return 1;\r
197 \r
198 err:\r
199         ctx->tos -= 1;\r
200         return 0;\r
201 \r
202 }\r
203 \r
204 \r
205 int BN_mont_mod_mul(BIGNUM *r, BIGNUM *x, BIGNUM *y, BN_MONTGOMERY *mont, BN_CTX *ctx)\r
206 /* r = x * y mod p */\r
207 /* r != x && r! = y !!! */\r
208 {\r
209         BIGNUM *xiy, *up;\r
210         BN_ULONG u;\r
211         int i;\r
212         \r
213 \r
214         assert(r != x && r != y);\r
215         assert(r != NULL && x != NULL  && y != NULL && mont != NULL && ctx != NULL);\r
216         assert(mont->p != NULL);\r
217         assert(BN_cmp(x, mont->p) < 0);\r
218         assert(BN_cmp(y, mont->p) < 0);\r
219         assert(!x->neg);\r
220         assert(!y->neg);\r
221 \r
222         if (BN_is_zero(x) || BN_is_zero(y))\r
223         {\r
224                 if (!BN_zero(r)) return 0;\r
225                 return 1;\r
226         }\r
227 \r
228 \r
229 \r
230         xiy = ctx->bn[ctx->tos]; \r
231         up = ctx->bn[ctx->tos + 1]; \r
232         ctx->tos += 2;\r
233 \r
234         if (!BN_zero(r)) goto err;\r
235 \r
236         for (i = 0; i < x->top; i++)\r
237         {\r
238                 u = (r->d[0] + x->d[i] * y->d[0]) * mont->p_inv_b_neg;\r
239 \r
240                 if (!BN_cpy_mul_word(xiy, y, x->d[i])) goto err;\r
241                 if (!BN_cpy_mul_word(up, mont->p, u)) goto err;\r
242 \r
243                 if (!BN_add(r, r, xiy)) goto err;\r
244                 if (!BN_add(r, r, up)) goto err;\r
245 \r
246 #ifdef TEST\r
247                 if (r->d[0]) goto err;\r
248 #endif\r
249                 if (!BN_rshift(r, r, BN_BITS2)) goto err; \r
250         }\r
251 \r
252         for (i = x->top; i < mont->p_num_bytes; i++)\r
253         {\r
254                 u = (r->d[0]) * mont->p_inv_b_neg;\r
255 \r
256                 if (!BN_cpy_mul_word(up, mont->p, u)) goto err;\r
257 \r
258                 if (!BN_add(r, r, up)) goto err;\r
259 \r
260 #ifdef TEST\r
261                 if (r->d[0]) goto err;\r
262 #endif\r
263                 if (!BN_rshift(r, r, BN_BITS2)) goto err; \r
264         }\r
265 \r
266 \r
267         if (BN_cmp(r, mont->p) >= 0) \r
268         {\r
269                 if (!BN_sub(r, r, mont->p)) goto err;\r
270         }\r
271 \r
272 \r
273         ctx->tos -= 2;\r
274         return 1;\r
275 \r
276 err:\r
277         ctx->tos -= 2;\r
278         return 0;\r
279 }\r
280 \r
281 int BN_mont_mod_add(BIGNUM *r, BIGNUM *x, BIGNUM *y, BN_MONTGOMERY *mont)\r
282 {\r
283         assert(r != NULL && x != NULL  && y != NULL && mont != NULL);\r
284         assert(mont->p != NULL);\r
285         assert(BN_cmp(x, mont->p) < 0);\r
286         assert(BN_cmp(y, mont->p) < 0);\r
287         assert(!x->neg);\r
288         assert(!y->neg);\r
289 \r
290         if (!BN_add(r, x, y)) return 0;\r
291         if (BN_cmp(r, mont->p) >= 0) \r
292         {\r
293                 if (!BN_sub(r, r, mont->p)) return 0;\r
294         }\r
295 \r
296         return 1;\r
297 }\r
298 \r
299 \r
300 int BN_mont_mod_sub(BIGNUM *r, BIGNUM *x, BIGNUM *y, BN_MONTGOMERY *mont)\r
301 {\r
302         assert(r != NULL && x != NULL  && y != NULL && mont != NULL);\r
303         assert(mont->p != NULL);\r
304         assert(BN_cmp(x, mont->p) < 0);\r
305         assert(BN_cmp(y, mont->p) < 0);\r
306         assert(!x->neg);\r
307         assert(!y->neg);\r
308 \r
309         if (!BN_sub(r, x, y)) return 0;\r
310         if (r->neg) \r
311         {\r
312                 if (!BN_add(r, r, mont->p)) return 0;\r
313         }\r
314 \r
315         return 1;\r
316 }\r
317 \r
318 int BN_mont_mod_lshift1(BIGNUM *r, BIGNUM *x, BN_MONTGOMERY *mont)\r
319 {\r
320         assert(r != NULL && x != NULL && mont != NULL);\r
321         assert(mont->p != NULL);\r
322         assert(BN_cmp(x, mont->p) < 0);\r
323         assert(!x->neg);\r
324 \r
325         if (!BN_lshift1(r, x)) return 0;\r
326 \r
327         if (BN_cmp(r, mont->p) >= 0) \r
328         {\r
329                 if (!BN_sub(r, r, mont->p)) return 0;\r
330         }\r
331 \r
332         return 1;\r
333 }\r
334 \r
335 int BN_mont_mod_lshift(BIGNUM *r, BIGNUM *x, int n, BN_MONTGOMERY *mont)\r
336 {\r
337         int sh_nb;\r
338 \r
339         assert(r != NULL && x != NULL && mont != NULL);\r
340         assert(mont->p != NULL);\r
341         assert(BN_cmp(x, mont->p) < 0);\r
342         assert(!x->neg);\r
343         assert(n > 0);\r
344 \r
345         if (r != x)\r
346         {\r
347                 if (BN_copy(r, x) == NULL) return 0;\r
348         }\r
349 \r
350         while (n)\r
351         {\r
352                 sh_nb = BN_num_bits(mont->p) - BN_num_bits(r);\r
353                 if (sh_nb > n) sh_nb = n;\r
354 \r
355                 if (sh_nb)\r
356                 {\r
357                         if(!BN_lshift(r, r, sh_nb)) return 0;\r
358                 }\r
359                 else \r
360                 {\r
361                         sh_nb = 1;\r
362                         if (!BN_lshift1(r, r)) return 0;\r
363                 }\r
364 \r
365                 if (BN_cmp(r, mont->p) >= 0) \r
366                 {\r
367                         if (!BN_sub(r, r, mont->p)) return 0;\r
368                 }\r
369 \r
370                 n -= sh_nb;\r
371         }\r
372 \r
373         return 1;\r
374 }\r