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 }