1 /* crypto/bn/bn_mod.c */
2 /*
3 * Includes code written by Lenka Fibikova <fibikova@exp-math.uni-essen.de>
4 * for the OpenSSL project.
5 */
6 /* ====================================================================
7 * Copyright (c) 1998-2018 The OpenSSL Project. All rights reserved.
8 *
9 * Redistribution and use in source and binary forms, with or without
10 * modification, are permitted provided that the following conditions
11 * are met:
12 *
13 * 1. Redistributions of source code must retain the above copyright
14 * notice, this list of conditions and the following disclaimer.
15 *
16 * 2. Redistributions in binary form must reproduce the above copyright
17 * notice, this list of conditions and the following disclaimer in
18 * the documentation and/or other materials provided with the
19 * distribution.
20 *
21 * 3. All advertising materials mentioning features or use of this
22 * software must display the following acknowledgment:
23 * "This product includes software developed by the OpenSSL Project
24 * for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
25 *
26 * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
27 * endorse or promote products derived from this software without
28 * prior written permission. For written permission, please contact
29 * openssl-core@openssl.org.
30 *
31 * 5. Products derived from this software may not be called "OpenSSL"
32 * nor may "OpenSSL" appear in their names without prior written
33 * permission of the OpenSSL Project.
34 *
35 * 6. Redistributions of any form whatsoever must retain the following
36 * acknowledgment:
37 * "This product includes software developed by the OpenSSL Project
38 * for use in the OpenSSL Toolkit (http://www.openssl.org/)"
39 *
40 * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
41 * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
42 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
43 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR
44 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
45 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
46 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
47 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
48 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
49 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
50 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
51 * OF THE POSSIBILITY OF SUCH DAMAGE.
52 * ====================================================================
53 *
54 * This product includes cryptographic software written by Eric Young
55 * (eay@cryptsoft.com). This product includes software written by Tim
56 * Hudson (tjh@cryptsoft.com).
57 *
58 */
59 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
60 * All rights reserved.
61 *
62 * This package is an SSL implementation written
63 * by Eric Young (eay@cryptsoft.com).
64 * The implementation was written so as to conform with Netscapes SSL.
65 *
66 * This library is free for commercial and non-commercial use as long as
67 * the following conditions are aheared to. The following conditions
68 * apply to all code found in this distribution, be it the RC4, RSA,
69 * lhash, DES, etc., code; not just the SSL code. The SSL documentation
70 * included with this distribution is covered by the same copyright terms
71 * except that the holder is Tim Hudson (tjh@cryptsoft.com).
72 *
73 * Copyright remains Eric Young's, and as such any Copyright notices in
74 * the code are not to be removed.
75 * If this package is used in a product, Eric Young should be given attribution
76 * as the author of the parts of the library used.
77 * This can be in the form of a textual message at program startup or
78 * in documentation (online or textual) provided with the package.
79 *
80 * Redistribution and use in source and binary forms, with or without
81 * modification, are permitted provided that the following conditions
82 * are met:
83 * 1. Redistributions of source code must retain the copyright
84 * notice, this list of conditions and the following disclaimer.
85 * 2. Redistributions in binary form must reproduce the above copyright
86 * notice, this list of conditions and the following disclaimer in the
87 * documentation and/or other materials provided with the distribution.
88 * 3. All advertising materials mentioning features or use of this software
89 * must display the following acknowledgement:
90 * "This product includes cryptographic software written by
91 * Eric Young (eay@cryptsoft.com)"
92 * The word 'cryptographic' can be left out if the rouines from the library
93 * being used are not cryptographic related :-).
94 * 4. If you include any Windows specific code (or a derivative thereof) from
95 * the apps directory (application code) you must include an acknowledgement:
96 * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
97 *
98 * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
99 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
100 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
101 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
102 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
103 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
104 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
105 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
106 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
107 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
108 * SUCH DAMAGE.
109 *
110 * The licence and distribution terms for any publically available version or
111 * derivative of this code cannot be changed. i.e. this code cannot simply be
112 * copied and put under another distribution licence
113 * [including the GNU Public Licence.]
114 */
115
116 #include "cryptlib.h"
117 #include "bn_lcl.h"
118
119 #if 0 /* now just a #define */
120 int BN_mod(BIGNUM *rem, const BIGNUM *m, const BIGNUM *d, BN_CTX *ctx)
121 {
122 return (BN_div(NULL, rem, m, d, ctx));
123 /* note that rem->neg == m->neg (unless the remainder is zero) */
124 }
125 #endif
126
BN_nnmod(BIGNUM * r,const BIGNUM * m,const BIGNUM * d,BN_CTX * ctx)127 int BN_nnmod(BIGNUM *r, const BIGNUM *m, const BIGNUM *d, BN_CTX *ctx)
128 {
129 /*
130 * like BN_mod, but returns non-negative remainder (i.e., 0 <= r < |d|
131 * always holds)
132 */
133
134 if (!(BN_mod(r, m, d, ctx)))
135 return 0;
136 if (!r->neg)
137 return 1;
138 /* now -|d| < r < 0, so we have to set r := r + |d| */
139 return (d->neg ? BN_sub : BN_add) (r, r, d);
140 }
141
BN_mod_add(BIGNUM * r,const BIGNUM * a,const BIGNUM * b,const BIGNUM * m,BN_CTX * ctx)142 int BN_mod_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m,
143 BN_CTX *ctx)
144 {
145 if (!BN_add(r, a, b))
146 return 0;
147 return BN_nnmod(r, r, m, ctx);
148 }
149
150 /*
151 * BN_mod_add variant that may be used if both a and b are non-negative and
152 * less than m. The original algorithm was
153 *
154 * if (!BN_uadd(r, a, b))
155 * return 0;
156 * if (BN_ucmp(r, m) >= 0)
157 * return BN_usub(r, r, m);
158 *
159 * which is replaced with addition, subtracting modulus, and conditional
160 * move depending on whether or not subtraction borrowed.
161 */
bn_mod_add_fixed_top(BIGNUM * r,const BIGNUM * a,const BIGNUM * b,const BIGNUM * m)162 int bn_mod_add_fixed_top(BIGNUM *r, const BIGNUM *a, const BIGNUM *b,
163 const BIGNUM *m)
164 {
165 size_t i, ai, bi, mtop = m->top;
166 BN_ULONG storage[1024 / BN_BITS2];
167 BN_ULONG carry, temp, mask, *rp, *tp = storage;
168 const BN_ULONG *ap, *bp;
169
170 if (bn_wexpand(r, m->top) == NULL)
171 return 0;
172
173 if (mtop > sizeof(storage) / sizeof(storage[0])
174 && (tp = OPENSSL_malloc(mtop * sizeof(BN_ULONG))) == NULL)
175 return 0;
176
177 ap = a->d != NULL ? a->d : tp;
178 bp = b->d != NULL ? b->d : tp;
179
180 for (i = 0, ai = 0, bi = 0, carry = 0; i < mtop;) {
181 mask = (BN_ULONG)0 - ((i - a->top) >> (8 * sizeof(i) - 1));
182 temp = ((ap[ai] & mask) + carry) & BN_MASK2;
183 carry = (temp < carry);
184
185 mask = (BN_ULONG)0 - ((i - b->top) >> (8 * sizeof(i) - 1));
186 tp[i] = ((bp[bi] & mask) + temp) & BN_MASK2;
187 carry += (tp[i] < temp);
188
189 i++;
190 ai += (i - a->dmax) >> (8 * sizeof(i) - 1);
191 bi += (i - b->dmax) >> (8 * sizeof(i) - 1);
192 }
193 rp = r->d;
194 carry -= bn_sub_words(rp, tp, m->d, mtop);
195 for (i = 0; i < mtop; i++) {
196 rp[i] = (carry & tp[i]) | (~carry & rp[i]);
197 ((volatile BN_ULONG *)tp)[i] = 0;
198 }
199 r->top = mtop;
200 r->flags |= BN_FLG_FIXED_TOP;
201 r->neg = 0;
202
203 if (tp != storage)
204 OPENSSL_free(tp);
205
206 return 1;
207 }
208
BN_mod_add_quick(BIGNUM * r,const BIGNUM * a,const BIGNUM * b,const BIGNUM * m)209 int BN_mod_add_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *b,
210 const BIGNUM *m)
211 {
212 int ret = bn_mod_add_fixed_top(r, a, b, m);
213
214 if (ret)
215 bn_correct_top(r);
216
217 return ret;
218 }
219
BN_mod_sub(BIGNUM * r,const BIGNUM * a,const BIGNUM * b,const BIGNUM * m,BN_CTX * ctx)220 int BN_mod_sub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m,
221 BN_CTX *ctx)
222 {
223 if (!BN_sub(r, a, b))
224 return 0;
225 return BN_nnmod(r, r, m, ctx);
226 }
227
228 /*
229 * BN_mod_sub variant that may be used if both a and b are non-negative,
230 * a is less than m, while b is of same bit width as m. It's implemented
231 * as subtraction followed by two conditional additions.
232 *
233 * 0 <= a < m
234 * 0 <= b < 2^w < 2*m
235 *
236 * after subtraction
237 *
238 * -2*m < r = a - b < m
239 *
240 * Thus it takes up to two conditional additions to make |r| positive.
241 */
bn_mod_sub_fixed_top(BIGNUM * r,const BIGNUM * a,const BIGNUM * b,const BIGNUM * m)242 int bn_mod_sub_fixed_top(BIGNUM *r, const BIGNUM *a, const BIGNUM *b,
243 const BIGNUM *m)
244 {
245 size_t i, ai, bi, mtop = m->top;
246 BN_ULONG borrow, carry, ta, tb, mask, *rp;
247 const BN_ULONG *ap, *bp;
248
249 if (bn_wexpand(r, m->top) == NULL)
250 return 0;
251
252 rp = r->d;
253 ap = a->d != NULL ? a->d : rp;
254 bp = b->d != NULL ? b->d : rp;
255
256 for (i = 0, ai = 0, bi = 0, borrow = 0; i < mtop;) {
257 mask = (BN_ULONG)0 - ((i - a->top) >> (8 * sizeof(i) - 1));
258 ta = ap[ai] & mask;
259
260 mask = (BN_ULONG)0 - ((i - b->top) >> (8 * sizeof(i) - 1));
261 tb = bp[bi] & mask;
262 rp[i] = ta - tb - borrow;
263 if (ta != tb)
264 borrow = (ta < tb);
265
266 i++;
267 ai += (i - a->dmax) >> (8 * sizeof(i) - 1);
268 bi += (i - b->dmax) >> (8 * sizeof(i) - 1);
269 }
270 ap = m->d;
271 for (i = 0, mask = 0 - borrow, carry = 0; i < mtop; i++) {
272 ta = ((ap[i] & mask) + carry) & BN_MASK2;
273 carry = (ta < carry);
274 rp[i] = (rp[i] + ta) & BN_MASK2;
275 carry += (rp[i] < ta);
276 }
277 borrow -= carry;
278 for (i = 0, mask = 0 - borrow, carry = 0; i < mtop; i++) {
279 ta = ((ap[i] & mask) + carry) & BN_MASK2;
280 carry = (ta < carry);
281 rp[i] = (rp[i] + ta) & BN_MASK2;
282 carry += (rp[i] < ta);
283 }
284
285 r->top = mtop;
286 r->flags |= BN_FLG_FIXED_TOP;
287 r->neg = 0;
288
289 return 1;
290 }
291
292 /*
293 * BN_mod_sub variant that may be used if both a and b are non-negative and
294 * less than m
295 */
BN_mod_sub_quick(BIGNUM * r,const BIGNUM * a,const BIGNUM * b,const BIGNUM * m)296 int BN_mod_sub_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *b,
297 const BIGNUM *m)
298 {
299 if (!BN_sub(r, a, b))
300 return 0;
301 if (r->neg)
302 return BN_add(r, r, m);
303 return 1;
304 }
305
306 /* slow but works */
BN_mod_mul(BIGNUM * r,const BIGNUM * a,const BIGNUM * b,const BIGNUM * m,BN_CTX * ctx)307 int BN_mod_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m,
308 BN_CTX *ctx)
309 {
310 BIGNUM *t;
311 int ret = 0;
312
313 bn_check_top(a);
314 bn_check_top(b);
315 bn_check_top(m);
316
317 BN_CTX_start(ctx);
318 if ((t = BN_CTX_get(ctx)) == NULL)
319 goto err;
320 if (a == b) {
321 if (!BN_sqr(t, a, ctx))
322 goto err;
323 } else {
324 if (!BN_mul(t, a, b, ctx))
325 goto err;
326 }
327 if (!BN_nnmod(r, t, m, ctx))
328 goto err;
329 bn_check_top(r);
330 ret = 1;
331 err:
332 BN_CTX_end(ctx);
333 return (ret);
334 }
335
BN_mod_sqr(BIGNUM * r,const BIGNUM * a,const BIGNUM * m,BN_CTX * ctx)336 int BN_mod_sqr(BIGNUM *r, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx)
337 {
338 if (!BN_sqr(r, a, ctx))
339 return 0;
340 /* r->neg == 0, thus we don't need BN_nnmod */
341 return BN_mod(r, r, m, ctx);
342 }
343
BN_mod_lshift1(BIGNUM * r,const BIGNUM * a,const BIGNUM * m,BN_CTX * ctx)344 int BN_mod_lshift1(BIGNUM *r, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx)
345 {
346 if (!BN_lshift1(r, a))
347 return 0;
348 bn_check_top(r);
349 return BN_nnmod(r, r, m, ctx);
350 }
351
352 /*
353 * BN_mod_lshift1 variant that may be used if a is non-negative and less than
354 * m
355 */
BN_mod_lshift1_quick(BIGNUM * r,const BIGNUM * a,const BIGNUM * m)356 int BN_mod_lshift1_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *m)
357 {
358 if (!BN_lshift1(r, a))
359 return 0;
360 bn_check_top(r);
361 if (BN_cmp(r, m) >= 0)
362 return BN_sub(r, r, m);
363 return 1;
364 }
365
BN_mod_lshift(BIGNUM * r,const BIGNUM * a,int n,const BIGNUM * m,BN_CTX * ctx)366 int BN_mod_lshift(BIGNUM *r, const BIGNUM *a, int n, const BIGNUM *m,
367 BN_CTX *ctx)
368 {
369 BIGNUM *abs_m = NULL;
370 int ret;
371
372 if (!BN_nnmod(r, a, m, ctx))
373 return 0;
374
375 if (m->neg) {
376 abs_m = BN_dup(m);
377 if (abs_m == NULL)
378 return 0;
379 abs_m->neg = 0;
380 }
381
382 ret = BN_mod_lshift_quick(r, r, n, (abs_m ? abs_m : m));
383 bn_check_top(r);
384
385 if (abs_m)
386 BN_free(abs_m);
387 return ret;
388 }
389
390 /*
391 * BN_mod_lshift variant that may be used if a is non-negative and less than
392 * m
393 */
BN_mod_lshift_quick(BIGNUM * r,const BIGNUM * a,int n,const BIGNUM * m)394 int BN_mod_lshift_quick(BIGNUM *r, const BIGNUM *a, int n, const BIGNUM *m)
395 {
396 if (r != a) {
397 if (BN_copy(r, a) == NULL)
398 return 0;
399 }
400
401 while (n > 0) {
402 int max_shift;
403
404 /* 0 < r < m */
405 max_shift = BN_num_bits(m) - BN_num_bits(r);
406 /* max_shift >= 0 */
407
408 if (max_shift < 0) {
409 BNerr(BN_F_BN_MOD_LSHIFT_QUICK, BN_R_INPUT_NOT_REDUCED);
410 return 0;
411 }
412
413 if (max_shift > n)
414 max_shift = n;
415
416 if (max_shift) {
417 if (!BN_lshift(r, r, max_shift))
418 return 0;
419 n -= max_shift;
420 } else {
421 if (!BN_lshift1(r, r))
422 return 0;
423 --n;
424 }
425
426 /* BN_num_bits(r) <= BN_num_bits(m) */
427
428 if (BN_cmp(r, m) >= 0) {
429 if (!BN_sub(r, r, m))
430 return 0;
431 }
432 }
433 bn_check_top(r);
434
435 return 1;
436 }
437