Coverage Report

Created: 2024-11-21 06:47

/src/boringssl/crypto/fipsmodule/bn/add.c.inc
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
}