1d9e397b599b13d642138480a28c14db7a136bf0Adam Langley/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) 2d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * All rights reserved. 3d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * 4d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * This package is an SSL implementation written 5d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * by Eric Young (eay@cryptsoft.com). 6d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * The implementation was written so as to conform with Netscapes SSL. 7d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * 8d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * This library is free for commercial and non-commercial use as long as 9d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * the following conditions are aheared to. The following conditions 10d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * apply to all code found in this distribution, be it the RC4, RSA, 11d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * lhash, DES, etc., code; not just the SSL code. The SSL documentation 12d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * included with this distribution is covered by the same copyright terms 13d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * except that the holder is Tim Hudson (tjh@cryptsoft.com). 14d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * 15d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * Copyright remains Eric Young's, and as such any Copyright notices in 16d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * the code are not to be removed. 17d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * If this package is used in a product, Eric Young should be given attribution 18d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * as the author of the parts of the library used. 19d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * This can be in the form of a textual message at program startup or 20d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * in documentation (online or textual) provided with the package. 21d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * 22d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * Redistribution and use in source and binary forms, with or without 23d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * modification, are permitted provided that the following conditions 24d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * are met: 25d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * 1. Redistributions of source code must retain the copyright 26d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * notice, this list of conditions and the following disclaimer. 27d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * 2. Redistributions in binary form must reproduce the above copyright 28d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * notice, this list of conditions and the following disclaimer in the 29d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * documentation and/or other materials provided with the distribution. 30d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * 3. All advertising materials mentioning features or use of this software 31d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * must display the following acknowledgement: 32d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * "This product includes cryptographic software written by 33d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * Eric Young (eay@cryptsoft.com)" 34d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * The word 'cryptographic' can be left out if the rouines from the library 35d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * being used are not cryptographic related :-). 36d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * 4. If you include any Windows specific code (or a derivative thereof) from 37d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * the apps directory (application code) you must include an acknowledgement: 38d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)" 39d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * 40d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND 41d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 42d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 43d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 44d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 45d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 46d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 47d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 48d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 49d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 50d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * SUCH DAMAGE. 51d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * 52d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * The licence and distribution terms for any publically available version or 53d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * derivative of this code cannot be changed. i.e. this code cannot simply be 54d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * copied and put under another distribution licence 55d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * [including the GNU Public Licence.] */ 56d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 57d9e397b599b13d642138480a28c14db7a136bf0Adam Langley#include <openssl/bn.h> 58d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 59d9e397b599b13d642138480a28c14db7a136bf0Adam Langley#include <openssl/err.h> 60d9e397b599b13d642138480a28c14db7a136bf0Adam Langley#include <openssl/mem.h> 61d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 62d9e397b599b13d642138480a28c14db7a136bf0Adam Langley#include "internal.h" 63d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 64d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 65d9e397b599b13d642138480a28c14db7a136bf0Adam Langleyint BN_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b) { 66d9e397b599b13d642138480a28c14db7a136bf0Adam Langley const BIGNUM *tmp; 67d9e397b599b13d642138480a28c14db7a136bf0Adam Langley int a_neg = a->neg, ret; 68d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 69d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* a + b a+b 70d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * a + -b a-b 71d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * -a + b b-a 72d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * -a + -b -(a+b) 73d9e397b599b13d642138480a28c14db7a136bf0Adam Langley */ 74d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (a_neg ^ b->neg) { 75d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* only one is negative */ 76d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (a_neg) { 77d9e397b599b13d642138480a28c14db7a136bf0Adam Langley tmp = a; 78d9e397b599b13d642138480a28c14db7a136bf0Adam Langley a = b; 79d9e397b599b13d642138480a28c14db7a136bf0Adam Langley b = tmp; 80d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 81d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 82d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* we are now a - b */ 83d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (BN_ucmp(a, b) < 0) { 84d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (!BN_usub(r, b, a)) { 85d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return 0; 86d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 87d9e397b599b13d642138480a28c14db7a136bf0Adam Langley r->neg = 1; 88d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } else { 89d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (!BN_usub(r, a, b)) { 90d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return 0; 91d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 92d9e397b599b13d642138480a28c14db7a136bf0Adam Langley r->neg = 0; 93d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 94d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return 1; 95d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 96d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 97d9e397b599b13d642138480a28c14db7a136bf0Adam Langley ret = BN_uadd(r, a, b); 98d9e397b599b13d642138480a28c14db7a136bf0Adam Langley r->neg = a_neg; 99d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return ret; 100d9e397b599b13d642138480a28c14db7a136bf0Adam Langley} 101d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 102d9e397b599b13d642138480a28c14db7a136bf0Adam Langleyint BN_uadd(BIGNUM *r, const BIGNUM *a, const BIGNUM *b) { 103d9e397b599b13d642138480a28c14db7a136bf0Adam Langley int max, min, dif; 104d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_ULONG *ap, *bp, *rp, carry, t1, t2; 105d9e397b599b13d642138480a28c14db7a136bf0Adam Langley const BIGNUM *tmp; 106d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 107d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (a->top < b->top) { 108d9e397b599b13d642138480a28c14db7a136bf0Adam Langley tmp = a; 109d9e397b599b13d642138480a28c14db7a136bf0Adam Langley a = b; 110d9e397b599b13d642138480a28c14db7a136bf0Adam Langley b = tmp; 111d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 112d9e397b599b13d642138480a28c14db7a136bf0Adam Langley max = a->top; 113d9e397b599b13d642138480a28c14db7a136bf0Adam Langley min = b->top; 114d9e397b599b13d642138480a28c14db7a136bf0Adam Langley dif = max - min; 115d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 116d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (bn_wexpand(r, max + 1) == NULL) { 117d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return 0; 118d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 119d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 120d9e397b599b13d642138480a28c14db7a136bf0Adam Langley r->top = max; 121d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 122d9e397b599b13d642138480a28c14db7a136bf0Adam Langley ap = a->d; 123d9e397b599b13d642138480a28c14db7a136bf0Adam Langley bp = b->d; 124d9e397b599b13d642138480a28c14db7a136bf0Adam Langley rp = r->d; 125d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 126d9e397b599b13d642138480a28c14db7a136bf0Adam Langley carry = bn_add_words(rp, ap, bp, min); 127d9e397b599b13d642138480a28c14db7a136bf0Adam Langley rp += min; 128d9e397b599b13d642138480a28c14db7a136bf0Adam Langley ap += min; 129d9e397b599b13d642138480a28c14db7a136bf0Adam Langley bp += min; 130d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 131d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (carry) { 132d9e397b599b13d642138480a28c14db7a136bf0Adam Langley while (dif) { 133d9e397b599b13d642138480a28c14db7a136bf0Adam Langley dif--; 134d9e397b599b13d642138480a28c14db7a136bf0Adam Langley t1 = *(ap++); 135d9e397b599b13d642138480a28c14db7a136bf0Adam Langley t2 = (t1 + 1) & BN_MASK2; 136d9e397b599b13d642138480a28c14db7a136bf0Adam Langley *(rp++) = t2; 137d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (t2) { 138d9e397b599b13d642138480a28c14db7a136bf0Adam Langley carry = 0; 139d9e397b599b13d642138480a28c14db7a136bf0Adam Langley break; 140d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 141d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 142d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (carry) { 143d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* carry != 0 => dif == 0 */ 144d9e397b599b13d642138480a28c14db7a136bf0Adam Langley *rp = 1; 145d9e397b599b13d642138480a28c14db7a136bf0Adam Langley r->top++; 146d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 147d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 148d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 149d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (dif && rp != ap) { 150d9e397b599b13d642138480a28c14db7a136bf0Adam Langley while (dif--) { 151d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* copy remaining words if ap != rp */ 152d9e397b599b13d642138480a28c14db7a136bf0Adam Langley *(rp++) = *(ap++); 153d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 154d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 155d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 156d9e397b599b13d642138480a28c14db7a136bf0Adam Langley r->neg = 0; 157d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return 1; 158d9e397b599b13d642138480a28c14db7a136bf0Adam Langley} 159d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 160d9e397b599b13d642138480a28c14db7a136bf0Adam Langleyint BN_add_word(BIGNUM *a, BN_ULONG w) { 161d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_ULONG l; 162d9e397b599b13d642138480a28c14db7a136bf0Adam Langley int i; 163d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 164d9e397b599b13d642138480a28c14db7a136bf0Adam Langley w &= BN_MASK2; 165d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 166d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* degenerate case: w is zero */ 167d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (!w) { 168d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return 1; 169d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 170d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 171d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* degenerate case: a is zero */ 172d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (BN_is_zero(a)) { 173d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return BN_set_word(a, w); 174d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 175d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 176d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* handle 'a' when negative */ 177d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (a->neg) { 178d9e397b599b13d642138480a28c14db7a136bf0Adam Langley a->neg = 0; 179d9e397b599b13d642138480a28c14db7a136bf0Adam Langley i = BN_sub_word(a, w); 180d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (!BN_is_zero(a)) { 181d9e397b599b13d642138480a28c14db7a136bf0Adam Langley a->neg = !(a->neg); 182d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 183d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return i; 184d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 185d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 186d9e397b599b13d642138480a28c14db7a136bf0Adam Langley for (i = 0; w != 0 && i < a->top; i++) { 187d9e397b599b13d642138480a28c14db7a136bf0Adam Langley a->d[i] = l = (a->d[i] + w) & BN_MASK2; 188d9e397b599b13d642138480a28c14db7a136bf0Adam Langley w = (w > l) ? 1 : 0; 189d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 190d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 191d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (w && i == a->top) { 192d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (bn_wexpand(a, a->top + 1) == NULL) { 193d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return 0; 194d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 195d9e397b599b13d642138480a28c14db7a136bf0Adam Langley a->top++; 196d9e397b599b13d642138480a28c14db7a136bf0Adam Langley a->d[i] = w; 197d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 198d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 199d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return 1; 200d9e397b599b13d642138480a28c14db7a136bf0Adam Langley} 201d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 202d9e397b599b13d642138480a28c14db7a136bf0Adam Langleyint BN_sub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b) { 203d9e397b599b13d642138480a28c14db7a136bf0Adam Langley int max; 204d9e397b599b13d642138480a28c14db7a136bf0Adam Langley int add = 0, neg = 0; 205d9e397b599b13d642138480a28c14db7a136bf0Adam Langley const BIGNUM *tmp; 206d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 207d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* a - b a-b 208d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * a - -b a+b 209d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * -a - b -(a+b) 210d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * -a - -b b-a 211d9e397b599b13d642138480a28c14db7a136bf0Adam Langley */ 212d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (a->neg) { 213d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (b->neg) { 214d9e397b599b13d642138480a28c14db7a136bf0Adam Langley tmp = a; 215d9e397b599b13d642138480a28c14db7a136bf0Adam Langley a = b; 216d9e397b599b13d642138480a28c14db7a136bf0Adam Langley b = tmp; 217d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } else { 218d9e397b599b13d642138480a28c14db7a136bf0Adam Langley add = 1; 219d9e397b599b13d642138480a28c14db7a136bf0Adam Langley neg = 1; 220d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 221d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } else { 222d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (b->neg) { 223d9e397b599b13d642138480a28c14db7a136bf0Adam Langley add = 1; 224d9e397b599b13d642138480a28c14db7a136bf0Adam Langley neg = 0; 225d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 226d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 227d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 228d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (add) { 229d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (!BN_uadd(r, a, b)) { 230d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return 0; 231d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 232d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 233d9e397b599b13d642138480a28c14db7a136bf0Adam Langley r->neg = neg; 234d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return 1; 235d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 236d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 237d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* We are actually doing a - b :-) */ 238d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 239d9e397b599b13d642138480a28c14db7a136bf0Adam Langley max = (a->top > b->top) ? a->top : b->top; 240d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (bn_wexpand(r, max) == NULL) { 241d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return 0; 242d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 243d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 244d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (BN_ucmp(a, b) < 0) { 245d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (!BN_usub(r, b, a)) { 246d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return 0; 247d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 248d9e397b599b13d642138480a28c14db7a136bf0Adam Langley r->neg = 1; 249d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } else { 250d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (!BN_usub(r, a, b)) { 251d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return 0; 252d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 253d9e397b599b13d642138480a28c14db7a136bf0Adam Langley r->neg = 0; 254d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 255d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 256d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return 1; 257d9e397b599b13d642138480a28c14db7a136bf0Adam Langley} 258d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 259d9e397b599b13d642138480a28c14db7a136bf0Adam Langleyint BN_usub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b) { 260d9e397b599b13d642138480a28c14db7a136bf0Adam Langley int max, min, dif; 261d9e397b599b13d642138480a28c14db7a136bf0Adam Langley register BN_ULONG t1, t2, *ap, *bp, *rp; 262d9e397b599b13d642138480a28c14db7a136bf0Adam Langley int i, carry; 263d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 264d9e397b599b13d642138480a28c14db7a136bf0Adam Langley max = a->top; 265d9e397b599b13d642138480a28c14db7a136bf0Adam Langley min = b->top; 266d9e397b599b13d642138480a28c14db7a136bf0Adam Langley dif = max - min; 267d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 268d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (dif < 0) /* hmm... should not be happening */ 269d9e397b599b13d642138480a28c14db7a136bf0Adam Langley { 270d9e397b599b13d642138480a28c14db7a136bf0Adam Langley OPENSSL_PUT_ERROR(BN, BN_usub, BN_R_ARG2_LT_ARG3); 271d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return 0; 272d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 273d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 274d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (bn_wexpand(r, max) == NULL) { 275d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return 0; 276d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 277d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 278d9e397b599b13d642138480a28c14db7a136bf0Adam Langley ap = a->d; 279d9e397b599b13d642138480a28c14db7a136bf0Adam Langley bp = b->d; 280d9e397b599b13d642138480a28c14db7a136bf0Adam Langley rp = r->d; 281d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 282d9e397b599b13d642138480a28c14db7a136bf0Adam Langley carry = 0; 283d9e397b599b13d642138480a28c14db7a136bf0Adam Langley for (i = min; i != 0; i--) { 284d9e397b599b13d642138480a28c14db7a136bf0Adam Langley t1 = *(ap++); 285d9e397b599b13d642138480a28c14db7a136bf0Adam Langley t2 = *(bp++); 286d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (carry) { 287d9e397b599b13d642138480a28c14db7a136bf0Adam Langley carry = (t1 <= t2); 288d9e397b599b13d642138480a28c14db7a136bf0Adam Langley t1 = (t1 - t2 - 1) & BN_MASK2; 289d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } else { 290d9e397b599b13d642138480a28c14db7a136bf0Adam Langley carry = (t1 < t2); 291d9e397b599b13d642138480a28c14db7a136bf0Adam Langley t1 = (t1 - t2) & BN_MASK2; 292d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 293d9e397b599b13d642138480a28c14db7a136bf0Adam Langley *(rp++) = t1 & BN_MASK2; 294d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 295d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 296d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (carry) /* subtracted */ 297d9e397b599b13d642138480a28c14db7a136bf0Adam Langley { 298d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (!dif) { 299d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* error: a < b */ 300d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return 0; 301d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 302d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 303d9e397b599b13d642138480a28c14db7a136bf0Adam Langley while (dif) { 304d9e397b599b13d642138480a28c14db7a136bf0Adam Langley dif--; 305d9e397b599b13d642138480a28c14db7a136bf0Adam Langley t1 = *(ap++); 306d9e397b599b13d642138480a28c14db7a136bf0Adam Langley t2 = (t1 - 1) & BN_MASK2; 307d9e397b599b13d642138480a28c14db7a136bf0Adam Langley *(rp++) = t2; 308d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (t1) { 309d9e397b599b13d642138480a28c14db7a136bf0Adam Langley break; 310d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 311d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 312d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 313d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 314d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (rp != ap) { 315d9e397b599b13d642138480a28c14db7a136bf0Adam Langley for (;;) { 316d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (!dif--) { 317d9e397b599b13d642138480a28c14db7a136bf0Adam Langley break; 318d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 319d9e397b599b13d642138480a28c14db7a136bf0Adam Langley rp[0] = ap[0]; 320d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (!dif--) { 321d9e397b599b13d642138480a28c14db7a136bf0Adam Langley break; 322d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 323d9e397b599b13d642138480a28c14db7a136bf0Adam Langley rp[1] = ap[1]; 324d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (!dif--) { 325d9e397b599b13d642138480a28c14db7a136bf0Adam Langley break; 326d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 327d9e397b599b13d642138480a28c14db7a136bf0Adam Langley rp[2] = ap[2]; 328d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (!dif--) { 329d9e397b599b13d642138480a28c14db7a136bf0Adam Langley break; 330d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 331d9e397b599b13d642138480a28c14db7a136bf0Adam Langley rp[3] = ap[3]; 332d9e397b599b13d642138480a28c14db7a136bf0Adam Langley rp += 4; 333d9e397b599b13d642138480a28c14db7a136bf0Adam Langley ap += 4; 334d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 335d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 336d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 337d9e397b599b13d642138480a28c14db7a136bf0Adam Langley r->top = max; 338d9e397b599b13d642138480a28c14db7a136bf0Adam Langley r->neg = 0; 339d9e397b599b13d642138480a28c14db7a136bf0Adam Langley bn_correct_top(r); 340d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 341d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return 1; 342d9e397b599b13d642138480a28c14db7a136bf0Adam Langley} 343d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 344d9e397b599b13d642138480a28c14db7a136bf0Adam Langleyint BN_sub_word(BIGNUM *a, BN_ULONG w) { 345d9e397b599b13d642138480a28c14db7a136bf0Adam Langley int i; 346d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 347d9e397b599b13d642138480a28c14db7a136bf0Adam Langley w &= BN_MASK2; 348d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 349d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* degenerate case: w is zero */ 350d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (!w) { 351d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return 1; 352d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 353d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 354d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* degenerate case: a is zero */ 355d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (BN_is_zero(a)) { 356d9e397b599b13d642138480a28c14db7a136bf0Adam Langley i = BN_set_word(a, w); 357d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (i != 0) { 358d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_set_negative(a, 1); 359d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 360d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return i; 361d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 362d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 363d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* handle 'a' when negative */ 364d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (a->neg) { 365d9e397b599b13d642138480a28c14db7a136bf0Adam Langley a->neg = 0; 366d9e397b599b13d642138480a28c14db7a136bf0Adam Langley i = BN_add_word(a, w); 367d9e397b599b13d642138480a28c14db7a136bf0Adam Langley a->neg = 1; 368d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return i; 369d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 370d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 371d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if ((a->top == 1) && (a->d[0] < w)) { 372d9e397b599b13d642138480a28c14db7a136bf0Adam Langley a->d[0] = w - a->d[0]; 373d9e397b599b13d642138480a28c14db7a136bf0Adam Langley a->neg = 1; 374d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return 1; 375d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 376d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 377d9e397b599b13d642138480a28c14db7a136bf0Adam Langley i = 0; 378d9e397b599b13d642138480a28c14db7a136bf0Adam Langley for (;;) { 379d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (a->d[i] >= w) { 380d9e397b599b13d642138480a28c14db7a136bf0Adam Langley a->d[i] -= w; 381d9e397b599b13d642138480a28c14db7a136bf0Adam Langley break; 382d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } else { 383d9e397b599b13d642138480a28c14db7a136bf0Adam Langley a->d[i] = (a->d[i] - w) & BN_MASK2; 384d9e397b599b13d642138480a28c14db7a136bf0Adam Langley i++; 385d9e397b599b13d642138480a28c14db7a136bf0Adam Langley w = 1; 386d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 387d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 388d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 389d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if ((a->d[i] == 0) && (i == (a->top - 1))) { 390d9e397b599b13d642138480a28c14db7a136bf0Adam Langley a->top--; 391d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 392d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 393d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return 1; 394d9e397b599b13d642138480a28c14db7a136bf0Adam Langley} 395