crypto/bn/bn_mod.c

   1 /*
   2  * Copyright 1998-2016 The OpenSSL Project Authors. All Rights Reserved.
   3  *
   4  * Licensed under the OpenSSL license (the "License").  You may not use
   5  * this file except in compliance with the License.  You can obtain a copy
   6  * in the file LICENSE in the source distribution or at
   7  * https://www.openssl.org/source/license.html
   8  */
   9
  10 #include "internal/cryptlib.h"
  11 #include "bn_lcl.h"
  12
  13 int BN_nnmod(BIGNUM *r, const BIGNUM *m, const BIGNUM *d, BN_CTX *ctx)
  14 {
  15     /*
  16      * like BN_mod, but returns non-negative remainder (i.e., 0 <= r < |d|
  17      * always holds)
  18      */
  19
  20     if (!(BN_mod(r, m, d, ctx)))
  21         return 0;
  22     if (!r->neg)
  23         return 1;
  24     /* now   -|d| < r < 0,  so we have to set  r := r + |d| */
  25     return (d->neg ? BN_sub : BN_add) (r, r, d);
  26 }
  27
  28 int BN_mod_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m,
  29                BN_CTX *ctx)
  30 {
  31     if (!BN_add(r, a, b))
  32         return 0;
  33     return BN_nnmod(r, r, m, ctx);
  34 }
  35
  36 /*
  37  * BN_mod_add variant that may be used if both a and b are non-negative and
  38  * less than m
  39  */
  40 int BN_mod_add_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *b,
  41                      const BIGNUM *m)
  42 {
  43     if (!BN_uadd(r, a, b))
  44         return 0;
  45     if (BN_ucmp(r, m) >= 0)
  46         return BN_usub(r, r, m);
  47     return 1;
  48 }
  49
  50 int BN_mod_sub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m,
  51                BN_CTX *ctx)
  52 {
  53     if (!BN_sub(r, a, b))
  54         return 0;
  55     return BN_nnmod(r, r, m, ctx);
  56 }
  57
  58 /*
  59  * BN_mod_sub variant that may be used if both a and b are non-negative and
  60  * less than m
  61  */
  62 int BN_mod_sub_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *b,
  63                      const BIGNUM *m)
  64 {
  65     if (!BN_sub(r, a, b))
  66         return 0;
  67     if (r->neg)
  68         return BN_add(r, r, m);
  69     return 1;
  70 }
  71
  72 /* slow but works */
  73 int BN_mod_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m,
  74                BN_CTX *ctx)
  75 {
  76     BIGNUM *t;
  77     int ret = 0;
  78
  79     bn_check_top(a);
  80     bn_check_top(b);
  81     bn_check_top(m);
  82
  83     BN_CTX_start(ctx);
  84     if ((t = BN_CTX_get(ctx)) == NULL)
  85         goto err;
  86     if (a == b) {
  87         if (!BN_sqr(t, a, ctx))
  88             goto err;
  89     } else {
  90         if (!BN_mul(t, a, b, ctx))
  91             goto err;
  92     }
  93     if (!BN_nnmod(r, t, m, ctx))
  94         goto err;
  95     bn_check_top(r);
  96     ret = 1;
  97  err:
  98     BN_CTX_end(ctx);
  99     return (ret);
 100 }
 101
 102 int BN_mod_sqr(BIGNUM *r, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx)
 103 {
 104     if (!BN_sqr(r, a, ctx))
 105         return 0;
 106     /* r->neg == 0,  thus we don't need BN_nnmod */
 107     return BN_mod(r, r, m, ctx);
 108 }
 109
 110 int BN_mod_lshift1(BIGNUM *r, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx)
 111 {
 112     if (!BN_lshift1(r, a))
 113         return 0;
 114     bn_check_top(r);
 115     return BN_nnmod(r, r, m, ctx);
 116 }
 117
 118 /*
 119  * BN_mod_lshift1 variant that may be used if a is non-negative and less than
 120  * m
 121  */
 122 int BN_mod_lshift1_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *m)
 123 {
 124     if (!BN_lshift1(r, a))
 125         return 0;
 126     bn_check_top(r);
 127     if (BN_cmp(r, m) >= 0)
 128         return BN_sub(r, r, m);
 129     return 1;
 130 }
 131
 132 int BN_mod_lshift(BIGNUM *r, const BIGNUM *a, int n, const BIGNUM *m,
 133                   BN_CTX *ctx)
 134 {
 135     BIGNUM *abs_m = NULL;
 136     int ret;
 137
 138     if (!BN_nnmod(r, a, m, ctx))
 139         return 0;
 140
 141     if (m->neg) {
 142         abs_m = BN_dup(m);
 143         if (abs_m == NULL)
 144             return 0;
 145         abs_m->neg = 0;
 146     }
 147
 148     ret = BN_mod_lshift_quick(r, r, n, (abs_m ? abs_m : m));
 149     bn_check_top(r);
 150
 151     BN_free(abs_m);
 152     return ret;
 153 }
 154
 155 /*
 156  * BN_mod_lshift variant that may be used if a is non-negative and less than
 157  * m
 158  */
 159 int BN_mod_lshift_quick(BIGNUM *r, const BIGNUM *a, int n, const BIGNUM *m)
 160 {
 161     if (r != a) {
 162         if (BN_copy(r, a) == NULL)
 163             return 0;
 164     }
 165
 166     while (n > 0) {
 167         int max_shift;
 168
 169         /* 0 < r < m */
 170         max_shift = BN_num_bits(m) - BN_num_bits(r);
 171         /* max_shift >= 0 */
 172
 173         if (max_shift < 0) {
 174             BNerr(BN_F_BN_MOD_LSHIFT_QUICK, BN_R_INPUT_NOT_REDUCED);
 175             return 0;
 176         }
 177
 178         if (max_shift > n)
 179             max_shift = n;
 180
 181         if (max_shift) {
 182             if (!BN_lshift(r, r, max_shift))
 183                 return 0;
 184             n -= max_shift;
 185         } else {
 186             if (!BN_lshift1(r, r))
 187                 return 0;
 188             --n;
 189         }
 190
 191         /* BN_num_bits(r) <= BN_num_bits(m) */
 192
 193         if (BN_cmp(r, m) >= 0) {
 194             if (!BN_sub(r, r, m))
 195                 return 0;
 196         }
 197     }
 198     bn_check_top(r);
 199
 200     return 1;
 201 }