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