1// Copyright 1995-2016 The OpenSSL Project Authors. All Rights Reserved.
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//     https://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15#include <openssl/bn.h>
16
17#include <string.h>
18
19#include <openssl/err.h>
20#include <openssl/mem.h>
21
22#include "../../internal.h"
23#include "internal.h"
24
25
26int BN_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b) {
27  const BIGNUM *tmp;
28  int a_neg = a->neg, ret;
29
30  //  a +  b	a+b
31  //  a + -b	a-b
32  // -a +  b	b-a
33  // -a + -b	-(a+b)
34  if (a_neg ^ b->neg) {
35    // only one is negative
36    if (a_neg) {
37      tmp = a;
38      a = b;
39      b = tmp;
40    }
41
42    // we are now a - b
43    if (BN_ucmp(a, b) < 0) {
44      if (!BN_usub(r, b, a)) {
45        return 0;
46      }
47      r->neg = 1;
48    } else {
49      if (!BN_usub(r, a, b)) {
50        return 0;
51      }
52      r->neg = 0;
53    }
54    return 1;
55  }
56
57  ret = BN_uadd(r, a, b);
58  r->neg = a_neg;
59  return ret;
60}
61
62int bn_uadd_consttime(BIGNUM *r, const BIGNUM *a, const BIGNUM *b) {
63  // Widths are public, so we normalize to make |a| the larger one.
64  if (a->width < b->width) {
65    const BIGNUM *tmp = a;
66    a = b;
67    b = tmp;
68  }
69
70  int max = a->width;
71  int min = b->width;
72  if (!bn_wexpand(r, max + 1)) {
73    return 0;
74  }
75  r->width = max + 1;
76
77  BN_ULONG carry = bn_add_words(r->d, a->d, b->d, min);
78  for (int i = min; i < max; i++) {
79    r->d[i] = CRYPTO_addc_w(a->d[i], 0, carry, &carry);
80  }
81
82  r->d[max] = carry;
83  return 1;
84}
85
86int BN_uadd(BIGNUM *r, const BIGNUM *a, const BIGNUM *b) {
87  if (!bn_uadd_consttime(r, a, b)) {
88    return 0;
89  }
90  bn_set_minimal_width(r);
91  return 1;
92}
93
94int BN_add_word(BIGNUM *a, BN_ULONG w) {
95  BN_ULONG l;
96  int i;
97
98  // degenerate case: w is zero
99  if (!w) {
100    return 1;
101  }
102
103  // degenerate case: a is zero
104  if (BN_is_zero(a)) {
105    return BN_set_word(a, w);
106  }
107
108  // handle 'a' when negative
109  if (a->neg) {
110    a->neg = 0;
111    i = BN_sub_word(a, w);
112    if (!BN_is_zero(a)) {
113      a->neg = !(a->neg);
114    }
115    return i;
116  }
117
118  for (i = 0; w != 0 && i < a->width; i++) {
119    a->d[i] = l = a->d[i] + w;
120    w = (w > l) ? 1 : 0;
121  }
122
123  if (w && i == a->width) {
124    if (!bn_wexpand(a, a->width + 1)) {
125      return 0;
126    }
127    a->width++;
128    a->d[i] = w;
129  }
130
131  return 1;
132}
133
134int BN_sub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b) {
135  int add = 0, neg = 0;
136  const BIGNUM *tmp;
137
138  //  a -  b	a-b
139  //  a - -b	a+b
140  // -a -  b	-(a+b)
141  // -a - -b	b-a
142  if (a->neg) {
143    if (b->neg) {
144      tmp = a;
145      a = b;
146      b = tmp;
147    } else {
148      add = 1;
149      neg = 1;
150    }
151  } else {
152    if (b->neg) {
153      add = 1;
154      neg = 0;
155    }
156  }
157
158  if (add) {
159    if (!BN_uadd(r, a, b)) {
160      return 0;
161    }
162
163    r->neg = neg;
164    return 1;
165  }
166
167  if (BN_ucmp(a, b) < 0) {
168    if (!BN_usub(r, b, a)) {
169      return 0;
170    }
171    r->neg = 1;
172  } else {
173    if (!BN_usub(r, a, b)) {
174      return 0;
175    }
176    r->neg = 0;
177  }
178
179  return 1;
180}
181
182int bn_usub_consttime(BIGNUM *r, const BIGNUM *a, const BIGNUM *b) {
183  // |b| may have more words than |a| given non-minimal inputs, but all words
184  // beyond |a->width| must then be zero.
185  int b_width = b->width;
186  if (b_width > a->width) {
187    if (!bn_fits_in_words(b, a->width)) {
188      OPENSSL_PUT_ERROR(BN, BN_R_ARG2_LT_ARG3);
189      return 0;
190    }
191    b_width = a->width;
192  }
193
194  if (!bn_wexpand(r, a->width)) {
195    return 0;
196  }
197
198  BN_ULONG borrow = bn_sub_words(r->d, a->d, b->d, b_width);
199  for (int i = b_width; i < a->width; i++) {
200    r->d[i] = CRYPTO_subc_w(a->d[i], 0, borrow, &borrow);
201  }
202
203  if (borrow) {
204    OPENSSL_PUT_ERROR(BN, BN_R_ARG2_LT_ARG3);
205    return 0;
206  }
207
208  r->width = a->width;
209  r->neg = 0;
210  return 1;
211}
212
213int BN_usub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b) {
214  if (!bn_usub_consttime(r, a, b)) {
215    return 0;
216  }
217  bn_set_minimal_width(r);
218  return 1;
219}
220
221int BN_sub_word(BIGNUM *a, BN_ULONG w) {
222  int i;
223
224  // degenerate case: w is zero
225  if (!w) {
226    return 1;
227  }
228
229  // degenerate case: a is zero
230  if (BN_is_zero(a)) {
231    i = BN_set_word(a, w);
232    if (i != 0) {
233      BN_set_negative(a, 1);
234    }
235    return i;
236  }
237
238  // handle 'a' when negative
239  if (a->neg) {
240    a->neg = 0;
241    i = BN_add_word(a, w);
242    a->neg = 1;
243    return i;
244  }
245
246  if ((bn_minimal_width(a) == 1) && (a->d[0] < w)) {
247    a->d[0] = w - a->d[0];
248    a->neg = 1;
249    return 1;
250  }
251
252  i = 0;
253  for (;;) {
254    if (a->d[i] >= w) {
255      a->d[i] -= w;
256      break;
257    } else {
258      a->d[i] -= w;
259      i++;
260      w = 1;
261    }
262  }
263
264  if ((a->d[i] == 0) && (i == (a->width - 1))) {
265    a->width--;
266  }
267
268  return 1;
269}
270