/src/boringssl/crypto/fipsmodule/bn/add.c.inc

Source (jump to first uncovered line)
/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
 * All rights reserved.
 *
 * This package is an SSL implementation written
 * by Eric Young (eay@cryptsoft.com).
 * The implementation was written so as to conform with Netscapes SSL.
 *
 * This library is free for commercial and non-commercial use as long as
 * the following conditions are aheared to.  The following conditions
 * apply to all code found in this distribution, be it the RC4, RSA,
 * lhash, DES, etc., code; not just the SSL code.  The SSL documentation
 * included with this distribution is covered by the same copyright terms
 * except that the holder is Tim Hudson (tjh@cryptsoft.com).
 *
 * Copyright remains Eric Young's, and as such any Copyright notices in
 * the code are not to be removed.
 * If this package is used in a product, Eric Young should be given attribution
 * as the author of the parts of the library used.
 * This can be in the form of a textual message at program startup or
 * in documentation (online or textual) provided with the package.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. All advertising materials mentioning features or use of this software
 *    must display the following acknowledgement:
 *    "This product includes cryptographic software written by
 *     Eric Young (eay@cryptsoft.com)"
 *    The word 'cryptographic' can be left out if the rouines from the library
 *    being used are not cryptographic related :-).
 * 4. If you include any Windows specific code (or a derivative thereof) from
 *    the apps directory (application code) you must include an acknowledgement:
 *    "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
 *
 * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 *
 * The licence and distribution terms for any publically available version or
 * derivative of this code cannot be changed.  i.e. this code cannot simply be
 * copied and put under another distribution licence
 * [including the GNU Public Licence.] */

#include <openssl/bn.h>

#include <string.h>

#include <openssl/err.h>
#include <openssl/mem.h>

#include "internal.h"


int BN_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b) {
  const BIGNUM *tmp;
  int a_neg = a->neg, ret;

  //  a +  b  a+b
  //  a + -b  a-b
  // -a +  b  b-a
  // -a + -b  -(a+b)
  if (a_neg ^ b->neg) {
    // only one is negative
    if (a_neg) {
      tmp = a;
      a = b;
      b = tmp;
    }

    // we are now a - b
    if (BN_ucmp(a, b) < 0) {
      if (!BN_usub(r, b, a)) {
        return 0;
      }
      r->neg = 1;
    } else {
      if (!BN_usub(r, a, b)) {
        return 0;
      }
      r->neg = 0;
    }
    return 1;
  }

  ret = BN_uadd(r, a, b);
  r->neg = a_neg;
  return ret;
}

int bn_uadd_consttime(BIGNUM *r, const BIGNUM *a, const BIGNUM *b) {
  // Widths are public, so we normalize to make |a| the larger one.
  if (a->width < b->width) {
    const BIGNUM *tmp = a;
    a = b;
    b = tmp;
  }

  int max = a->width;
  int min = b->width;
  if (!bn_wexpand(r, max + 1)) {
    return 0;
  }
  r->width = max + 1;

  BN_ULONG carry = bn_add_words(r->d, a->d, b->d, min);
  for (int i = min; i < max; i++) {
    r->d[i] = CRYPTO_addc_w(a->d[i], 0, carry, &carry);
  }

  r->d[max] = carry;
  return 1;
}

int BN_uadd(BIGNUM *r, const BIGNUM *a, const BIGNUM *b) {
  if (!bn_uadd_consttime(r, a, b)) {
    return 0;
  }
  bn_set_minimal_width(r);
  return 1;
}

int BN_add_word(BIGNUM *a, BN_ULONG w) {
  BN_ULONG l;
  int i;

  // degenerate case: w is zero
  if (!w) {
    return 1;
  }

  // degenerate case: a is zero
  if (BN_is_zero(a)) {
    return BN_set_word(a, w);
  }

  // handle 'a' when negative
  if (a->neg) {
    a->neg = 0;
    i = BN_sub_word(a, w);
    if (!BN_is_zero(a)) {
      a->neg = !(a->neg);
    }
    return i;
  }

  for (i = 0; w != 0 && i < a->width; i++) {
    a->d[i] = l = a->d[i] + w;
    w = (w > l) ? 1 : 0;
  }

  if (w && i == a->width) {
    if (!bn_wexpand(a, a->width + 1)) {
      return 0;
    }
    a->width++;
    a->d[i] = w;
  }

  return 1;
}

int BN_sub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b) {
  int add = 0, neg = 0;
  const BIGNUM *tmp;

  //  a -  b  a-b
  //  a - -b  a+b
  // -a -  b  -(a+b)
  // -a - -b  b-a
  if (a->neg) {
    if (b->neg) {
      tmp = a;
      a = b;
      b = tmp;
    } else {
      add = 1;
      neg = 1;
    }
  } else {
    if (b->neg) {
      add = 1;
      neg = 0;
    }
  }

  if (add) {
    if (!BN_uadd(r, a, b)) {
      return 0;
    }

    r->neg = neg;
    return 1;
  }

  if (BN_ucmp(a, b) < 0) {
    if (!BN_usub(r, b, a)) {
      return 0;
    }
    r->neg = 1;
  } else {
    if (!BN_usub(r, a, b)) {
      return 0;
    }
    r->neg = 0;
  }

  return 1;
}

int bn_usub_consttime(BIGNUM *r, const BIGNUM *a, const BIGNUM *b) {
  // |b| may have more words than |a| given non-minimal inputs, but all words
  // beyond |a->width| must then be zero.
  int b_width = b->width;
  if (b_width > a->width) {
    if (!bn_fits_in_words(b, a->width)) {
      OPENSSL_PUT_ERROR(BN, BN_R_ARG2_LT_ARG3);
      return 0;
    }
    b_width = a->width;
  }

  if (!bn_wexpand(r, a->width)) {
    return 0;
  }

  BN_ULONG borrow = bn_sub_words(r->d, a->d, b->d, b_width);
  for (int i = b_width; i < a->width; i++) {
    r->d[i] = CRYPTO_subc_w(a->d[i], 0, borrow, &borrow);
  }

  if (borrow) {
    OPENSSL_PUT_ERROR(BN, BN_R_ARG2_LT_ARG3);
    return 0;
  }

  r->width = a->width;
  r->neg = 0;
  return 1;
}

int BN_usub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b) {
  if (!bn_usub_consttime(r, a, b)) {
    return 0;
  }
  bn_set_minimal_width(r);
  return 1;
}

int BN_sub_word(BIGNUM *a, BN_ULONG w) {
  int i;

  // degenerate case: w is zero
  if (!w) {
    return 1;
  }

  // degenerate case: a is zero
  if (BN_is_zero(a)) {
    i = BN_set_word(a, w);
    if (i != 0) {
      BN_set_negative(a, 1);
    }
    return i;
  }

  // handle 'a' when negative
  if (a->neg) {
    a->neg = 0;
    i = BN_add_word(a, w);
    a->neg = 1;
    return i;
  }

  if ((bn_minimal_width(a) == 1) && (a->d[0] < w)) {
    a->d[0] = w - a->d[0];
    a->neg = 1;
    return 1;
  }

  i = 0;
  for (;;) {
    if (a->d[i] >= w) {
      a->d[i] -= w;
      break;
    } else {
      a->d[i] -= w;
      i++;
      w = 1;
    }
  }

  if ((a->d[i] == 0) && (i == (a->width - 1))) {
    a->width--;
  }

  return 1;
}

Coverage Report

Created: 2024-11-21 06:47

Line	Count	Source (jump to first uncovered line)
1		/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
2		* All rights reserved.
3		*
4		* This package is an SSL implementation written
5		* by Eric Young (eay@cryptsoft.com).
6		* The implementation was written so as to conform with Netscapes SSL.
7		*
8		* This library is free for commercial and non-commercial use as long as
9		* the following conditions are aheared to. The following conditions
10		* apply to all code found in this distribution, be it the RC4, RSA,
11		* lhash, DES, etc., code; not just the SSL code. The SSL documentation
12		* included with this distribution is covered by the same copyright terms
13		* except that the holder is Tim Hudson (tjh@cryptsoft.com).
14		*
15		* Copyright remains Eric Young's, and as such any Copyright notices in
16		* the code are not to be removed.
17		* If this package is used in a product, Eric Young should be given attribution
18		* as the author of the parts of the library used.
19		* This can be in the form of a textual message at program startup or
20		* in documentation (online or textual) provided with the package.
21		*
22		* Redistribution and use in source and binary forms, with or without
23		* modification, are permitted provided that the following conditions
24		* are met:
25		* 1. Redistributions of source code must retain the copyright
26		* notice, this list of conditions and the following disclaimer.
27		* 2. Redistributions in binary form must reproduce the above copyright
28		* notice, this list of conditions and the following disclaimer in the
29		* documentation and/or other materials provided with the distribution.
30		* 3. All advertising materials mentioning features or use of this software
31		* must display the following acknowledgement:
32		* "This product includes cryptographic software written by
33		* Eric Young (eay@cryptsoft.com)"
34		* The word 'cryptographic' can be left out if the rouines from the library
35		* being used are not cryptographic related :-).
36		* 4. If you include any Windows specific code (or a derivative thereof) from
37		* the apps directory (application code) you must include an acknowledgement:
38		* "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
39		*
40		* THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
41		* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
42		* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
43		* ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
44		* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
45		* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
46		* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
47		* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
48		* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
49		* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
50		* SUCH DAMAGE.
51		*
52		* The licence and distribution terms for any publically available version or
53		* derivative of this code cannot be changed. i.e. this code cannot simply be
54		* copied and put under another distribution licence
55		* [including the GNU Public Licence.] */
56
57		#include <openssl/bn.h>
58
59		#include <string.h>
60
61		#include <openssl/err.h>
62		#include <openssl/mem.h>
63
64		#include "internal.h"
65
66
67	7.52k	int BN_add(BIGNUM r, const BIGNUM a, const BIGNUM *b) {
68	7.52k	const BIGNUM *tmp;
69	7.52k	int a_neg = a->neg, ret;
70
71		// a + b a+b
72		// a + -b a-b
73		// -a + b b-a
74		// -a + -b -(a+b)
75	7.52k	if (a_neg ^ b->neg) {
76		// only one is negative
77	1.25k	if (a_neg) {
78	796	tmp = a;
79	796	a = b;
80	796	b = tmp;
81	796	}
82
83		// we are now a - b
84	1.25k	if (BN_ucmp(a, b) < 0) {
85	564	if (!BN_usub(r, b, a)) {
86	0	return 0;
87	0	}
88	564	r->neg = 1;
89	695	} else {
90	695	if (!BN_usub(r, a, b)) {
91	0	return 0;
92	0	}
93	695	r->neg = 0;
94	695	}
95	1.25k	return 1;
96	1.25k	}
97
98	6.27k	ret = BN_uadd(r, a, b);
99	6.27k	r->neg = a_neg;
100	6.27k	return ret;
101	7.52k	}
102
103	189k	int bn_uadd_consttime(BIGNUM r, const BIGNUM a, const BIGNUM *b) {
104		// Widths are public, so we normalize to make \|a\| the larger one.
105	189k	if (a->width < b->width) {
106	14.4k	const BIGNUM *tmp = a;
107	14.4k	a = b;
108	14.4k	b = tmp;
109	14.4k	}
110
111	189k	int max = a->width;
112	189k	int min = b->width;
113	189k	if (!bn_wexpand(r, max + 1)) {
114	0	return 0;
115	0	}
116	189k	r->width = max + 1;
117
118	189k	BN_ULONG carry = bn_add_words(r->d, a->d, b->d, min);
119	290k	for (int i = min; i < max; i++) {
120	101k	r->d[i] = CRYPTO_addc_w(a->d[i], 0, carry, &carry);
121	101k	}
122
123	189k	r->d[max] = carry;
124	189k	return 1;
125	189k	}
126
127	189k	int BN_uadd(BIGNUM r, const BIGNUM a, const BIGNUM *b) {
128	189k	if (!bn_uadd_consttime(r, a, b)) {
129	0	return 0;
130	0	}
131	189k	bn_set_minimal_width(r);
132	189k	return 1;
133	189k	}
134
135	3.48M	int BN_add_word(BIGNUM *a, BN_ULONG w) {
136	3.48M	BN_ULONG l;
137	3.48M	int i;
138
139		// degenerate case: w is zero
140	3.48M	if (!w) {
141	952k	return 1;
142	952k	}
143
144		// degenerate case: a is zero
145	2.52M	if (BN_is_zero(a)) {
146	520k	return BN_set_word(a, w);
147	520k	}
148
149		// handle 'a' when negative
150	2.00M	if (a->neg) {
151	0	a->neg = 0;
152	0	i = BN_sub_word(a, w);
153	0	if (!BN_is_zero(a)) {
154	0	a->neg = !(a->neg);
155	0	}
156	0	return i;
157	0	}
158
159	4.25M	for (i = 0; w != 0 && i < a->width; i++) {
160	2.24M	a->d[i] = l = a->d[i] + w;
161	2.24M	w = (w > l) ? 1 : 0;
162	2.24M	}
163
164	2.00M	if (w && i == a->width) {
165	558	if (!bn_wexpand(a, a->width + 1)) {
166	0	return 0;
167	0	}
168	558	a->width++;
169	558	a->d[i] = w;
170	558	}
171
172	2.00M	return 1;
173	2.00M	}
174
175	14.6k	int BN_sub(BIGNUM r, const BIGNUM a, const BIGNUM *b) {
176	14.6k	int add = 0, neg = 0;
177	14.6k	const BIGNUM *tmp;
178
179		// a - b a-b
180		// a - -b a+b
181		// -a - b -(a+b)
182		// -a - -b b-a
183	14.6k	if (a->neg) {
184	1.55k	if (b->neg) {
185	760	tmp = a;
186	760	a = b;
187	760	b = tmp;
188	796	} else {
189	796	add = 1;
190	796	neg = 1;
191	796	}
192	13.1k	} else {
193	13.1k	if (b->neg) {
194	2.04k	add = 1;
195	2.04k	neg = 0;
196	2.04k	}
197	13.1k	}
198
199	14.6k	if (add) {
200	2.83k	if (!BN_uadd(r, a, b)) {
201	0	return 0;
202	0	}
203
204	2.83k	r->neg = neg;
205	2.83k	return 1;
206	2.83k	}
207
208	11.8k	if (BN_ucmp(a, b) < 0) {
209	8.06k	if (!BN_usub(r, b, a)) {
210	0	return 0;
211	0	}
212	8.06k	r->neg = 1;
213	8.06k	} else {
214	3.78k	if (!BN_usub(r, a, b)) {
215	0	return 0;
216	0	}
217	3.78k	r->neg = 0;
218	3.78k	}
219
220	11.8k	return 1;
221	11.8k	}
222
223	770k	int bn_usub_consttime(BIGNUM r, const BIGNUM a, const BIGNUM *b) {
224		// \|b\| may have more words than \|a\| given non-minimal inputs, but all words
225		// beyond \|a->width\| must then be zero.
226	770k	int b_width = b->width;
227	770k	if (b_width > a->width) {
228	0	if (!bn_fits_in_words(b, a->width)) {
229	0	OPENSSL_PUT_ERROR(BN, BN_R_ARG2_LT_ARG3);
230	0	return 0;
231	0	}
232	0	b_width = a->width;
233	0	}
234
235	770k	if (!bn_wexpand(r, a->width)) {
236	0	return 0;
237	0	}
238
239	770k	BN_ULONG borrow = bn_sub_words(r->d, a->d, b->d, b_width);
240	924k	for (int i = b_width; i < a->width; i++) {
241	154k	r->d[i] = CRYPTO_subc_w(a->d[i], 0, borrow, &borrow);
242	154k	}
243
244	770k	if (borrow) {
245	0	OPENSSL_PUT_ERROR(BN, BN_R_ARG2_LT_ARG3);
246	0	return 0;
247	0	}
248
249	770k	r->width = a->width;
250	770k	r->neg = 0;
251	770k	return 1;
252	770k	}
253
254	766k	int BN_usub(BIGNUM r, const BIGNUM a, const BIGNUM *b) {
255	766k	if (!bn_usub_consttime(r, a, b)) {
256	0	return 0;
257	0	}
258	766k	bn_set_minimal_width(r);
259	766k	return 1;
260	766k	}
261
262	13.2k	int BN_sub_word(BIGNUM *a, BN_ULONG w) {
263	13.2k	int i;
264
265		// degenerate case: w is zero
266	13.2k	if (!w) {
267	0	return 1;
268	0	}
269
270		// degenerate case: a is zero
271	13.2k	if (BN_is_zero(a)) {
272	7	i = BN_set_word(a, w);
273	7	if (i != 0) {
274	7	BN_set_negative(a, 1);
275	7	}
276	7	return i;
277	7	}
278
279		// handle 'a' when negative
280	13.2k	if (a->neg) {
281	0	a->neg = 0;
282	0	i = BN_add_word(a, w);
283	0	a->neg = 1;
284	0	return i;
285	0	}
286
287	13.2k	if ((bn_minimal_width(a) == 1) && (a->d[0] < w)) {
288	0	a->d[0] = w - a->d[0];
289	0	a->neg = 1;
290	0	return 1;
291	0	}
292
293	13.2k	i = 0;
294	22.7k	for (;;) {
295	22.7k	if (a->d[i] >= w) {
296	13.2k	a->d[i] -= w;
297	13.2k	break;
298	13.2k	} else {
299	9.49k	a->d[i] -= w;
300	9.49k	i++;
301	9.49k	w = 1;
302	9.49k	}
303	22.7k	}
304
305	13.2k	if ((a->d[i] == 0) && (i == (a->width - 1))) {
306	629	a->width--;
307	629	}
308
309	13.2k	return 1;
310	13.2k	}