5 * Montgomery Modular Arithmetic Functions.
7 * Copyright (C) Lenka Fibikova 2000
21 #define BN_mask_word(x, m) ((x->d[0]) & (m))
23 BN_MONTGOMERY *BN_mont_new()
27 ret=(BN_MONTGOMERY *)malloc(sizeof(BN_MONTGOMERY));
29 if (ret == NULL) return NULL;
31 if ((ret->p = BN_new()) == NULL)
41 void BN_mont_clear_free(BN_MONTGOMERY *mont)
43 if (mont == NULL) return;
45 if (mont->p != NULL) BN_clear_free(mont->p);
47 mont->p_num_bytes = 0;
49 mont->p_inv_b_neg = 0;
52 int BN_to_mont(BIGNUM *x, BN_MONTGOMERY *mont, BN_CTX *ctx)
57 assert(mont->p != NULL);
61 if (!BN_lshift(x, x, mont->R_num_bits)) return 0;
62 if (!BN_mod(x, x, mont->p, ctx)) return 0;
68 static BN_ULONG BN_mont_inv(BIGNUM *a, int e, BN_CTX *ctx)
69 /* y = a^{-1} (mod 2^e) for an odd number a */
71 BN_ULONG y, exp, mask;
72 BIGNUM *x, *xy, *x_sh;
75 assert(a != NULL && ctx != NULL);
76 assert(e <= BN_BITS2);
78 assert(!BN_is_zero(a) && !a->neg);
84 if((x = BN_dup(a)) == NULL) return 0;
85 if(!BN_mask_bits(x, e)) return 0;
87 xy = ctx->bn[ctx->tos];
88 x_sh = ctx->bn[ctx->tos + 1];
91 if (BN_copy(xy, x) == NULL) goto err;
92 if (!BN_lshift1(x_sh, x)) goto err;
95 for (i = 2; i <= e; i++)
97 if (exp < BN_mask_word(xy, mask))
100 if (!BN_add(xy, xy, x_sh)) goto err;
104 if (!BN_lshift1(x_sh, x_sh)) goto err;
111 if (xy->d[0] != 1) goto err;
114 if (x != NULL) BN_clear_free(x);
120 if (x != NULL) BN_clear_free(x);
126 int BN_mont_set(BIGNUM *p, BN_MONTGOMERY *mont, BN_CTX *ctx)
128 assert(p != NULL && ctx != NULL);
129 assert(mont != NULL);
130 assert(mont->p != NULL);
131 assert(!BN_is_zero(p) && !p->neg);
134 mont->p_num_bytes = p->top;
135 mont->R_num_bits = (mont->p_num_bytes) * BN_BITS2;
137 if (BN_copy(mont->p, p) == NULL);
139 mont->p_inv_b_neg = BN_mont_inv(p, BN_BITS2, ctx);
140 mont->p_inv_b_neg = 0 - mont->p_inv_b_neg;
145 static int BN_cpy_mul_word(BIGNUM *ret, BIGNUM *a, BN_ULONG w)
148 if (BN_copy(ret, a) == NULL) return 0;
150 if (!BN_mul_word(ret, w)) return 0;
156 int BN_mont_red(BIGNUM *y, BN_MONTGOMERY *mont, BN_CTX *ctx)
157 /* yR^{-1} (mod p) */
163 assert(y != NULL && mont != NULL && ctx != NULL);
164 assert(mont->p != NULL);
165 assert(BN_cmp(y, mont->p) < 0);
169 if (BN_is_zero(y)) return 1;
172 up = ctx->bn[ctx->tos];
176 for (i = 0; i < mont->p_num_bytes; i++)
178 u = (y->d[0]) * mont->p_inv_b_neg; /* u = y_0 * p' */
180 if (!BN_cpy_mul_word(up, p, u)) goto err; /* up = u * p */
182 if (!BN_add(y, y, up)) goto err;
184 if (y->d[0]) goto err;
186 if (!BN_rshift(y, y, BN_BITS2)) goto err; /* y = (y + up)/b */
190 if (BN_cmp(y, mont->p) >= 0)
192 if (!BN_sub(y, y, mont->p)) goto err;
205 int BN_mont_mod_mul(BIGNUM *r, BIGNUM *x, BIGNUM *y, BN_MONTGOMERY *mont, BN_CTX *ctx)
206 /* r = x * y mod p */
207 /* r != x && r! = y !!! */
214 assert(r != x && r != y);
215 assert(r != NULL && x != NULL && y != NULL && mont != NULL && ctx != NULL);
216 assert(mont->p != NULL);
217 assert(BN_cmp(x, mont->p) < 0);
218 assert(BN_cmp(y, mont->p) < 0);
222 if (BN_is_zero(x) || BN_is_zero(y))
224 if (!BN_zero(r)) return 0;
230 xiy = ctx->bn[ctx->tos];
231 up = ctx->bn[ctx->tos + 1];
234 if (!BN_zero(r)) goto err;
236 for (i = 0; i < x->top; i++)
238 u = (r->d[0] + x->d[i] * y->d[0]) * mont->p_inv_b_neg;
240 if (!BN_cpy_mul_word(xiy, y, x->d[i])) goto err;
241 if (!BN_cpy_mul_word(up, mont->p, u)) goto err;
243 if (!BN_add(r, r, xiy)) goto err;
244 if (!BN_add(r, r, up)) goto err;
247 if (r->d[0]) goto err;
249 if (!BN_rshift(r, r, BN_BITS2)) goto err;
252 for (i = x->top; i < mont->p_num_bytes; i++)
254 u = (r->d[0]) * mont->p_inv_b_neg;
256 if (!BN_cpy_mul_word(up, mont->p, u)) goto err;
258 if (!BN_add(r, r, up)) goto err;
261 if (r->d[0]) goto err;
263 if (!BN_rshift(r, r, BN_BITS2)) goto err;
267 if (BN_cmp(r, mont->p) >= 0)
269 if (!BN_sub(r, r, mont->p)) goto err;