diff options
-rw-r--r-- | crypto/bn/bn_modfs.c | 516 | ||||
-rw-r--r-- | crypto/bn/bn_modfs.h | 62 | ||||
-rw-r--r-- | crypto/bn/bn_mont2.c | 748 | ||||
-rw-r--r-- | crypto/bn/bn_mont2.h | 80 | ||||
-rw-r--r-- | crypto/ec/ec.c | 242 | ||||
-rw-r--r-- | crypto/ec/ec.h | 170 | ||||
-rw-r--r-- | crypto/ec/ec_point.c | 2922 |
7 files changed, 2370 insertions, 2370 deletions
diff --git a/crypto/bn/bn_modfs.c b/crypto/bn/bn_modfs.c index 2697d54303..c6986fb2e7 100644 --- a/crypto/bn/bn_modfs.c +++ b/crypto/bn/bn_modfs.c @@ -1,258 +1,258 @@ -/*
- *
- * bn_modfs.c
- *
- * Some Modular Arithmetic Functions.
- *
- * Copyright (C) Lenka Fibikova 2000
- *
- *
- */
-
-
-#include <stdio.h>
-#include <stdlib.h>
-#include <assert.h>
-
-#include "bn_modfs.h"
-
-#define MAX_ROUNDS 10
-
-int BN_smod(BIGNUM *rem, BIGNUM *m, BIGNUM *d, BN_CTX *ctx)
-{
- int r_sign;
-
- assert(rem != NULL && m != NULL && d != NULL && ctx != NULL);
-
- if (d->neg) return 0;
- r_sign = m->neg;
-
- if (r_sign) m->neg = 0;
- if (!(BN_div(NULL,rem,m,d,ctx))) return 0;
- if (r_sign)
- {
- m->neg = r_sign;
- if (!BN_is_zero(rem))
- {
- rem->neg = r_sign;
- BN_add(rem, rem, d);
- }
- }
- return 1;
-}
-
-int BN_mod_sub(BIGNUM *r, BIGNUM *a, BIGNUM *b, BIGNUM *m, BN_CTX *ctx)
-{
- assert(r != NULL && a != NULL && b != NULL && m != NULL && ctx != NULL);
-
- if (!BN_sub(r, a, b)) return 0;
- return BN_smod(r, r, m, ctx);
-
-}
-
-int BN_mod_add(BIGNUM *r, BIGNUM *a, BIGNUM *b, BIGNUM *m, BN_CTX *ctx)
-{
- assert(r != NULL && a != NULL && b != NULL && m != NULL && ctx != NULL);
-
- if (!BN_add(r, a, b)) return 0;
- return BN_smod(r, r, m, ctx);
-
-}
-
-int BN_mod_sqr(BIGNUM *r, BIGNUM *a, BIGNUM *p, BN_CTX *ctx)
-{
- assert(r != NULL && a != NULL && p != NULL && ctx != NULL);
-
- if (!BN_sqr(r, a, ctx)) return 0;
- return BN_div(NULL, r, r, p, ctx);
-}
-
-int BN_swap(BIGNUM *x, BIGNUM *y)
-{
- BIGNUM *c;
-
- assert(x != NULL && y != NULL);
-
- if ((c = BN_dup(x)) == NULL) goto err;
- if ((BN_copy(x, y)) == NULL) goto err;
- if ((BN_copy(y, c)) == NULL) goto err;
- BN_clear_free(c);
- return 1;
-
-err:
- if (c != NULL) BN_clear_free(c);
- return 0;
-}
-
-
-int BN_legendre(BIGNUM *a, BIGNUM *p, BN_CTX *ctx)
-{
- BIGNUM *x, *y, *y2;
- BN_ULONG m;
- int L;
-
- assert(a != NULL && p != NULL && ctx != NULL);
-
- x = ctx->bn[ctx->tos];
- y = ctx->bn[ctx->tos + 1];
- y2 = ctx->bn[ctx->tos + 2];
-
- ctx->tos += 3;
-
- if (!BN_smod(x, a, p, ctx)) goto err;
- if (BN_is_zero(x))
- {
-
- ctx->tos -= 3;
- return 0;
- }
-
- if (BN_copy(y, p) == NULL) goto err;
- L = 1;
-
- while (1)
- {
- if (!BN_rshift1(y2, y)) goto err;
- if (BN_cmp(x, y2) > 0)
- {
- if (!BN_sub(x, y, x)) goto err;
- if (BN_mod_word(y, 4) == 3)
- L = -L;
- }
- while (BN_mod_word(x, 4) == 0)
- BN_div_word(x, 4);
- if (BN_mod_word(x, 2) == 0)
- {
- BN_div_word(x, 2);
- m = BN_mod_word(y, 8);
- if (m == 3 || m == 5) L = -L;
- }
- if (BN_is_one(x))
- {
- ctx->tos -= 3;
- return L;
- }
-
- if (BN_mod_word(x, 4) == 3 && BN_mod_word(y, 4) == 3) L = -L;
- if (!BN_swap(x, y)) goto err;
-
- if (!BN_smod(x, x, y, ctx)) goto err;
-
- }
-
-
-err:
- ctx->tos -= 3;
- return -2;
-
-}
-
-int BN_mod_sqrt(BIGNUM *x, BIGNUM *a, BIGNUM *p, BN_CTX *ctx)
-/* x^2 = a (mod p) */
-{
- int ret;
- BIGNUM *n0, *n1, *r, *b, *m;
- int max;
-
- assert(x != NULL && a != NULL && p != NULL && ctx != NULL);
- assert(BN_cmp(a, p) < 0);
-
- ret = BN_legendre(a, p, ctx);
- if (ret < 0 || ret > 1) return 0;
- if (ret == 0)
- {
- if (!BN_zero(x)) return 0;
- return 1;
- }
-
- n0 = ctx->bn[ctx->tos];
- n1 = ctx->bn[ctx->tos + 1];
- ctx->tos += 2;
-
- if ((r = BN_new()) == NULL) goto err;
- if ((b = BN_new()) == NULL) goto err;
- if ((m = BN_new()) == NULL) goto err;
-
-
- if (!BN_zero(n0)) goto err;
- if (!BN_zero(n1)) goto err;
- if (!BN_zero(r)) goto err;
- if (!BN_zero(b)) goto err;
- if (!BN_zero(m)) goto err;
-
- max = 0;
-
- do{
- if (max++ > MAX_ROUNDS) goto err; /* if p is not prime could never stop*/
- if (!BN_add_word(m, 1)) goto err;
- ret = BN_legendre(m, p, ctx);
- if (ret < -1 || ret > 1) goto err;
-
- }while(ret != -1);
-
- if (BN_copy(n1, p) == NULL) goto err;
- if (!BN_sub_word(n1, 1)) goto err;
-
- while (!BN_is_odd(n1))
- {
- if (!BN_add_word(r, 1)) goto err;
- if (!BN_rshift1(n1, n1)) goto err;
- }
-
- if (!BN_mod_exp_simple(n0, m, n1, p, ctx)) goto err;
-
- if (!BN_sub_word(n1, 1)) goto err;
- if (!BN_rshift1(n1, n1)) goto err;
- if (!BN_mod_exp_simple(x, a, n1, p, ctx)) goto err;
-
- if (!BN_mod_sqr(b, x, p, ctx)) goto err;
- if (!BN_mod_mul(b, b, a, p, ctx)) goto err;
-
- if (!BN_mod_mul(x, x, a, p, ctx)) goto err;
-
- while (!BN_is_one(b))
- {
-
- if (!BN_one(m)) goto err;
- if (!BN_mod_sqr(n1, b, p, ctx)) goto err;
- while(!BN_is_one(n1))
- {
- if (!BN_mod_mul(n1, n1, n1, p, ctx)) goto err;
- if (!BN_add_word(m, 1)) goto err;
- }
-
- if (!BN_sub(r, r, m)) goto err;
- if (!BN_sub_word(r, 1)) goto err;
- if (r->neg) goto err;
-
- if (BN_copy(n1, n0) == NULL) goto err;
- while(!BN_is_zero(r))
- {
- if (!BN_mod_mul(n1, n1, n1, p, ctx)) goto err;
- if (!BN_sub_word(r, 1)) goto err;
- }
-
- if (!BN_mod_mul(n0, n1, n1, p, ctx)) goto err;
- if (BN_copy(r, m) == NULL) goto err;
- if (!BN_mod_mul(x, x, n1, p, ctx)) goto err;
- if (!BN_mod_mul(b, b, n0, p, ctx)) goto err;
- }
-
-
-#ifdef TEST
- BN_mod_sqr(n0, x, p, ctx);
- if (BN_cmp(n0, a)) goto err;
-#endif
-
- if (r != NULL) BN_clear_free(r);
- if (b != NULL) BN_clear_free(b);
- if (m != NULL) BN_clear_free(m);
- ctx->tos -= 2;
- return 1;
-err:
- if (r != NULL) BN_clear_free(r);
- if (b != NULL) BN_clear_free(b);
- if (m != NULL) BN_clear_free(m);
- ctx->tos -= 2;
- return 0;
-}
+/* + * + * bn_modfs.c + * + * Some Modular Arithmetic Functions. + * + * Copyright (C) Lenka Fibikova 2000 + * + * + */ + + +#include <stdio.h> +#include <stdlib.h> +#include <assert.h> + +#include "bn_modfs.h" + +#define MAX_ROUNDS 10 + +int BN_smod(BIGNUM *rem, BIGNUM *m, BIGNUM *d, BN_CTX *ctx) +{ + int r_sign; + + assert(rem != NULL && m != NULL && d != NULL && ctx != NULL); + + if (d->neg) return 0; + r_sign = m->neg; + + if (r_sign) m->neg = 0; + if (!(BN_div(NULL,rem,m,d,ctx))) return 0; + if (r_sign) + { + m->neg = r_sign; + if (!BN_is_zero(rem)) + { + rem->neg = r_sign; + BN_add(rem, rem, d); + } + } + return 1; +} + +int BN_mod_sub(BIGNUM *r, BIGNUM *a, BIGNUM *b, BIGNUM *m, BN_CTX *ctx) +{ + assert(r != NULL && a != NULL && b != NULL && m != NULL && ctx != NULL); + + if (!BN_sub(r, a, b)) return 0; + return BN_smod(r, r, m, ctx); + +} + +int BN_mod_add(BIGNUM *r, BIGNUM *a, BIGNUM *b, BIGNUM *m, BN_CTX *ctx) +{ + assert(r != NULL && a != NULL && b != NULL && m != NULL && ctx != NULL); + + if (!BN_add(r, a, b)) return 0; + return BN_smod(r, r, m, ctx); + +} + +int BN_mod_sqr(BIGNUM *r, BIGNUM *a, BIGNUM *p, BN_CTX *ctx) +{ + assert(r != NULL && a != NULL && p != NULL && ctx != NULL); + + if (!BN_sqr(r, a, ctx)) return 0; + return BN_div(NULL, r, r, p, ctx); +} + +int BN_swap(BIGNUM *x, BIGNUM *y) +{ + BIGNUM *c; + + assert(x != NULL && y != NULL); + + if ((c = BN_dup(x)) == NULL) goto err; + if ((BN_copy(x, y)) == NULL) goto err; + if ((BN_copy(y, c)) == NULL) goto err; + BN_clear_free(c); + return 1; + +err: + if (c != NULL) BN_clear_free(c); + return 0; +} + + +int BN_legendre(BIGNUM *a, BIGNUM *p, BN_CTX *ctx) +{ + BIGNUM *x, *y, *y2; + BN_ULONG m; + int L; + + assert(a != NULL && p != NULL && ctx != NULL); + + x = ctx->bn[ctx->tos]; + y = ctx->bn[ctx->tos + 1]; + y2 = ctx->bn[ctx->tos + 2]; + + ctx->tos += 3; + + if (!BN_smod(x, a, p, ctx)) goto err; + if (BN_is_zero(x)) + { + + ctx->tos -= 3; + return 0; + } + + if (BN_copy(y, p) == NULL) goto err; + L = 1; + + while (1) + { + if (!BN_rshift1(y2, y)) goto err; + if (BN_cmp(x, y2) > 0) + { + if (!BN_sub(x, y, x)) goto err; + if (BN_mod_word(y, 4) == 3) + L = -L; + } + while (BN_mod_word(x, 4) == 0) + BN_div_word(x, 4); + if (BN_mod_word(x, 2) == 0) + { + BN_div_word(x, 2); + m = BN_mod_word(y, 8); + if (m == 3 || m == 5) L = -L; + } + if (BN_is_one(x)) + { + ctx->tos -= 3; + return L; + } + + if (BN_mod_word(x, 4) == 3 && BN_mod_word(y, 4) == 3) L = -L; + if (!BN_swap(x, y)) goto err; + + if (!BN_smod(x, x, y, ctx)) goto err; + + } + + +err: + ctx->tos -= 3; + return -2; + +} + +int BN_mod_sqrt(BIGNUM *x, BIGNUM *a, BIGNUM *p, BN_CTX *ctx) +/* x^2 = a (mod p) */ +{ + int ret; + BIGNUM *n0, *n1, *r, *b, *m; + int max; + + assert(x != NULL && a != NULL && p != NULL && ctx != NULL); + assert(BN_cmp(a, p) < 0); + + ret = BN_legendre(a, p, ctx); + if (ret < 0 || ret > 1) return 0; + if (ret == 0) + { + if (!BN_zero(x)) return 0; + return 1; + } + + n0 = ctx->bn[ctx->tos]; + n1 = ctx->bn[ctx->tos + 1]; + ctx->tos += 2; + + if ((r = BN_new()) == NULL) goto err; + if ((b = BN_new()) == NULL) goto err; + if ((m = BN_new()) == NULL) goto err; + + + if (!BN_zero(n0)) goto err; + if (!BN_zero(n1)) goto err; + if (!BN_zero(r)) goto err; + if (!BN_zero(b)) goto err; + if (!BN_zero(m)) goto err; + + max = 0; + + do{ + if (max++ > MAX_ROUNDS) goto err; /* if p is not prime could never stop*/ + if (!BN_add_word(m, 1)) goto err; + ret = BN_legendre(m, p, ctx); + if (ret < -1 || ret > 1) goto err; + + }while(ret != -1); + + if (BN_copy(n1, p) == NULL) goto err; + if (!BN_sub_word(n1, 1)) goto err; + + while (!BN_is_odd(n1)) + { + if (!BN_add_word(r, 1)) goto err; + if (!BN_rshift1(n1, n1)) goto err; + } + + if (!BN_mod_exp_simple(n0, m, n1, p, ctx)) goto err; + + if (!BN_sub_word(n1, 1)) goto err; + if (!BN_rshift1(n1, n1)) goto err; + if (!BN_mod_exp_simple(x, a, n1, p, ctx)) goto err; + + if (!BN_mod_sqr(b, x, p, ctx)) goto err; + if (!BN_mod_mul(b, b, a, p, ctx)) goto err; + + if (!BN_mod_mul(x, x, a, p, ctx)) goto err; + + while (!BN_is_one(b)) + { + + if (!BN_one(m)) goto err; + if (!BN_mod_sqr(n1, b, p, ctx)) goto err; + while(!BN_is_one(n1)) + { + if (!BN_mod_mul(n1, n1, n1, p, ctx)) goto err; + if (!BN_add_word(m, 1)) goto err; + } + + if (!BN_sub(r, r, m)) goto err; + if (!BN_sub_word(r, 1)) goto err; + if (r->neg) goto err; + + if (BN_copy(n1, n0) == NULL) goto err; + while(!BN_is_zero(r)) + { + if (!BN_mod_mul(n1, n1, n1, p, ctx)) goto err; + if (!BN_sub_word(r, 1)) goto err; + } + + if (!BN_mod_mul(n0, n1, n1, p, ctx)) goto err; + if (BN_copy(r, m) == NULL) goto err; + if (!BN_mod_mul(x, x, n1, p, ctx)) goto err; + if (!BN_mod_mul(b, b, n0, p, ctx)) goto err; + } + + +#ifdef TEST + BN_mod_sqr(n0, x, p, ctx); + if (BN_cmp(n0, a)) goto err; +#endif + + if (r != NULL) BN_clear_free(r); + if (b != NULL) BN_clear_free(b); + if (m != NULL) BN_clear_free(m); + ctx->tos -= 2; + return 1; +err: + if (r != NULL) BN_clear_free(r); + if (b != NULL) BN_clear_free(b); + if (m != NULL) BN_clear_free(m); + ctx->tos -= 2; + return 0; +} diff --git a/crypto/bn/bn_modfs.h b/crypto/bn/bn_modfs.h index b7ae4964d8..c596ca3973 100644 --- a/crypto/bn/bn_modfs.h +++ b/crypto/bn/bn_modfs.h @@ -1,32 +1,32 @@ -/*
- *
- * bn_modfs.h
- *
- * Some Modular Arithmetic Functions.
- *
- * Copyright (C) Lenka Fibikova 2000
- *
- *
- */
-
-#ifndef HEADER_BN_MODFS_H
-#define HEADER_BN_MODFS_H
-
-
-#include "bn.h"
-
-#ifdef BN_is_zero
-#undef BN_is_zero
-#define BN_is_zero(a) (((a)->top == 0) || (((a)->top == 1) && ((a)->d[0] == (BN_ULONG)0)))
-#endif /*BN_is_zero(a)*/
-
-
-int BN_smod(BIGNUM *rem, BIGNUM *m, BIGNUM *d, BN_CTX *ctx);
-int BN_mod_sub(BIGNUM *r, BIGNUM *a, BIGNUM *b, BIGNUM *m, BN_CTX *ctx);
-int BN_mod_add(BIGNUM *r, BIGNUM *a, BIGNUM *b, BIGNUM *m, BN_CTX *ctx);
-int BN_mod_sqr(BIGNUM *r, BIGNUM *a, BIGNUM *p, BN_CTX *ctx);
-int BN_swap(BIGNUM *x, BIGNUM *y);
-int BN_legendre(BIGNUM *a, BIGNUM *p, BN_CTX *ctx);
-int BN_mod_sqrt(BIGNUM *x, BIGNUM *a, BIGNUM *p, BN_CTX *ctx);
-
+/* + * + * bn_modfs.h + * + * Some Modular Arithmetic Functions. + * + * Copyright (C) Lenka Fibikova 2000 + * + * + */ + +#ifndef HEADER_BN_MODFS_H +#define HEADER_BN_MODFS_H + + +#include "bn.h" + +#ifdef BN_is_zero +#undef BN_is_zero +#define BN_is_zero(a) (((a)->top == 0) || (((a)->top == 1) && ((a)->d[0] == (BN_ULONG)0))) +#endif /*BN_is_zero(a)*/ + + +int BN_smod(BIGNUM *rem, BIGNUM *m, BIGNUM *d, BN_CTX *ctx); +int BN_mod_sub(BIGNUM *r, BIGNUM *a, BIGNUM *b, BIGNUM *m, BN_CTX *ctx); +int BN_mod_add(BIGNUM *r, BIGNUM *a, BIGNUM *b, BIGNUM *m, BN_CTX *ctx); +int BN_mod_sqr(BIGNUM *r, BIGNUM *a, BIGNUM *p, BN_CTX *ctx); +int BN_swap(BIGNUM *x, BIGNUM *y); +int BN_legendre(BIGNUM *a, BIGNUM *p, BN_CTX *ctx); +int BN_mod_sqrt(BIGNUM *x, BIGNUM *a, BIGNUM *p, BN_CTX *ctx); + #endif
\ No newline at end of file diff --git a/crypto/bn/bn_mont2.c b/crypto/bn/bn_mont2.c index 9f6222fb13..871282400c 100644 --- a/crypto/bn/bn_mont2.c +++ b/crypto/bn/bn_mont2.c @@ -1,374 +1,374 @@ -/*
- *
- * bn_mont2.c
- *
- * Montgomery Modular Arithmetic Functions.
- *
- * Copyright (C) Lenka Fibikova 2000
- *
- *
- */
-
-
-#include <stdio.h>
-#include <stdlib.h>
-#include <assert.h>
-
-#include "bn.h"
-#include "bn_modfs.h"
-#include "bn_mont2.h"
-
-#define BN_mask_word(x, m) ((x->d[0]) & (m))
-
-BN_MONTGOMERY *BN_mont_new()
-{
- BN_MONTGOMERY *ret;
-
- ret=(BN_MONTGOMERY *)malloc(sizeof(BN_MONTGOMERY));
-
- if (ret == NULL) return NULL;
-
- if ((ret->p = BN_new()) == NULL)
- {
- free(ret);
- return NULL;
- }
-
- return ret;
-}
-
-
-void BN_mont_clear_free(BN_MONTGOMERY *mont)
-{
- if (mont == NULL) return;
-
- if (mont->p != NULL) BN_clear_free(mont->p);
-
- mont->p_num_bytes = 0;
- mont->R_num_bits = 0;
- mont->p_inv_b_neg = 0;
-}
-
-int BN_to_mont(BIGNUM *x, BN_MONTGOMERY *mont, BN_CTX *ctx)
-{
- assert(x != NULL);
-
- assert(mont != NULL);
- assert(mont->p != NULL);
-
- assert(ctx != NULL);
-
- if (!BN_lshift(x, x, mont->R_num_bits)) return 0;
- if (!BN_mod(x, x, mont->p, ctx)) return 0;
-
- return 1;
-}
-
-
-static BN_ULONG BN_mont_inv(BIGNUM *a, int e, BN_CTX *ctx)
-/* y = a^{-1} (mod 2^e) for an odd number a */
-{
- BN_ULONG y, exp, mask;
- BIGNUM *x, *xy, *x_sh;
- int i;
-
- assert(a != NULL && ctx != NULL);
- assert(e <= BN_BITS2);
- assert(BN_is_odd(a));
- assert(!BN_is_zero(a) && !a->neg);
-
-
- y = 1;
- exp = 2;
- mask = 3;
- if((x = BN_dup(a)) == NULL) return 0;
- if(!BN_mask_bits(x, e)) return 0;
-
- xy = ctx->bn[ctx->tos];
- x_sh = ctx->bn[ctx->tos + 1];
- ctx->tos += 2;
-
- if (BN_copy(xy, x) == NULL) goto err;
- if (!BN_lshift1(x_sh, x)) goto err;
-
-
- for (i = 2; i <= e; i++)
- {
- if (exp < BN_mask_word(xy, mask))
- {
- y = y + exp;
- if (!BN_add(xy, xy, x_sh)) goto err;
- }
-
- exp <<= 1;
- if (!BN_lshift1(x_sh, x_sh)) goto err;
- mask <<= 1;
- mask++;
- }
-
-
-#ifdef TEST
- if (xy->d[0] != 1) goto err;
-#endif
-
- if (x != NULL) BN_clear_free(x);
- ctx->tos -= 2;
- return y;
-
-
-err:
- if (x != NULL) BN_clear_free(x);
- ctx->tos -= 2;
- return 0;
-
-}
-
-int BN_mont_set(BIGNUM *p, BN_MONTGOMERY *mont, BN_CTX *ctx)
-{
- assert(p != NULL && ctx != NULL);
- assert(mont != NULL);
- assert(mont->p != NULL);
- assert(!BN_is_zero(p) && !p->neg);
-
-
- mont->p_num_bytes = p->top;
- mont->R_num_bits = (mont->p_num_bytes) * BN_BITS2;
-
- if (BN_copy(mont->p, p) == NULL);
-
- mont->p_inv_b_neg = BN_mont_inv(p, BN_BITS2, ctx);
- mont->p_inv_b_neg = 0 - mont->p_inv_b_neg;
-
- return 1;
-}
-
-static int BN_cpy_mul_word(BIGNUM *ret, BIGNUM *a, BN_ULONG w)
-/* ret = a * w */
-{
- if (BN_copy(ret, a) == NULL) return 0;
-
- if (!BN_mul_word(ret, w)) return 0;
-
- return 1;
-}
-
-
-int BN_mont_red(BIGNUM *y, BN_MONTGOMERY *mont, BN_CTX *ctx)
-/* yR^{-1} (mod p) */
-{
- int i;
- BIGNUM *up, *p;
- BN_ULONG u;
-
- assert(y != NULL && mont != NULL && ctx != NULL);
- assert(mont->p != NULL);
- assert(BN_cmp(y, mont->p) < 0);
- assert(!y->neg);
-
-
- if (BN_is_zero(y)) return 1;
-
- p = mont->p;
- up = ctx->bn[ctx->tos];
- ctx->tos += 1;
-
-
- for (i = 0; i < mont->p_num_bytes; i++)
- {
- u = (y->d[0]) * mont->p_inv_b_neg; /* u = y_0 * p' */
-
- if (!BN_cpy_mul_word(up, p, u)) goto err; /* up = u * p */
-
- if (!BN_add(y, y, up)) goto err;
-#ifdef TEST
- if (y->d[0]) goto err;
-#endif
- if (!BN_rshift(y, y, BN_BITS2)) goto err; /* y = (y + up)/b */
- }
-
-
- if (BN_cmp(y, mont->p) >= 0)
- {
- if (!BN_sub(y, y, mont->p)) goto err;
- }
-
- ctx->tos -= 1;
- return 1;
-
-err:
- ctx->tos -= 1;
- return 0;
-
-}
-
-
-int BN_mont_mod_mul(BIGNUM *r, BIGNUM *x, BIGNUM *y, BN_MONTGOMERY *mont, BN_CTX *ctx)
-/* r = x * y mod p */
-/* r != x && r! = y !!! */
-{
- BIGNUM *xiy, *up;
- BN_ULONG u;
- int i;
-
-
- assert(r != x && r != y);
- assert(r != NULL && x != NULL && y != NULL && mont != NULL && ctx != NULL);
- assert(mont->p != NULL);
- assert(BN_cmp(x, mont->p) < 0);
- assert(BN_cmp(y, mont->p) < 0);
- assert(!x->neg);
- assert(!y->neg);
-
- if (BN_is_zero(x) || BN_is_zero(y))
- {
- if (!BN_zero(r)) return 0;
- return 1;
- }
-
-
-
- xiy = ctx->bn[ctx->tos];
- up = ctx->bn[ctx->tos + 1];
- ctx->tos += 2;
-
- if (!BN_zero(r)) goto err;
-
- for (i = 0; i < x->top; i++)
- {
- u = (r->d[0] + x->d[i] * y->d[0]) * mont->p_inv_b_neg;
-
- if (!BN_cpy_mul_word(xiy, y, x->d[i])) goto err;
- if (!BN_cpy_mul_word(up, mont->p, u)) goto err;
-
- if (!BN_add(r, r, xiy)) goto err;
- if (!BN_add(r, r, up)) goto err;
-
-#ifdef TEST
- if (r->d[0]) goto err;
-#endif
- if (!BN_rshift(r, r, BN_BITS2)) goto err;
- }
-
- for (i = x->top; i < mont->p_num_bytes; i++)
- {
- u = (r->d[0]) * mont->p_inv_b_neg;
-
- if (!BN_cpy_mul_word(up, mont->p, u)) goto err;
-
- if (!BN_add(r, r, up)) goto err;
-
-#ifdef TEST
- if (r->d[0]) goto err;
-#endif
- if (!BN_rshift(r, r, BN_BITS2)) goto err;
- }
-
-
- if (BN_cmp(r, mont->p) >= 0)
- {
- if (!BN_sub(r, r, mont->p)) goto err;
- }
-
-
- ctx->tos -= 2;
- return 1;
-
-err:
- ctx->tos -= 2;
- return 0;
-}
-
-int BN_mont_mod_add(BIGNUM *r, BIGNUM *x, BIGNUM *y, BN_MONTGOMERY *mont)
-{
- assert(r != NULL && x != NULL && y != NULL && mont != NULL);
- assert(mont->p != NULL);
- assert(BN_cmp(x, mont->p) < 0);
- assert(BN_cmp(y, mont->p) < 0);
- assert(!x->neg);
- assert(!y->neg);
-
- if (!BN_add(r, x, y)) return 0;
- if (BN_cmp(r, mont->p) >= 0)
- {
- if (!BN_sub(r, r, mont->p)) return 0;
- }
-
- return 1;
-}
-
-
-int BN_mont_mod_sub(BIGNUM *r, BIGNUM *x, BIGNUM *y, BN_MONTGOMERY *mont)
-{
- assert(r != NULL && x != NULL && y != NULL && mont != NULL);
- assert(mont->p != NULL);
- assert(BN_cmp(x, mont->p) < 0);
- assert(BN_cmp(y, mont->p) < 0);
- assert(!x->neg);
- assert(!y->neg);
-
- if (!BN_sub(r, x, y)) return 0;
- if (r->neg)
- {
- if (!BN_add(r, r, mont->p)) return 0;
- }
-
- return 1;
-}
-
-int BN_mont_mod_lshift1(BIGNUM *r, BIGNUM *x, BN_MONTGOMERY *mont)
-{
- assert(r != NULL && x != NULL && mont != NULL);
- assert(mont->p != NULL);
- assert(BN_cmp(x, mont->p) < 0);
- assert(!x->neg);
-
- if (!BN_lshift1(r, x)) return 0;
-
- if (BN_cmp(r, mont->p) >= 0)
- {
- if (!BN_sub(r, r, mont->p)) return 0;
- }
-
- return 1;
-}
-
-int BN_mont_mod_lshift(BIGNUM *r, BIGNUM *x, int n, BN_MONTGOMERY *mont)
-{
- int sh_nb;
-
- assert(r != NULL && x != NULL && mont != NULL);
- assert(mont->p != NULL);
- assert(BN_cmp(x, mont->p) < 0);
- assert(!x->neg);
- assert(n > 0);
-
- if (r != x)
- {
- if (BN_copy(r, x) == NULL) return 0;
- }
-
- while (n)
- {
- sh_nb = BN_num_bits(mont->p) - BN_num_bits(r);
- if (sh_nb > n) sh_nb = n;
-
- if (sh_nb)
- {
- if(!BN_lshift(r, r, sh_nb)) return 0;
- }
- else
- {
- sh_nb = 1;
- if (!BN_lshift1(r, r)) return 0;
- }
-
- if (BN_cmp(r, mont->p) >= 0)
- {
- if (!BN_sub(r, r, mont->p)) return 0;
- }
-
- n -= sh_nb;
- }
-
- return 1;
-}
+/* + * + * bn_mont2.c + * + * Montgomery Modular Arithmetic Functions. + * + * Copyright (C) Lenka Fibikova 2000 + * + * + */ + + +#include <stdio.h> +#include <stdlib.h> +#include <assert.h> + +#include "bn.h" +#include "bn_modfs.h" +#include "bn_mont2.h" + +#define BN_mask_word(x, m) ((x->d[0]) & (m)) + +BN_MONTGOMERY *BN_mont_new() +{ + BN_MONTGOMERY *ret; + + ret=(BN_MONTGOMERY *)malloc(sizeof(BN_MONTGOMERY)); + + if (ret == NULL) return NULL; + + if ((ret->p = BN_new()) == NULL) + { + free(ret); + return NULL; + } + + return ret; +} + + +void BN_mont_clear_free(BN_MONTGOMERY *mont) +{ + if (mont == NULL) return; + + if (mont->p != NULL) BN_clear_free(mont->p); + + mont->p_num_bytes = 0; + mont->R_num_bits = 0; + mont->p_inv_b_neg = 0; +} + +int BN_to_mont(BIGNUM *x, BN_MONTGOMERY *mont, BN_CTX *ctx) +{ + assert(x != NULL); + + assert(mont != NULL); + assert(mont->p != NULL); + + assert(ctx != NULL); + + if (!BN_lshift(x, x, mont->R_num_bits)) return 0; + if (!BN_mod(x, x, mont->p, ctx)) return 0; + + return 1; +} + + +static BN_ULONG BN_mont_inv(BIGNUM *a, int e, BN_CTX *ctx) +/* y = a^{-1} (mod 2^e) for an odd number a */ +{ + BN_ULONG y, exp, mask; + BIGNUM *x, *xy, *x_sh; + int i; + + assert(a != NULL && ctx != NULL); + assert(e <= BN_BITS2); + assert(BN_is_odd(a)); + assert(!BN_is_zero(a) && !a->neg); + + + y = 1; + exp = 2; + mask = 3; + if((x = BN_dup(a)) == NULL) return 0; + if(!BN_mask_bits(x, e)) return 0; + + xy = ctx->bn[ctx->tos]; + x_sh = ctx->bn[ctx->tos + 1]; + ctx->tos += 2; + + if (BN_copy(xy, x) == NULL) goto err; + if (!BN_lshift1(x_sh, x)) goto err; + + + for (i = 2; i <= e; i++) + { + if (exp < BN_mask_word(xy, mask)) + { + y = y + exp; + if (!BN_add(xy, xy, x_sh)) goto err; + } + + exp <<= 1; + if (!BN_lshift1(x_sh, x_sh)) goto err; + mask <<= 1; + mask++; + } + + +#ifdef TEST + if (xy->d[0] != 1) goto err; +#endif + + if (x != NULL) BN_clear_free(x); + ctx->tos -= 2; + return y; + + +err: + if (x != NULL) BN_clear_free(x); + ctx->tos -= 2; + return 0; + +} + +int BN_mont_set(BIGNUM *p, BN_MONTGOMERY *mont, BN_CTX *ctx) +{ + assert(p != NULL && ctx != NULL); + assert(mont != NULL); + assert(mont->p != NULL); + assert(!BN_is_zero(p) && !p->neg); + + + mont->p_num_bytes = p->top; + mont->R_num_bits = (mont->p_num_bytes) * BN_BITS2; + + if (BN_copy(mont->p, p) == NULL); + + mont->p_inv_b_neg = BN_mont_inv(p, BN_BITS2, ctx); + mont->p_inv_b_neg = 0 - mont->p_inv_b_neg; + + return 1; +} + +static int BN_cpy_mul_word(BIGNUM *ret, BIGNUM *a, BN_ULONG w) +/* ret = a * w */ +{ + if (BN_copy(ret, a) == NULL) return 0; + + if (!BN_mul_word(ret, w)) return 0; + + return 1; +} + + +int BN_mont_red(BIGNUM *y, BN_MONTGOMERY *mont, BN_CTX *ctx) +/* yR^{-1} (mod p) */ +{ + int i; + BIGNUM *up, *p; + BN_ULONG u; + + assert(y != NULL && mont != NULL && ctx != NULL); + assert(mont->p != NULL); + assert(BN_cmp(y, mont->p) < 0); + assert(!y->neg); + + + if (BN_is_zero(y)) return 1; + + p = mont->p; + up = ctx->bn[ctx->tos]; + ctx->tos += 1; + + + for (i = 0; i < mont->p_num_bytes; i++) + { + u = (y->d[0]) * mont->p_inv_b_neg; /* u = y_0 * p' */ + + if (!BN_cpy_mul_word(up, p, u)) goto err; /* up = u * p */ + + if (!BN_add(y, y, up)) goto err; +#ifdef TEST + if (y->d[0]) goto err; +#endif + if (!BN_rshift(y, y, BN_BITS2)) goto err; /* y = (y + up)/b */ + } + + + if (BN_cmp(y, mont->p) >= 0) + { + if (!BN_sub(y, y, mont->p)) goto err; + } + + ctx->tos -= 1; + return 1; + +err: + ctx->tos -= 1; + return 0; + +} + + +int BN_mont_mod_mul(BIGNUM *r, BIGNUM *x, BIGNUM *y, BN_MONTGOMERY *mont, BN_CTX *ctx) +/* r = x * y mod p */ +/* r != x && r! = y !!! */ +{ + BIGNUM *xiy, *up; + BN_ULONG u; + int i; + + + assert(r != x && r != y); + assert(r != NULL && x != NULL && y != NULL && mont != NULL && ctx != NULL); + assert(mont->p != NULL); + assert(BN_cmp(x, mont->p) < 0); + assert(BN_cmp(y, mont->p) < 0); + assert(!x->neg); + assert(!y->neg); + + if (BN_is_zero(x) || BN_is_zero(y)) + { + if (!BN_zero(r)) return 0; + return 1; + } + + + + xiy = ctx->bn[ctx->tos]; + up = ctx->bn[ctx->tos + 1]; + ctx->tos += 2; + + if (!BN_zero(r)) goto err; + + for (i = 0; i < x->top; i++) + { + u = (r->d[0] + x->d[i] * y->d[0]) * mont->p_inv_b_neg; + + if (!BN_cpy_mul_word(xiy, y, x->d[i])) goto err; + if (!BN_cpy_mul_word(up, mont->p, u)) goto err; + + if (!BN_add(r, r, xiy)) goto err; + if (!BN_add(r, r, up)) goto err; + +#ifdef TEST + if (r->d[0]) goto err; +#endif + if (!BN_rshift(r, r, BN_BITS2)) goto err; + } + + for (i = x->top; i < mont->p_num_bytes; i++) + { + u = (r->d[0]) * mont->p_inv_b_neg; + + if (!BN_cpy_mul_word(up, mont->p, u)) goto err; + + if (!BN_add(r, r, up)) goto err; + +#ifdef TEST + if (r->d[0]) goto err; +#endif + if (!BN_rshift(r, r, BN_BITS2)) goto err; + } + + + if (BN_cmp(r, mont->p) >= 0) + { + if (!BN_sub(r, r, mont->p)) goto err; + } + + + ctx->tos -= 2; + return 1; + +err: + ctx->tos -= 2; + return 0; +} + +int BN_mont_mod_add(BIGNUM *r, BIGNUM *x, BIGNUM *y, BN_MONTGOMERY *mont) +{ + assert(r != NULL && x != NULL && y != NULL && mont != NULL); + assert(mont->p != NULL); + assert(BN_cmp(x, mont->p) < 0); + assert(BN_cmp(y, mont->p) < 0); + assert(!x->neg); + assert(!y->neg); + + if (!BN_add(r, x, y)) return 0; + if (BN_cmp(r, mont->p) >= 0) + { + if (!BN_sub(r, r, mont->p)) return 0; + } + + return 1; +} + + +int BN_mont_mod_sub(BIGNUM *r, BIGNUM *x, BIGNUM *y, BN_MONTGOMERY *mont) +{ + assert(r != NULL && x != NULL && y != NULL && mont != NULL); + assert(mont->p != NULL); + assert(BN_cmp(x, mont->p) < 0); + assert(BN_cmp(y, mont->p) < 0); + assert(!x->neg); + assert(!y->neg); + + if (!BN_sub(r, x, y)) return 0; + if (r->neg) + { + if (!BN_add(r, r, mont->p)) return 0; + } + + return 1; +} + +int BN_mont_mod_lshift1(BIGNUM *r, BIGNUM *x, BN_MONTGOMERY *mont) +{ + assert(r != NULL && x != NULL && mont != NULL); + assert(mont->p != NULL); + assert(BN_cmp(x, mont->p) < 0); + assert(!x->neg); + + if (!BN_lshift1(r, x)) return 0; + + if (BN_cmp(r, mont->p) >= 0) + { + if (!BN_sub(r, r, mont->p)) return 0; + } + + return 1; +} + +int BN_mont_mod_lshift(BIGNUM *r, BIGNUM *x, int n, BN_MONTGOMERY *mont) +{ + i |