/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 07:03

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	19.0k	int BN_add(BIGNUM r, const BIGNUM a, const BIGNUM *b) {
68	19.0k	const BIGNUM *tmp;
69	19.0k	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	19.0k	if (a_neg ^ b->neg) {
76		// only one is negative
77	0	if (a_neg) {
78	0	tmp = a;
79	0	a = b;
80	0	b = tmp;
81	0	}
82
83		// we are now a - b
84	0	if (BN_ucmp(a, b) < 0) {
85	0	if (!BN_usub(r, b, a)) {
86	0	return 0;
87	0	}
88	0	r->neg = 1;
89	0	} else {
90	0	if (!BN_usub(r, a, b)) {
91	0	return 0;
92	0	}
93	0	r->neg = 0;
94	0	}
95	0	return 1;
96	0	}
97
98	19.0k	ret = BN_uadd(r, a, b);
99	19.0k	r->neg = a_neg;
100	19.0k	return ret;
101	19.0k	}
102
103	125k	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	125k	if (a->width < b->width) {
106	17.1k	const BIGNUM *tmp = a;
107	17.1k	a = b;
108	17.1k	b = tmp;
109	17.1k	}
110
111	125k	int max = a->width;
112	125k	int min = b->width;
113	125k	if (!bn_wexpand(r, max + 1)) {
114	0	return 0;
115	0	}
116	125k	r->width = max + 1;
117
118	125k	BN_ULONG carry = bn_add_words(r->d, a->d, b->d, min);
119	922k	for (int i = min; i < max; i++) {
120	797k	r->d[i] = CRYPTO_addc_w(a->d[i], 0, carry, &carry);
121	797k	}
122
123	125k	r->d[max] = carry;
124	125k	return 1;
125	125k	}
126
127	125k	int BN_uadd(BIGNUM r, const BIGNUM a, const BIGNUM *b) {
128	125k	if (!bn_uadd_consttime(r, a, b)) {
129	0	return 0;
130	0	}
131	125k	bn_set_minimal_width(r);
132	125k	return 1;
133	125k	}
134
135	459k	int BN_add_word(BIGNUM *a, BN_ULONG w) {
136	459k	BN_ULONG l;
137	459k	int i;
138
139		// degenerate case: w is zero
140	459k	if (!w) {
141	61.0k	return 1;
142	61.0k	}
143
144		// degenerate case: a is zero
145	398k	if (BN_is_zero(a)) {
146	9.08k	return BN_set_word(a, w);
147	9.08k	}
148
149		// handle 'a' when negative
150	389k	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	807k	for (i = 0; w != 0 && i < a->width; i++) {
160	418k	a->d[i] = l = a->d[i] + w;
161	418k	w = (w > l) ? 1 : 0;
162	418k	}
163
164	389k	if (w && i == a->width) {
165	41	if (!bn_wexpand(a, a->width + 1)) {
166	0	return 0;
167	0	}
168	41	a->width++;
169	41	a->d[i] = w;
170	41	}
171
172	389k	return 1;
173	389k	}
174
175	5.41k	int BN_sub(BIGNUM r, const BIGNUM a, const BIGNUM *b) {
176	5.41k	int add = 0, neg = 0;
177	5.41k	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	5.41k	if (a->neg) {
184	0	if (b->neg) {
185	0	tmp = a;
186	0	a = b;
187	0	b = tmp;
188	0	} else {
189	0	add = 1;
190	0	neg = 1;
191	0	}
192	5.41k	} else {
193	5.41k	if (b->neg) {
194	0	add = 1;
195	0	neg = 0;
196	0	}
197	5.41k	}
198
199	5.41k	if (add) {
200	0	if (!BN_uadd(r, a, b)) {
201	0	return 0;
202	0	}
203
204	0	r->neg = neg;
205	0	return 1;
206	0	}
207
208	5.41k	if (BN_ucmp(a, b) < 0) {
209	623	if (!BN_usub(r, b, a)) {
210	0	return 0;
211	0	}
212	623	r->neg = 1;
213	4.79k	} else {
214	4.79k	if (!BN_usub(r, a, b)) {
215	0	return 0;
216	0	}
217	4.79k	r->neg = 0;
218	4.79k	}
219
220	5.41k	return 1;
221	5.41k	}
222
223	660k	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	660k	int b_width = b->width;
227	660k	if (b_width > a->width) {
228	114	if (!bn_fits_in_words(b, a->width)) {
229	6	OPENSSL_PUT_ERROR(BN, BN_R_ARG2_LT_ARG3);
230	6	return 0;
231	6	}
232	108	b_width = a->width;
233	108	}
234
235	660k	if (!bn_wexpand(r, a->width)) {
236	0	return 0;
237	0	}
238
239	660k	BN_ULONG borrow = bn_sub_words(r->d, a->d, b->d, b_width);
240	1.05M	for (int i = b_width; i < a->width; i++) {
241	396k	r->d[i] = CRYPTO_subc_w(a->d[i], 0, borrow, &borrow);
242	396k	}
243
244	660k	if (borrow) {
245	3	OPENSSL_PUT_ERROR(BN, BN_R_ARG2_LT_ARG3);
246	3	return 0;
247	3	}
248
249	660k	r->width = a->width;
250	660k	r->neg = 0;
251	660k	return 1;
252	660k	}
253
254	659k	int BN_usub(BIGNUM r, const BIGNUM a, const BIGNUM *b) {
255	659k	if (!bn_usub_consttime(r, a, b)) {
256	9	return 0;
257	9	}
258	659k	bn_set_minimal_width(r);
259	659k	return 1;
260	659k	}
261
262	87.1k	int BN_sub_word(BIGNUM *a, BN_ULONG w) {
263	87.1k	int i;
264
265		// degenerate case: w is zero
266	87.1k	if (!w) {
267	0	return 1;
268	0	}
269
270		// degenerate case: a is zero
271	87.1k	if (BN_is_zero(a)) {
272	0	i = BN_set_word(a, w);
273	0	if (i != 0) {
274	0	BN_set_negative(a, 1);
275	0	}
276	0	return i;
277	0	}
278
279		// handle 'a' when negative
280	87.1k	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	87.1k	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	87.1k	i = 0;
294	119k	for (;;) {
295	119k	if (a->d[i] >= w) {
296	87.1k	a->d[i] -= w;
297	87.1k	break;
298	87.1k	} else {
299	32.6k	a->d[i] -= w;
300	32.6k	i++;
301	32.6k	w = 1;
302	32.6k	}
303	119k	}
304
305	87.1k	if ((a->d[i] == 0) && (i == (a->width - 1))) {
306	567	a->width--;
307	567	}
308
309	87.1k	return 1;
310	87.1k	}