1 /*
2 * Copyright 1998-2024 The OpenSSL Project Authors. All Rights Reserved.
3 *
4 * Licensed under the Apache License 2.0 (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 "internal/nelem.h"
12 #include "bn_local.h"
13
BN_nnmod(BIGNUM * r,const BIGNUM * m,const BIGNUM * d,BN_CTX * ctx)14 int BN_nnmod(BIGNUM *r, const BIGNUM *m, const BIGNUM *d, BN_CTX *ctx)
15 {
16 /*
17 * like BN_mod, but returns non-negative remainder (i.e., 0 <= r < |d|
18 * always holds)
19 */
20
21 if (r == d) {
22 ERR_raise(ERR_LIB_BN, ERR_R_PASSED_INVALID_ARGUMENT);
23 return 0;
24 }
25
26 if (!(BN_mod(r, m, d, ctx)))
27 return 0;
28 if (!r->neg)
29 return 1;
30 /* now -|d| < r < 0, so we have to set r := r + |d| */
31 return (d->neg ? BN_sub : BN_add) (r, r, d);
32 }
33
BN_mod_add(BIGNUM * r,const BIGNUM * a,const BIGNUM * b,const BIGNUM * m,BN_CTX * ctx)34 int BN_mod_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m,
35 BN_CTX *ctx)
36 {
37 if (!BN_add(r, a, b))
38 return 0;
39 return BN_nnmod(r, r, m, ctx);
40 }
41
42 /*
43 * BN_mod_add variant that may be used if both a and b are non-negative and
44 * less than m. The original algorithm was
45 *
46 * if (!BN_uadd(r, a, b))
47 * return 0;
48 * if (BN_ucmp(r, m) >= 0)
49 * return BN_usub(r, r, m);
50 *
51 * which is replaced with addition, subtracting modulus, and conditional
52 * move depending on whether or not subtraction borrowed.
53 */
bn_mod_add_fixed_top(BIGNUM * r,const BIGNUM * a,const BIGNUM * b,const BIGNUM * m)54 int bn_mod_add_fixed_top(BIGNUM *r, const BIGNUM *a, const BIGNUM *b,
55 const BIGNUM *m)
56 {
57 size_t i, ai, bi, mtop = m->top;
58 BN_ULONG storage[1024 / BN_BITS2];
59 BN_ULONG carry, temp, mask, *rp, *tp = storage;
60 const BN_ULONG *ap, *bp;
61
62 if (bn_wexpand(r, mtop) == NULL)
63 return 0;
64
65 if (mtop > OSSL_NELEM(storage)) {
66 tp = OPENSSL_malloc(mtop * sizeof(BN_ULONG));
67 if (tp == NULL)
68 return 0;
69 }
70
71 ap = a->d != NULL ? a->d : tp;
72 bp = b->d != NULL ? b->d : tp;
73
74 for (i = 0, ai = 0, bi = 0, carry = 0; i < mtop;) {
75 mask = (BN_ULONG)0 - ((i - a->top) >> (8 * sizeof(i) - 1));
76 temp = ((ap[ai] & mask) + carry) & BN_MASK2;
77 carry = (temp < carry);
78
79 mask = (BN_ULONG)0 - ((i - b->top) >> (8 * sizeof(i) - 1));
80 tp[i] = ((bp[bi] & mask) + temp) & BN_MASK2;
81 carry += (tp[i] < temp);
82
83 i++;
84 ai += (i - a->dmax) >> (8 * sizeof(i) - 1);
85 bi += (i - b->dmax) >> (8 * sizeof(i) - 1);
86 }
87 rp = r->d;
88 carry -= bn_sub_words(rp, tp, m->d, mtop);
89 for (i = 0; i < mtop; i++) {
90 rp[i] = (carry & tp[i]) | (~carry & rp[i]);
91 ((volatile BN_ULONG *)tp)[i] = 0;
92 }
93 r->top = mtop;
94 r->flags |= BN_FLG_FIXED_TOP;
95 r->neg = 0;
96
97 if (tp != storage)
98 OPENSSL_free(tp);
99
100 return 1;
101 }
102
BN_mod_add_quick(BIGNUM * r,const BIGNUM * a,const BIGNUM * b,const BIGNUM * m)103 int BN_mod_add_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *b,
104 const BIGNUM *m)
105 {
106 int ret = bn_mod_add_fixed_top(r, a, b, m);
107
108 if (ret)
109 bn_correct_top(r);
110
111 return ret;
112 }
113
BN_mod_sub(BIGNUM * r,const BIGNUM * a,const BIGNUM * b,const BIGNUM * m,BN_CTX * ctx)114 int BN_mod_sub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m,
115 BN_CTX *ctx)
116 {
117 if (!BN_sub(r, a, b))
118 return 0;
119 return BN_nnmod(r, r, m, ctx);
120 }
121
122 /*
123 * BN_mod_sub variant that may be used if both a and b are non-negative,
124 * a is less than m, while b is of same bit width as m. It's implemented
125 * as subtraction followed by two conditional additions.
126 *
127 * 0 <= a < m
128 * 0 <= b < 2^w < 2*m
129 *
130 * after subtraction
131 *
132 * -2*m < r = a - b < m
133 *
134 * Thus it takes up to two conditional additions to make |r| positive.
135 */
bn_mod_sub_fixed_top(BIGNUM * r,const BIGNUM * a,const BIGNUM * b,const BIGNUM * m)136 int bn_mod_sub_fixed_top(BIGNUM *r, const BIGNUM *a, const BIGNUM *b,
137 const BIGNUM *m)
138 {
139 size_t i, ai, bi, mtop = m->top;
140 BN_ULONG borrow, carry, ta, tb, mask, *rp;
141 const BN_ULONG *ap, *bp;
142
143 if (bn_wexpand(r, mtop) == NULL)
144 return 0;
145
146 rp = r->d;
147 ap = a->d != NULL ? a->d : rp;
148 bp = b->d != NULL ? b->d : rp;
149
150 for (i = 0, ai = 0, bi = 0, borrow = 0; i < mtop;) {
151 mask = (BN_ULONG)0 - ((i - a->top) >> (8 * sizeof(i) - 1));
152 ta = ap[ai] & mask;
153
154 mask = (BN_ULONG)0 - ((i - b->top) >> (8 * sizeof(i) - 1));
155 tb = bp[bi] & mask;
156 rp[i] = ta - tb - borrow;
157 if (ta != tb)
158 borrow = (ta < tb);
159
160 i++;
161 ai += (i - a->dmax) >> (8 * sizeof(i) - 1);
162 bi += (i - b->dmax) >> (8 * sizeof(i) - 1);
163 }
164 ap = m->d;
165 for (i = 0, mask = 0 - borrow, carry = 0; i < mtop; i++) {
166 ta = ((ap[i] & mask) + carry) & BN_MASK2;
167 carry = (ta < carry);
168 rp[i] = (rp[i] + ta) & BN_MASK2;
169 carry += (rp[i] < ta);
170 }
171 borrow -= carry;
172 for (i = 0, mask = 0 - borrow, carry = 0; i < mtop; i++) {
173 ta = ((ap[i] & mask) + carry) & BN_MASK2;
174 carry = (ta < carry);
175 rp[i] = (rp[i] + ta) & BN_MASK2;
176 carry += (rp[i] < ta);
177 }
178
179 r->top = mtop;
180 r->flags |= BN_FLG_FIXED_TOP;
181 r->neg = 0;
182
183 return 1;
184 }
185
186 /*
187 * BN_mod_sub variant that may be used if both a and b are non-negative and
188 * less than m
189 */
BN_mod_sub_quick(BIGNUM * r,const BIGNUM * a,const BIGNUM * b,const BIGNUM * m)190 int BN_mod_sub_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *b,
191 const BIGNUM *m)
192 {
193 if (r == m) {
194 ERR_raise(ERR_LIB_BN, ERR_R_PASSED_INVALID_ARGUMENT);
195 return 0;
196 }
197
198 if (!BN_sub(r, a, b))
199 return 0;
200 if (r->neg)
201 return BN_add(r, r, m);
202 return 1;
203 }
204
205 /* slow but works */
BN_mod_mul(BIGNUM * r,const BIGNUM * a,const BIGNUM * b,const BIGNUM * m,BN_CTX * ctx)206 int BN_mod_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m,
207 BN_CTX *ctx)
208 {
209 BIGNUM *t;
210 int ret = 0;
211
212 bn_check_top(a);
213 bn_check_top(b);
214 bn_check_top(m);
215
216 BN_CTX_start(ctx);
217 if ((t = BN_CTX_get(ctx)) == NULL)
218 goto err;
219 if (a == b) {
220 if (!BN_sqr(t, a, ctx))
221 goto err;
222 } else {
223 if (!BN_mul(t, a, b, ctx))
224 goto err;
225 }
226 if (!BN_nnmod(r, t, m, ctx))
227 goto err;
228 bn_check_top(r);
229 ret = 1;
230 err:
231 BN_CTX_end(ctx);
232 return ret;
233 }
234
BN_mod_sqr(BIGNUM * r,const BIGNUM * a,const BIGNUM * m,BN_CTX * ctx)235 int BN_mod_sqr(BIGNUM *r, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx)
236 {
237 if (!BN_sqr(r, a, ctx))
238 return 0;
239 /* r->neg == 0, thus we don't need BN_nnmod */
240 return BN_mod(r, r, m, ctx);
241 }
242
BN_mod_lshift1(BIGNUM * r,const BIGNUM * a,const BIGNUM * m,BN_CTX * ctx)243 int BN_mod_lshift1(BIGNUM *r, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx)
244 {
245 if (!BN_lshift1(r, a))
246 return 0;
247 bn_check_top(r);
248 return BN_nnmod(r, r, m, ctx);
249 }
250
251 /*
252 * BN_mod_lshift1 variant that may be used if a is non-negative and less than
253 * m
254 */
BN_mod_lshift1_quick(BIGNUM * r,const BIGNUM * a,const BIGNUM * m)255 int BN_mod_lshift1_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *m)
256 {
257 if (!BN_lshift1(r, a))
258 return 0;
259 bn_check_top(r);
260 if (BN_cmp(r, m) >= 0)
261 return BN_sub(r, r, m);
262 return 1;
263 }
264
BN_mod_lshift(BIGNUM * r,const BIGNUM * a,int n,const BIGNUM * m,BN_CTX * ctx)265 int BN_mod_lshift(BIGNUM *r, const BIGNUM *a, int n, const BIGNUM *m,
266 BN_CTX *ctx)
267 {
268 BIGNUM *abs_m = NULL;
269 int ret;
270
271 if (!BN_nnmod(r, a, m, ctx))
272 return 0;
273
274 if (m->neg) {
275 abs_m = BN_dup(m);
276 if (abs_m == NULL)
277 return 0;
278 abs_m->neg = 0;
279 }
280
281 ret = BN_mod_lshift_quick(r, r, n, (abs_m ? abs_m : m));
282 bn_check_top(r);
283
284 BN_free(abs_m);
285 return ret;
286 }
287
288 /*
289 * BN_mod_lshift variant that may be used if a is non-negative and less than
290 * m
291 */
BN_mod_lshift_quick(BIGNUM * r,const BIGNUM * a,int n,const BIGNUM * m)292 int BN_mod_lshift_quick(BIGNUM *r, const BIGNUM *a, int n, const BIGNUM *m)
293 {
294 if (r != a) {
295 if (BN_copy(r, a) == NULL)
296 return 0;
297 }
298
299 while (n > 0) {
300 int max_shift;
301
302 /* 0 < r < m */
303 max_shift = BN_num_bits(m) - BN_num_bits(r);
304 /* max_shift >= 0 */
305
306 if (max_shift < 0) {
307 ERR_raise(ERR_LIB_BN, BN_R_INPUT_NOT_REDUCED);
308 return 0;
309 }
310
311 if (max_shift > n)
312 max_shift = n;
313
314 if (max_shift) {
315 if (!BN_lshift(r, r, max_shift))
316 return 0;
317 n -= max_shift;
318 } else {
319 if (!BN_lshift1(r, r))
320 return 0;
321 --n;
322 }
323
324 /* BN_num_bits(r) <= BN_num_bits(m) */
325
326 if (BN_cmp(r, m) >= 0) {
327 if (!BN_sub(r, r, m))
328 return 0;
329 }
330 }
331 bn_check_top(r);
332
333 return 1;
334 }
335
