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