2 * Copyright 1998-2016 The OpenSSL Project Authors. All Rights Reserved.
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
10 #include "internal/cryptlib.h"
13 int BN_nnmod(BIGNUM *r, const BIGNUM *m, const BIGNUM *d, BN_CTX *ctx)
16 * like BN_mod, but returns non-negative remainder (i.e., 0 <= r < |d|
20 if (!(BN_mod(r, m, d, ctx)))
24 /* now -|d| < r < 0, so we have to set r := r + |d| */
25 return (d->neg ? BN_sub : BN_add) (r, r, d);
28 int BN_mod_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m,
33 return BN_nnmod(r, r, m, ctx);
37 * BN_mod_add variant that may be used if both a and b are non-negative and
40 int BN_mod_add_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *b,
43 if (!BN_uadd(r, a, b))
45 if (BN_ucmp(r, m) >= 0)
46 return BN_usub(r, r, m);
50 int BN_mod_sub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m,
55 return BN_nnmod(r, r, m, ctx);
59 * BN_mod_sub variant that may be used if both a and b are non-negative and
62 int BN_mod_sub_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *b,
68 return BN_add(r, r, m);
73 int BN_mod_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m,
84 if ((t = BN_CTX_get(ctx)) == NULL)
87 if (!BN_sqr(t, a, ctx))
90 if (!BN_mul(t, a, b, ctx))
93 if (!BN_nnmod(r, t, m, ctx))
102 int BN_mod_sqr(BIGNUM *r, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx)
104 if (!BN_sqr(r, a, ctx))
106 /* r->neg == 0, thus we don't need BN_nnmod */
107 return BN_mod(r, r, m, ctx);
110 int BN_mod_lshift1(BIGNUM *r, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx)
112 if (!BN_lshift1(r, a))
115 return BN_nnmod(r, r, m, ctx);
119 * BN_mod_lshift1 variant that may be used if a is non-negative and less than
122 int BN_mod_lshift1_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *m)
124 if (!BN_lshift1(r, a))
127 if (BN_cmp(r, m) >= 0)
128 return BN_sub(r, r, m);
132 int BN_mod_lshift(BIGNUM *r, const BIGNUM *a, int n, const BIGNUM *m,
135 BIGNUM *abs_m = NULL;
138 if (!BN_nnmod(r, a, m, ctx))
148 ret = BN_mod_lshift_quick(r, r, n, (abs_m ? abs_m : m));
156 * BN_mod_lshift variant that may be used if a is non-negative and less than
159 int BN_mod_lshift_quick(BIGNUM *r, const BIGNUM *a, int n, const BIGNUM *m)
162 if (BN_copy(r, a) == NULL)
170 max_shift = BN_num_bits(m) - BN_num_bits(r);
174 BNerr(BN_F_BN_MOD_LSHIFT_QUICK, BN_R_INPUT_NOT_REDUCED);
182 if (!BN_lshift(r, r, max_shift))
186 if (!BN_lshift1(r, r))
191 /* BN_num_bits(r) <= BN_num_bits(m) */
193 if (BN_cmp(r, m) >= 0) {
194 if (!BN_sub(r, r, m))