/src/openssl/crypto/bn/bn_mod.c
Line | Count | Source (jump to first uncovered line) |
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 | | |
14 | | int BN_nnmod(BIGNUM *r, const BIGNUM *m, const BIGNUM *d, BN_CTX *ctx) |
15 | 661k | { |
16 | | /* |
17 | | * like BN_mod, but returns non-negative remainder (i.e., 0 <= r < |d| |
18 | | * always holds) |
19 | | */ |
20 | | |
21 | 661k | if (r == d) { |
22 | 5 | ERR_raise(ERR_LIB_BN, ERR_R_PASSED_INVALID_ARGUMENT); |
23 | 5 | return 0; |
24 | 5 | } |
25 | | |
26 | 661k | if (!(BN_mod(r, m, d, ctx))) |
27 | 53 | return 0; |
28 | 660k | if (!r->neg) |
29 | 628k | return 1; |
30 | | /* now -|d| < r < 0, so we have to set r := r + |d| */ |
31 | 32.1k | return (d->neg ? BN_sub : BN_add) (r, r, d); |
32 | 660k | } |
33 | | |
34 | | int BN_mod_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m, |
35 | | BN_CTX *ctx) |
36 | 89 | { |
37 | 89 | if (!BN_add(r, a, b)) |
38 | 0 | return 0; |
39 | 89 | return BN_nnmod(r, r, m, ctx); |
40 | 89 | } |
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 | | */ |
54 | | int bn_mod_add_fixed_top(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, |
55 | | const BIGNUM *m) |
56 | 2.11M | { |
57 | 2.11M | size_t i, ai, bi, mtop = m->top; |
58 | 2.11M | BN_ULONG storage[1024 / BN_BITS2]; |
59 | 2.11M | BN_ULONG carry, temp, mask, *rp, *tp = storage; |
60 | 2.11M | const BN_ULONG *ap, *bp; |
61 | | |
62 | 2.11M | if (bn_wexpand(r, mtop) == NULL) |
63 | 0 | return 0; |
64 | | |
65 | 2.11M | if (mtop > OSSL_NELEM(storage)) { |
66 | 108 | tp = OPENSSL_malloc(mtop * sizeof(BN_ULONG)); |
67 | 108 | if (tp == NULL) |
68 | 0 | return 0; |
69 | 108 | } |
70 | | |
71 | 2.11M | ap = a->d != NULL ? a->d : tp; |
72 | 2.11M | bp = b->d != NULL ? b->d : tp; |
73 | | |
74 | 14.1M | for (i = 0, ai = 0, bi = 0, carry = 0; i < mtop;) { |
75 | 12.0M | mask = (BN_ULONG)0 - ((i - a->top) >> (8 * sizeof(i) - 1)); |
76 | 12.0M | temp = ((ap[ai] & mask) + carry) & BN_MASK2; |
77 | 12.0M | carry = (temp < carry); |
78 | | |
79 | 12.0M | mask = (BN_ULONG)0 - ((i - b->top) >> (8 * sizeof(i) - 1)); |
80 | 12.0M | tp[i] = ((bp[bi] & mask) + temp) & BN_MASK2; |
81 | 12.0M | carry += (tp[i] < temp); |
82 | | |
83 | 12.0M | i++; |
84 | 12.0M | ai += (i - a->dmax) >> (8 * sizeof(i) - 1); |
85 | 12.0M | bi += (i - b->dmax) >> (8 * sizeof(i) - 1); |
86 | 12.0M | } |
87 | 2.11M | rp = r->d; |
88 | 2.11M | carry -= bn_sub_words(rp, tp, m->d, mtop); |
89 | 14.1M | for (i = 0; i < mtop; i++) { |
90 | 12.0M | rp[i] = (carry & tp[i]) | (~carry & rp[i]); |
91 | 12.0M | ((volatile BN_ULONG *)tp)[i] = 0; |
92 | 12.0M | } |
93 | 2.11M | r->top = mtop; |
94 | 2.11M | r->flags |= BN_FLG_FIXED_TOP; |
95 | 2.11M | r->neg = 0; |
96 | | |
97 | 2.11M | if (tp != storage) |
98 | 108 | OPENSSL_free(tp); |
99 | | |
100 | 2.11M | return 1; |
101 | 2.11M | } |
102 | | |
103 | | int BN_mod_add_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, |
104 | | const BIGNUM *m) |
105 | 2.11M | { |
106 | 2.11M | int ret = bn_mod_add_fixed_top(r, a, b, m); |
107 | | |
108 | 2.11M | if (ret) |
109 | 2.11M | bn_correct_top(r); |
110 | | |
111 | 2.11M | return ret; |
112 | 2.11M | } |
113 | | |
114 | | int BN_mod_sub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m, |
115 | | BN_CTX *ctx) |
116 | 143 | { |
117 | 143 | if (!BN_sub(r, a, b)) |
118 | 0 | return 0; |
119 | 143 | return BN_nnmod(r, r, m, ctx); |
120 | 143 | } |
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 | | */ |
136 | | int bn_mod_sub_fixed_top(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, |
137 | | const BIGNUM *m) |
138 | 0 | { |
139 | 0 | size_t i, ai, bi, mtop = m->top; |
140 | 0 | BN_ULONG borrow, carry, ta, tb, mask, *rp; |
141 | 0 | const BN_ULONG *ap, *bp; |
142 | |
|
143 | 0 | if (bn_wexpand(r, mtop) == NULL) |
144 | 0 | return 0; |
145 | | |
146 | 0 | rp = r->d; |
147 | 0 | ap = a->d != NULL ? a->d : rp; |
148 | 0 | bp = b->d != NULL ? b->d : rp; |
149 | |
|
150 | 0 | for (i = 0, ai = 0, bi = 0, borrow = 0; i < mtop;) { |
151 | 0 | mask = (BN_ULONG)0 - ((i - a->top) >> (8 * sizeof(i) - 1)); |
152 | 0 | ta = ap[ai] & mask; |
153 | |
|
154 | 0 | mask = (BN_ULONG)0 - ((i - b->top) >> (8 * sizeof(i) - 1)); |
155 | 0 | tb = bp[bi] & mask; |
156 | 0 | rp[i] = ta - tb - borrow; |
157 | 0 | if (ta != tb) |
158 | 0 | borrow = (ta < tb); |
159 | |
|
160 | 0 | i++; |
161 | 0 | ai += (i - a->dmax) >> (8 * sizeof(i) - 1); |
162 | 0 | bi += (i - b->dmax) >> (8 * sizeof(i) - 1); |
163 | 0 | } |
164 | 0 | ap = m->d; |
165 | 0 | for (i = 0, mask = 0 - borrow, carry = 0; i < mtop; i++) { |
166 | 0 | ta = ((ap[i] & mask) + carry) & BN_MASK2; |
167 | 0 | carry = (ta < carry); |
168 | 0 | rp[i] = (rp[i] + ta) & BN_MASK2; |
169 | 0 | carry += (rp[i] < ta); |
170 | 0 | } |
171 | 0 | borrow -= carry; |
172 | 0 | for (i = 0, mask = 0 - borrow, carry = 0; i < mtop; i++) { |
173 | 0 | ta = ((ap[i] & mask) + carry) & BN_MASK2; |
174 | 0 | carry = (ta < carry); |
175 | 0 | rp[i] = (rp[i] + ta) & BN_MASK2; |
176 | 0 | carry += (rp[i] < ta); |
177 | 0 | } |
178 | |
|
179 | 0 | r->top = mtop; |
180 | 0 | r->flags |= BN_FLG_FIXED_TOP; |
181 | 0 | r->neg = 0; |
182 | |
|
183 | 0 | return 1; |
184 | 0 | } |
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 | | */ |
190 | | int BN_mod_sub_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, |
191 | | const BIGNUM *m) |
192 | 2.30M | { |
193 | 2.30M | if (r == m) { |
194 | 0 | ERR_raise(ERR_LIB_BN, ERR_R_PASSED_INVALID_ARGUMENT); |
195 | 0 | return 0; |
196 | 0 | } |
197 | | |
198 | 2.30M | if (!BN_sub(r, a, b)) |
199 | 0 | return 0; |
200 | 2.30M | if (r->neg) |
201 | 1.13M | return BN_add(r, r, m); |
202 | 1.16M | return 1; |
203 | 2.30M | } |
204 | | |
205 | | /* slow but works */ |
206 | | int BN_mod_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m, |
207 | | BN_CTX *ctx) |
208 | 355k | { |
209 | 355k | BIGNUM *t; |
210 | 355k | int ret = 0; |
211 | | |
212 | 355k | bn_check_top(a); |
213 | 355k | bn_check_top(b); |
214 | 355k | bn_check_top(m); |
215 | | |
216 | 355k | BN_CTX_start(ctx); |
217 | 355k | if ((t = BN_CTX_get(ctx)) == NULL) |
218 | 0 | goto err; |
219 | 355k | if (a == b) { |
220 | 314k | if (!BN_sqr(t, a, ctx)) |
221 | 0 | goto err; |
222 | 314k | } else { |
223 | 40.6k | if (!BN_mul(t, a, b, ctx)) |
224 | 0 | goto err; |
225 | 40.6k | } |
226 | 355k | if (!BN_nnmod(r, t, m, ctx)) |
227 | 29 | goto err; |
228 | 355k | bn_check_top(r); |
229 | 355k | ret = 1; |
230 | 355k | err: |
231 | 355k | BN_CTX_end(ctx); |
232 | 355k | return ret; |
233 | 355k | } |
234 | | |
235 | | int BN_mod_sqr(BIGNUM *r, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx) |
236 | 952 | { |
237 | 952 | if (!BN_sqr(r, a, ctx)) |
238 | 0 | return 0; |
239 | | /* r->neg == 0, thus we don't need BN_nnmod */ |
240 | 952 | return BN_mod(r, r, m, ctx); |
241 | 952 | } |
242 | | |
243 | | int BN_mod_lshift1(BIGNUM *r, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx) |
244 | 0 | { |
245 | 0 | if (!BN_lshift1(r, a)) |
246 | 0 | return 0; |
247 | 0 | bn_check_top(r); |
248 | 0 | return BN_nnmod(r, r, m, ctx); |
249 | 0 | } |
250 | | |
251 | | /* |
252 | | * BN_mod_lshift1 variant that may be used if a is non-negative and less than |
253 | | * m |
254 | | */ |
255 | | int BN_mod_lshift1_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *m) |
256 | 851k | { |
257 | 851k | if (!BN_lshift1(r, a)) |
258 | 0 | return 0; |
259 | 851k | bn_check_top(r); |
260 | 851k | if (BN_cmp(r, m) >= 0) |
261 | 424k | return BN_sub(r, r, m); |
262 | 426k | return 1; |
263 | 851k | } |
264 | | |
265 | | int BN_mod_lshift(BIGNUM *r, const BIGNUM *a, int n, const BIGNUM *m, |
266 | | BN_CTX *ctx) |
267 | 2 | { |
268 | 2 | BIGNUM *abs_m = NULL; |
269 | 2 | int ret; |
270 | | |
271 | 2 | if (!BN_nnmod(r, a, m, ctx)) |
272 | 0 | return 0; |
273 | | |
274 | 2 | if (m->neg) { |
275 | 0 | abs_m = BN_dup(m); |
276 | 0 | if (abs_m == NULL) |
277 | 0 | return 0; |
278 | 0 | abs_m->neg = 0; |
279 | 0 | } |
280 | | |
281 | 2 | ret = BN_mod_lshift_quick(r, r, n, (abs_m ? abs_m : m)); |
282 | 2 | bn_check_top(r); |
283 | | |
284 | 2 | BN_free(abs_m); |
285 | 2 | return ret; |
286 | 2 | } |
287 | | |
288 | | /* |
289 | | * BN_mod_lshift variant that may be used if a is non-negative and less than |
290 | | * m |
291 | | */ |
292 | | int BN_mod_lshift_quick(BIGNUM *r, const BIGNUM *a, int n, const BIGNUM *m) |
293 | 441k | { |
294 | 441k | if (r != a) { |
295 | 379k | if (BN_copy(r, a) == NULL) |
296 | 0 | return 0; |
297 | 379k | } |
298 | | |
299 | 1.22M | while (n > 0) { |
300 | 785k | int max_shift; |
301 | | |
302 | | /* 0 < r < m */ |
303 | 785k | max_shift = BN_num_bits(m) - BN_num_bits(r); |
304 | | /* max_shift >= 0 */ |
305 | | |
306 | 785k | if (max_shift < 0) { |
307 | 0 | ERR_raise(ERR_LIB_BN, BN_R_INPUT_NOT_REDUCED); |
308 | 0 | return 0; |
309 | 0 | } |
310 | | |
311 | 785k | if (max_shift > n) |
312 | 109k | max_shift = n; |
313 | | |
314 | 785k | if (max_shift) { |
315 | 389k | if (!BN_lshift(r, r, max_shift)) |
316 | 0 | return 0; |
317 | 389k | n -= max_shift; |
318 | 396k | } else { |
319 | 396k | if (!BN_lshift1(r, r)) |
320 | 0 | return 0; |
321 | 396k | --n; |
322 | 396k | } |
323 | | |
324 | | /* BN_num_bits(r) <= BN_num_bits(m) */ |
325 | | |
326 | 785k | if (BN_cmp(r, m) >= 0) { |
327 | 434k | if (!BN_sub(r, r, m)) |
328 | 0 | return 0; |
329 | 434k | } |
330 | 785k | } |
331 | 441k | bn_check_top(r); |
332 | | |
333 | 441k | return 1; |
334 | 441k | } |