172c33676SMaxim Ag /* $OpenBSD: bn_add.c,v 1.13 2018/07/23 18:07:21 tb Exp $ */
2f5b1c8a1SJohn Marino /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
3f5b1c8a1SJohn Marino * All rights reserved.
4f5b1c8a1SJohn Marino *
5f5b1c8a1SJohn Marino * This package is an SSL implementation written
6f5b1c8a1SJohn Marino * by Eric Young (eay@cryptsoft.com).
7f5b1c8a1SJohn Marino * The implementation was written so as to conform with Netscapes SSL.
8f5b1c8a1SJohn Marino *
9f5b1c8a1SJohn Marino * This library is free for commercial and non-commercial use as long as
10f5b1c8a1SJohn Marino * the following conditions are aheared to. The following conditions
11f5b1c8a1SJohn Marino * apply to all code found in this distribution, be it the RC4, RSA,
12f5b1c8a1SJohn Marino * lhash, DES, etc., code; not just the SSL code. The SSL documentation
13f5b1c8a1SJohn Marino * included with this distribution is covered by the same copyright terms
14f5b1c8a1SJohn Marino * except that the holder is Tim Hudson (tjh@cryptsoft.com).
15f5b1c8a1SJohn Marino *
16f5b1c8a1SJohn Marino * Copyright remains Eric Young's, and as such any Copyright notices in
17f5b1c8a1SJohn Marino * the code are not to be removed.
18f5b1c8a1SJohn Marino * If this package is used in a product, Eric Young should be given attribution
19f5b1c8a1SJohn Marino * as the author of the parts of the library used.
20f5b1c8a1SJohn Marino * This can be in the form of a textual message at program startup or
21f5b1c8a1SJohn Marino * in documentation (online or textual) provided with the package.
22f5b1c8a1SJohn Marino *
23f5b1c8a1SJohn Marino * Redistribution and use in source and binary forms, with or without
24f5b1c8a1SJohn Marino * modification, are permitted provided that the following conditions
25f5b1c8a1SJohn Marino * are met:
26f5b1c8a1SJohn Marino * 1. Redistributions of source code must retain the copyright
27f5b1c8a1SJohn Marino * notice, this list of conditions and the following disclaimer.
28f5b1c8a1SJohn Marino * 2. Redistributions in binary form must reproduce the above copyright
29f5b1c8a1SJohn Marino * notice, this list of conditions and the following disclaimer in the
30f5b1c8a1SJohn Marino * documentation and/or other materials provided with the distribution.
31f5b1c8a1SJohn Marino * 3. All advertising materials mentioning features or use of this software
32f5b1c8a1SJohn Marino * must display the following acknowledgement:
33f5b1c8a1SJohn Marino * "This product includes cryptographic software written by
34f5b1c8a1SJohn Marino * Eric Young (eay@cryptsoft.com)"
35f5b1c8a1SJohn Marino * The word 'cryptographic' can be left out if the rouines from the library
36f5b1c8a1SJohn Marino * being used are not cryptographic related :-).
37f5b1c8a1SJohn Marino * 4. If you include any Windows specific code (or a derivative thereof) from
38f5b1c8a1SJohn Marino * the apps directory (application code) you must include an acknowledgement:
39f5b1c8a1SJohn Marino * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
40f5b1c8a1SJohn Marino *
41f5b1c8a1SJohn Marino * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
42f5b1c8a1SJohn Marino * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
43f5b1c8a1SJohn Marino * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
44f5b1c8a1SJohn Marino * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
45f5b1c8a1SJohn Marino * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
46f5b1c8a1SJohn Marino * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
47f5b1c8a1SJohn Marino * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
48f5b1c8a1SJohn Marino * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
49f5b1c8a1SJohn Marino * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
50f5b1c8a1SJohn Marino * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
51f5b1c8a1SJohn Marino * SUCH DAMAGE.
52f5b1c8a1SJohn Marino *
53f5b1c8a1SJohn Marino * The licence and distribution terms for any publically available version or
54f5b1c8a1SJohn Marino * derivative of this code cannot be changed. i.e. this code cannot simply be
55f5b1c8a1SJohn Marino * copied and put under another distribution licence
56f5b1c8a1SJohn Marino * [including the GNU Public Licence.]
57f5b1c8a1SJohn Marino */
58f5b1c8a1SJohn Marino
59f5b1c8a1SJohn Marino #include <stdio.h>
60f5b1c8a1SJohn Marino
61f5b1c8a1SJohn Marino #include <openssl/err.h>
62f5b1c8a1SJohn Marino
63f5b1c8a1SJohn Marino #include "bn_lcl.h"
64f5b1c8a1SJohn Marino
65f5b1c8a1SJohn Marino int
BN_add(BIGNUM * r,const BIGNUM * a,const BIGNUM * b)66f5b1c8a1SJohn Marino BN_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b)
67f5b1c8a1SJohn Marino {
6872c33676SMaxim Ag int ret, r_neg;
69f5b1c8a1SJohn Marino
70f5b1c8a1SJohn Marino bn_check_top(a);
71f5b1c8a1SJohn Marino bn_check_top(b);
72f5b1c8a1SJohn Marino
7372c33676SMaxim Ag if (a->neg == b->neg) {
7472c33676SMaxim Ag r_neg = a->neg;
75f5b1c8a1SJohn Marino ret = BN_uadd(r, a, b);
7672c33676SMaxim Ag } else {
7772c33676SMaxim Ag int cmp = BN_ucmp(a, b);
7872c33676SMaxim Ag
7972c33676SMaxim Ag if (cmp > 0) {
8072c33676SMaxim Ag r_neg = a->neg;
8172c33676SMaxim Ag ret = BN_usub(r, a, b);
8272c33676SMaxim Ag } else if (cmp < 0) {
8372c33676SMaxim Ag r_neg = b->neg;
8472c33676SMaxim Ag ret = BN_usub(r, b, a);
8572c33676SMaxim Ag } else {
8672c33676SMaxim Ag r_neg = 0;
8772c33676SMaxim Ag BN_zero(r);
8872c33676SMaxim Ag ret = 1;
8972c33676SMaxim Ag }
9072c33676SMaxim Ag }
9172c33676SMaxim Ag
9272c33676SMaxim Ag r->neg = r_neg;
93f5b1c8a1SJohn Marino bn_check_top(r);
94f5b1c8a1SJohn Marino return ret;
95f5b1c8a1SJohn Marino }
96f5b1c8a1SJohn Marino
97f5b1c8a1SJohn Marino int
BN_uadd(BIGNUM * r,const BIGNUM * a,const BIGNUM * b)98f5b1c8a1SJohn Marino BN_uadd(BIGNUM *r, const BIGNUM *a, const BIGNUM *b)
99f5b1c8a1SJohn Marino {
100f5b1c8a1SJohn Marino int max, min, dif;
10172c33676SMaxim Ag const BN_ULONG *ap, *bp;
10272c33676SMaxim Ag BN_ULONG *rp, carry, t1, t2;
103f5b1c8a1SJohn Marino
104f5b1c8a1SJohn Marino bn_check_top(a);
105f5b1c8a1SJohn Marino bn_check_top(b);
106f5b1c8a1SJohn Marino
107f5b1c8a1SJohn Marino if (a->top < b->top) {
10872c33676SMaxim Ag const BIGNUM *tmp;
10972c33676SMaxim Ag
110f5b1c8a1SJohn Marino tmp = a;
111f5b1c8a1SJohn Marino a = b;
112f5b1c8a1SJohn Marino b = tmp;
113f5b1c8a1SJohn Marino }
114f5b1c8a1SJohn Marino max = a->top;
115f5b1c8a1SJohn Marino min = b->top;
116f5b1c8a1SJohn Marino dif = max - min;
117f5b1c8a1SJohn Marino
118f5b1c8a1SJohn Marino if (bn_wexpand(r, max + 1) == NULL)
119f5b1c8a1SJohn Marino return 0;
120f5b1c8a1SJohn Marino
121f5b1c8a1SJohn Marino r->top = max;
122f5b1c8a1SJohn Marino
123f5b1c8a1SJohn Marino ap = a->d;
124f5b1c8a1SJohn Marino bp = b->d;
125f5b1c8a1SJohn Marino rp = r->d;
126f5b1c8a1SJohn Marino
127f5b1c8a1SJohn Marino carry = bn_add_words(rp, ap, bp, min);
128f5b1c8a1SJohn Marino rp += min;
129f5b1c8a1SJohn Marino ap += min;
130f5b1c8a1SJohn Marino
131f5b1c8a1SJohn Marino while (dif) {
132f5b1c8a1SJohn Marino dif--;
133f5b1c8a1SJohn Marino t1 = *(ap++);
13472c33676SMaxim Ag t2 = (t1 + carry) & BN_MASK2;
135f5b1c8a1SJohn Marino *(rp++) = t2;
13672c33676SMaxim Ag carry &= (t2 == 0);
137f5b1c8a1SJohn Marino }
13872c33676SMaxim Ag *rp = carry;
13972c33676SMaxim Ag r->top += carry;
14072c33676SMaxim Ag
141f5b1c8a1SJohn Marino r->neg = 0;
142f5b1c8a1SJohn Marino bn_check_top(r);
143f5b1c8a1SJohn Marino return 1;
144f5b1c8a1SJohn Marino }
145f5b1c8a1SJohn Marino
146f5b1c8a1SJohn Marino int
BN_usub(BIGNUM * r,const BIGNUM * a,const BIGNUM * b)147f5b1c8a1SJohn Marino BN_usub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b)
148f5b1c8a1SJohn Marino {
149f5b1c8a1SJohn Marino int max, min, dif;
15072c33676SMaxim Ag const BN_ULONG *ap, *bp;
15172c33676SMaxim Ag BN_ULONG t1, t2, borrow, *rp;
152f5b1c8a1SJohn Marino
153f5b1c8a1SJohn Marino bn_check_top(a);
154f5b1c8a1SJohn Marino bn_check_top(b);
155f5b1c8a1SJohn Marino
156f5b1c8a1SJohn Marino max = a->top;
157f5b1c8a1SJohn Marino min = b->top;
158f5b1c8a1SJohn Marino dif = max - min;
159f5b1c8a1SJohn Marino
16072c33676SMaxim Ag if (dif < 0) {
16172c33676SMaxim Ag BNerror(BN_R_ARG2_LT_ARG3);
16272c33676SMaxim Ag return 0;
163f5b1c8a1SJohn Marino }
164f5b1c8a1SJohn Marino
165f5b1c8a1SJohn Marino if (bn_wexpand(r, max) == NULL)
16672c33676SMaxim Ag return 0;
167f5b1c8a1SJohn Marino
168f5b1c8a1SJohn Marino ap = a->d;
169f5b1c8a1SJohn Marino bp = b->d;
170f5b1c8a1SJohn Marino rp = r->d;
171f5b1c8a1SJohn Marino
17272c33676SMaxim Ag borrow = bn_sub_words(rp, ap, bp, min);
173f5b1c8a1SJohn Marino ap += min;
174f5b1c8a1SJohn Marino rp += min;
17572c33676SMaxim Ag
176f5b1c8a1SJohn Marino while (dif) {
177f5b1c8a1SJohn Marino dif--;
178f5b1c8a1SJohn Marino t1 = *(ap++);
17972c33676SMaxim Ag t2 = (t1 - borrow) & BN_MASK2;
180f5b1c8a1SJohn Marino *(rp++) = t2;
18172c33676SMaxim Ag borrow &= (t1 == 0);
182f5b1c8a1SJohn Marino }
18372c33676SMaxim Ag
18472c33676SMaxim Ag while (max > 0 && *--rp == 0)
18572c33676SMaxim Ag max--;
186f5b1c8a1SJohn Marino
187f5b1c8a1SJohn Marino r->top = max;
188f5b1c8a1SJohn Marino r->neg = 0;
189f5b1c8a1SJohn Marino bn_correct_top(r);
19072c33676SMaxim Ag return 1;
191f5b1c8a1SJohn Marino }
192f5b1c8a1SJohn Marino
193f5b1c8a1SJohn Marino int
BN_sub(BIGNUM * r,const BIGNUM * a,const BIGNUM * b)194f5b1c8a1SJohn Marino BN_sub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b)
195f5b1c8a1SJohn Marino {
19672c33676SMaxim Ag int ret, r_neg;
197f5b1c8a1SJohn Marino
198f5b1c8a1SJohn Marino bn_check_top(a);
199f5b1c8a1SJohn Marino bn_check_top(b);
200f5b1c8a1SJohn Marino
20172c33676SMaxim Ag if (a->neg != b->neg) {
20272c33676SMaxim Ag r_neg = a->neg;
20372c33676SMaxim Ag ret = BN_uadd(r, a, b);
204f5b1c8a1SJohn Marino } else {
20572c33676SMaxim Ag int cmp = BN_ucmp(a, b);
20672c33676SMaxim Ag
20772c33676SMaxim Ag if (cmp > 0) {
20872c33676SMaxim Ag r_neg = a->neg;
20972c33676SMaxim Ag ret = BN_usub(r, a, b);
21072c33676SMaxim Ag } else if (cmp < 0) {
21172c33676SMaxim Ag r_neg = !b->neg;
21272c33676SMaxim Ag ret = BN_usub(r, b, a);
213f5b1c8a1SJohn Marino } else {
21472c33676SMaxim Ag r_neg = 0;
21572c33676SMaxim Ag BN_zero(r);
21672c33676SMaxim Ag ret = 1;
217f5b1c8a1SJohn Marino }
218f5b1c8a1SJohn Marino }
219f5b1c8a1SJohn Marino
22072c33676SMaxim Ag r->neg = r_neg;
221f5b1c8a1SJohn Marino bn_check_top(r);
22272c33676SMaxim Ag return ret;
223f5b1c8a1SJohn Marino }
224